Задача целочисленного программирования
Задача целочисленного программирования — это основная задача целочисленного программирования.
Математическая модель
Математическая модель задачи целочисленного программирования имеет следующий вид:
или
Метод решения
Задача целочисленного программирования решается методом Гомори. Суть метода состоит в первоначальном решении симплекс-методом вспомогательной задачи линейного программирования (без ограничения целочисленности) вида:
или
Затем для нецелочисленной переменной оптимального решения вспомогательной задачи составляется ограничение отсечения и вновь решается вспомогательная задача, но уже М-методом. Причём если в r-ой строке последней симплекс-таблицы базисная переменная не является целочисленной (а она должна быть целочисленной по условию задачи), то составляется ограничение отсечения вида:
{arj}=arj-[arj] - дробная часть числа.
Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение.
Пример решения
Задача целочисленного программирования имеет вид:
Строим вспомогательную задачу линейного программирования (без ограничения целочисленности):
Вспомогательную задачу приводим к каноническому виду:
Решаем первую вспомогательную задачу симплекс-методом:
Составляем первое ограничение отсечения (в ограничении используются десятичные дроби):
Решаем вторую вспомогательную задачу М-методом:
Составляем второе ограничение отсечения (в ограничении используются правильные дроби):
Решаем третью вспомогательную задачу М-методом:
Оптимальное решение последней вспомогательной задачи x1=5, x2=2, x3=0, x4=7, x5=4, x6=1, x7=0, x8=0, L=38.
Оптимальное решение задачи целочисленного программирования x1=5, x2=2, Lц =38.
Другие задачи:
Ссылки
- Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование, «Наука», М., 1969.
- Участник:Logic-samara
