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

Так как  b₁A₁ + b₂A₂ + … + b_mA_m = B , то по определению опорного решения X₀ = (b₁, b₂, …, b_m, 0, …, 0)  является опорным решением данной задачи. Это решение определяется системой единичных базисных векторов A₁, A₂, …, A_m , которые образуют базис m-мерного пространства. Поэтому каждый из векторов A₁, A₂, …, A_n , а также вектор В могут быть представлены в виде линейной комбинации векторов данного базиса. Таким образом, базисные переменные x₁, x₂, …, x_m приравниваем к b₁, b₂, …, b_m соответственно, то есть

x₁ = b₁ , x₂ = b₂ ,   …, x_m = b_m . Переменные  x_m+1, …, x_n  приравниваем к нулю.

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

X₀ = (x₁ = b₁; x₂ = b₂; …; x_m = b_m; x_m+1 = 0; …; x_n = 0).

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

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

Z(X) = c₁x₁ + c₂x₂ + … + c_mx_m + c_m+1x_m+1 + … + c_nx_n .В столбце В записаны свободные

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

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

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

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

Z = c₁b₁ + c₂b₂ + … + c_mb_m = C_б ∙В ,                                                 (7)

где С_б=(с₁,с₂,…,с_m), B=(b₁,b₂,…,b_m).∆_j. =С_б. A_j – c_j =(c₁, c₂, …, c_m)∙(а_1j, а_2j, …, а_mj) – c_j = c₁а_1j + c₂а_2j + … + c_mа_mj - c_j .

Для базисных столбцов  A₁, A₂, …, A_m  оценки равны  ∆_j = 0 .

Решение, соответствующее этой таблице,X₀ = (x₁= b₁ , x₂ = b₂ , …, x_m = b_m , x_m+1 = 0, …, x_n= 0).

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

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

Пример 2. Z(X) = x₁ + x₂ + x₃ → min,

x₁ + 0x₂ + 0x₃ - x₄ – х₅ = 1,

0x₁ + x₂ + 0x₃ - 2x₄ – 2х₅ = 1,

0x₁ + 0x₂ + x₃ - 3x₄ – 3х₅ = 2,

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

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