Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Задача целочисленного программирования

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Задача целочисленного программирования — это задача линейного программирования, в которой решение ищется в целых числах. Ниже представлена основная задача целочисленного программирования.

Математическая модель[править]

Математическая модель задачи целочисленного программирования имеет следующий вид:

или

Метод решения[править]

Задача целочисленного программирования решается методом Гомори. Суть метода состоит в первоначальном решении симплекс-методом вспомогательной задачи линейного программирования (без ограничения целочисленности) вида:

или

Затем для нецелочисленной переменной оптимального решения вспомогательной задачи составляется ограничение отсечения и вновь решается вспомогательная задача, но уже М-методом. Причём если в r-ой строке последней симплекс-таблицы базисная переменная не является целочисленной (а она должна быть целочисленной по условию задачи), то составляется ограничение отсечения вида:

ЗЦП04.JPG, где

{arj}=arj-[arj] - дробная часть числа.

Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение.

Пример решения[править]

Задача целочисленного программирования имеет вид:

ЗЦП11.JPG

Строим вспомогательную задачу линейного программирования (без ограничения целочисленности):

ЗЦП12.JPG

Вспомогательную задачу приводим к каноническому виду:

ЗЦП13.PNG

Решаем первую вспомогательную задачу симплекс-методом:

ЗЦП21.PNG

Составляем первое ограничение отсечения (в ограничении используются десятичные дроби):

ЗЦП14.JPG

Решаем вторую вспомогательную задачу М-методом:

ЗЦП22.PNG

Составляем второе ограничение отсечения (в ограничении используются правильные дроби):

ЗЦП15.JPG

Решаем третью вспомогательную задачу М-методом:

ЗЦП23.JPG

Оптимальное решение последней вспомогательной задачи 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