Использование линейного программирования для решения задач оптимизации (стр. 4 из 4)

х₁ +х₂ + х₄ ≤ 30; (9)

х₁ + 4х₂ + х₅ ≤ 84.

Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х₃, х₄, х_5.

Не основные переменные: х₁, х_{2. .}

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

х₃ = 75 - 3х₁ - х₂ ;

х₄ = 30 х₁ - х₂; (10)

х₅ = 84 - х₁ - 4х_2.

Положив основные переменные равными нулю, то есть х₁ = 0, х₂ = 0, получим базисное решение Х₁ = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:

F = 30х₁ + 40х_{2 .}

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

х₃ = 75 - х₂ ≥ 0; х₂ ≤ 75;

х₄ = 30 - х₂ ≥ 0; откуда х₂ ≤ 30;

х₅ = 84 - 4х₂ ≥ 0; х₂ ≤ 84.

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

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ = min {75, 30, 84/4} = 84/4 = 21. При х₂ = 21 переменная х = 0 и переходит в не основные.

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

IIшаг.

Основные переменные: х₂, х₃, х_4.

Не основные переменные: х₁, х_{. .}

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

х₂ = (84 - х₁ - х₅)/4;

х₃ = 75 - 3х ₁ - 84/4 + х₁/4 + х₅/4;

х₄ = 30 - х₁ - 84/4 + х₁ /4 + х₅/4;

или

х₂ =21 0,25 х₁ - 0,25х₅;

х=54 - 2,75х₁ + 0,25х₅;

х=9 - 0,75х₁ + 0,25х₅.

Второе базисное решение Х₂ = (0, 21, 54, 9, 0 ) является допустимым.

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

F = 30х₁ + 40 (84 - х₁ - х₅)/4 = 840 + 20х₁ - 10х₅

Значение линейной функции F₂ = F(X₂) = 840.

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

х₂ =21 - 0,25х₅ ≥ 0; х₅ ≤ 84;

х₃ =54+ 0,25х₅ ≥ 0; откуда х₅ ≤ -216; (11)

х₄ =9 + 0,25х₅ ≥ 0. х₅ ≤ -36 .

Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х_1, входящей в выражение для F с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х₅ :

Х₅ = min {84, -216,-36} = -36 .

При х₅ = -36 х₄ = 0 переходит в неосновные переменные.

Разрешающим будет третье уравнение.

III шаг.

Основные переменные : х₁, х₂, х_3.

Неосновные переменные : х₄, х_5.

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

х₁= 12– 4/3х₄ + 1/3х₅;

х₂ = 18 + 1/3х₄ - 1/3х₅;

х₃ = 21 + 11/3х₄ - 11/3х_5.

Третье базисное решение Х₃ = (12, 18, 21, 0, 0) является допустимым.

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

F = 30(12– 4/3х₄ + 1/3х₅)+ 40(18 + 1/3х₄ - 1/3х₅) = 1080 – 80/3х₄ - 10/3х_5.

Значение линейной функции F₃ = F(X₃) = 1080.

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

Прибыль предприятия принимает максимальное значение 1080 ден. ед. при реализации 12 единиц продукции Р₁(Х₁=12) и Р₂(Х ₂=18). Дополнительные переменные х ₃, х ₄, х _5.

показывают разницу между запасами ресурсов каждого вида и их потреблением, то есть остатки ресурсов. При оптимальном плане производства х ₄ = х ₅ = 0, остатки ресурсов S₂ и S₃ равны нулю, а остатки ресурсов S₁ = 21.

Ответ: максимальная прибыль от реализации продукции равна 1080 ден. ед.

2 способ – геометрический метод

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

линейной функции F = 30х₁ + 40х₂ →maxпри следующих ограничениях:

3х₁ + х₂ ≤ 75, (I)

х₁ + х₂ ≤ 30, (II) (12)

х₁ +4х₂ ≤ 84, (III), х₁ ≥ 0, х₂ ≥ 0, х₂ ≥ х₁

по смыслу задачи.

Изобразим многоугольник решений данной задачи.