Базисным решением системы /w-линейных уравнений с п переменными называются решения, в котором все « - w неосновных переменных равны 0.
В задачах линейного программирования особый интерес представляют допустимые базисные решения, или как их еще называют опорные планы. Число базисных переменных является конечным, так как оно равно числу комбинаций основных переменных и не превосходит числа
С . Базисное решение, в котором хотя бы одна из основных переменных равна О, называется вырожденным.
Пример. Найти все базисные решения следующей системы:
f Xl - Х2 - 2x3 + Х4 = О [2xi + Х2 + 2X3 - Х4 = 2.
Также было установлено, что существует три группы основных переменных {xi,X2}, {хрХз}, {xi,X4}, т.е. число базисных решений равно
трем. Приравняв не основные переменные к нулю, т.е. Х3 = Х4 = О, получим систему уравнений вида:
Х1-Х2 =0 [2xi+X2=2,
откуда Xi=2/3, Х2=2/3, следовательно, первое базисное решение Xj = {2/3,2/3,0,0} допустимое. Если взять за основные переменные х,, Хз и приравнять к нулю соответствующие неосновные переменные Х2 = Х4 = О, получим второе базисное решение Х2 = {2/3,0,2/3,0}.
Аналогично можно найти и третье базисное решение Х3 = {2 / 3,0,0, -2 / 3}, которое в силу отрицагельности последней компоненты не является допустимым.
2.2. Геометрический смысл задачи линейного программирования
Рассмотрим следующую задачу линейного программирования:
max(xi +Х2) Зх, +5x2 <15 -х, + Х2 < 2 10xi+7x2 <35 -х, -Х2 <-"! XiO Х2 > 0.
Известно, что уравнение axi -\-bx2=c определяет прямую на плоскости Х1ОХ2 (если а и b равны нулю одновременно). При этом вся плоскость делиться на две полуплоскости. Если две точки
плоскости Х, ,Х2 , Xj ,Х2 ЛС-
жат по разные стороны прямой, то
величины
-\-bx2 -с
В том случае, если в задаче линейного программирования две переменные xj ИХ2 а область допустимых решений ограничена, оптимальное решение может быть получено путем параллельного перемещения параметрического семейства прямых cjXj+C2X2=d до пересечения с областью допустимых решений задачи.
При этом выражение C]Xj-\-C2X2 является целевой функцией, а параметр d принимает любые произвольные значения.
+bx2 -с принимают значения
разных знаков, в противном случае указанные величины принимают значения одного знака.
-Х,+Х2=2
3x1 + 5x2=15
Рис. 2.1
Учитьшая приведенные рассуждения, изобразим на координатной плоскости множество точек, удовлетворяющих всем ограничениям примера.
На рис. 2.1 заштриховано множество допустимых точек, т.е. точек плоскости, координаты которых удовлетворяют всем неравенствам рассматриваемой задачи линейного программирования.
Исследуем целевую функцию Xj + Х2. Рассмотрим прямую Xj + Х2 = 5. График этой прямой изображен пунктирной прямой линией.
Учитывая, что график не пересекает множество допустимых точек, нет допустимых точек, которые придавали бы целевой функции значение 5.
Рассмотрим параметрическое семейство прямых х + Хз = i , представляющих собой множество параллельных прямых, каждая из которых соответствует определенному значению параметра L. Тогда задачу линейного
программирования можно сформулировать следующим образом. Найти такое максимальное значение I, при котором прямая х, + = I пересекает допустимое множество. Если двигать эту прямую параллельно самой себе в направлении начала координат, то первой точкой будет точка А с (10 А5Л
координатами -,- , которая находится на пересечении прямых ч29 29)
Юх, + 7x2 = 35 и Зх, + 5x2 = 15. На этом примере можно увидеть основные свойства задач линейного программирования: в нем допустимое множество точек представляет собой выпуклый многоушльник, получившийся в результате пересечения полуплоскостей и наибольшее значение целевой функции достигается в его вершине - крайней точке.
Решение задачи линейного программирования может быть не единственным, а состоять из бесконечного числа точек.
Рассмотрим следующий пример:
max(8xi +9X2) 3x1+6x2 <18 7xi+4x2<28 8x1 + 9x2 < 36 Xl >0 Х2 >0.
Здесь решением служит любая точка отрезка между точками
18 12 77
108 28
. Отметим, что сами эти точки - вершины допус-
31 31J
тимого многоугольника- также являются решениями. Из рассматриваемых примеров следует, что решение задачи линейного программирования состоит в следующем: необходимо построить многоугольник допустимых точек, найти его вершины и выбрать из них те, координаты которых придают максимальное значение целевой функции.
2.3. Выпуклые множества
Пусть Л" -«-мерное евклидово пространство и X некоторое множество пространства Л", т.е. X с Л".
Определение 2.1. Множество X назьюается выпуклым, если с любыми двумя точками х,, Х2 {х.хХ ) оно содержит все точки вида
х = ах,+(1-а)х2,где Oal.