Линейное программирвание

  ∆₄ = < с_Б, A₄ > – c₄ = 1∙(-1) + 0∙5 + 2∙1 – 4= -3,

  ∆₅ = < с_Б, A₅ > – c₅ = 1∙0 + 0∙0 + 2∙1 – 2= 0.

  Так как оценка ∆₄ < 0, то базисный план x⁰ не оптимален. Заметим, что симплексные оценки, соответствующие базисным переменным, всегда равны нулю, так что достаточно проверять только небазисные оценки.  

2.2 Реализация симплекс-метода  на примере

  Продемонстрируем  применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП

  Матрица условий A = (A₁, A₂, A₃, A₄), где

        

  Целевой вектор c =(c₁, c₂, c₃, c₄) = (1, 2, 0, 0); вектор правых частей b=(b₁, b₂) = (4, 12).

  Шаг 0. Нахождение начальной угловой точки (базисного плана).

  Задача  имеет предпочтительный вид, так  как правые части уравнений положительны, а столбцы матрицы условий A_3, A₄ образуют единичную подматрицу. Значит начальная базисная матрица  = (A₃, A₄); x₃ и x₄ – базисные переменные, x₁ и x₂ - небазисные переменные, c_Б = (c_3, c₄₎ = = (0, 0).

  Начальный базисный план имеет вид x⁰ = (0, 0, x₃, x₄₎ = (0, 0, 4, 12); f(x^o) = 0.

  Шаг 1. Проверка базисного плана на оптимальность.

  Подсчитаем  симплексные оценки для небазисных переменных по формуле (5.1)  

  D₁ = < c_Б, A₁ > – c₁ = 0 ·(–1) + 0 ·3 – 1 = –1.

  D₂ = < c_Б, A₂ > – c₂ = 0 ·2 + 0 · 2 – 2 = –2.

  Так как оценки отрицательны, то план x – не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

  Шаг 2. Нахождение переменной вводимой в базис.

  Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать  положительной) одну из небазисных переменных x₁ или x₂, поскольку обе оценки D_j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x_2.

  Шаг 3. Определение переменной выводимой из базиса.

  После ввода в базис переменной x₂ новый план будет иметь вид   

  x' = (0, x_2, x₃, x₄).

  Этот  план не является базисным, так как  он содержит только одну нулевую координату, значит надо сделать нулевой (исключить  из базиса) одну из переменных x₃ или x₄. Подставим координаты плана x' = (0, x_2, x₃, x₄) в ограничения задачи. Получим

 

  2x₂+ x₃ = 4,

  2x₂ + x₄ = 12.

  Выразим отсюда базисные переменные x₃ и x₄ через переменную x₂, вводимую в базис.

  Так переменные x₃ и x₄ должны быть неотрицательны, получим систему неравенств

  Чем больше значение x₂, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).

  Перепишем последние неравенства в виде

  2x₂ ≤ 4,

  2x₂ ≤ 12,

  откуда  максимальное значение x₂ = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x₃ и x₄, получаем x₃ = 0. Следовательно x₃ выводится из базиса. 

  Шаг 4. Определение координат нового базисного плана.

  Новый базисный план (смежная угловая точка) имеет вид

  x' = (0, x_2, 0, x₄)

  Базис этой точки состоит из столбцов A₂ и A₄, так что  = (A_2, A₄). Этот базис не является единичным, так как вектор A₂ = (2,2), и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x_2, x_4, то есть чтобы переменная x₂ входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

  – x₁+ 2 x₂+ x₃ = 4, (p₁₎

  3x₁ +2 x₂ + x₄ = 12. (p₂₎

  Поделим первое уравнение на коэффициент  при x₂. Получим новое уравнение  = p₁ / 2, эквивалентное исходному 

  – 1/2 x₁+ x₂+ 1/2 x₃ = 2. ( )

  Используем  это уравнение, которое назовем  разрешающим, для исключения переменной x₂из второго уравнения. Для этого надо уравнение   умножить на 2 и вычесть из p₂.Получим   = p₂ – 2   = p₂ – p₁:

  4 x₁ – x₃ + x₄ = 8. ( )

  В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x₂, x₄:   

  f(x) = x₁ + 2 x₂ + 0 x₃ + 0 x₄ max®

  – 1/2 x₁+ x₂+ 1/2 x₃ = 2 ( )

  4 x₁ – x₃ + x₄ = 8 ( ₎

  x_j ³ 0, j = 1,2,3,4

 

  Подставляя  сюда представление нового базисного  плана x¹ = (0, x_2, 0, x₄), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений   

  x' = (0, 2, 0, 8); f(x¹)=4.

  На  этом завершается первая итерация простого симплекс-метода. Далее процесс решения  задачи продолжается с шага 1, состоящем  в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда  все симплексные оценки текущего базисного плана окажутся неотрицательными.

  Мы  не будем проводить вторую итерацию по схеме первой, поскольку все  вычисления симплекс-метода удобнее  проводить в табличном виде.  

2.3 Табличная реализация  простого симплекс-метода

  Табличную реализацию продемонстрируем на том  же примере (2.2)–(2.5).

  Шаг 0. Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x_1,...,x₄) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений – элементы матрицы условийА, так что под переменной x₁ располагается столбец A₁, под переменной x₂ – столбец A₂ и т.д. В правый столбец заносятся правые части ограничений (числа b_i > 0).

  Затем находим столбцы матрицы условий, образующие единичный базис –  в нашем примере это A₃ и A₄ – и соответствующие им базисные переменные x_3, x₄ записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.

 

  Таблица 1 -  Начальная симплекс-таблица

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

  x^o = (0, 0, x₃, x₄₎ = (0, 0, 4, 12).  

  Шаг 1. Для проверки плана x^o на оптимальность подсчитаем симплексные оценки для небазисных переменных x₁ и x₂ по формуле    

  D_j=< c_Б, A_j > – c_j.

  D₁ = < c_Б, A₁ > – c₁ = 0 ·(–1) + 0 ·3 – 1 = –1.

  При табличной реализации для подсчета оценки D₁ надо найти сумму произведений элементов первого столбца (c_Б) на соответствующие элементы столбца A₁ при небазисной переменной x₁. Аналогично подсчитывается оценка D₂, как скалярное произведение первого столбца (c_Б) на столбец при переменной x₂.   

  D₂ = < c_Б, A₂ > – c₂ = 0 ·2 + 0 · 2 – 2 = –2.

  Симплексные оценки записываются в последней  строке симплекс-таблицы, которая называется дельта-строкой. При этом заполняются  не только клетки при небазисных переменных, но и базисные клетки. Легко проверить, что для базисных единичных столбцов матрицы условий симплексные  оценки равны нулю. В последней  клетке строки оценок записываем значение целевой функции в точке x^o_. Заметим, что, так как небазисные координаты базисного плана равны нулю, то подсчет целевой функции удобно производить по формуле   

  f(x)= < c_Б, x_Б >,

  перемножая  скалярно первый и последний столбцы  таблицы. 

  Так как среди оценок D_j есть отрицательные, то план x^o – не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.

  Шаг 2. Поскольку обе оценки D₁ и D₂ < 0, то в базис можно включить любую из переменных x_1, x₂. Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x₂.