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

В качестве первого примера рассмотрим задачу об использовании ресурсов, сформулированную в § 1.2 и уже решенную геометрически в примере 4.1.

Пример 5.1. Решить симплексным методом задачу:

при ограничениях:

(5.1)

Рис. 5.2

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

(5.2)

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

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

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

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

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

(5.3)

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

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

откуда

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

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

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

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

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

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

т.е (5.4)

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

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

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

Значение линейной функции . Изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае .

Однако значение F ₂не является максимальным, так как повторяя рассуждения первого шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х ₁ входящей в выражение для F с положительным коэффициентом. Система уравнений (5.4) определяет наибольшее возможное значение для х ₁: х ₁ = min . Второе уравнение является разрешающим, переменная х _з переходит в неосновные, при этом .

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

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

(5.5)

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

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

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

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

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

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

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