Решение задачи линейного программирования табличным симплексным методом

 

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

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

Данный переход возможен, если известен какой-нибудь исходный опорный план.

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

Пусть исходная задача приведена к каноническому виду (3.6):

F = c₁x₁ + c₂x₂ + ……+ c_nx_n ® max (3.12)

……………………………………… . (3.13)

Здесь a_ij, b_i, c_i ( ) - заданные постоянные числа (m<n, b_i ³ 0). Говорят, что система уравнений, записанная в форме (3.13), имеет предпочтительный вид.

Векторная форма данной задачи имеет следующий вид:

(3.14)

(3.15)

где ; .

Так как , то по определению опорного плана является опорным планом данной задачи.

Этот план определяется системой единичных векторов Р_n+1,Р_n+2,….. Р_n+m, которые образуют базис m- мерного пространства.

 

Алгоритм табличного симплексного метода

I. Построение начального опорного плана:

1) Приведение задачи к каноническому виду.

2) Приведение системы ограничений к предпочтительному виду (3.13).

3) Построение первой симплекс- таблицы:

а) в столбце «Базис» записываются базисные переменные Х_n+1,…, Х_n+m (если некоторые или все переменные Х_n+1,…, Х_n+m, не входят в целевую функцию, то их коэффициенты равны нулю);

б) в столбце С_б записываются коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и переменные данного базиса;

в) в столбце Р_о записываются свободные члены b₁, b₂,…, b_m системы ограничений в предпочтительном виде;

г) на пересечении последних (n+m) столбцов и первых m строк расположена матрица коэффициентов системы ограничений;

д) в индексной строке (m+1^я строка) располагают коэффициенты и , рассчитанные как скалярные произведения соответствующих векторов: .

4) Проверка условия оптимальности:

а) все , - данный опорный план является оптимальным;

б) для некоторого j , и все соответствующие этому индексу величины а_ij£0, , - функция неограниченная сверху:

в) для некоторого j, и для каждого такого j по крайней мере одно из чисел а_ij>0, тогда можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции увеличится.

II. Переход к лучшему опорному плану (см. таблицу).

1) Выбор разрешающего столбца:

для всех выбирается , для выбранного в базис вводят соответствующую переменную X_k.

2) Выбор разрешающей строки:

Для разрешающего столбца определяют (a_ik > 0): выбранная строка с индексом r определяет переменную х_r , которую необходимо вывести из базиса.

3) Выбор разрешающего элемента: это элемент, стоящий на пересечении строки с индексом r и столбца с индексом k: а_rk.

4) Симплексные преобразования и построение второй симплекс-таблицы:

а) столбец «Базис»: переменная X_r заменяется на X_k, остальные переменные не меняются;

б) С_б заполняется соответствующими коэффициентами при базисных переменных в целевой функции;

в) элементы разрешающей строки делятся на разрешающий элемент и записываются в соответствующей по номеру строке новой таблицы;

г) элементы разрешающего столбца равны нулю, за исключением элемента, соответствующего месту разрешающего элемента. Он равен 1.

д) все остальные элементы новой таблицы рассчитываются по формулам:

, при i≠r (3.16)

где , b_i^’- элементы новой симплекс-таблицы, a_ij, b_i - элементы предыдущей симплекс-таблицы, a_rk - разрешающий элемент, a_ik - элемент разрешающего столбца, b_r, a_rj - элементы разрешающей строки.

5) Проверка условий оптимальности (I.4) и либо переход к (II), либо конец.

 

i

Базис

Сб

Ро

С1

С2

…

Сr

…

Сk

…

Сn

Сn+1

Сn+2

…

Сn+m

X1

X2

…

Xr

…

Xk

…

Xn

Xn+1

Xn+2

…

Xn+m

1

Xn+1

Cn+1

b1

a11

a12

.

a1r

.

a1k

.

a1n

1

0

.

0

2

Xn+2

Cn+2

b2

a12

a22

.

a2r

.

a2k

.

a2n

0

1

.

0

.

….

….

…

…

…

.

…

.

…

.

…

…

…

.

…

r

Xn+r

Cn+r

br

ar1

ar2

.

arr

.

ark

.

arn

…

…

.

….

.

….

….

…

…

…

.

…

.

…

.

…

…

…

.

…

m

Xn+m

Cn+m

bm

am1

am2

.

amr

.

amk

.

amn

0

0

.

1

m+1

Do

D1

D2

.

Dr

.

Dk

.

Dn

0

0

.

0

Примечание. Для каждой симплексной таблицы можно записать текущий опорный план по следующему правилу: значение базисных переменных записаны в соответствующих ячейках столбца Р_о, а небазисные переменные равны нулю. Кроме того, в ячейке записано текущее значение целевой функции при текущем опорном плане задачи. В последней таблице (для которой ), в указанных ячейках будет записан оптимальный план и максимальное значение целевой функции F_max(X^*).