С начальным базисом

Симплекс-метод решения задачи ЛП

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

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

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

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

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z	−4	-6					−
s 1							64/1=64
s 2							72/3=24
s 3							20/1=20

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

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

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

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

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z
s 1
s 2
x 2

Остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z -строки таблицы "Итерация 1". На месте −6 в первой строке (z-строке) в столбце х ₂ таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х ₂ таблицы "Итерация 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 ₂ появился ноль 0, цель достигнута. Элементы разрешающего столбца х ₂ выделены красным цветом.

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z	−4
s 1
s 2
x 2

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z	−4
s 1					−1
s 2
x 2

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z	−4
s 1					−1
s 2					−3
x 2

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

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

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

Старая z-строка (−4 −6 0 0 0 0)

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

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

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z	−4						−
s 1					−1		44/2=22
s 2					−3		12/1=12
x 2							−

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

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z					−6		−
s 1				−2			20/5=4
x 1					−3		−
x 2							20/1=20

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

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

БП	x 1	x 2	s 1	s 2	s 3	Решение	Отношение
z			6/5	8/5			−
s 3			1/5	−2/5			−
x 1			3/5	−1/5			−
x 2			−1/5	2/5			−

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