До сих пор мы всесторонне рассматривали задачу, решение которой осуществлялось на основе простейшего алгоритма симплексного метода, поскольку все ограничения имели вид меньше либо равно. В этом случае дополнительные переменные задачи образуют единичный базис. Но может получиться так, что система ограничений представлена в канонической форме, но она не приведена к единичному базису.
При решении таких задач был введен метод искусственного базиса . Он особенно удобен, когда число переменных значительно превосходит число уравнений.
Алгоритм решения задачи симплексным методом с искусственным базисом рассмотрим на примере.
Пример 1
Найти максимум Z=4X1+2X2+X3
3Х1+2Х2+Х3=15
Хj³0, j=1,...,3
Переходим к канонической форме:
Х1+Х2+Х3-Х4=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3=15
Хj³0, j=1,...,5
Zmax=4X1+2X2+X3+0×X4+0×X5
Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением и в нем отсутствует базисная переменная. Для того, чтобы был единичный базис вводим в соответствующие ограничения искусственные переменные y1 и y2 с положительными коэффициентами (+1).
Следует отметить, что искусственные переменные вводятся только для математической формализации задачи. Поэтому схема вычислений должна быть такой, чтобы искусственные пременные не могли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например, 10000. Причем, при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум – со знаком плюс. Теперь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z–задачи и искусственные переменные с коэффициентом ±М, т.е.
T=Z-M S yi, при решении на максимум целевой функции и
T=Z+M S y, при решении на минимум целевой функции
В нашем случае:
Х1+Х2+Х3-Х4+y1=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3+y2=15
Хj³0, j=1,...,5
Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)
Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на 2 строки:
В первую строку записываем оценки, которые не содержат коэффициент М;
Во вторую строку- оценки по каждой свободной переменной, содержащие коффициент М.
Расчет элементов (оценок) этих двух строк производится по формуле (2). Только отличие:
При расчете оценок Z -строки должны быть учтены коэффициенты Cj , входящие в функцию Z ;
При расчете оценок М-строки этот коэффициент во внимание не берется, а М -выносится как общий множитель.
Для того, чтобы Т-задача и Z-задача были равны, нужно, чтобы yi были равны нулю. Поэтому пока y i не равно нулю, разрешающий столбец выбирается по оценкам во второй строке, используя алгоритм симплексного метода.
Лишь после того, как все y i станут равны нулю, дальнейший расчет будет вестись по первой индексной строке, т.е. -обычная Z-задача.
Причем, когда искусственная переменная будет выводиться из базиса, ее выбросим из симплексной таблицы, а в следующей симплекс-таблице не будет бывшего разрешающего столбца.
Между оптимальными решениями М-задачи и Z-задачи существует связь, устанавливаемая следующей теоремой:
1. Если в оптимальном решении М-задачи все искусственные переменные (y i) равны нулю, то это решение будет являться оптимальным решением Z-задачи.
2. Если в оптимальном решении М-задачи, хотя бы одна из искусственных переменных отлична от нуля, то Z-задача не имеет решения по причине несовместности системы ограничений.
3. Если М-задача оказалась неразрешимой (Т®+¥ или-¥), то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.
Составим первую симплексную таблицу. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наибольшей по абсолютной величине отрицательной оценке (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит У из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной X2 с оценкой (-3).
Таблица 3.1.
Первая симплексная таблица
Заполнение Z- строки осуществляется по формуле (2):
а00 = 0 × 8– 0 = 0
а01 =0 × 2– 4 = -4
а02 =0 × 1– 2 = -2
а03 =0 × 1– 1 = -1
а02 =0 × 0– 0 = 0
Заполнение М- строки:
а¢00 = -М × 8 + (–М) × 15 = -23М
а¢01 = -М × 1 + (–М) × 3= -4М
а¢02 = -М × 1 + (–М) × 2= -3М
а¢03 = -М × 1+ (–М) × 1 = -2М
а¢04 = -М ×(-1)+ (–М) × 0 = 1М
М выносим как общий множитель.
В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной X4 переносим без изменений.
Таблица 3.2.
Вторая симплексная таблица
Во второй таблице получаем вырожденное решение, так как получаются два одинаковых минимальных симплексных отношений. Поэтому находим отношения элементов столбца следующего за разрешающим к элементам разрешающего столбца с учетом знака.
Таблица 3.3.
Третья симплексная таблица
Теперь решаем обычным симплексным методом.
Таблица 3.4.
Четвертая симплексная таблица
| Св.П | Cj | |||
| Б.П. | Ci | ai0 | X5 | X4 |
| Х3 | -1 | |||
| X1 | ||||
| Х2 | -2 | -1 | ||
| Z |
В оценочной строке все элементы являются неотрицательными величинами, следовательно получено оптимальное решение:
Zmax=15 Xopt(0,7,1,0,0)
Пример2
Задача решалась на минимум (Z®min) целевой функции. На последней итерации получили следующую таблицу:
Таблица 3.5.
Последняя симплексная таблица
| Св.П | Cj | ||||
| Б.П. | Ci | ai0 | X1 | X3 | X4 |
| У1 | М | -1/2 | -1/2 | -1/2 | -1 |
| X5 | 1/2 | 1/2 | 1/2 | ||
| Х2 | 15/2 | 3/2 | 1/2 | ||
| Z | -1 | ||||
| М | -1/2 | -1/2 | -1/2 | -1 |
В Т-задаче получено оптимальное решение, так как в М-строке нет больше положительных оценок, т.е. выбор разрешающего столбца невозможен, а У1 находится в базисе. В этом случае исходная задача не имеет решения по причине несовместности системы ограничений.
| x 1 | - | 2 | x 2 | + | S 1 | = | 2 | ||||||||||
| 2 | x 1 | +3 | x 2 | - | S 2 | = | 4 | ||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 2 |
| x 1 | - | 2 | x 2 | + | S 1 | = | 2 | |||||||||||||
| 2 | x 1 | +3 | x 2 | - | S 2 | + | R 1 | = | 4 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 2 |
| x 1 = 0 x 2 = 0 S 2 = 0 S 1 = 2 S 3 = 2 R 1 = 4 |
=> W = 4 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | св. член | Θ |
| 1 | -2 | 1 | 0 | 0 | 0 | 2 | |
| 2 | 3 | 0 | -1 | 0 | 1 | 4 | 4: 3 ≈ 1,33 |
| -2 | 1 | 0 | 0 | 1 | 0 | 2 | 2: 1 = 2 |
| -2 | -3 | 0 | 1 | 0 | 0 | W - 4 | |
| 1 | -2 | 1 | 0 | 0 | 0 | 2 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 1/3 | 4/3 | |
| -2 | 1 | 0 | 0 | 1 | 0 | 2 | |
| -2 | -3 | 0 | 1 | 0 | 0 | W - 4 | |
| 7/3 | 0 | 1 | -2/3 | 0 | 2/3 | 14/3 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 1/3 | 4/3 | |
| -8/3 | 0 | 0 | 1/3 | 1 | -1/3 | 2/3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| 7/3 | x 1 | + | S 1 | - | 2/3 | S 2 | = | 14/3 | |||||||||
| 2/3 | x 1 | + | x 2 | - | 1/3 | S 2 | = | 4/3 | |||||||||
| - | 8/3 | x 1 | + | 1/3 | S 2 | + | S 3 | = | 2/3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | св. член | Θ |
| 7/3 | 0 | 1 | -2/3 | 0 | 14/3 | 14/3: 7/3 = 2 |
| 2/3 | 1 | 0 | -1/3 | 0 | 4/3 | 4/3: 2/3 = 2 |
| -8/3 | 0 | 0 | 1/3 | 1 | 2/3 | |
| -7/3 | 0 | 0 | 5/3 | 0 | F - 20/3 | |
| 1 | 0 | 3/7 | -2/7 | 0 | 2 | |
| 2/3 | 1 | 0 | -1/3 | 0 | 4/3 | |
| -8/3 | 0 | 0 | 1/3 | 1 | 2/3 | |
| -7/3 | 0 | 0 | 5/3 | 0 | F - 20/3 | |
| 1 | 0 | 3/7 | -2/7 | 0 | 2 | |
| 0 | 1 | -2/7 | -1/7 | 0 | 0 | |
| 0 | 0 | 8/7 | -3/7 | 1 | 6 | |
| 0 | 0 | 1 | 1 | 0 | F - 2 |
| S 1 = 0 S 2 = 0 x 1 = 2 x 2 = 0 S 3 = 6 |
=> F - 2 = 0 => F = 2 |
Решение системы производится путём ввода искусственных переменных R i со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом ).
Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной . Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (x n+m) и искусственные (R i)- базисными.
Исходная таблица для "Метода искусственного базиса" имеет следующий вид:
| x 1 | x 2 | ... | x n-1 | x n | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
| R i | a i,1 | a i,2 | ... | a i,n-1 | a i,n | b i |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
| M | -∑a i,1 | -∑a i,2 | ... | -∑a i,n-1 | -∑a i,n | -∑b i |
Элементы дополнительной строки M расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные R i) взятая с противоположным знаком.
Приводим задачу ЛП к каноническому виду
F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1
a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2
.........................................
a i,1 x 1 +a i,2 x 2 +...a i,n x n +R i =b i
.......................................
a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x n+m , к каждому i-му условию-равенству добавляем искусственную переменную R i .
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
| x 1 | x 2 | ... | x n-1 | x n | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
| x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
| R i | a i,1 | a i,2 | ... | a i,n-1 | a i,n | b i |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
| M | -∑a i,1 | -∑a i,2 | ... | -∑a i,n-1 | -∑a i,n | -∑b i |
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b 0 - текущее значение целевой функции и элемент -∑b i) нет отрицательных, то найдено оптимальное решение.
2.1 Положительность строки M
Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑b i)
При a i,l >0, b i >0
Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2
Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2 .
2.2 Положительность строки F
Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b 0), выбираем среди отрицательных элементов строки F максимальный по модулю.
-a 0,l =min{-a 0,i }
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0
k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.
Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса , который является по сути разновидностью симплекс-метода.
Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i 1 -м, i 2 -м, …, i s -м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеx m +1 , x m +2 , …, x m + s , а в целевую функцию - слагаемые ±Mx m +1 , ±Mx m +2 , …, ±Mx m + s , где M >>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной .
Например, вспомогательная (дополнительная) задача с искусственными переменными для задачи (1.5) будет иметь вид
c 1 x 1 +c 2 x 2 +…+c n x n +Mx n + m +1 +Mx n + m +2 +…+Mx n +2 m ®min
Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу:
c 1 x 1 +c 2 x 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + m ®max
(5.1)
5.1.1. Если ( , , …, , , …, ) оптимальное решение вспомогательной задачи , где , …, - значения искусственных переменных , , , …, - значения переменных в исходной задаче в канонической форме , то =…= =0 и ( , , …, ) - оптимальное решение исходной задачи . При этом значения целевой функции исходной и вспомогательной задач совпадают .
Отсюда получаем, что для решения задачи линейного программирования, методом искусственного базиса достаточно:
1. Привести задачу к каноническому виду.
2. Если в задаче в каноническом виде нет базиса из единичных векторов, то составить вспомогательную задачу (если в задаче в каноническом виде имеется базис из единичных векторов, то задача решается обычным симплекс-методом).
3. Решить вспомогательную задачу, и если ( , , …, , , …, ) - оптимальное решение вспомогательной задачи, где x 1 , x 2 , …, x m - основные и дополнительные переменные (из задачи в каноническом виде), x m +1 , x m +2 , …, x m + s - искусственные переменные то ( , , …, ) - решение задачи в каноническом виде. Оптимальное значение целевой функции вспомогательной задачи равно оптимальному значению исходной задачи.
При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями:
1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ±M , то оценки D k имеют вид ± M , причём M - достаточно большое число. Поэтому при ≠0 знак D k фактически определяется знаком при . В связи с этим в симплекс-таблице на начальном этапе (пока в базис входят искусственные переменные) вместо одной строки D k записывают две строки и , и при применении критерия оптимальности ориентируются только на строку .
2. Искусственные переменные по мере их выведения из базиса исключаются из дальнейшего рассмотрения.
3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты D k при M будут равны нулю, в таблице остаётся только строка =D k .
Пример. Решить пример из предыдущего параграфа методом искусственного базиса.
Решение. Напоминаем задачу:
3x 1 +x 2 +2x 3 ® max(min)
1. Приведём задачу к каноническому виду:
3x 1 +x 2 +2x 3 ® max(min)
2. В базис в виде единичного вектора входит только вектор при x 4 , то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x 6 и x 7:
В целевую функцию они войдут с коэффициентами M или -M в зависимости от того, решается задача на min или на max.
Решим задачу на максимум. Тогда вспомогательная задача - следующая:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max
3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:
| Базис | С б | Своб. чл. | -3 | -M | -M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | -M | -1 | min | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | -M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -8 | -2 | -3 |
Здесь D 2 =-2M -1, D 3 =-3M -2. Коэффициенты при M записаны в строке . Имеем, что D 2 <0 и D 3 <0, то есть для переменных x 2 и x 3 нарушается критерий оптимальности. Поэтому в базис будем вводить x 2 или x 3 . Какую именно из этих переменных, и вместо какой из искусственных (вместо x 6 или вместо x 7), определяем с помощью столбцов q 2 и q 3 . На пересечении столбца q 2 и строк и числа соответственно 2 и 4 означают, что в случае включения в базис x 2 значение функции возрастёт на -q 2 D 2 =4M +2, а в случае включения в базис x 3 значение функции возрастёт на -q 3 D 3 =3M +2<-q 2 D 2 . Поэтому в базис включаем x 2 (что обеспечивает большее возрастание функции и в конечном итоге ускоряет процесс решения задачи). Так как min =2 достигается в строке x 6 , то из базиса исключаем x 6 . Строим новую симплекс-таблицу, в который уже столбец с искусственной переменной x 6 отсутствует (вычеркнут), так как искусственная переменная x 6 из дальнейшего процесса исключается. В новой таблице коэффициент при x 2 в первой строке (которая теперь соответствует новой базисной переменной x 2) равен 1, а во второй равен нулю. Поэтому первые две строки в новую таблицу переписываем из старой. Для того, чтобы в строке x 7 при x 2 получить 0, из строки x 7 в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:
| Базис | С б | Своб. чл. | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | min | ||||||||
| -4 | -2 |
Так как D k <0 только для одного значения k =1, а именно, D 1 =-2M +2<0 (напоминаем, что M - достаточно большое число, так что -2M <2 и D 1 <0), то ищем только отношения q 1 . Минимум этих отношений достигается в строке x 7: min =2. Поэтому искусственная переменная исключается из базиса, а вместо неё в базис включается x 1 .
Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x 1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x 1 появятся соответственно 0, 0 и 1:
| Базис | С б | Своб. чл. | -3 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||
| x 2 | 3/2 | -1/2 | |||||
| x 4 | 3/2 | 1/2 | |||||
| x 7 | -3 | -1/2 | -1/2 | ||||
| D k | -2 |
В полученной таблице D k ³0 для всех k X 0 =(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x 4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).
Решим задачу на минимум (min). Тогда вспомогательная задача - следующая:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max
Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:
| Базис | С б | Своб. чл. | -3 | M | M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | M | -1 | min | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -1 |
Критерий оптимальности нарушается для переменных x 2 и x 3: D 2 =2M -1>0, D 3 =3M -2>0. Так как -q 2 D 2 =-4M +2 по абсолютной величине превосходит -q 3 D 3 =-3M +2, то в базис включаем x 2 . При этом min =2 достигается в строке x 6 , и из базиса исключаем x 6 . Переход к новой таблице аналогичен переходу при решении задачи на max:
| Базис | С б | Своб. чл. | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | min | ||||||||
| -1 | -1 |
Теперь D 1 >0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x 1 вместо x 7:
| Базис | С б | Своб. чл. | -3 | q 3 | q 5 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||||
| x 2 | 3/2 | -1/2 | 8/3 | - | |||||
| x 4 | 3/2 | 1/2 | 4/3 | ||||||
| x 7 | -3 | -1/2 | -1/2 | - | - | ||||
| D k | -2 | -4/3 | -4 |
Имеем D 3 =1>0 и D 5 =1>0. Так как |-q 5 D 5 |=|-q 3 D 3 |, то вводим в базис x 5 (вместо x 4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):
В полученной таблице D k £0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X 0 =(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6.
Ответ: F min =-6, минимум достигается в точке X 2 =(4; 6; 0);
F max =-2, максимум достигается в точке X 1 =(2; 4; 0).
5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.
Теория двойственности
Пусть решаем ЗЛП в виде
В этом случае общая схема симплекс-метода претерпевает некоторые изменения. А именно:
1) Пусть дан базис некоторого опорного решения и соответствующая ему симплекс-таблица . В верхней строке этой таблицы (заголовки столбцов) располагаются свободные переменные, в крайнем левом столбце – базисные переменные; крайний правый столбец – это столбец свободных членов, а самая нижняя строка является строкой целевой функции и называется вектором относительных оценок. Остальное содержимое таблицы - столбцы матрицы ограничений, отвечающие соответствующим столбцам свободных переменных. Координаты вектора относительных оценок находят по правилу: вектор из коэффициентов при базисных переменных в целевой функции скалярно умножить на i -й столбец симплекс-таблицы и вычесть из найденного числа коэффициент целевой функции при соответствующем свободном переменном.
2) Если все относительные оценки (нижняя строка этой таблицы) неотрицательны, то построено оптимальное опорное решение.
3) Если существует отрицательная оценка и соответствующий ей столбец (разрешающий) состоит из неположительных элементов, то имеет место неразрешимость целевой функции Z (X ), то есть max Z (X ) ®+¥.
4) Иначе, выбрать ведущий элемент (задаёт ведущую строку) и сделать с ним шаг жордановых исключений, перейдя к новой симплекс-таблице, которую проанализировать как в пункте 2).
Метод искусственного базиса
Метод искусственного базиса применяется для решения задач ЛП в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов.
Пусть задана задача ЛП в канонической форме, то есть имеет вид (2.1.1), и в ней отсутствует единичный базис. К этой задаче строим вспомогательную задачу (ВЗ): 
Здесь w 1 , w 2 ,…, w m – искусственные переменные. Запишем ограничения в векторном виде: A 1 x 1 +A 2 x 2 +…+A n x n +A n +1 w 1 +…+A n + m w m =B , где , , …, , , , …, , . Таким образом, вектора , , …, образуют единичный базис в R m , и все искусственные переменные соответствующие этим векторам будут базисными. Далее строится обычная симплекс-таблица. Если ВЗ не имеет решения в силу неограниченности целевой функции, то исходная задача также не имеет решения по той же причине. Пусть в результате знакомых по симплекс-методу необходимых преобразований получили оптимальную симплекс-таблицу к ВЗ. Очевидно, что максимальное значение целевой функции ВЗ равно 0, то есть max F =0. Если же maxF <0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F =0. Тогда возможны такие ситуации:
1) все искусственные переменные стали свободными и были исключены из таблицы. В этом случае вычеркиваем столбцы, соответствующие искусственным переменным и последнюю строку. Вместо неё приписываем новую строку оценок, но с использованием исходной целевой функции Z (X ). Тем самым получена начальная симплекс-таблица для исходной задачи ЛП, к которой применяем симплекс-метод;
2) в оптимальном решении ВЗ хотя бы одна искусственная переменная осталась базисной. Тогда:
а) либо все числа в строках, соответствующих оставшимся базисным искусственным переменным, равны 0;
б) либо есть хоть одно отличное от 0.
В первом случае, поступаем также как и пункте 1). Во втором, выбираем любой ненулевой элемент в качестве ведущего и делаем шаг жордановых исключений. Через конечное число шагов мы придем или к пункту 1), или к пункту 2)а).
Заметим, что если среди векторов A j , j =1,2,…,n , были вектора, которые могли бы войти в базис, то искусственные переменные вводят только в те уравнения системы ограничений, в которых отсутствует базисная переменная.
Пример. Максимизировать функцию Z =x 1 +2x 2 -2x 3 при ограничениях
Решение. Преобразуем исходную задачу линейного программирования к канонической (см. (2.1.1). Для этого введём в ограничения дополнительные неотрицательные переменные. А именно, в первое неравенство – переменную x 4 со знаком «+», во второе – x 5 со знаком «-» (см. §2.2). Система ограничений примет вид:
Эту систему запишем в векторной форме: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 =B , где
Очевидно, что в данной системе ограничений отсутствует единичный базис. Это означает, что среди векторов A j нет трёх необходимых единичных векторов, которые должны образовывать базис в R 3 . Однако заметим, что вектор A 4 является частью базиса. Ему соответствует базисная переменная x 4 . Необходимо найти ещё два единичных вектора. Для этого применим метод искусственного базиса. Введём искусственные переменные в те уравнения ограничений, в которых не присутствует базисная переменная x 4 и построим следующую вспомогательную задачу (ВЗ):
F =-w 1 -w 2 ®max
где w 1 , w 2 – искусственные переменные. Система ограничений ВЗ в векторном виде имеет вид: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 +A 6 w 1 +A 7 w 2 =B , где вектора A j , j =1,2,3,4,5 определяются также, как и выше, а и . Таким образом, вектора A 4 , A 6 , A 7 образуют базис в R 3 и им соответствуют базисные переменные (БП) – x 4 , w 1 , w 2 . Все остальные переменные, а именно x 1 , x 2 , x 3 , x 5 объявляются свободными (СП). Далее к ВЗ применяем обычный симплекс-метод. Как и раньше, см. §5.1, начальный опорный план получается, если присвоить свободным переменным значения, равные нулю. При этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных коэффициентов В , то есть x 1 =x 2 =x 3 =x 5 =0¸ а x 4 =8, w 1 =4, w 2 =12. Строим симплекс-таблицу, соответствующую начальному опорному плану:
| СП БП. | x 1 | x 2 | x 3 | x 5 | B |
| x 4 | -3 | ||||
| w 1 | -1 | ||||
| w 2 | -2 | ||||
| F | -4 | -3 | -16 |
С этой таблицей проводим необходимые преобразования (см. §5.1) симплекс-метода, пока не получим оптимальную симплекс-таблицу или не получим неразрешимость. В нашем случае, мы уже на втором шаге будем иметь такую симплекс-таблицу:
| СП БП. | w 1 | x 2 | x 3 | w 2 | B |
| x 4 | -0,5 | -3 | -0,5 | -0,5 | |
| x 1 | 0,25 | 0,75 | 0,25 | ||
| x 5 | -0,75 | -2 | |||
| F |
Эта таблица будет оптимальной для ВЗ. При этом все искусственные переменные стали свободными и max F =0. Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием исходной целевой функции Z (X ), получим начальную симплекс-таблицу для исходной задачи ЛП:
| СП БП. | x 2 | x 3 | B |
| x 4 | -3 | -0,5 | |
| x 1 | 0,75 | ||
| x 5 | -2 | ||
| Z | -2 | 2,75 |
Проанализировав последнюю таблицу, делаем вывод, что исходная задача ЛП не имеет решения в силу неограниченности целевой функции.
Пример. Минимизировать функцию 
при ограничениях
Если ввести дополнительные неотрицательные переменные , , , , и перейти к задаче на нахождение максимума целевой функции, исходная задача примет вид:
Базисное решение (допустимый план) будет иметь вид: , а , , w 1 =10, w 2 =5. Строим симплекс-таблицу к ВЗ, соответствующую начальному опорному плану:
| СП БП. | x 1 | x 2 | x 3 | x 4 | B |
| w 1 | -1 | ||||
| w 2 | -1 | ||||
| x 5 | |||||
| x 6 | -1 | ||||
| F | -1 | -1 | -15 |
Проводя преобразования по методу Жордана-Гаусса, на втором шаге будем иметь оптимальную симплекс-таблицу ВЗ (5.2.2). Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием целевой функции Z 1 (X ), получим начальную симплекс-таблицу для задачи (5.2.1).
