Постановка задачи выбора варианта как задачи дискретного программирования логическая переменная «включения процесса»

Постановка задачи выбора варианта как задачи дискретного программирования, логическая переменная «включения процесса», дискретная функция прибыли, ограничения потребления ресурсов запасами ресурсов, оптимальный вариант «включения процессов», нахождение оптимального решения методом перебора.

Дискретное программирование – это один из разделов математического программирования. Основная задача дискретного программирования – выбор
наилучшего варианта из конечного, возможно, очень большого их числа. Возникающие при этом экстремальные задачи имеют ряд особенностей, которые не встречаются в таких стандартных задачах математического программирования, как линейные, выпуклые или многокритериальные задачи. В противоположность задачам оптимизации с непрерывными переменными, переменные в задачах дискретного программирования принимают только дискретные значения, например, целочисленные.
Дискретной называется переменная, которая может принимать не любые значения из своего диапазона изменения, а только отдельные, причем изолированные друг от друга. Дискретная переменная может принимать конечное или счетное число значений.
С математической точки зрения дискретное и целочисленное программирование – не одно и тоже. Дискретные значения могут быть не целыми числами.
Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования:
Найти максимум или минимум линейной функции:
fx0=maxfx minfx, x∈G,
множество допустимых решений которого конечно, т.е. 0≤G=N<∞, где G – число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать: x1,x2…xN вычислить fxi,i =1,2,…, N, и найти наибольшее (наименьшее) значение. Однако такой метод полного перебора вариантов при решении задачи реализовать становится невозможным, если N окажется настолько большим, что этот перебор невыполним даже на ЭВМ любой мощности.
Наиболее распространенными задачами дискретного программирования являются задачи:
1) о контейнерных перевозках (о рюкзаке, о кошелке), в которой определяется максимум перевезенной продукции при ограничениях на вместимость;
2) о назначениях (выбора), в которой определяется наиболее рациональное использование потенциала сотрудников при выполнении определенных работ;
3) коммивояжера, в которой определяется минимальный путь агента, проходящий через необходимые пункты возможного сбыта продукции;
4) транспортная, один из случаев задачи дискретного программирования.
Одними из основных методов решения задач дискретного программирования являются метод перебора, отсечения, метод ветвей и границ и динамическое программирование.
Первые попытки решения задач целочисленного линейного программирования сводились к отбрасыванию условия целочисленности, решению линейной задачи и округлению полученного решения. Можно привести простой пример, который показывает неприемлемость такого подхода:
Найти x1-3×2+3×3→max
2×1+x2-x3≤44×1-3×2≤2-3×1+2×2+x3≤3×1,x2,x3-целые
Игнорируя условие целочисленности, получим оптимальное решение линейной задачи x1=0,5,×2=0,×3=4,5.
Никакие округления компонент этого решения не дают даже целочисленного плана. Оптимальным решением данной целочисленной задачи является: x1=2,×2=2,×3=5.
Дискретные задачи характеризуются тем, что область допустимых решений невыпукла и несвязна, а это делает невозможным решение их с помощью стандартных методов, применяемых для решения регулярных задач математического программирования.
Рассмотрим далее ряд специальных оптимизационных задач, сводящихся к задачам линейного целочисленного программирования. Одной из таких задач является задача о назначениях, с помощью которой можно получить ответ на вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими; как наилучшим образом распределить экипажи самолетов; как назначить людей на различные должности (отсюда и название задачи) и т.д.
Там, где есть варианты, из которых надо выбирать, задачу можно решать с помощью логических (булевых) переменных, которые в случае положительного ответа «да» принимают значение, равное 1, в случае «нет» – 0.
Например. Компания реализует продукцию в 5 районах. Покупательные способности жителей района оцениваются следующим образом:
Район 1 2 3 4 5
Покупательная способность (спрос) 80000 60000 50000 40000 20000
Профессиональный уровень пяти продавцов различен. Предполагается, что доля реализуемых покупательных способностей (спроса) составляет:
Продавец A B C D E
Доля реализации спроса 0,5 0,7 0,45 0,8 0,4
Как следует распределить продавцов по районам (одного продавца в один район), чтобы максимизировать количество проданной продукции?