2.8. Целочисленное линейное программирование. Метод Гомори
Если управляющие переменные в задаче линейного программирования определяют количество единиц неделимой продукции, то оптимальное решение должно быть получено в целых числах. К задачам такого типа относится большое число экономических задач, например распределение производственных заказов между предприятиями, оптимальный раскрой материалов, определение загрузки оборудования, распределение транспортных средств по рейсам, задачи производства и реализации неделимой продукции. Если единица составляет малую часть от общего количества, например при планировании массового и крупносерийного производства, то для нахождения оптимального решения применяют обычный симплекс-метод и округляют полученное решение до целого. В противном случае, например при планировании производства или реализации автомобилей, округление может привести к решению, далекому от оптимального. Линейные задачи, решение которых должно быть получено в целых числах, называют задачами целочисленного программирования (ЦЛП).
Математическая модель, задачи ЦЛП имеет следующий вид:
(2.8.1)
(2.8.2)
где Z — множество целых чисел.
Для
решения задачи ЦЛП может быть применен
метод Гомори.
Метод Гомори содержит два этапа.
Этап 1. Решение исходной задачи обычным симплекс-методом и проверка решения на целочисленность. Если решение содержит хотя бы одно дробное значение, то переходят к этапу 2, в противном случае расчет заканчивается.
Этап 2. Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс-методом. Дополнительное ограничение (сечение) отсекает нецелочисленные решения.
Сечение обладает следующими двумя свойствами:
любое целочисленное решение ему удовлетворяет;
любое нецелочисленное решение задачи ему не удовлетворяет.
Объясним, как составляется сечение.
Пусть выполнен этап 1;
;
– дробное
число. Рассмотрим
-е
ограничение:
Так
как
–
дробное, а в правой части все переменные
целые, то хотя бы одно, значение
должно быть дробным.
Возьмем дробную часть от левой и правой частей ограничения.
Обозначим через {r} дробную часть числа r.
Дробная часть суммы не превосходит суммы дробных частей слагаемых, поэтому
Дробная часть произведения не превосходит произведения целого на дробную часть, следовательно:
В результате имеем
Обозначим
,
.
Тогда из последнего неравенства получаем
Отняв от левой части неравенства дополнительную неотрицательную переменную, переходим к уравнению
,
При дополнении этого ограничения к исходной задаче мы получили задачу большей размерности.
Эту задачу решают обычным симплекс-методом, т.е. переходят к этапу 1.
Если при решении задачи симплекс-методом имеется несколько дробных решений, то дополнительные ограничения следует составлять для значения, имеющего максимальную дробную часть.
3. Транспортная задача как пример специальной задачи линейного программирования
Среди задач линейной оптимизации могут быть выделены два класса задач со специальной структурой: транспортная задача и задача о назначениях. Эти задачи используются для моделирования и оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения индивидуальных контрактов на транспортировки, составления оптимального штатного расписания, определения оптимальной специализации предприятий, рабочих участков и станков, оптимального назначения кандидатов на работы, оптимального использования торговых агентов. Критерием эффективности в данных задачах является линейная функция, ограничения также линейны, поэтому для их решения могут применяться методы линейной оптимизации, например симплекс-метод. Однако специальная структура таких задач позволяет разработать более удобные методы их решения. Некоторые из таких методов приведены в данной книге. Даны общая формулировка задач, основные термины и определения, этапы построения математических моделей, способы получения оптимальных решений. Также приведены числовые примеры экономических задач, которые могут быть решены этими методами.