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

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

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

Таблица 3.1

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

Базисные переменные

Свободные члены

x 1

x 2

xi

xr

xr+ 1

xj

xn

x 1

b1

a 1 r+ 1

a 1 j

a 1 n

x 2

b2

a 2 r+ 1

a 2 j

a 2 n

xi

bi

ai, r+ 1

ai j

ai n

xr

bn

ar, r+ 1

a r j

a r n

c 0

–

–

c r+ 1

cj

cn

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

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

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

+ с _{r+ 1} x _{r+ 1} +…+ c _j x _j +…+ c _n x _n = c ₀.

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

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

Таблица 3.2

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

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

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

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

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

a'_qk = a _qk / a _qp, k = 0, 1, …, n.

a’_2k = a _2k / a ₂₅, k = 0, 1, …, 5,

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

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

a'_ik = a _ik – a’_qk a _ip, i = 0, 1, …, r.

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

Таблица 3.3

Таблица с новым базисом х₁, х₂, х₃

Базисные переменные

Свободные члены

x 1

x 2

x 3

x4

x5

x 1

-3

x 5

-2

x 3

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

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

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

 

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

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

 

⇐ Предыдущая123456Следующая ⇒