9.15. параметрические задачи линейного программирования

9.15. параметрические задачи линейного программирования

Семейство задач линейного программирования в канонической форме

f>=Yj b'j+yjO *,(min), j-1

п

£ ai/xj=bi, і=1, 2, m, Xj^0,j= 2, n

(9.44)

(9.45) (9.46)

(где Yj, yj — некоторые числа, j=l, 2, п); t — параметр, — со < / < + оо) называется параметрической задачей линейного программирования.

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

Пусть а — некоторое опорное решение задачи (9.44)—(9.46). Обозначим через А (а) множество всех значений параметра /, при которых а является оптимальным решением задачи (9.44)-—(9.46).

Возможны лишь следующие случаи: 1) Л (а)=0;

2) Д (а) = {/0}; 3) Д («*)=[*,, /J; 4) Д (<*) = ]-оо, /,];

5) Д (а) = [(2, +оо[; 6) Д (а)=]-со, +оо[.

Рассмотрим некоторый базис Ви В2, ВТ опорного решения а. Тогда оценки этого базиса для задачи (9.44)—(9.46) имеют вид

8j+8'jt,j=l, 2, п.

Обозначим через Т (Ви В2, В,) множество всех решений системы неравенств

6j+S'jt*£0,j=U2, п.

Тогда:

1) А(а)зТ(В1гВг, В,);

если а — невырожденное опорное решение, то

Д (а)=Г(5ь В2, ...,ВГ);

если а — вырожденное опорное решение, то

А(я)=иТ(ВиВ2,...,Вг),

где объединение берется по всем базисам опорного решения а.

Таким образом, всегда можно найти множество всех значений параметра t, при которых данное опорное решение является оптимальным решением параметрической задачи линейного программирования .

О Например, а=(5; 0; 6; 0) — невырожденное опорное решение задачи

/ = (-6 + /) jc, + (3 + 0 Xl+(-n+2t) хэ + (1-0*4 (шш)>

2*1+х2 +Зхз=28, ,

Х1+Х2 + ХЪ~ХЧ=11,

^5=0,7 = 1,2,3,4.

Опорное решение а является оптимальным решением данной задачи тогда и только тогда, когда

-4-/^0 /3=-4, 2/-5^0 /^5/2,

т. е. Д (се) = [-4, 5/2]. При этом/, (ct)= 17/-96. •

Если параметрическая задача линейного программирования (9.44)—(9.46) имеет непустое допустимое множество, то существуют опорные решения этой задачи а,, а2, а, такие, что:

пересечение множеств Д (а,) и Д (ctj), іф], является либо пустым, либо состоит из единственной точки;

і

если t$ [j А (а,), то целевая функция задачи (9.44)—(9.46) не

ограничена снизу на допустимом множестве.

Существует специальный алгоритм, позволяющий за конечное число шагов найти эти опорные решения а; (г = 1, 2, s) и определить соответствующие множества Д (ос,).

9.16. Целочисленные задачи линейного программирования

Целочисленная задача линейного программирования — это оптимизационная задача (V, f, fl), где целевая функция / является линейной функцией на У—Я", a Q — множеством решений некоторой системы линейных уравнений или линейных неравенств, у которых координаты с заданными номерами — целые числа.

Целочисленная задача линейного программирования отличается от общей задачи линейного программирования только дополнительным требованием о целочисленности некоторых (быть

Симплекс-таблицу для данной задачи приведем к базису Аи Аг опорного решения а:

может, и всех) неизвестных. Если в задаче требуется целочнслен-ность всех неизвестных, то ее называют полностью целочисленной.

Задача о загрузке корабля. В морском порту имеются

предметы п видов. Предмет 7-го вида имеет массу я, и ценность

с-, (/=1, 2 п). Требуется загрузить корабль данной грузоподъемности Ь так, чтобы ценность груза была наибольшей.

Обозначив через Xj количество предметов 7-го вида (j=l, 2, ...

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

я

f= Z cjxj (max)>

X cijXj^b,

Jt;3*0,7=1, 2, л,

Xj — uenoej 7=1, 2, п.

Задача о распределении капиталовложений между проектами. Имеется л проектов Ри Pjt Р„, причем для каждого проекта Р, известны ожидаемый эффект yj от его реализации и необходимая величина капиталовложений gj. Общий объем капиталовложений не может превышать заданной величины Ь. Требуется определить, какие проекты необходимо реализовать, чтобы суммарный эффект был наибольшим.

Введем неизвестные Xj (/= 1, 2, л), полагая

/= Е yjxj (max),

л

O^Xj^l, Xj — целое,7=1, 2, л.

В ряде случаев оптимизационную задачу с разрывной целевой функцией удается свести к целочисленной задаче линейного программирования.

Рассмотрим, например, задачу максимизации с целевой функцией

я

/= Е Cj (xf),

где

fO, если Xi—0, [cjXj+dj, если xj>0,

допустимое множество О. которой задано системой ограничений

R

£ ачх,=Ь» i=l, 2, т, Xj>0,j=l, 2, п.

Введем л новых неизвестных, полагая

если Xj>0, ЄСЛИ Xj= 0.

Если допустимое множество £1 ограничено, то исходная оптимизационная задача сводится к целочисленной задаче линейного программирования:

л

/= £ (c/xj + (max), /-і

я

£ aijxj=bl, i~ 2, т, jх^ 0; Xj^M у/, 0 <у^ 1; yj — целое,;= I, 2, n,

где А/ — достаточно большое число.

Если допустимое множество целочисленной задачи линейного программировании является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере.

Задача о коммивояжере. Имеется л городов Аи Аг, А„ и задана матрица С=(с$) расстояний между этими городами. Выезжая из исходного города Аи коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в Определить, в каком порядке следует объезжать города, чтобы суммарное пройденное расстояние было наименьшим.

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

Целочисленное оптимальное решение ослабления является оптимальным решением и исходной целочисленной задачи.

В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда может быть выбрано целочисленным) будет оптимальным решением исходной целочисленной задачи линейного программирования.

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

С другой стороны, для решения комбинаторной опимизаци-онной задачи можно попробовать перебрать все допустимые решения этой задачи и выбрать среди них такое, на котором целевая функция принимает наибольшее (наименьшее) значение. Однако встречаются задачи, у которых допустимых решений очень много и перебрать их все практически невозможно.

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

Известны различные методы решения целочисленных задач линейного программирования: методы отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий целочисленной задачи линейного программирования.