Метод искусственного базиса (или метод “М”) может быть применен для решения задачи ЛП, если ее система ограничений, помимо неравенств смысла “≤” имеет неравенства смысла “≥” или строгие равенства. Рассмотрим задачу ЛП, заданную в самом общем виде.
Найти экстремум функции
Алгоритм метода «М».
1. От системы неравенств переходим к системе уравнений, вводя дополнительные неотрицательные переменные:
2. В ограничения, в которые дополнительные неотрицательные переменные вошли со знаком минус или вообще не вошли, вводятся так называемые искусственные переменные: 
3. В линейную форму (1.26) вводится сумма искусственных переменных 
с коэффициентом M>0. Для того, чтобы искусственные переменные не содержались в оптимальном плане исходной задачи, коэффициенту М придается произвольно большое значение по сравнению с коэффициентами 
линейной формы (1.26). В этом случае при максимизации функции цели (1.26), берем (-М), при минимизации (+М).
4. Строим расширенную М – задачу ЛП:
найти экстремум линейной формы
при следующих ограничениях:
Найдем первоначальный опорный план М – задачи.
Так как дополнительные неотрицательные переменные 
и искусственные переменные 
входят в ограничения с положительными единичными коэффициентами, которые составляют систему линейно-независимых векторов как столбцы единичной матрицы, то упомянутые переменные будут являться базисными, а все остальные – свободными, т.е.
Тогда первоначальный опорный план будет иметь вид:
6. Для отыскания оптимального плана расширенной М – задачи составляют симплекс-таблицу, которая на одну строку больше, чем обычная. В эту (m+2) индексную строку записываются соответствующий коэффициенты при М, входящими в целевую функцию с противоположным знаком.
Проверяется признак оптимальности по (m+2)-й строке и определяется переменная, подлежащая включению в базис. Симплекс-процедуру по (m+2) индексной строке проводят до тех пор, пока по этой строке не будет выполнен признак оптимальности. Затем процесс отыскания оптимального плана продолжают по (m+1) индексной строке.
7. Анализируем оптимальный план М – задачи. Если в этом плане все искусственные переменные равны нулю, т.е. 
то план X(x 1 , x 2 , …, x n) является оптимальным планом исходной задачи. Если же в оптимальном плане М – задачи хотя бы одна искусственная переменная не равна нулю, т.е. 
то исходная задача решения не имеет.
Если в процессе решения М – задачи устанавливаем ее не разрешимость, то неразрешима и исходная задача.
Решение контрольного примера.
Найти минимум функции
при следующих ограничениях:
1. От системы неравенств переходим к системе уравнений, вводя в 1-е и во 2-е ограничения дополнительные неотрицательные переменные x 4 и x 5 . Третье уравнение переписываем без изменения:
 |
2. Во 2-е и 3-е уравнения вводим искусственные переменные y 1 и y 2:
3. В линейную форму L(X) вводим сумму y 1 +y 2 с множителем М. Так как задача поставлена на минимум, то множитель М берем со знаком «+».
4. Строим М – задачу. Найти минимум линейной формы
при следующих ограничениях:
5. Решаем эту задачу симплекс-методом. Так как x 4 , y 1 , y 2 являются базисными переменными, то выражаем их через свободные и подставляем в функцию L(X):
6. Строим симплекс-таблицу, которая имеет две индексные строки: в первую, как обычно, записываются коэффициенты Cj, взятые с противоположным знаком, а во вторую – соответствующие коэффициенты при множителе М (тоже с обратным знаком, кроме свободного члена).
Проверяем признак оптимальности по (m+2) индексной строке. Так как задача на минимум, то признак не выполнен, поскольку в столбце x 2 находится положительный элемент 4. Отмечаем этот ключевой столбец стрелкой и , как обычно, выбираем ключевую строку. При выборе ключевой строки получили два одинаковых наименьших значения θ. Чтобы избежать зацикливания, применяем правило Креко. Строки x 1 и y 1 делим на соответствующие элементы ключевого столбца 2 и 4. Результаты от деления читаем слева направо, и ту строку, где первым встретится меньшее число, выбираем за ключевую, т.е.
Отмечаем строку y 1 стрелкой и находим генеральный элемент 4. Затем выполняем обычную симплекс-процедуру и получаем вторую таблицу (таблица 1.2.), в которой опять анализируем (m+2)-ю индексную строку и выбираем столбец x 3 за ключевой.
В результате построения третьей таблицы (таблица 1.2.) получаем оптимальный план расширенной задачи 
так как по обеим индексным строкам признак оптимальности выполнен.
Вследствие того, что все искусственные переменные выведены из базиса, оптимальным планом исходной задачи является план 
и 
Для рассматриваемой задачи можно построить второе оптимальное решение 
с тем же самым значением L min =24 (таблица 1.2.). Следовательно, задача имеет множество оптимальных планов 
где 
Таблица 1.2.
| № таблиц | Базисные переменные | Свободные члены | X 1 | X 2 | X 3 | X 4 | X 5 | å | Q |
| X 4 | -4 | ||||||||
| Y 1 | -1 | -2 | -1 | ||||||
| Y 2 | - | ||||||||
| L(X) | -1 | -2 | -2 | -5 | Min | ||||
| 4 | -1 | - | |||||||
| X 4 | 7/2 | -3 | 1/2 | - | |||||
| X 2 | -1/4 | -1/4 | -1/4 | - | |||||
| Y 2 | |||||||||
| L(X) | -3/2 | -3 | -1/2 | Min | |||||
| 2 | |||||||||
| X 3 | 1/2 | 15/2 | |||||||
| X 2 | -1/4 | 27/4 | - | ||||||
| X 4 | 1/2 | 49/2 | 18/5 | ||||||
| L(X) | -1/2 | 47/2 | Min | ||||||
| X 3 | 21/5 | -1/10 | -1/20 | 101/20 | |||||
| X 2 | -1/4 | 27/4 | |||||||
| X 4 | 18/5 | 1/5 | -1/10 | 49/10 | |||||
| L(X) | -1/2 | 47/2 | min |
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 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. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
| 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
Найти максимум 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 находится в базисе. В этом случае исходная задача не имеет решения по причине несовместности системы ограничений.
