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

4) В столбце С_б симплексной таблицы запишем коэффициенты целевой функции Z(X), номера которых совпадают с номерами базисных столбцов этой строки.

5) В столбце В запишем свободные члены  b₁ = 4, b₂ =13, b₃=2.

6) Сверху над столбцами А₁, А₂, А₃ и А₄ запишем коэффициенты целевой функции с₁=0, с₂=1, с₃=1 и с₄=-2.

7) В столбцах А₁, А₂, А₃ и А₄ запишем столбцы матрицы А.

8) В строке 4 запишем текущее значение Z целевой функции, а также оценки ∆₁, ∆₂, ∆₃ и ∆₄.

9) Находим Z по формуле: Z= С_б∙В = (с₁=0, с₃=1, с₂=1) ∙ (b₁=4, b₂=13, b₃=2) = (0) ∙ (4) + (1) ∙ (13) + (1) ∙ (2) = 15.

10) Находим оценки небазисных столбцов (∆₄) по формуле: ∆₄ = С_бА₄ – с₄ = (с₁=0, с₃=1, с₂=1) ∙ (а₁₄=3, а₂₄= 4, а₃₄= -2) – c₄ = (0) ∙ (3) + (1) ∙ (4) + (1) ∙ (-2) – (-2) = 4 > 0 .

Для базисных столбцов А₁, А₂, А₃  оценки равны  ∆_j = 0, j = 1, 2, 3.

11) Значения базисных переменных в таблице равны x₁=b₁= 4, x₂=b₃= 2,

x₃=b₂=13. Небазисную переменную х₄ приравниваем к нулю.

12) Первоначальное решение, соответствующее этой таблицеX₀ = (x₁=b₁=4, x₂=b₃=2, x₃=b₂=13, x₄=0).

13) Проверим оптимальность текущего решения Х₀ по значениям ∆_j , j = 1, 2, 3, 4. Так как данная задача – задача на нахождение максимума и ∆_j ≥ 0 при j = 1, 2, 3, 4, значит текущий план оптимален  Х^*=Х₀=(4, 2, 13, 0), а максимальное значение функции Z(X) равно  max Z(X) = Z(X₀) = 15.

1.2.4. Улучшение текущего плана в задаче на минимум (максимум)

1°) Если есть только одна оценка ∆_j > 0 (∆_j < 0), то переход к лучшему текущему плану произойдет, если мы включим в число базисных столбцов тот столбец таблицы, для которого положительна (отрицательна) оценка ∆_j, то есть столбец A_j. Для этого находим ведущий элемент преобразования по формуле   θ_j =   =   ,  , . . . ,  =  , то есть  а_kj ведущий элемент – это один из (а_1j, а_2j, …, а_mj).

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

x₁ + 0x₂ + 0x₃ + 3x₄ = 4,

0x₁ + 0x₂ + x₃ + 4x₄ = 13 ,

0x₁ + x₂ + 0x₃ - 2x₄ = 2 ,

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

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

2) Первоначальное решение, соответствующее этой таблице Х₀=(4, 2, 13,).

3) Проверим оптимальность текущего решения Х₀ по значениям ∆_j , j = 1, 2, 3, 4. Так как данная задача – задача на нахождение минимума и ∆₄ = 4 > 0,значит текущий план Х₀ не оптимален.

4) Для улучшения текущего плана Х₀ находим сначала θ₄ для столбца А₄  с положительной

оценкой по формуле θ₄==  .;

а₁₄=3 - ведущий элемент преобразования.

5) Обводим а₁₄=3 кружком в первой строке. 6) В столбце Б вместо А₁ запишем А₄.

7) В столбце С_б заменим коэффициент с₁=0 на с₄= -2.

8) Поделим все элементы 1-ой строки, начиная со столбца В и до конца, на ведущий элемент а₁₄=3.

9) Ко второй строке прибавим первую, умноженную на  -4/3.

10)К третьей строке прибавим первую, умноженную на 2/3.11)Запишем симплексную таблицу.