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₂ по формуле 

?_j=< c_Б, A_j > - c_j.

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

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

?₂ = < c_Б, A₂ > - c₂ = 0 ·2 + 0 · 2 - 2 = -2.

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

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

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

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

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

Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом.

В примере ведущим будет столбец при x₂.

Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f(x) ???. В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x₂, при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x₂ = min{4/2, 12/2}=2.

По таблице это значение вычисляется как наименьшее из отношений компонент базисного плана (из последнего столбца) к соответствующим положительным элементам ведущего столбца.

Наименьшее отношение находится в строке с базисной переменной x_3. Значит переменная x₃ исключается из состава базисных переменных (x₃ = 0).

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

В примере ведущей строкой будет первая строка.

Элемент, находящийся на пересечение ведущей строки и ведущего столбца, называется ведущим элементом.

В нашем случае ведущий элемент a₁₂ = 2.

Табл. 2 - Начальная симплекс-таблица с ведущими строкой и столбцом

Шаг 4. Для получения нового базисного плана приведем задачу к новому предпочтительному виду относительно новых базисных переменных. 

Для этого построим новую симплекс-таблицу, во втором столбце которой вместо исключаемой переменной x₃ запишем новую базисную переменную x₂, а в первом столбце (с_Б) вместо с₃ запишем коэффициент целевой функции при x₂ : c₂=2. В новой симплекс таблице столбец при x₂ должен стать единичным (ведущий элемент должен равняться единице, а все остальные элементы должны обратиться в ноль). Это достигается следующими преобразованиями строк таблицы.

a. Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.

Полученную строку p₁ назовем разрешающей.

b. К оставшейся второй строке прибавим разрешающую строку, умноженную на такое число, чтобы элемент, стоящий в ведущем столбце обратился в ноль.

p₂ = p₂ + (- 2) p₁ = p₂ - p_1.

c. Заполним последнюю строку, вычислив оценки ?_j = < c_Б, A_j > - - c_j, где c_Б, A_j - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= < c_Б, x_Б >.

Получим вторую симплекс-таблицу с новым базисом.

Таблица 3 - Результат первой итерации

Новый базисный план x = (0, x₂, 0, x₄₎ = (0, 2, 0, 8).

Поскольку оценка ?₁= -2 < 0, то план x не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода. 

Так как ?₁ < 0, то в базис вводится переменная x₁. Первый столбец, содержащий x₁ - ведущий.

Находим отношения компонент базисного плана к соответствующим положительным элементам ведущего столбца и в качестве ведущей строки берем строку с наименьшим отношением. В таблице 2 в ведущем столбце только второй элемент больше нуля (= 4), следовательно, вторая строка будет ведущей, а расположенная в ней базисная переменная x₄ подлежит исключению из базиса. 

Выделяем ведущий столбец и ведущую строку и на их пересечении находим ведущий элемент (= 4).

Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x₄ на x_1, и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок ?_j = < c_Б, A_j > - c_j, где c_Б, A_j - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x)= < c_Б, x_Б >.

Таблица 4 - Результат второй итерации

Новый базисный план x = (x₁, x₂, 0, 0₎ = (2, 3, 0, 0). Поскольку все оценки неотрицательны, то план x - оптимальный план.

Таким образом, x* = (2, 3, 0, 0), f(x*) = 8.