9.16. целочисленные задачи линейного программирования
9.16. целочисленные задачи линейного программирования
Целочисленная задача линейного программирования — это оптимизационная задача (V, /, Q), где целевая функция/является линейной функцией на VR", a Q — множеством решений некоторой системы линейных уравнений или линейных неравенств, у которых координаты с заданными номерами — целые числа.
Целочисленная задача линейного программирования отличается от общей задачи линейного программирования только дополнительным требованием о целочисленности некоторых (быть может, и всех) неизвестных. Если в задаче требуется целочисленность всех неизвестных, то ее называют полностью целочисленной.
Задача о загрузке корабля. В морском порту имеются предметы п видов. Предмет у'-го вида имеет массу а. и ценность с. (/' = 1, 2,
и). Требуется загрузить корабль данной грузоподъемности Ъ так, чтобы ценность груза была наибольшей.
Обозначив через х. количество предметов у'-го вида (у = 1, 2,
и), которые необходимо погрузить на корабль, получим целочисленную задачу линейного программирования:
и
f = Xc;*/(max)>
и У'=1
Ху^О, / = 1,2, ...,п, Xj — целое, у = 1,2,и.
Задача о распределении капиталовложений между проектами.
Имеется и проектов Ру,Р.,Рп, причем для каждого проекта Р. известны ожидаемый эффект у. от его реализации и необходимая величина капиталовложений g.. Общий объем капиталовложений не может превышать заданной величины Ъ. Требуется определить, какие проекты необходимо реализовать, чтобы суммарный эффект был наибольшим.
253
Введем неизвестные Xj (7 = 1, 2,и), полагая Ґ1, если проект Pj реализуется; J [О, если проект Pj не реализуется. Получим целочисленную задачу линейного программирования:
л
f = ^yjXj(max),
п
J,gjXj < b,
У=і
0<Xj<l, 7 = 1,2, ...,n,
Xj — целое, 7 = 1,2,п.
В ряде случаев оптимизационную задачу с разрывной целевой функцией удается свести к целочисленной задаче линейного программирования.
Рассмотрим, например, задачу максимизации с целевой функцией
7=1
где
І
0, еслих, = О,
CjXj + fly, еслих,> О, допустимое множество Q которой задано системой ограничений
л
Y*atixj=bi> i = l,2,-,m,
Xj>0, 7=1,2,и.
Введем п новых неизвестных, полагая
У і ГО, если Xj О, 11, ЄСЛИ Xj > 0.
Если допустимое множество Q ограничено, то исходная оптимизационная задача сводится к целочисленной задаче линейного программирования:
л
7=1
254
п
Y*atixj=bi> г = 1,2,...,/и,
х.>0; х.<Му., 0<ц<1, у=1, 2,..., и, уу —целое, 7=1,2,и,
где М— достаточно большое число.
Если допустимое множество целочисленной задачи линейного программирования является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере.
Задача о коммивояжере. Имеется п городов Ар А2,Ап и задана матрица С = (су) расстояний между этими городами. Выезжая из исходного города Av коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в Av Определить, в каком порядке следует объезжать города, чтобы суммарное пройденное расстояние было наименьшим.
Если в целочисленной задаче линейного программирования отбросить требование о целочисленности неизвестных, то получим задачу линейного программирования, которая называется ослаблением исходной целочисленной задачи.
Целочисленное оптимальное решение ослабления является оптимальным решением и исходной целочисленной задачи.
В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда может быть выбрано целочисленным) будет оптимальным решением исходной задачи.
В большинстве же случаев ослабление целочисленной задачи имеет только нецелочисленное оптимальное решение, причем если округлить нецелочисленные координаты этого решения, то нельзя получить даже допустимого решения исходной задачи.
С другой стороны, для решения комбинаторной оптимизационной задачи можно попробовать перебрать все допустимые решения этой задачи и выбрать среди них такое, на котором целевая функция принимает наибольшее (наименьшее) значение. Однако
255
существуют задачи, у которых допустимых решений очень много и перебрать их все практически невозможно.
Таким образом, целочисленные задачи линейного программирования образуют специфический класс оптимизационных задач, для решения которых требуются специальные методы.
Известны различные методы решения целочисленных задач: метод отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий задачи.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы