Пример 2.3.1. Решить злп (2.2.1), (2.2.5) симплекс-методом.

Решение. Для решения ЗЛП необходимо, чтобы все свободные члены системы ограничений (2.2.1) были неотрицательными. Для этого первое неравенство системы умножим на (–1):

(2.3.1)

Замечание. Если нужно максимизировать целевую функцию, то удобнее перейти к нахождению минимума max z = – min(–z).

Перейдем к минимуму в нашей задаче:

min(–z) = – x₁ – 4x₂

Приведем задачу к канонической форме, вводя дополнительные переменные x₃ , x₄, x₅ в систему ограничений (2.3.1).

Замечание. Если неравенство имеет знак “”, то дополнительную переменную вводят со знаком “+”; если неравенство имеет знак “”, то дополнительную переменную вводят со знаком “– ”.

ЗЛП (2.3.1) в канонической форме имеет следующий вид:

min(–z) = – x₁ – 4x₂

Для получения единичной матрицы, составленной из векторов при базисных переменных, введем искусственные переменные в систему ограничений: если дополнительная переменная имеет знак минус, то в это уравнение вводят искусственную переменную со знаком плюс; если дополнительная переменная имеет знак плюс, то в это уравнение искусственную переменную вводить не нужно. Искусственные переменные одновременно вводятся в целевую функцию z с неизвестным положительным коэффициентом М.

(3.2.2)

min(–z) = – x₁ – 4x₂ + Мx₆ + Мx₇

В векторной форме система ограничений (3.2.2) имеет вид

р₁x₁ + р₂x₂ + р₃x₃ + р₄x₄ + р₅x₅ + р₆x₆ + р₇x₇ = р₀,

где р₁ = , р₂ = , р₃ = , р₄ = , р₅ = , р₆ = , р₇ = , р₀ =

Переменные x₁ и x₂ являются основными, x₃, x₄, x₅ – дополнительными, x₆, x₇ – искусственными. Векторы р₆, р₄, р₇ образуют единичный базис, причем р₆ – первый базисный вектор.

Заполним первую симплекс-таблицу. Исходная симплекс-таблица заполняется следующим образом. В первой строке записывают коэффициенты целевой функции. В столбец “Базис” записывают базисные векторы. В столбце “С” записывают коэффициенты целевой функции при базисных векторах. В столбцах “р₀”, “р₁”, “р₂”, “р₃”, “р₄”, “р₅”, “р₆”, “р₇” записывают компоненты соответствующих векторов.

Для заполнения клеток таблицы, которые находятся в двух последних строках нужно элементы столбца “С” умножить на соответствующие элементы рассчитываемого столбца и отнять число, стоящее в первой строке (за исключением столбца “р₀”). Например, для заполнения клеток столбца “р₂” умножим элементы столбца “С” на соответствующие элементы столбца “р₂” и отнимем число – 4: М·5 + 0·1 + М·1 – (– 4) = 4 + 6М. В клетку на пересечении столбца “р₂” и z-строки записывают 4, а в клетку на пересечении столбца “р₂” и М-строки записывают 6.

Таблица 2.3.1

Первая симплексная таблица

Последние две строки симплекс-таблицы называются индексными. В них, начиная со второго столбца “р₁”, содержатся оценки оптимальности, с помощью которых проверяют оптимальность опорного плана, соответствующего данной таблице. Значение составляющих опорного плана расположено в столбце “р₀”, причем небазисным переменным присваивают нулевые значения.

Первой симплекс-таблице 2.3.1 соответствует опорный план:

x₁ = 0, x₂ = 0, x₃ = 0, х₄ = 6, x₅ = 0, x₆ = 5, x₇ = 7.

Критерий оптимальности проверяют по М-строке, а если она отсутствует, то по z-строке.