Табличный симплекс-метод

Процесс решения ЗЛП можно представить в виде последовательности заполняемых таблиц. Покажем это на примере.

Пример 3.5. Рассмотрим предыдущий пример 3.4. После выделения базиса заполняется таблица (табл. 3.1), где r – число базисных переменных, х1,…, хr – базисные переменные.

Таблица 3.1

Исходная таблица для симплекс-метод.

Базисные переменные Свободные члены x1 x2 xi xr xr+1 xj xn
x1 b1 a1 r+1 a1 j a1n
x2 b2 a2 r+1 a2 j a2n
xi bi ai, r+1 ai j ai n
xr bn ar, r+1 ar j ar n
c0 c r+1 cj cn

r – число базисных переменных

при минимизации по системе вида

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

+ с r+1 x r+1 +…+ c j x j +…+ c n x n = c0.

Для нашего случая имеем:

Исходная таблица имеет вид (табл. 3.2).

Таблица 3.2

Исходная таблица для симплекс-метода

Базисные переменные Свободные члены x1 x2 x3 x4 x5
x1 -2
x2 -2
x3
-1

1)Выбирают разрешающий p-й столбец из условия: оценка с р >0 и хотя бы один элемент в этом столбце a i p >0 (в нашем случае р = 5).

2)Выбирают q-ю разрешающую строку из условия для aip > 0 (в нашем случае: элемент a­15 = -2 < 0 и поэтому отношение не рассматривается) ; откуда q = 2.

3)Производят перерасчёт элементов q-й (2-й) разрешающей строки по формуле:

a'qk = a qk / a qp , k = 0, 1, …, n.

a’2k = a 2k / a 25, k = 0, 1, …, 5,

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

4)Вычисляют элементы всех остальных строк (при k p) по формуле

a'ik = a ik – a’qk a ip, i = 0, 1, …, r.

Иначе говоря, к каждой из остальных строк прибавляют вновь полученную разрешающую строку, умноженную на такое число, чтобы в клетках столбца для х5 появились нули, и записывают преобразованные строки на месте прежних в новой таблице (табл. 3.3). Базис в новой таблице изменится с х1, х2, х3 на х1, х5, х3. Далее все рассуждения повторяются.



Таблица 3.3

Таблица с новым базисом х1, х2, х3

Базисные переменные Свободные члены x1 x2 x3 x4 x5
x1 -3
x5 -2
x3 1/5 -1 -1/5 1/5
-2 -1

Для таблицы 3.3 разрешающий столбец с переменной х4, т. к. с4 = 1>0,

а34 = 5>0. В качестве разрешающей строки выбирается строка с базисной переменной х3, т. к. а34 = 5>0. Все элементы базисной строки нормируются делением на 5. С помощью вновь полученной базисной строки в разрешающем столбце с х4 формируются нули (см. табл. 3.4).

Таблица 3.4

Итоговая таблица с оптимальным решением

Базисные переменные Свободные члены x1 x2 x3 x4 x5
x1 28/5 7/5 3/5
x2 12/5 3/5 3/5
x4 1/5 -1/5 1/5
-11/5 -4/5 -1/5

Строка с не имеет положительных оценок сj в последней 5-й строке. Следовательно, достигнуто оптимальное решение , которое соответствует .

Для сведения задачи на max к задаче на min надо целевую функцию умножить на (-1), а далее все рассуждения и преобразования остаются прежними. Полученное оптимальное значение опять-таки умножается на (-1), что является max значением целевой функции.


5219036346410095.html
5219098914514869.html
    PR.RU™