Симплекс метод с искусственными переменными примеры. Решение задач линейного программирования методом искусственного базиса
Решение задачи линейного программирования симплекс-методом начинается с нахождения какого-либо опорного плана.
Рассмотрим третий случай построения начального опорного плана (первый и второй описаны в пункте 2.1).
Пусть система ограничений имеет вид
Перейдем к
каноническому виду путем введения
дополнительных переменных
,
которые вычитаем из левых частей
неравенств системы. Получим систему
.
Теперь система
ограничений не имеет предпочтительного
вида, так как дополнительные переменные
x
n
+ i
входят
в левую часть (приb
i
0) с коэффициентами, равными –1. В этом
случае вводится так называемыйискусственный базис
путем перехода
кМ-задаче.
К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные w i . В целевую функцию переменныеw i вводят с коэффициентомM в случае решения задачи на минимум и с коэффициентом –M – для задачи на максимум, гдеM – большое положительное число. Полученная задача называетсяМ-задачей , соответствующей исходной. Она всегда имеет предпочтительный вид.
Пусть исходная задача линейного программирования имеет вид
|
| |
|
| |
|
|
;
;
При этом ни одно из ограничений не имеет предпочтительной переменной. М-задача будет записываться следующим образом:
|
| |
|
| |
;
При этом знак “–” в функции (10) относится к задаче на максимум. Задача (10)–(12) имеет предпочтительный вид. Ее начальный опорный план имеет вид
.
Если некоторые из уравнений (8) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема 5.
Если в оптимальном планех
опт
М
-задачи (10)–(12) все искусственные
переменные
,
то план
является оптимальным планом исходной
задачи (7)–(9).
Теорема 6 (признак несовместности системы ограничений ) . Если в оптимальном планеМ -задачи хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна.
В случае М
-задачи
индексную строку симплексной таблицы
разбиваем на две. В первой строке
записываются свободные члены выражений
и
,
а во второй – коэффициенты, содержащиеМ
. Признак оптимальности проверяется
сначала по второй строке. По ней же
определяется переменная, подлежащая
включению в базис. По мере исключения
из базиса искусственных переменных
соответствующие им столбцы элементов
можно опускать. Объясняется это тем,
что искусственные переменные в базис
не возвращают, а поэтому отвечающие им
столбцы больше не потребуются. После
исключения из базиса всех искусственных
переменных процесс отыскания оптимального
плана продолжают с использованием
первой строки целевой функции.
Пример 4. Решить с использованием искусственного базиса задачу линейного программирования
Первое ограничение имеет предпочтительную переменную х 3 , а второе – нет. Поэтому вводим в него искусственную переменнуюw 1 . Приходим кМ- задаче
Занесем условие М- задачи в симплексную табл. 5. Начальный опорный план имеет видx 0 = (x 1 ;x 2 ;x 3 ;x 4 ;w 1) = (0; 0; 2; 0; 12),z (x 0) = 0 – 12M .
Таблица 5
|
с Б | |||||||||
|
|
|||||||||
|
z j – c j | |||||||||
|
| |||||||||
Сделаем необходимые пояснения.
Индексную строку удобно разбить на две. В первой из них записываются свободные члены выражений 0 =c Б А 0 и j =c Б A j –c j , а во второй – коэффициенты, содержащиеM . Например, для табл. 5:
Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существуют отрицательные оценки, то план x 0 не является оптимальным.
Переходим к новой табл. 6.
Разрешающий столбец
находим по max{|–3M
|; |–4M
|} = 4M
,
разрешающая строка определяется по
.
Следовательно, 1 – разрешающий элемент.
Таблица 6
|
с Б | |||||||
|
z j – c j | |||||||
В индексной строке нет отрицательных оценок. Следовательно, по признаку оптимальности опорный план (0; 2; 0; 0; 4) оптимален. Но так как в оптимальном плане искусственная переменная w 1 не равна 0, то по теореме 6 система ограничений исходной задачи несовместна. Задача решения не имеет.
Ответ: нет решения.
Пример 5. Решить с использованием искусственного базиса задачу
Упорядочим запись исходной задачи. Умножим второе неравенство на –1:
Сведем задачу к каноническому виду. Получим
Первое и четвертое ограничения имеют предпочтительные переменные, а второе и третье – нет. Поэтому вводим в них искусственные переменные w 1 иw 2 . Приходим кМ- задаче
Занесем условие М- задачи в симплексную табл. 7. Начальный опорный план имеет видx 0 = (0; 0; 10; 0; 0; 4; 3; 9),z (x 0) = 0 + 12M .
Таблица 7
|
с Б | |||||||||||
|
|
|||||||||||
|
z j – c j | |||||||||||
|
| |||||||||||
Мы решаем задачу на минимум. Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существует положительная оценка, то план x 0 не является оптимальным. Переходим к новой табл. 8.
Таблица 8
|
с Б | |||||||||||
Решение системы производится путём ввода искусственных переменных 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 и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
Когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0}.
В ограничения и в функцию цели вводят так называемые «искусственные переменные» R j следующим образом:
∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j
При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c i x i , а другая – для составляющей M ∑R j Рассмотрим процедуру решения задачи на конкретном примере.
Пример 1. Найти максимум функции F(x) = -x 1 + 2x 2 - x 3 при ограничениях:
2x 1 +3x 2 +x 3 =3,
x 1 ≥0, x 2 ≥0, x 3 ≥0 .
Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи
2x 1 + 3x 2 + x 3 + R 1 = 3;
x 1 + 3x 3 + R 2 = 2 ;
Функция цели F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).
Выразим сумму R 1 + R 2 из системы ограничений: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , тогда F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) .
При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x 1 , x 2 , x 3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.
Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x 3 , которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R 2 должна быть из базиса исключена. Ведущий элемент обведен контуром.
В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:
x 1 =0; x 2 =7/9; F max =8/9.
Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥
Пример 2 . Найти минимальное значение функции F(x) = 2x 1 + 3x 2 - x 3 при следующих ограничениях
2x 1 +x 2 -3x 3 ≥6,
x 1 -x 2 +2x 3 =4,
x 1 +x 2 +x 3 ≤5,
x 1 ≥0, x 2 ≥0, x 3 ≥0 .
Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x 4 , x 5 и искусственную переменную R следующим образом:
2x 1 -x 2 +3x 3 +x 4 =-6,
x 1 -x 2 +2x 3 +R=4,
x 1 +x 2 +x 3 +x 5 =5,
Пусть x 4 , R и x 5 – базисные переменные, а x 1 , x 2 , x 3 – небазисные. Функция цели F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).
В первой (табл. 4.) коэффициенты при небазисных переменных в F-строке и M-строках знака не меняют, так как осуществляется минимизация функции. Свободный член в методе искусственного базиса в M-строке берется с противоположным знаком. Решение, соответствующее табл. 4, не является допустимым, так как есть отрицательный свободный член.
Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения. После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x 3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.
Таблица 4
| базисные переменные | Свободные члены | Небазисные переменные | ||
| x 1 | x 2 | x 3 | ||
| x 4 | -6 | -2 | -1 | 3 |
| R | 4 | 1 | -1 | 2 |
| x 5 | 5 | 1 | 1 | 1 |
| F | 0 | 2 | 3 | -1 |
| M | -4 | -1 | 1 | -2 |
Таблица 5
| базисные переменные | Свободные члены | Небазисные переменные | ||
| x 4 | x 2 | x 3 | ||
| x 1 | 3 | -1/2 | 1/2 | -3/2 |
| R | 1 | 1/2 | -3/2 | 7/2 |
| x 5 | 2 | 1/2 | 1/2 | 5/2 |
| F | -6 | 1 | 2 | 2 |
| M | -1 | -1/2 | 3/2 | -7/2 |
Таблица 6
Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x 4 = x 2 = 0;
x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
 |
Правая часть ограничений системы уравнений имеет вид:
Запишем текущий опорный план:
 |
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x
при 
. min
(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x
3 . Сделаем исключение Гаусса для столбца x
2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x
1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x
4 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными 
нет отрицательных элементов.
Решение можно записать так: 
.
Значение целевой функции в данной точке: F
(X
)=
.
Пример 2. Найти максимум функции
Р е ш е н и е.
Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x
2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
 |
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 1. Из базиса выходит вектор x
2 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x
3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор x
5 . Сделаем исключение Гаусса для столбца x
3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
Пример 2. Найти оптимальный план задачи линейного программирования:
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса , который является по сути разновидностью симплекс-метода.
Пусть задача приведена к каноническому виду (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 методом искусственного базиса.
Теория двойственности
