Решение задач линейного программирования различными методами (стр. 3 из 3)
Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.
Индивидуальное задание.
В таблице 11 приведены значения gi(x) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x.
Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f4(100) выпуска продукции был максимальным. Для упрощения вычислений значения xпринимать кратными 20 тыс. гр.
Таблица 11
| Предприятие | Прирост выпуска продукции, тыс. гр. | Средства c, тыс. гр. | Номер варианта | ||||
| 20 | 40 | 60 | 80 | 100 | |||
| 1 | G1(x) | 11 | 21 | 40 | 54 | 62 | 6 |
| 2 | G2(x) | 13 | 20 | 42 | 45 | 61 | |
| 3 | G3(x) | 12 | 22 | 34 | 55 | 60 | |
| 4 | G4(x) | 10 | 27 | 33 | 57 | 69 | |
Функциональное уравнение Беллмана для рассматриваемой задачи
f1(x)=max[g1(x)]=g1(x) – для первого предприятия;
- для остальных предприятий.
Решение задачи оптимального распределения средств между предприятиями методом динамического программирования
Таблица 12
| Средства с, тыс. гр. | Предприятие | |||
| 1 | 2 | 3 | 4 | |
| G1(x) | G2(x) | G3(x) | G4(x) | |
| 20 | 11 | 13 | 12 | 10 |
| 40 | 21 | 20 | 22 | 27 |
| 60 | 40 | 42 | 34 | 33 |
| 80 | 54 | 45 | 55 | 57 |
| 100 | 62 | 62 | 60 | 69 |
Таблица 13
| X1*(c) | 20 | 40 | 60 | 80 | 100 |
| F1(c) | 11 | 21 | 40 | 54 | 62 |
Таблица 14
| x С | 0 | 20 | 40 | 60 | 80 | 100 | F2(c) | X2*(c) |
| 20 | 0+13 | 12+0 | 13 | 0 | ||||
| 40 | 0+24 | 12+13 | 22+0 | 25 | 20 | |||
| 60 | 0+42 | 12+24 | 22+13 | 34+0 | 42 | 0 | ||
| 80 | 0+45 | 12+42 | 22+24 | 34+13 | 55+0 | 55 | 80 | |
| 100 | 0+67 | 12+45 | 22+42 | 34+24 | 55+3 | 60+0 | 68 | 80 |
Таблица 15
| x С | 0 | 20 | 40 | 60 | 80 | 100 | F3(c) | X3*(c) |
| 20 | 0+13 | 10+0 | 13 | 0 | ||||
| 40 | 0+29 | 10+13 | 27+0 | 27 | 40 | |||
| 60 | 0+42 | 10+25 | 27+13 | 33+0 | 42 | 0 | ||
| 80 | 0+55 | 10+42 | 27+25 | 33+13 | 57+0 | 57 | 80 | |
| 100 | 0+68 | 10+55 | 27+42 | 33+25 | 52+13 | 69+0 | 69 | 40 |
Таблица 16
| С | X1*(c) | F1(c) | X2*(c) | F2(c) | X3*(c) | F3(c) | X4*(c) | F4(c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 20 | 20 | 11 | 20 | 13 | 0 | 13 | 0 | 13 |
| 40 | 40 | 21 | 20 | 24 | 20 | 25 | 40 | 27 |
| 60 | 60 | 40 | 60 | 42 | 0 | 42 | 0 | 42 |
| 80 | 80 | 54 | 80 | 45 | 80 | 55 | 80 | 57 |
| 100 | 100 | 62 | 20 | 67 | 80 | 68 | 40 | 69 |
Итак, из таблицы 16 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. При этом четвертому предприятию нужно выделить 40 тыс. грн., а остальным 60 тыс. грн.
Оптимальное распределение оставшихся 60 тыс. грн. между 3-мя предприятиями обеспечит прирост продукции на сумму 42 тыс. грн., при условии, что 3-му предприятию не будут выделены средства. Остается 60 тыс. грн., которые надо распределить между 2-мя предприятиями. Выделив всю оставшуюся сумму (60 тыс. грн.) второму, прибыль составит 42 тыс. грн. первому предприятию средств не остается.
Максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. и будет получен, если первому предприятию не выделять средств, второму — 60 тыс. грн., третьему не выделять, а четвертому — 40 тыс. грн.
Это решение можно записать в виде:
X*=(0,0,60,40); f*=f4(100)=69 тыс. гр.