Учитывая свойство оптимального решения, которое заключается в том, что оно может быть представлено как выпуклая комбинация базисных решений, получим, принимая за базисные решения:
X, =(3;5;0;0;9), Хс =(6;2;0;9;0)
Х=аХ, +(1-а)Х2 ;0<а< 1.
3.7. Неограниченность целевой функции
Если система ограничений в задаче линейного программирования непротиворечива, то применение конечного числа итераций симплекс-метода приводит либо к получению решения задачи (может быть неединственного) либо к установлению факта неограниченно-целевой функции.
Рассмотрим следующую задачу линейного программирования. Решить задачу минимизации линейной целевой функции:
F = 2Xj-3x2+l-при ограничениях:
2х-х>\ х,>0
Рассмотрим геометрическое решение этой задачи.
,F=-6
(3.33)
(3.34) (3.35) (3.36) (3.37)
12 3 4 5 6
Рис. 3.4
Из рис. 3.4 видно, что если перемещать линию уровня в направлении, противоположном вектору q (в направлении убывания), то она всегда
будет пересекать множество допустимых решений и, следовательно, це-
левая функция не ограниченна на множестве заданном ограничениями (З.ЗЗН3.37).
Если эту задачу решать симплексным методом, то на очередном шаге решения задачи получаем: основные переменные х, х, х. неосновные
переменные х, дс.
5 1 1
X, = - + -х, -\--Хл 1 3 3 3 3 4
7 2 1
2 = 3 + 33-34 Х5 =4 + Хз -Х4;
F= ~--~Хз +-Х4С, минимум не достигнут: переменная х имеет от-
X = (5/3; 7/3; 0; 0; 4) - базисное решение;
1 2 4
----Хо + -.
3 3 5
рицательный коэффициент в выражении для F, Определяем х3 = min( 00,00,00) = 00, следовательно, уравнения не ограничивают рост
хз и, следовательно, оптимальное значение функции F не ограниченно и
отрицательно, т.е. Fmm = -qo . Из рассмотренного примера видно, что если на каком либо шаге получаем во всех уравнениях системы бесконечные оценочные отношения переменной, которая переводится в основные, то задача не имеет конечного оптимума (Fmax= , если задача на максимум и Fmin = -00, если задача на минимум).
Можно сделать следующий вывод. Если система ограничений непротиворечива, то выполнение конечного плана шагов симплексного метода либо приводит к нахождению оптимального решения задачи (возможно неединственного), либо к установлению того факта, что целевая функция не имеет конечного оптимума.
Глава 4
ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Каждой задаче линейного программирования можно поставить в соответствие так называемую двойственную или сопряженную задачу по отношению к исходной. Аппарат теории двойственности может быть эффективно использован для проведения качественных исследований свойств задачи линейного программирования.
4.1. Двойственная задача для стандартной и канонической задачи линейного программирования
Каждой задаче линейного программирования на максимум может бьпъ поставлена в соответствие задача линейного программирования на минимум, получаемая из исходной путем определенных преобразований. Эти задачи называются симметричными или взаимно-двойственными.
Рассмотрим частный вид задачи выбора оптимально производственной программы, представленной в гл. 1.
Пусть предприятие № 1 имеет запасы материально-сырьевых ресурсов в объемах bf (/ = 1,...,т), где
т - число видов ресурсов. Как и раньше будем считать, что aj - это
объем материально-сырьевых ресурсов вида /, необходимых для выпуска одной единицы продукции вида j, Cj - прибыль от выпуска и реализации единицы продукции вида j {j =!,.;.,«).
Далее будем считать, что предприятие № 2 решило купить все материально-сырьевые ресурсы у предприятия № 1 по некоторым оптимальным ценам на эти ресурсы, которые обозначим как у\,..,Ут • Естественно, что предприятие №2 заинтересовано в том, чтобы затраты на приобретение материально-сырьевых ресурсов были минимальными, т.е.
Z = Ь,у, + Z)2>2 + + КУш ™п.
С другой стороны, предприятие № 1, которое продает материально-сырьевые ресурсы (далее их будем называть ресурсы), заинтересовано в