Решение задач линейного программирования методом искусственного базиса.

Пусть решаем ЗЛП в виде

В этом случае общая схема симплекс-метода претерпевает некоторые изменения. А именно:

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).

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 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. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Решение системы производится путём ввода искусственных переменных 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

Целевая функция:

1X 1 +5X 2 +4X 3 -3X 4 →max

2X 1 +7X 2 +1X 3 +0X 4 ≤5
1X 1 +4X 2 +2X 3 +8X 4 =6
-1X 1 +0X 2 +2X 3 +5X 4 =9

Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак ≥, то при переходе к равенству знаки всех его коэффициентов и свободных членов меняются на противоположные. Тогда система запишется в виде:

2X 1 +7X 2 +1X 3 +0X 4 +X5=5
1X 1 +4X 2 +2X 3 +8X 4 +R1=6
-1X 1 +0X 2 +2X 3 +5X 4 +R2=9
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком

Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.

Из данных задачи составляем исходную симплекс таблицу.

	X1	X2	X3	X4	Своб член
F	-1	-5	-4	3	0
X5	2	7	1	0	5
R1	1	4	2	8	6
R2	-1	0	2	5	9
M	0	-4	-4	-13	-15

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -13 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8.

	X1	X2	X3	Своб член
F	-1.375	-6.5	-4.75	-2.25
X5	2	7	1	5
X4	0.125	0.5	0.25	0.75
R2	-1.625	-2.5	0.75	5.25
M	1.625	2.5	-0.75	-5.25

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0.75 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 0.25.

	X1	X2	X4	Своб член
F	1	3	19	12
X5	1.5	5	-4	2
X3	0.5	2	4	3
R2	-2	-4	-3	3
M	2	4	3	-3

В столбце свободных членов и в строке F нет отрицательных элементов. Выполнение алгоритма на этом завершено, однако не все искусственные переменные (R) были исключены из базиса (условия исходной задачи не совместны).

Метод искусственного базиса (М-задача).

Для многих задач линейного програм­мирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов P j не всегда есть m единичных.

Рассмотрим такую задачу:

Пусть требуется найти максимум функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n (1)

при условиях

……………………………………… (2)

где b i  0 (i =l, m), m <.>n и среди векторов P 1 , P 2 , …, P n нет m единичных.

Определение . Задача, состоящая в определении максимального значения функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n -М x n +1 - …- М x n + m (3)

при условиях

……………………………………… (4)

где M - некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (М-задачей) по отношению к задаче (1) - (2).

Расширенная задача имеет опорный план

Х=(0; 0; ...; 0; b 1 ; b 2 ; ...;b m).

определяемых системой единичных векторов P n +1 ; Р п+2 , … Р п+т , образующих базис m-ro векторного пространства, который назы­вается искусственным. Сами векторы, так же как и переменные x n + i (i =l, m ), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема Если в оптимальном плане X*=(x* 1 , x * 2 , ...; x * n , x * n +1 ; ...; x * n + m) расширенной задачи (3) - (4) значения ис­кусственных переменных x * n + i =0 (i =1, m ), то X*=(x* 1 , x * 2 , ...; x * n) является оптимальным планом задачи (1) - (2).

Таким образом, если в найденном оптимальном плане расши­ренной задачи, значения искусственных переменных равны ну­лю, то тем самым получен оптимальный план исходной задачи.

Значения индексной строки ∆ 0 , ∆ 1 , …, ∆ n состоят из двух частей, одна из кото­рых зависит от M, а другая - нет. Заполняют симплекс - таблицу, которая содер­жит на одну строку больше, чем обычная симплексная табли­ца. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю – слагаемые, не содержащие M. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусствен­ный вектор, исключенный из базиса, в следующую симплекс-таблицу не записывают. Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс по (m+2) -и строке ведут до тех пор, пока:

либо все искусственные векторы не будут исключены из базиса;

либо не все искусственные векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в индексах ∆ 1 , …, ∆ n .

В первом случае базис отвечает некоторому опорному пла­ну исходной задачи и определение ее оптимального плана про­должают по (m+1)-й строке.

Во втором случае, если значение ∆ 0 отрицательное, исходная задача не имеет решения; если же ∆ 0 =0, то найденный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.

Этапы нахождения решения задачи (1) - (2)

методом искусственного базиса:

Составляют расширенную задачу (3) - (4).

Находят опорный план расширенной задачи.

С помощью обычных вычислений симплекс-метода исклю­чают искусственные переменные из базиса. В результате либо на­ходят опорный план исходной задачи (1) - (2), либо уста­навливают ее неразрешимость.

Используя найденный опорный план задачи (1) - (2), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

Пример.

Найти минимум функции F = - 2x 1 + 3x 2 - 6x 3 - x 4

при ограничениях:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 ≤22

x 1 -x 2 +2x 3 ≥10

x i ≥0, i =1,4

Решение.

Запишем данную задачу в форме основной задачи: найти максимум функции F = 2x 1 - 3x 2 + 6x 3 + x 4

при ограничениях:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6= 10

x i ≥0, i =1, 6

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

Среди векторов P 1 , Р 2 , … P 6 только два единичных (P 4 и P 5). Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную х 7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F = 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7

при ограничениях:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6 +x 7= 10

Расширенная задача имеет опорный план Х=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P 4 , P 5 , Р 7 .

Понятие двойственной (соапряженной) задачи линейного программирования.

Правила построения двойственной задачи.

С каждой задачей линейного программирования (ЗЛП), которая называется двойственной задачей (или сопряженной) по отношению к исходной задаче, которая называется прямой.

Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:

F=c 1 x 1 +c 2 x 2 +…+c n x n  max (3.6)

a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1 ,

a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2 ,

………………………………

a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)

a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,

x j ≥ 0, , l ≤ n (3.8)

Задача, состоящая в нахождении минимального значения функции

L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)

при условиях

a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1

a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2

………………………………

a 1 l y 1 + a 2 l y 2 +…+ a m l y m ≥ c l (3.10)

a l +1,1 y 1 + a l +1,2 y 2 +…+ a l +1,m y m = c l+1

………………………………

a m1 y 1 + a m2 y 2 +…+ a mn y m = c m

y i ≥ 0, , k ≤ m (3.11)

называется двойственной по отношению к задаче (3.6) – (3.8).

Правила построения двойственной задачи приведены в таблице:

Структурные характеристики ЗЛП	Задача линейного программирования
		Двойственная
1. Целевая функция	Максимизация (max)	Минимизация (min)
2. Количество переменных	n переменных	Равно количеству ограничений прямой задачи (3.7), y i , т.е. m
3. Количество ограничений	m ограничений	Равно количеству переменных прямой задачи x j , , т.е n
4. Матрица коэффициентов в системе ограничений
5. Коэффициенты при переменных в целевой функции	c 1 ,c 2, …,c n	b 1 ,b 2, …,b m
6. Правая часть системы ограничений	b 1 ,b 2, …,b m	c 1 ,c 2, …,c n
7. Знаки в системе ограничений	а) x j ≥ 0- условие неотрицательности	j-е ограничение имеет знак «≥»
	б) на переменную x j не наложено условие неотрицательности	j-е ограничение имеет знак «=»
	в) i-е ограничение имеет знак «≤»	переменная y i ≥0
	г) i-е ограничение имеет знак «=»	на переменную y i не наложено условие неотрицательности

Примечание

Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.9) – (3.11) прямой ЗЛП, а задачу (3.6) – (3.8) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.

Если исходная задача решается на max (min), а в системе ограничений) i -е (j -е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:

а) либо домножить обе части i -го (j -го) неравенства на (-1) и поменять знак на «≤» («≥»)

б) либо привести i -е (j -е) ограничение к равенству путем введения дополнительной переменной x n+ i ≥0