Использование симплекс-метода

Преобразуем исходную математическую модель к каноническому виду

F = 2 х ₁ + 3 х ₂ ® max;

х ₁ + х ₂ + х ₃ = 8;

4 х ₁ + 10 х ₂ + х ₄ = 40;

х ₁ + х ₅ = 4;

х ₁ ³ 0; х ₂ ³ 0; х ₃ ³ 0; х ₄ ³ 0; х ₅ ³ 0.

Здесь х ₃, х ₄, х ₅ – дополнительные балансовые (остаточные) переменные, добавленные в неравенства для преобразования их в равенства.

Допустимое базисное решение имеет вид

х ₁ = 0; х ₂ = 0; х ₃ = 8; х ₄ = 40; х ₅ = 4; F = 0.

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

Базис	Решение	x 1	x 2	x 3	x 4	x 5
x 3
x 4
x 5
F max		–2	–3

Столбец x ₂выберем в качестве разрешающего, поскольку в последней строке симплекс-таблицы для столбцов небазисных переменных именно в нем находится наименьшее отрицательное число (–3).

Вычислим симплекс-отношения путем деления элементов столбца «Решение» на положительные элементы разрешающего столбца:

для строки x ₃: 8 / 1 = 8;

для строки x ₄: 40 / 10 = 4.

Строку x ₄ определим в качестве разрешающей, так как ей соответствует наименьшее симплекс-отношение.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

Небазисная переменная x ₂, находящаяся в разрешающем столбце, вводится в базис, а базисная переменная x ₄, напротив, из базиса выводится.

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

Элементы разрешающей строки получаются путем деления старого значения на величину разрешающего элемента:

для столбца «Решение»: 40 / 10 = 4;

для столбца x ₁: 4 / 10 = 0,4;

для столбца x ₂: 10 / 10 = 1;

для столбца x ₃: 0 / 10 = 0;

для столбца x ₄: 1 / 10 = 0,1;

для столбца x ₅: 0 / 10 = 0.

Все остальные элементы вычисляются по формуле:

НЭ = СТЭ – К×НЭР,

где НЭ – новый элемент; СТЭ – старый элемент; РЭ – разрешающий элемент; К – коэффициент текущей строки в разрешающем столбце; НЭР – соответствующий новый элемент разрешающей строки.

В нашем случае получим:

для строки x ₃: 8 – 1 ´ 4 = 4; 1 – 1 ´ 0,4 = 0,6; 1 – 1 ´ 1 = 0;

1 – 1 ´ 0 = 1; 0 – 1 ´ 0,1 = –0,1; 0 – 1 ´ 0 = 0;

для строки x ₅: 4 – 0 ´ 4 = 4; 1 – 0 ´ 0,4 = 1; 0 – 0 ´ 1 = 0;

0 – 0 ´ 0 = 0; 0 – 0 ´ 0,1 = 0; 1 – 0 ´ 0 = 1;

для строки F _max: 0 – (–3) ´ 4 = 12; –2 – (–3) ´ 0,4 = –0,8; –3 – (–3) ´ 1 = 0;

0 – (–3) ´ 0 = 0; 0 – (–3) ´ 0,1 = 0,3; 0 – (–3) ´ 0 = 0;

Таким образом, симплекс-таблица примет вид.

Базис	Решение	x 1	x 2	x 3	x 4	x 5
x 3		0,6			–0,1
x 2		0,4			0,1
x 5
F max		–0,8			0,3

Новое базисное решение

х ₁ = 0; х ₂ = 4; х ₃ = 4; х ₄ = 0; х ₅ = 4; F = 12,

хотя и улучшает значение целевой функции по сравнению с начальным, но не является оптимальным, поскольку в последней строке F _max симплекс-таблицы имеются отрицательные элементы (значение –0,8 в столбце х ₁).

Выберем столбец х ₁ в качестве разрешающего, как содержащий отрицательный элемент в последней строке симплекс-таблицы.

Строку x ₅ определим в качестве разрешающей, так как ей соответствует наименьшее симплекс-отношение (отношение элементов столбца «Решение» на положительные элементы разрешающего столбца).

Аналогично описанному выше вычислим элементы новой симплекс-таблицы.

Базис	Решение	x 1	x 2	x 3	x 4	x 5
x 3	1,6				–0,1	–0,6
x 2	2,4				0,1	–0,4
x 1
F max	15,2				0,3	0,8

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

х ₁ = 4; х ₂ = 2,4; х ₃ = 1,6; х ₄ = 0; х ₅ = 0; F = 15,2.

2. Построим математическую модель двойственной задачи.

f = 8 y ₁ + 40 y ₂ + 4 y ₃ ® min;

y ₁ + 4 y ₂ + y ₃ ³ 2;

y ₁ + 10 y ₂ ³ 3;

y ₁ ³ 0; y ₂ ³ 0; y ₃ ³ 0.

Оптимальное решение двойственной задачи можно определить на основе оптимального решения прямой задачи

Из теорем двойственности следует:

1) экстремальные значения целевых функций разрешимых прямой и двойственной задач совпадают;

2) компоненты оптимального плана одной из задач находятся в строке целевой функции итоговой симплекс-таблицы другой задачи.

Значение переменной y_i двойственной задачи соответствует теневой цене i -го ресурса прямой задачи.

При приведении исходной задачи линейного программирования к каноническому в первое неравенство, соответствующее ресурсу Р₁, для преобразования его в равенство добавлялась балансовая переменная х ₃. Таким образом, значение переменной y ₁ следует искать в последней строке итоговой симплекс-таблицы в столбце х ₃.

Рассуждая аналогичным образом, в столбцах х ₄, х ₅, находим значения y ₂, y ₃.

Оптимальное решение двойственной задачи будет иметь вид:

y ₁ = 0; y ₂ = 0,3; y ₃ = 0,8; F = 15,2.

3. Определим статус ресурсов.

Ресурс называется дефицитным, если он израсходован полностью. Имеющийся же в некотором избытке ресурс относят к разряду недефицитных.