Необходимо решить задачу линейного программирования.

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

2x 1 +5x 2 +3x 3 +8x 4 →min

Ограничивающие условия:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Приведем систему ограничений к каноническому виду, для этого необходимо перейти от неравенств к равенствам, с добавлением дополнительных переменных.

Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак "≤" на "=". Т. к. второе и третье неравенства имеют знаки "≥" необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получем эквивалентную задачу:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

					Своб член
F
X5
X6
X7

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -6, он задает ведущую строку - X6. В этой строке так же находим максимальный по модулю отрицательный элемент: -10 он находится в столбце X3 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

	X1	X2	X6	X4	Своб член
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -0.4, он задает ведущую строку - X7. В этой строке так же находим максимальный по модулю отрицательный элемент: -8.3 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

	X1	X7	X6	X4	Своб член
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

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

	X2	X7	X6	X4	Своб член
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x 3 =0.539, x 1 =0.153. Переменные x 2 и x 4 не входят в базис, поэтому x 2 =0 x 4 =0.

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:

Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод . Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод , т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

симплекс-метод итерация 0

							Отношение

Для улучшения решения перейдем к следующей итерации симплекс-метода , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x 2 (коэффициент -6).

Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x 2 заменит в базисе s 1 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка (-4 -6 0 0 0 0) -(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

симплекс-метод итерация 1

							Отношение

Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

симплекс-метод итерация 2

							Отношение

Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.

симплекс-метод итерация 3

							Отношение

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

Назначение сервиса . Онлайн-калькулятор используется для решения задач линейного программирования P-методом в следующих формах записи: базовой форме записи симплекс-метода, в виде симплексной таблицы, модифицированным симплекс-методом.

Инструкция для решения задач двойственным симплекс-методом . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения двойственным симплекс-методом).

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

При этом ограничения типа x i ≥ 0 не учитывайте.

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x i имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

1. Составление псевдоплана . Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
2. Проверка плана на оптимальность . Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом .
3. Выбор ведущих строки и столбца . Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
4. Расчет нового опорного плана . Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса . Далее переход к этапу 2.

Более подробный алгоритм двойственного симплекс-метода . Особенности двойственного симплекс-метода Используются при решении методом Гомори .

Пример . Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание : Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x 1 + 2x 2 + x 3 при следующих условиях-ограничений.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x 4 . Во втором неравенстве смысла (≤) вводим базисную переменную x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-1 -1 0 1 0 2 1 -1 0 1

Решим систему уравнений относительно базисных переменных:
x 4 , x 5 ,
Полагая, что свободные переменные равны нулю, получим первый опорный план:
X1 = (0,0,0,-10,8)

Базис	B	x 1	x 2	x 3	x 4	x 5
x 4	-10	-1	-1	0	1	0
x 5	8	2	1	-1	0	1
F(X0)	0	-4	-2	-1	0	0

Итерация №1

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.


Ведущей будет первая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5
x 4	-10	-1	-1	0	1	0
x 5	8	2	1	-1	0	1
F(X0)	0	-4	-2	-1	0	0
θ	0	-4: (-1) = 4	-2: (-1) = 2	-	-	-

4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса .

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 5	-2	1	0	-1	1	1
F(X0)	20	-2	0	-1	-2	0

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
-10: -1	-1: -1	-1: -1	0: -1	1: -1	0: -1
8-(-10 1):-1	2-(-1 1):-1	1-(-1 1):-1	-1-(0 1):-1	0-(1 1):-1	1-(0 1):-1
0-(-10 -2):-1	-4-(-1 -2):-1	-2-(-1 -2):-1	-1-(0 -2):-1	0-(1 -2):-1	0-(0 -2):-1

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x 5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x 3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 5	-2	1	0	-1	1	1
F(X0)	20	-2	0	-1	-2	0
θ	0	-	-	-1: (-1) = 1	-	-

4. Пересчет симплекс-таблицы. Выполняем преобразования.

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 3	2	-1	0	1	-1	-1
F(X1)	22	-3	0	0	-3	-1

Или более подробно:

B	x 1	x 2	x 3	x 4	x 5
10-(-2 0):-1	1-(1 0):-1	1-(0 0):-1	0-(-1 0):-1	-1-(1 0):-1	0-(1 0):-1
-2: -1	1: -1	0: -1	-1: -1	1: -1	1: -1
20-(-2 -1):-1	-2-(1 -1):-1	0-(0 -1):-1	-1-(-1 -1):-1	-2-(1 -1):-1	0-(1 -1):-1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 3	2	-1	0	1	-1	-1
F(X1)	22	-3	0	0	-3	-1

Оптимальный план можно записать так: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22

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

Для решения ЗЛП симплекс-методом ее приводят к каноническому виду, т.е. из ограничений – неравенств надо сделать ограничения – равенства. Для этого в каждое ограничение вводится дополнительная неотрицательная балансовая переменная со знаком «+», если знак неравенства «£», и со знаком «–», ели знак неравенства «³».

В целевой функции эти дополнительные переменные входят с нулевыми коэффициентами, т.е. запись целевой функции не изменится. Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных: .

Если ограничения задачи отображают наличие и расход ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в канонической форме, равно объему неиспользованного ресурса.

Для решения задачи симплекс-методом будем использовать укороченные симплексные таблицы системы линейных уравнений и метод модифицированного жорданова исключения .

1. Составляем первый опорный план

Задача остается прежней. Приведем стандартную форму системы неравенств (1) в каноническую форму системы уравнений путем введения дополнительных балансовых переменных x 3 , x 4 , x 5 , x 6 .

или

В экономическом смысле значения дополнительных переменных x 3 , x 4 , x 5 определяют остатки сырья после реализации продукции.

Матрица полученной системы уравнений имеет вид:

Видно, что в матрице A базисным минором 4-го порядка является определитель, составленный из единичных коэффициентов при дополнительных переменных x 3 , x 4 , x 5 , x 6 , так как он отличен от нуля и равен 1. Это означает, что векторы-столбцы при этих переменных является линейно независимыми, т.е. образуют базис , а соответствующие им переменные x 3 , x 4 , x 5 , x 6 являются базисными (основными). Переменные x 1 , x 2 будут называться свободными (неосновными).

Если свободным переменным x 1 и x 2 задавать различные значения, то, решая систему относительно базисных переменных, получим бесконечное множество частных решений. Если свободным переменным задавать только нулевые значения, то из бесконечного множества частных решений выделяют базисные решения – опорные планы.

Чтобы выяснить, могут ли переменные быть базисными, необходимо вычислить определитель, состоящий из коэффициентов при этих переменных. Если данный определитель не равен нулю, то эти переменные могут быть базисными.

Количество базисных решений и соответствующее ему число групп базисных переменных может быть не более, чем , где n –общее число переменных, r – число базисных переменных, r ≤ m ≤ n .

Для нашей задачи r = 4; n = 6. Тогда , т.е. возможны 15 групп из 4-х базисных переменных (или 15 базисных решений).

Разрешим систему уравнений относительно базисных переменных x 3 , x 4 , x 5 , x 6:

Полагая, что свободные переменные x 1 = 0, x 2 = 0, получим значения базисных переменных: x 3 = 312; x 4 = 15; x 5 = 24; x 6 = –10, т.е. базисное решение будет = (0; 0; 312; 15; 24; –10).

Данное базисное решение является недопустимым , т.к. x 6 = –10 ≤ 0, а по условию ограничений x 6 ≥ 0. Поэтому вместо переменной x 6 в качестве базисной надо взять другую переменную из числа свободных x 1 или x 2 .

Дальнейшее решение будем выполнять, используя укороченные симплексные таблицы, заполнив строки первой таблицы коэффициентами системы следующим образом (табл. 1):

Таблица 1

F –строка называется индексной . Она заполняется коэффициентами целевой функции, взятыми с противоположными знаками, так как уравнение функции можно представить в виде F = 0 – (– 4x 1 – 3x 2).

В столбце свободных членов b i есть отрицательный элемент b 4 = –10, т.е. решение системы является недопустимым. Чтобы получить допустимое решение (опорный план), элемент b 4 надо сделать неотрицательным.

Выбираем x 6 -строку с отрицательным свободным членом. В этой строке есть отрицательные элементы. Выбираем любой из них, например, «–1» в x 1 -столбце, и x 1 -столбец принимаем в качестве разрешающего столбца (он определит, что переменная x 1 перейдет из свободных в базисные).

Делим свободные члены b i на соответствующие элементы a is разрешающего столбца, получаем оценочные отношения Θ i = = {24, 15, 12, 10}. Из них выбираем наименьшее положительное (minΘ i =10), которое будет соответствовать разрешающей строке . Разрешающая строка определяет переменную x j , которая на следующем шаге выступает из базиса и станет свободной. Поэтому x 6 -строка является разрешающей строкой, а элемент «–1» – разрешающим элементом . Обводим его кружком. Переменные x 1 и x 6 меняются местами.

Оценочные отношения Θ i в каждой строке определяются по правилам:

1) Θ i = , если b i и a is имеют разные знаки;

2) Θ i = ∞, если b i = 0 и a is < 0;

3) Θ i = ∞, если a is = 0;

4) Θ i = 0, если b i = 0 и a is > 0;

5) Θ i = , если b i и a is имеют одинаковые знаки.

Совершаем шаг модифицированного жорданова исключения (ШМЖИ) с разрешающим элементом и составляем новую таблицу (табл. 2) по следующему правилу:

1) на месте разрешающего элемента (РЭ) устанавливается величина, ему обратная, т.е. ;

2) элементы разрешающей строки делятся на РЭ;

3) элементы разрешающего столбца делятся на РЭ и знак меняется;

4) остальные элементы находятся по правилу прямоугольника:

Из табл. 2 видно, что свободные члены в b i -столбце являются неотрицательными, следовательно, получено первоначальное допустимое решение – первый опорный план = (10; 0; 182; 5; 4; 0). При этом значение функции F () = 40. Геометрически это соответствует вершине F (10; 0) многоугольника решений (рис. 1).

Таблица 2

2. Проверяем план на оптимальность. Опорный план не оптимальный, так как в F -строке имеется отрицательный коэффициент «–4». Улучшаем план.

3. Нахождение нового опорного плана

Выбираем разрешающий элемент по правилу:

Выбираем наименьший отрицательный коэффициент в F -строке «–4», который и определяет разрешающий столбец – x 6 ; переменную x 6 переводим в базисные;

Находим отношения Θ i , среди них выбираем наименьшее положительное, которое соответствует разрешающей строке:

min Θ i = min {14, 5, 2, ∞} = 2, следовательно, x 5 -строка – разрешающая, переменную x 5 переводим в свободные (переменные x 5 и x 6 меняются местами).

На пересечении разрешающих строки и столбца стоит разрешающий элемент «2»;

Выполняем шаг ШМЖИ, строим табл. 3 по вышеприведенному правилу и получаем новый опорный план = (12; 0; 156; 3; 0; 2).

Таблица 3

4. Проверка нового опорного плана на оптимальность

Опорный план также не является оптимальным, так как в F -строке имеется отрицательный коэффициент «–1». Значение функции F () = 48, что геометрически соответствует вершине E (12; 0) многоугольника решений (рис. 1). Улучшаем план.

5. Нахождение нового опорного плана

x 2 -столбец – разрешающий, так как в F -строке наименьший отрицательный коэффициент «–1» находится в x 2 -столбце (Δ 2 = –1). Находим наименьшее Θ i : min Θ i = min {≈ 9, 6, ∞, 24} = 6, следовательно, x 4 -строка – разрешающая. Разрешающий элемент «1/2». Меняем местами переменные x 2 и x 4 . Выполняем шаг ШМЖИ, строим табл. 4, получаем новый опорный план = (9; 6; 51; 0; 0; 5).

6. Проверка опорного плана на оптимальность

В F -строке все коэффициенты неотрицательны, следовательно, опорный план является оптимальным. Геометрически соответствует точке D (9;6) (см. рис. 1). Оптимальный план дает максимальное значение целевой функции у.е.

11.4. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

Из результатов предыдущих пунктов следует, что для получения решения исходной задачи можно перейти к двойственной и, используя оценки ее оптимального плана, определить оптимальное решение исходной задачи.

Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках –двойственная.

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

Рассматривая это условие с учетом двойственности, можно записать

.

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

Это позволило разработать новый метод решения задач линейного программирования, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное» решение (в обычном симплекс-методе сначала находится допустимое , но неоптимальное решение). Новый метод, получивший название двойственного симплекс-метода , обеспечивает выполнение условия оптимальности решения и систематическое «приближение» его к области допустимых решений. Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

Двойственный симплекс-метод позволяет решать задачи линейного программирования, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размера симплексной таблицы. Рассмотрим применение двойственного симплекс-метода на примере.

Пример . Найти минимум функции

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

.

Перейдем к канонической форме:

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

Начальная симплекс-таблица имеет вид

Базисные переменные	x 1	x 2	x 3	x 4	x 5	Решение
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Начальное базисное решение оптимальное, но не допустимое.

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

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

Условие оптимальности . Включаемая в базис переменная выбирается из числа небазисных переменных следующим образом. Вычисляются отношения коэффициентов левой части -уравнения к соответствующим коэффициентам уравнения, ассоциированного с исключаемой переменной. Отношения с положительным или нулевым значением знаменателя не учитываются. В задаче минимизации вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задаче максимизации – отношение, наименьшее по абсолютной величине (при наличии альтернатив выбор делается произвольно). Если знаменатели всех отношений равны нулю или положительные, задача не имеет допустимых решений.

После выбора включаемой в базис и исключаемой переменных для получения следующего решения осуществляется обычная операция преобразования строк симплекс-таблицы.

В рассматриваемом примере исключаемой переменной является . Отношения, вычисленные для определения новой базисной переменной, приведены в следующей таблице:

Переменные	x 1	x 2	x 3	x 4	x 5
Уравнение x 4 -уравнение	–2 –4	–1 –3
Отношение

В качестве включаемой переменной выбирается x 2 . Последующее преобразование строк приводит к новой симплекс-таблице:

Базисные переменные	x 1	x 2	x 3	x 4	x 5	Решение
x 3 x 2 x 5						–1 –1

Новое решение также оптимальное, но все еще недопустимое. В качестве новой исключаемой переменной выберем (произвольно) x 3 . Определим включаемую переменную.

Переменные	x 1	x 2	x 3	x 4	x 5
Уравнение x 4 -уравнение
отношение