Задача линейного программирования. Проверка оптимальности текущего плана, страница 2

Так как  b1A1 + b2A2 + … + bmAm = B , то по определению опорного решения X0 = (b1, b2, …, bm, 0, …, 0)  является опорным решением данной задачи. Это решение определяется системой единичных базисных векторов A1, A2, …, Am , которые образуют базис m-мерного пространства. Поэтому каждый из векторов A1, A2, …, An , а также вектор В могут быть представлены в виде линейной комбинации векторов данного базиса. Таким образом, базисные переменные x1, x2, …, xm приравниваем к b1, b2, …, bm соответственно, то есть

x1 = b1 , x2 = b2 ,   …, xm = bm . Переменные  xm+1, …, xn  приравниваем к нулю.

Получаем первоначальный план (или допустимое базисное решение):

X0 = (x1 = b1; x2 = b2; …; xm = bm; xm+1 = 0; …; xn = 0).

1.2.2. Составление симплексной таблицы. Симплексная таблица имеет следующий вид:

Б

Сб

В

с1

с2

сm

cm+1

cn

A1

A2

Am

Am+1

An

1

A1

c1

b1

1

0

0

a1 m+1

a1 n

2

A2

c2

b2

0

1

0

a2 m+1

a2 n

m

Am

cm

bm

0

0

1

am m+1

am n

m+1

Z

1

2

m

m+1

n

В столбце Б перечислены базисные столбцы матрицы А, так что в столбце Ai единица стоит на i-ом месте. В столбце Сб записаны коэффициенты целевой функции, номера которых совпадают с номерами базисных столбцов этой строки.

Z(X) = c1x1 + c2x2 + … + cmxm + cm+1xm+1 + … + cnxn .В столбце В записаны свободные

члены bj, j=1,2,…, m. Сверху над столбцами А1, А2, …,   Аn записаны коэффициенты

целевой функции с1, с2, …, сn. В столбцах А1, А2, …, Аn записаны столбцы матрицы А.

В строке m+1 записаны текущие значения Z целевой функции, а также оценки  ∆1, ∆2, …,

n  столбцов А1, А2, …, Аn. Эти числа находятся по следующим формулам:

Z = c1b1 + c2b2 + … + cmbm = Cб ∙В ,                                                 (7)

где Сб=(с12,…,сm), B=(b1,b2,…,bm).∆j. =Сб. Aj – cj =(c1, c2, …, cm)∙(а1j, а2j, …, аmj) – cj = c1а1j + c2а2j + … + cmаmj - cj .

Для базисных столбцов  A1, A2, …, Am  оценки равны  ∆j = 0 .

Решение, соответствующее этой таблице,X0 = (x1= b1 , x2 = b2 , …, xm = bm , xm+1 = 0, …, xn= 0).

1.2.3. Проверка оптимальности текущего плана. Оптимальность текущего плана Х0 можно проверить по значениям∆m+1 , ∆m+2 , …, ∆n:

°1) В задаче на минимум, если  ∆j ≤ 0  при всех  j = m+1, m+2, …, n, то текущий план Х0 оптимален: Х0 = Х*, и тогда  min Z(Х) = Z – это число из симплексной таблицы (оно стоит внизу под столбцом В). Если же хотя бы одна оценка  ∆j > 0 , то текущий план Х0 не оптимален, его можно улучшить, то есть перейти к другому текущему плану Х1, для которого значение Z(Х) окажется меньшим.

Пример 2. Z(X) = x1 + x2 + x3 → min,

x1 + 0x2 + 0x3 - x4 – х5 = 1,

0x1 + x2 + 0x3 - 2x4 – 2х5 = 1,

0x1 + 0x2 + x3 - 3x4 – 3х5 = 2,

xi ≥ 0 ,  i = 1, 2, 3, 4, 5.

Решение. 1) Составим симплексную таблицу.