Контрольное задание № 4.
Решение задач линейного программирования Симплекс-методом.
Условие задачи.
Предприятие производит 3 вида продукции: А1, А2, А3, используя сырье двух видов: В1 и В2. Известны затраты i – го вида на единицу изделия g – го вида aig, количества сырья каждого вида bi (i=1,2), а так же прибыль, полученная от единицы изделия g-го вида cg (g=1,2,3).
-
Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
-
Сколько изделий каждого вида необходимо произвести, чтобы получить максимум товарной продукции?
-
Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли при условии, что необходимо выполнить план выпуска?
X вариант
|
Матрица затрат сырья i – го вида на единицу продукции g – го вида A=(aig) |
||||
|
Сырье
|
Виды продукции |
Количество сырья |
||
|
А1 |
А2 |
А3 |
||
|
В1 |
2 |
1 |
2 |
2100 |
|
В2 |
2 |
2 |
1 |
1200 |
|
Прибыль от единицы каждого изделия (с1, с2, с3) |
3 |
3 |
2 |
|
|
План выпуска |
200 |
100 |
600 |
|
Решение задачи.
-
Найдем количество изделий каждого вида, которые нужно произвести для того, чтобы получить максимум прибыли.
|
|
|
|
|
|
|
|
|
|
|
Найдем наибольшее значение функции прибыли |
||||||
|
L |
= |
|
3 |
x1 |
+ |
3 |
x2 |
+ |
2 |
x3 |
|
при следующих ограничениях |
|
|
|
2 |
x1 |
+ |
|
x2 |
+ |
2 |
x3 |
|
2100 |
|
|
2 |
x1 |
+ |
2 |
x2 |
+ |
|
x3 |
|
1200 |
|
|
|
2 |
x1 |
+ |
|
x2 |
+ |
2 |
x3 |
+ |
|
S1 |
|
|
|
= |
2100 |
|
|
2 |
x1 |
+ |
2 |
x2 |
+ |
|
x3 |
|
|
|
+ |
|
S2 |
= |
1200 |
|
S1 |
0
S2
0
|
Введенные нами переменные S1, S2, называются балансовыми переменными. |
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
отношение |
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
L |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
Разделим элементы строки 1 на 2. |
|||||||||||||||||||||||||||||||||||||||
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
L |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
От элементов строки 2 вычитаем соответствующие элементы строки 1. |
|
К элементам строки L прибавим соответствующие элементы строки 1, умноженные на 2. |
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
L |
|
|
|
|
|
|
|
X |
1 |
= |
( |
0, |
0, |
1050, |
0, |
150 |
) |
|
L (X 1) = 2100. |
|||||||||
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
отношение |
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
L |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
Разделим элементы строки 2 на 3/2. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
L |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
От элементов строки 1 вычитаем соответствующие элементы строки 2, умноженные на 1/2. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
К элементам строки L прибавим соответствующие элементы строки 2, умноженные на 2. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
x1 |
x2 |
x3 |
S1 |
S2 |
свободные члены |
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
L |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
X |
2 |
= |
( |
0, |
100, |
1000, |
0, |
0 |
) |
|
L (X 2) = 2300. |
|
|
|
L |
= |
2300 |
|
-1/3 |
x1 |
|
-1/3 |
S1 |
|
-4/3 |
S2 |
|
Сейчас x1=0. |
|
Если
увеличим значение x1,
то значение функции L |
|
Сейчас S1=0. |
|
Если
увеличим значение S1,
то значение функции L |
|
Сейчас S2=0. |
|
Если
увеличим значение S2,
то значение функции L |
|
Больше не удастся увеличить значение функции L. |
|
Ответ 1): |
|
Lmax = 2300 |
|
x1 = 0 x2 = 100 x3 = 1000 |
|
|