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

Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А.

Решение.

Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потре

буется (12 х1 +4 х2) единиц ресурса I, (4х1 +4х2) единиц ресурса II, (3х1 +12х2) единиц ресурса III. Так кА потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х1 +4х2 ≤ 300; 3х1 + х2 ≤ 75;

4х1 +4х2 ≤ 120; или х1 + х2 ≤ 30; (6)

3х1 +12х2 ≤ 252. х1 +4х2 ≤ 84.

По смыслу задачи переменные х1 ≥ 0, х2 ≥ 0. (7)

Суммарная прибыль А составит 30х1 от реализации продукции А и 40х 2 от реализации продукции В, то есть : F = 30х1 +40х 2 (8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

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

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

31 +х2 + х3 ≤ 75;

х1 +х2 + х4 ≤ 30; (9)

х1 + 4х2 + х5 ≤ 84.

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

I шаг.

Основные переменные: х3, х4, х5.

Не основные переменные: х1, х2. .

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

х3 = 75 - 3х1 - х2 ;

х4 = 30 х1 - х2; (10)

х5 = 84 - х1 - 4х2.

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

F = 30х1 + 40х2 .

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

х3 = 75 - х2 ≥ 0; х2 ≤ 75;

х4 = 30 - х2 ≥ 0; откуда х2 ≤ 30;

х5 = 84 - 4х2 ≥ 0; х2 ≤ 84.

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

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

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

II шаг.

Основные переменные: х2, х3, х4.

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

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

х2 = (84 - х1 - х5)/4;

х3 = 75 - 3х 1 - 84/4 + х1/4 + х5/4;

х4 = 30 - х1 - 84/4 + х1 /4 + х5/4;

или

х2 =21 0,25 х1 - 0,25х5;

х =54 - 2,75х1 + 0,25х5;

х =9 - 0,75х1 + 0,25х5.

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

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

F = 30х1 + 40 (84 - х1 - х5)/4 = 840 + 20х1 - 10х5

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

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

х2 =21 - 0,25х5 ≥ 0; х5 ≤ 84;

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

х4 =9 + 0,25х5 ≥ 0. х5 ≤ -36 .

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

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

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

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

III шаг.

Основные переменные : х1, х2, х3.

Неосновные переменные : х4, х5.

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

х1= 12 – 4/3х4 + 1/3х5;

х2 = 18 + 1/3х4 - 1/3х5;

х3 = 21 + 11/3х4 - 11/3х5.

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

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

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

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

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

 Скачать реферат