Материал: Математические методы и модели в экономике. Амелин С.В

В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой функции, в третьем – правые части уравнений системы ограничений. Далее записана матрица из коэффициентов левой

части системы ограничений aij, изменяющаяся в процессе пересчета. В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x)

= Ci X i , и далее – оценки неизвестных, найденные по фор-

i

муле j = Ci аij – Cj.

i

Если среди оценок j есть отрицательные, то опорный план не является оптимальным и значение целевой функции можно улучшить. Для этого нужно пересчитать симплексную таблицу, выбрав соответствующим образом ключевой элемент, стоящий на пересечении ключевой s-ой строки и ключевого k-го столбца, причем берется столбец с наибольшей по абсолютной величине отрицательной оценкой.

Для определения ключевой строки находим отношения правых частей уравнений к положительным элементам ключе-

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

Пересчет таблицы производится по следующему правилу: 1) Элементы ключевой строки делятся на ключевой эле-

мент

Далее, с помощью метода Жордана - Гаусса проводят пересчет таблицы таким образом, чтобы элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов.

101

2) Остальные элементы матрицы, включая и свободные члены системы уравнений (правые части ограничений - bi) преобразуются согласно выражению:

Это правило пересчёта можно изобразить в виде «схемы прямоугольника»:

или

Так, для столбца «План Xi» получим:

Таким образом, в данной задаче для получения следующей симплексной таблицы вычтем из элементов третьей строки соответствующие элементы первой строки, а из элементов второй строки – элементы первой строки, поделенные на два (на ключевой элемент).

Переменная, соответствующая ключевой строке, выводится из базиса, а переменная, соответствующая ключевому столбцу, вводится вместо неё в базис (Х2 вместо Х4).

Для каждого шага итерации строится своя симплексная таблица (рис. 50).

102