Пример 4 Задача об использовании ресурсов

Разберем процесс нахождения оптимального плана:

Для решения задачу необходимо привести к канонической форме:

(1)

Среди переменных задачи можно выделить базисные x₃, x₄ и x₅, и небазисные x₁, x₂. Приравняв небазисные переменные x₁, x₂ к нулю, т. е. x₁ = 0, x₂ = 0, получим исходный базисный план (невырожденный): x₃=36, x₄ = 20, x₅ = 40. Для этого плана значение целевой функции f = 0.

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

Приведем задачу (1) к виду:

(2)

Анализируя функцию f в (2), приходим к выводу, что увеличение значения f, означающее увеличение дохода, может произойти только в том случае, если значения х₁ или х₂ будут возрастать.

Увеличение значений х₁ или х₂ равносильно переводу их в число базисных.

В первую очередь увеличим значение х₂, так как единица продукции Р₂ приносит больший доход (значение х₁ пока остается равным нулю). Значение х₂ нельзя увеличивать бесконечно, а только до такой величины, которая будет удовлетворять условиям:

(3)

Определим значение x₂(X₁ = 0) из следующих соотношений, полученных на основе ограничений задачи (3.22):

Для выполнения условий (3) необходимо, чтобы . Поскольку данное значение х₂ получилось из третьего ограничения, то выразив х₂ из этого ограничения через переменные х₁ и Х₅, получим (переменная х₂ переводится в число базисных вместо х₅, которая становится небазисной):

(4)

Подставив выражение (4) в два оставшихся ограничения и целевую функцию, получим после первой итерации такой вид задачи:

(5)

Определим новый базисный план, полученный после первой итерации: х₁=0, х₅ = 0 (небазисные переменные); x₃ = 6, x₄=Ю, x₂ = 5 (базисные переменные). Значение целевой функции f = 75.

На основании анализа f в (5) можно сделать вывод, что полученный план не является оптимальным, так как значение целевой функции может быть увеличено за счет увеличения значения x₁ (увеличение значения х₅ приведет к уменьшению значения f). Значение х₁ также нельзя увеличивать бесконечно, а только до такой величины, которая будет удовлетворять условиям:

(6)

Определим значение x₁(x₅ = 0) из следующих соотношений, полученных на основе ограничений задачи (5):

Для выполнения условий (6) необходимо, чтобы . Поскольку данное значение х₁ получилось из первого ограничения, то, выразив х₁ из этого ограничения через переменные x₃ и x₅, получим (переменная x₁ переводится в число базисных вместо х₃, которая становится небазисной):

(7)

Подставив выражение (7) в два оставшихся ограничения и целевую функцию, получим после второй итерации следующий вид задачи:

(8)

Определим базисный план, полученный в результате, второй итерации:. x₃=0 и x₅=0(небазисные переменные), х₁=2, x₂=4, x₄=4 (базисные переменные). Значение целевой функции f = 84.

Анализ f в (8) показывает, что полученный в результате второй итерации план является оптимальным, так как значение целевой функции не может быть увеличено за счёт увеличения значений x₃ и x₅.

На основании оптимального плана (х₁=2, x₂=4, x₄=4) делаем вывод, что предприятие для получения максимального дохода в размере 84 руб. должно выпускать из имеющегося количества сырья 2 ед. продукции Р₁ и 4 ед. продукции Р₂.

 

Коэффициенты, стоящие в скобках при небазисных переменных в целевой функции, называются относительными оценками и обозначаются , где I_b — множество индексов базисных переменных. Относительными эти оценки называются потому, что их значение зависит от выбора базисного плана. Например, в

Условие оптимальности плана задачи линейного программирования (для задачи на max). Если для некоторого базисного плана оценки , то этот план является оптимальным.

Рассмотренное условие является достаточным условием оптимальности базисного плана задачи. Необходимость этого условия в общем случае не имеет места и может нарушаться только для вырожденного базисного плана. Оптимальному вырожденному базисному плану могут соответствовать отрицательные оценки .