Пример решения задачи симплексным методом

Решить задачу 2.1.

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком “плюс”, так как все неравенства имеют вид «≤».

Получим систему ограничений в виде:

,

,

,

.

Для нахождения первоначального базисного решения разобьем переменные на две группы — основные и неосновные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅,х₆ , отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель из их коэффициентов и проверять, равен ли он нулю. Достаточно воспользоваться следующим правилом: в качестве основных переменных на первом шаге следует выбрать (если возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не ходит ни одна из этих переменных.

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

I ш а г. Основные переменные: х₃, х₄, х₅, х₆. Неосновные переменные: х₁, х₂.

Выразим основные переменные через неосновные:

,

, (2.1.1)

,

Положив неосновные переменные равными нулю, т.е. х₁ =0, х₂ = 0, получим базисное решение Х₁= (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине О (0;0) многогранника ОАВСDЕ на рис. 2.1.1.

Рис. 2.1.1

Поскольку это решение допустимое, нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через неосновные переменные: F = 2х₁ + 3х₂.

При решении Х₁ значение функции равно F(Х₁). Легко понять, что функцию F можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для F с положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функций “лучше” (по крайней мере “не хуже”). В данном примере для увеличения F можно переводить в основные либо х₁, либо х₂, так как обе эти переменные входят в выражение дня F со знаком “плюс”. Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х₂ (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).

Система (2.1.1) накладывает ограничения на рост переменной х₂. Поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как неосновная переменная):

, ,

, откуда ,

,

.

Каждое уравнение системы (2.1.1), кроме последнего, определяет оценочное отношение — границу роста переменной х₂, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х₂ при условии, что эти числа имеют разные знаки. Последнее уравнение системы не ограничивает рост переменной х₂, так как данная переменная в него не входит (или формально входит с нулевым коэффициентом). В этом случае условимся обозначать границу символом ∞. Такой же символ будем использовать, когда свободный член и коэффициент при переменной в уравнении имеют одинаковые знаки, так как и в этом случае нет ограничений на рост переменной.

Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ =min (18/3; 16/1; 5/1; ∞} =5. При х₂ =5 переменная х5 обращается в нуль и переходит в неосновные.

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

II шаг. Основные переменные: х₂, х₃,х₄ , х₆. Неосновные переменные: х₁, х₅.

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х₂):

,

,

,

,

Или

,

, (2.1.2)

,

.

Второе базисное решение Х₂ (0; 5; 3; 11; 0; 21) является допустимым и соответствует вершине А (0;5) на рис. 2.1.1. Геометрическая интерпретация перехода от Х₁ к Х₂ — переход от вершины О к соседней вершине А на многоугольнике решений ОАBCDЕ.

Выразив линейную функцию через неосновные переменные на этом шаге, получаем:

F=2х₁+3х₂=2х₁+3(5—х₅) = 15+2х₁-3х₅.

Значение линейной функции F₂ = F (Х₂) =15. Изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае
D F₁=5*3=15, F₂ = F₁+ D F ₁ =0+15= 15.

Однако значение F₂ не является максимальным, так как повторяя рассуждения 1 шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х₁, входящей в выражение для F с положительным коэффициентом. Система уравнений (2.1.2) определяет наибольшее возможное значение для х₁: х₁ = min{∞;3/1;11/2; ∞} = 3. Второе уравнение является разрешающим, переменная х₃ переходит в неосновные, при этом D F₂=3*2=6.

III шаг. Основные переменные: х₁, х₂, х₄, х₆. Неосновные переменные х₃, х₅.

Как и на II шаге, выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х_I). После преобразований получаем:

,

,

, (2.1.3)

.

Базисное решение Х₃ = (3; 5; 0; 5; 0; 12) соответствует вершине В (3;5). Выражаем линейную функцию через неосновные переменные
F = 2х₁ + 3Х₂= = 2(3 - х₃ + 3х₅) + 3(5 — х₅) = 21 - 2_х3+ 3х₅, F₃= F (Х₃) =21. Проверяем: F₃ - F₂= 21 - 15 = 6 = D F₂. Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х₅ в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х₅ в основную переменную. При определении наибольшего возможного значения для х₅ следует обратить внимание на первое уравнение в системе (2.1.3), которое не дает ограничений на рост х₅, так как свободный член и коэффицииент при х₅ имеют одинаковые знаки. Поэтому
х₅ = min{∞;5;1;12/9} = 1. Третье уравнение является разрешающим, и переменная х₄ переходит в неосновные; D F₃ = 1*3= 3.

IV ш а г. Основные переменные: х₁, х₂, х₅, х₆. Неосновные переменные: х₃, х₄.

После преобразований получим:

,

,

,

.

Базисное решение Х = (6; 4; 0; 0; 1; 3) соответствует вершине С (6; 4) на рис. 2.1.1.

Линейная функция, выраженная через неосновные переменные, имеет вид: .Это выражение не содержит положительных коэффициентов при неосновных переменных, поэтому значение F₄= F(Х₄) = 24 максимальное. Функцию F невозможно еще увеличить, переходя к другому допустимому базисному решению, т.е. решение Х₄ оптимальное. Вспоминая экономический смысл всех переменных, можно сделать следующие выводы.

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции Р₁(х₁ =6) и 4 единиц продукции
Р₂(х₂= 4). Дополнительные переменные х₃, х₄, х₅, х₆ показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптимальном плане производства х₃ = х₄ = 0, т.е. остатки ресурсов S₁ и S₂ равны нулю, а остатки, ресурсов S₃ и S₄ равны соответственно 1 и 3 единицам.