Симплексный метод

В рассматриваемом многоугольнике ОАВС в любой вершине две из пяти переменных (х, у, и, v, w ) равны нулю, а остальные три больше нуля.
В общей задаче, содержащей п переменных и т ограничений в виде неравенств, требуется т свободных переменных и решение, максимизирующее принятый критерий оптимальности, из общего числа т -\- п переменных, включая свободные, содержит точно т ненулевых значений.

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

Алгоритм можно разбить на четыре шага.
1.Очевидным допустимым решением системы
40x + 25y + u = 1000
35 x + 28 y + v = 980 (1)
25 x + 35 y + w =875
является следующий набор значений переменных:
х = у = 0, и = 1000, v = 980 и w = 875.

Это решение можно изменить, увеличив либо х, либо у.
Из целевой функции Z = 1,20 х + 1,40 у видно, что скорость возрастания Z при увеличении х равна 1,2 и 1,4 при увеличении у.
Поэтому целесообразно увеличить у.
2. Увеличение у приведет к уменьшению и, v и w, так что у можно увеличивать лишь до тех пор, пока одна из переменных и, v или w не станет равной нулю.

Из системы уравнений
40x + 25y + u = 1000
35 x + 28 y + v = 980 (1)
25 x + 35 y + w =875
ясно, что в первом уравнении и = 0, когда у = 40,
во втором — что v = 0 при у = 35 и в третьем —
что w = 0 при у = 25.

Таким образом, у можно увеличить только до 25, что даст
и = 375, v = 280 и w = 0. Эти расчеты выполнить очень просто в силу следующих причин:
а) Z не содержит ненулевых переменных и, v и w:
б) каждое из уравнений системы содержит в точности одну ненулевую переменную и, v или w, и коэффициенты при каждой из них равны единице.

Изменим теперь Z и уравнения (1) так, чтобы выполнялись условия а) и б) для новых значений ненулевых переменных у, и и v.
Третье уравнение системы (1) является единственным, содержащим переменную w, ставшую равной нулю. Разделив это уравнение на 35, т. е. на коэффициент при новой ненулевой переменной у получаем:
5/7X +Y+ W/35 =25 (2)

Вычтем далее умноженное на соответствующие множители (25 и 28) уравнение (2) из остальных уравнений системы (1 ), чтобы исключить из них у. Имеем:
155/7X + U + 5/7 W = 375 (3)
15X + V - 4/5 W = 280 (4)
Но из (2) получаем 5/7 х + у + (W 35) — 25 = 0.
Следовательно, если вычесть кратные этому выражению величины из Z, то Z не изменится.
Если же вычесть из Z это выражение, предварительно умножив его на 1,4, то тем самым будет исключена переменная у.

Следовательно, Z = 0,2х — 0,04W + 35.
Очевидно, что из двух нулевых переменных х и w только х может увеличивать значение Z при увеличении от нуля.
Чтобы определить, насколько можно увеличить х, разделим коэффициенты при х в (2), (3) и (4) на постоянные, стоящие в правой части.
Получаем 35, 16• 29/31 и 18•2/3.
Увеличение значения х до 16• 29/31 приведет к уменьшению u до нуля при y = 12•28/31 и V= 25•30/31.

Разделив (2) на коэффициент при х и перенеся постоянную в левую часть, получим:
X + 7/155 U + W /31 - 16• 29/31 = 0 (5)
Если вычесть (5), обе части которого умножены на 0,2 из
Z = 0,2х — 0,04W + 35,
то получим
Z = - 1,4/155 U - 26/755W +38• 12/31

Отсюда можно сделать вывод, что увеличение любой переменной U или W приведет только к уменьшению Z.
Следовательно, максимальное значение Z найдено и равно
38•12/31

Решение оптимизационной задачи в табличной форме
Составим таблицу (табл. 1), в которой строки, обозначенные Р3, P4 и Р5, соответствуют первому набору значений ненулевых переменных и, v и w. Столбцы, обозначенные P1 , P2 , P3 P4, и P5 , соответствуют переменным х, у, и, v и w. Добавим еще один столбец P0 соответствующий постоянным (правым частям) уравнений, и строку Δ, в которой проставлены коэффициенты функции Z.

Таблица полностью определяет уравнения
Z = 1,20 х + 1,40 у и
40x + 25y + u = 1000
35 x + 28 y + v = 980 (1)
25 x + 35 y + w =875
Пустые клетки таблицы соответствуют нулям.
Используя таблицу 1, можно вновь применить алгоритм из четырех шагов, соответствующих только что выполненным вычислениям.

1. Выбрать столбец с наибольшим положительным элементом в строке А. В данном случае это столбец P2 с элементом 1,4.
2. Разделить положительные элементы в выбранном на шаге 1
столбце на соответствующие элементы столбца Ро и выбрать наименьший результат. В этом примере выбран столбец P2 Результаты деления по строкам следующие: для Р3 — 1000/25 = 40, для Р4 —980/28 = 35 и для Р5 — 875/35 = 25. Поэтому выбирается строка Р5

Разделить строку, выбранную на шаге 2, на наибольший элемент столбца, выбранного на шаге 1, и обозначить результат символом этого столбца. В этом примере элементы строки Р5 делятся на 35
и результат получает обозначение P2.
Это дает:

4. Исключить элементы всех строк (включая строку Δ)
кроме строки, измененной на шаге 3, вычитая умноженную на соответствующие множители строку, полученную на шаге 3, которой приписано новое обозначение. Если все элементы получающейся в итоге строки А отрицательны или равны нулю, то оптимальное решение найдено. В противном случае нужно вернуться к шагу 1.

В рассматриваемом примере строка Р2 умножается на 25 и результат вычитается из строки Р3. Аналогичную операцию мы производим над строками Р4 (предварительно умножая Р2 на 28) и Δ(предварительно умножая Р2 на 1,4). В результате получается табл. 3

Константа, получаемая при исключении переменной из строки Δ на последующих шагах, не нужна, и поэтому ее обычно опускают.
Поскольку в строке Δ еще имеется положительный элемент, необходимо вернуться к шагу 1 и повторить все шаги алгоритма. В результате получаем табл. 4