Отыскание максимума линейной функции

В качестве первого примера рассмотрим задачу об использова­нии ресурсов, сформулированную в разд. 1.2 и уже решенную геометрически в задаче АЛ. ^ 5Л. Решить симплексным методом задачу:

F = 2х, + Зх₂ -> max при ограничениях:

x_l +3jc₂ £18,
2.x, + х₂<16,
х₂ £5,
Зх, ^21,

х, £ 0, х₂ > 0.

Симплексный метод

Рис. 5.2

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком "плюс", так как все неравенства имеют вид "<" [см. систему ограничений (1.26)].

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

JCi + 3*2 + *3 = 18,

2х,

= 16,

= 5, = 21.

Зх,

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

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

-*.^--■-■

Глава 5

Симплексный метод

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

I ш а г . Основные переменные: х₃, *4, *5> *6-Неосновные переменные: х\, х₂.

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

Положив неосновные переменные равными нулю, т.е. х\ = О, х₂ = 0, получим базисное решение Х\ = (0; 0; 18; 16; 5; 21), кото­рое является допустимым и соответствует вершине О(0;0) много­гранника OABCDE на рис. 5.2. Поскольку это решение допусти­мое, нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через неосновные переменные: F = 2х, + Зх₂. При решении Х\ значение функции равно F[X[). Легко понять, что функцию F можно увеличить за счет увеличе­ния любой из неосновных переменных, входящих в выражение для Fc положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не ну­левое, а положительное значение (если новое решение будет вы­рождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине много­угольника, где значение линейной функции "лучше" (по крайней мере "не хуже"). В данном примере для увеличения F можно пе­реводить в основные либо х_ь либо х₂, так как обе эти переменные входят в выражение для Fco знаком "плюс". Для определенности в такой ситуации будем выбирать переменную, имеющую боль­ший коэффициент, т.е. в данном случае х₂ (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).

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

х₃ = 18 - Зх₂ > 0,

Хл = 16 - Хт > 0,

• - ^ _п откуда <

Х5 = 5 - х₂ > 0,

х₆ =21,

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

Не накладывает ограничений на рост переменной, переводи­мой в основные, и такое уравнение, где свободный член отсутст­вует (т.е. равен 0), а переводимая переменная имеет положитель­ный коэффициент. И в этом случае граница обозначается симво­лом да. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Все возможные случаи, которые возникают при оценке переменной, переводимой в основные, перечислены в конце разд. 5.3.

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ - min {18/3; 16/1; 5/1; «>} - 5. При х₂ = 5 переменная х₅ обращается в нуль и переходит в неосновные.

Глава 5

Симплексный метод

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

II шаг.Основные переменные: Х2, хз, Х4, Х(,. Неосновные переменные: х\, х$.

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

х₂ = 5 - х₅,

х₃ = 18 - х, - 3(5- х₅),

., _л ., . (5.4)

х₄ = 16 - 2Х| - (5- х₅),

х₅ = 21 - Зх,, или

^х2 ⁼ 5 - Х^

Х₃ = J — Xj +JX5,

п 1

х₄ = 11 - 2xj + х₅, х₅ = 21 - Зх,.

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

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

F = 2Х( + Зх₂ = 2х, + 3(5 - х₅) = 15 + 2х₍ - Зх₅.

Значение линейной функции F₂ = F(X₂) = 15. Изменение зна­чения линейной функции легко определить заранее как произве­дение наибольшего возможного значения переменной, переводи­мой в основные, на ее коэффициент в выражении для линейной функции; в данном случае А/] = 5-3 = 15, F₂ = F\ + А/-] =

= 0 + 15-15.

Однако значение F₂ не является максимальным, так как повто­ряя рассуждения I шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной xj, входящей в выражение для F с положительным коэффициентом. Система уравнений (5.4) определяет наибольшее возможное значение для х\. X] = min{oo;3/l;ll/2;oo| = 3. Второе уравнение является разре­шающим, переменная хз переходит в неосновные, при этом AF₂ = 3-2 = 6.

Ill шаг.Основные переменные: xj, Х2, Х4, Хб. Неосновные переменные: Х3, X5.

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

= 3 - х₃ + Зх

** ^{= 5}________ Z*l-------- , (5.5)

|х₄ = э + 2х₃ - 5х₅,

, = 12 + Зх₃ - 9х₅.

Базисное решение Лз = (3; 5; 0; 5; 0; 12) соответствует вер­шине В (3;5). Выражаем линейную функцию через неосновные переменные: / = 2х! + Зх₂ = 2(3 — Х3 + 3xs) + 3(5 — Х5) = 21 — - 2х₃ + Зх₅, ^з = Д*з) = 21. Проверяем: F₃ - F₂ = 21 - 15 т 6 = = AF₂. Третье допустимое базисное решение тоже не является оптим&чьным, поскольку при неосновной переменной Х5 в вы­ражении линейной функции через неосновные переменные со­держится положительный коэффициент. Переводим Х5 в основ­ную переменную. При определении наибольшего возможного значения для х₅ следует обратить внимание на первое уравнение в системе (5.5), которое не дает ограничений на рост х$, так как свободный член и коэффициент при xs имеют одинаковые зна­ки. Поэтому х₅ = min{oo;5;l;12/9} = 1. Третье уравнение является разрешающим, и переменная х₄ переходит в неосновные; AF₃ = 1 • 3 = 3.

Глава 5

Симплексный метод

IV шаг.Основные переменные: х\, xi, x$, х^. Неосновные переменные: *з, х$.

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

a ^{J 3}

л ² 1

*2 =4--Х₃+-Х₄₎

1 ² *

х₅ =1 + -х₃т-х_4>

,39

*6 - ^-Т^З + Т*4.

Базисное решение Хл, = (6_; 4; 0; 0; 1; 3) соответствует вершине

С(6; 4) на рис. 5.2.

Линейная функция, выраженная через неосновные перемен-

4 3 ные, имеет вид: F = 24 - — х_г - — х₄ . Это выражение не содержит

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

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции Р\{х\ = 6) и 4 единиц продукции Pi(xi ⁼ 4). Дополнительные переменные х$, х+, х$, д% показывают разницу между запасами ресурсов каждого вида иих потреблением, т.е. остатки ресурсов. При оптимальном плане производства *з — М ⁼ 0. ^те- остатки ресурсов S\ и 5₂ равны нулю, а остатки ресурсов S$ и S₄ равны соответственно 1 и3 единицам. ►

Теперь можно в общем виде сформулировать критерий опти­мальности решения при отыскании максимума линейной функции: