Экономический смысл полученных результатов.
Смысл двойственных оценок ресурсов у1=0, у2=7, у3=9 показывает, что добавление одной единицы 1-го (2-го;3-го) ресурса обеспечит прирост прибыли на 0 (7, 9) денежных единиц.
Оценки 3-ей (4-ой) технологий D3=18 (D4=8) показывает, что если произвести одну единицу продукции 3-го (4-го) вида (они не входят в оптимальную производственную программу), то прибыль уменьшится на 18 (8) денежных единиц.
V. “РАСШИВКА УЗКИХ МЕСТ“ ПРОИЗВОДСТВА. ФОРМУЛИРОВКА И СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.
При выполнении оптимальной производственной программ второй и третий ресурсы используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. T=(t1, t2, t3) – вектор дополнительных объёмов ресурсов.
Итак, необходимо составить план “расшивки узких мест“ производства, то есть указать, сколько единиц каждого из дефицитных видов ресурсов должно быть приобретено, чтобы суммарный прирост прибыли был максимальным при условии, что для расчетов используются найденные двойственные оценки ресурсов.
Так как мы используем найденные оценки ресурсов, то должно выполняться условие:
Q (B + T) ³ 0 Û Q B + Q T ³ 0 Û H + Q T ³0
Итак задача состоит в том, чтобы найти вектор T=(t1, t2, t3) такой, что
w = у1t1 + y2t2 + y3t3 ® max ,
где w – суммарный прирост прибыли, при условии сохранения двойственных оценок ресурсов (и следовательно структуры производственной программы)
H = Q T ³ 0.
Подставив соответствующие значения, получим требуемую математическую модель:
w=7t2+ 9t3 ® max (1)
18 1 1/9 -2/3 0 0
30 + 0 1/3 0 * t2 ³ 0
46 0 -2/9 1/3 t3 0
предполагая, что дополнительно можно надеяться получить не более 1/3 первоначального объёма ресурса каждого вида, то есть
0 140
t2 £ 1/3 90
t3 198
причём по смыслу задачи t2 ³ 0, t3 ³ 0. Перепишем неравенства в другом виде. Получим:
|
|
18 + 1/9t2 – 2/3t3 ³ 0 -t2 + 6t3 £ 162
30 + 1/3t2 ³ 0 Þ -t2 £ 90
46 – 2/9t2 + 1/3t3 ³ 0 2t2 - 3t3 £ 414
t2 £ 30, t3 £ 66 t2 £ 30, t3 £ 66
Задача оказалась с 3-мя переменными, поэтому, согласно с заданием, мы решим её графически.
|
-t2 + 6t3 £ 162 (2)
-t2 £ 90 (3)
2t2 - 3t3 £ 414 (3)
t2 £ 30 (4)
t3 £ 66 (5)
t2 ³ 0, t3 ³ 0
| (1) | t2 | -162 | |
| t3 |
| (2) | t2 | ||
| t3 | -90 | -90 |
| (3) | t2 | ||
| t3 | -138 |
По графику на рисунке 1 видно, что решение данной задачи находится в точке А(30; 32). Таким образом программа «Расшивки узких мест производства» имеет вид: t1=0, t2=30, t3=32 и прирост прибыли составит w= 7*30 + 9*32 = 498
Св)одная таблица результатов по пунктам 1-5
| Cj | Bi | X4+i | Yi | Ti | ||||
| aij | ||||||||
| Xj | ||||||||
| Dj |
VI. СОСТАВЛЕНИЕ МОДЕЛИ НОВОЙ ПРОИЗВОДСTВЕННОЙ ПРОГРАММЫ С УЧЁТОМ ПРОПОРЦИЙ.
Пусть для выпуска продукции требуется некоторые затраты в определённых пропорциях. Пусть a = 1, b = 3, g=2, d=8, тогда:
x1/a = x3/b, а х2/g = х4/d, то есть х3 = 3х1, х4 = 4х2.
Исходя из полученных данных получаем, что математическая модель производственной задачи с учётом полученных пропорций примет вид:
Р(х) = 27х1 + 39х2 + 3*18х1 + 4*20х2®max
|
2х1 + x2 + 3*6х1 + 4*5x2 £ 140
3х2 + 4*4x2 £ 90
3х1 + 2х2 + 3*4х1 £ 198
P(x)=81x1 + 119x2®max
|
20x1 + 21x2 £ 140
19x2 £ 90
15x1 + 2x2 £ 198
x1 ³ 0, x2 ³ 0
Полученную задачу можно решить графически:
| (1) | x1 | ||
| x2 | 6,67 |
| (2) | x1 | ||
| x2 | 4,73 | 4,73 |
| (1) | x1 | 13,2 | |
| x2 |
Grad = (81;119)
Решение задачи приведено на Рис. 2.
Решение задачи находится в точке А с координатами x1 = 2,03, x2 = 4,73, откуда оптимальный план производства: x1 = 2,03, x2 = 4,73, x3 =6,09 , x4 = 18,92, а максимальная прибыль составит P(x)max = 727,3
VII. МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Решение задачи планирования с учётом пропорций оказалось не целочисленным, следовательно следует решить задачу методом ветвей и границ, для нахождения целочисленных решений.
G0 = P(x) = 81x1 + 119x2®max
|
20x1 + 21x2 £ 140
19x2 £ 90
15x1 + 2x2 £ 198
x1 = 2.03, x2 = 4.73, P(x)max = 727.3
Pгр = -¥
|
|
G1 = G0 , x2 £ 4 G2 = G0, x2 ³ 5
т. А (2,8; 4) решений нет
P(x)max = 702,8 Pгр = -¥
|
|
G3 = G1 , x1 £ 2 G4 = G1, x1 ³ 3
т. А (2; 4) т. А (3; 3,8)
P(x)max = 638 P(x)max = 525
Pгр = 638
|
|
т. А (3,85; 3) решений нет
P(x)max = 668,85 Pгр = -¥
|
|
G7 = G5 , x1 £ 3 G8= G5, x1 ³ 4
т. А (3;3) т. А (4; 2,85)
P(x)max = 600 P(x)max = 664
Pгр = 600
|
|
G9 = G8, x2 £ 2 G10= G8, x2 ³ 3
т. А (4,9; 2) решений нет
P(x)max = 638,2 Pгр = -¥
Получили целочисленное решение, при котором x1=2, x2=4, а P(x)max = 638.
VIII . ТРАНСПОРТНАЯ ЗАДАЧА.
| 1+а11 | 1+а12 | 1+а13 | 1+а14 |
| 1+а21 | 1+а22 | 1+а23 | 1+а24 |
| 1+а31 | 1+а32 | 1+а33 | 1+а34 |
За вектор объёмов производства примём вектор объёмов ресурсов:
(b1,b2,b3)
а за вектор объёмов потребления принять:
(lс1,lс2,lс3,lс4),
где
3 2 7 6
А = 1 4 1 5 – матрица транспортных издержек
4 3 5 1
b = 90 -- вектор объёма ресурсов
l=(b1+b2+b3) / (c1 + c2 + c3 + c4) = (198+90+140) / (27+39+18+20) = 4
с= (27*4; 39*4; 18*4; 20*4) -- вектор объёма потребления
с=(108; 156; 72; 80)
В нашей задаче 4 потребителя и 3 поставщика, причём суммарный объем поставок равный 428 превышает суммарный объем потребления равный 416. Поэтому для решения задачи ведём дополнительно ещё одного потребителя, с потреблением равным 12.
Имеем:
| p\q | q1 = 3 | q2 = 6 | q3 = 2 | q4 = 5 | q5 = 0 | -- |
| p1 = 0 | -- | -- | -- | |||
| p2 = -2 | -- | -- | -- | |||
| p3 = 1 | -- | -- | ||||
| -- |
Для заполненных клеток pi + qj = Cij
Проверка на оптимальность
Для незаполненных клеток Dij=pi + qj - cij
D13 = -4 D14 = -6 D15 = -1
D22 = -4 D24 = -7 D25 = -3
D31 = 0 D33 = -1
Т.к. все Dij £ 0, то мы нашли оптимальное решение:
90 108 -- -- --
Xопт = 18 -- 72 -- --
-- 48 -- 80 12
Rmin = 90*3 + 108*2+ 18 + 72 + 48*3 + 80 = 3840