Прикладная математика (стр. 8 из 14)
jj(xj) = xj2 + 5xj + 2
(33)т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3 y1
1 2 4 1 5 2 1 3 2 2
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем
F1 (x = y2), F2 (x = y3), ..., Fk (x = yk+1), ... и соответственно находим
1 (x= y2), 2 (x = y3 ), ..., ` k (x = yk+1), ...Положим k = 1. Согласно (27) имеем
(34)Учтем, что согласно (28) параметр состояния x = у2 может принимать целые значения на отрезке
0
у2 d2 + d30
y2 2 + 4т.е.
у2 = 0, 1, 2, 3, 4, 5, 6.
При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29)
0
х1 3 + у2Однако, на первом этапе объем производства х1 не может быть меньше единицы, так как спрос d1 = 3, а исходный запас у1 = 2. Более того, из балансового уравнения
х1 + у1 - d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния x= у2 соотношением
x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1 (35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому
F1(x = y2) = W1 (x1, y2)
| x = y2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
 F1 (x = y2) | 8 | 17 | 28 | 41 | 56 | 73 | 92 |
| x1(x=y2) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию
F2(x = y3) с помощью соотношения (32)
(37)Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно (25), в пределах
0 £ x2£ d2 + y3 или 0 £ x2£ 2 + y3 (38)
где верхняя граница зависит от параметра состояния x = у3, который, согласно (15), принимает значения на отрезке
0 £ y3£ d3 , т.е. 0 £ y3£ 4 (39)
а аргумент у2 в последнем слагаемом справа в соотношении (37) связан с х2 и у3 балансовым уравнением
x2 + y2 - d2 = y3
откуда следует
y2 = y3 + d2 - x2 = y3 + 2 - x2 (40)
Придавая параметру состояния различные значения от 0 до 4, будем последовательно вычислять W2 (x2, x), а затем определять F2(x ) и
2(x ).Положим, например x = у3 = 2. Тогда, согласно (38),
0 £ x2£ 4,
т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (40):
у2 = 4 - х2
Последовательно находим:
если x2 = 0, то y2 = 4-0 = 4, W2 (0,2) = 02 + 5×0 + 2 + 3×2 + F1(4) = 8 + 56 = 64,
x2 = 1, y2 = 4-1 = 3, W2 (1,2) = 12 + 5×1 + 2 + 3×2 + F1(3) = 14 + 41 = 55,
x2 = 2, y2 = 4-2 =2, W2 (2,2) = 22 + 5×2 + 2 + 3×2 + F1(2) = 22 + 28 = 50,
x2 = 3, y2 = 4-3 = 1, W2 (3,2) = 32 + 5×3 + 2 + 3×2 + F1(1) = 32 + 17 = 49*,
x2 = 4, y2 = 4-4 = 0, W2 (3,2) = 42 + 5×4 + 2 + 3×2 + F1(0) = 44 + 8 = 52.
| x= у3 | 0 | 1 | 2 | 3 | 4 |
| F2 (x= y3) | 24 | 36 | 49 | 63 | 78 |
 (x= y3) | 2 | 2 | 3 | 3 | 4 |
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 (x = y4):
Вычисляем значение функции состояния только для одного значения аргумента x = у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем
F3 (x = y4) = min W3 (x3,0) = min (80, 71, 65, 62, 62) = 62,
x3
причем минимум достигается при двух значениях переменной х3, равных
`
3 (x = y4 = 0) = 3 или ` 3 (x = y4 = 0) = 4.Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна
= 3 или 
= 4.Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции
= 3.Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что
х3 + у3 - d3 = y4
или
3 + у3 - 4 = 0,
откуда
у3 = 1.
Из таблицы (3) значений
находим 
Аналогично, продолжая двигаться в обратном направлении и учтя, что
х2 + у2 - d2 = y3
 |  | xk | yk = yk+1 + dk - xk | Wk(xk, yk+1) =jk(xk) + hkyk+1 + Fk-1(yk) | |
| 0 £ y3£ d3 | x = y3 | 0 £ x2£ d2 + y3 | x2 | y2 = y3 + d2 - x2 | W2(x2, y3) = a  + bx + c + h2y3 + F1(y2) |
| 0 £ y3£ 4 | x = y3 | 0 £ x2£ 2 + y3 | x2 | y2 = y3 + 3 - x2 |  |
| y3 = 0 | 0 £ x2£ 2 | x2 = 0 x2 = 1 x2 = 2 | y2 = 2-0 = 2 y2 = 2- 1 = 1 y2 = 2-2 = 0 | W2(0;0) = 02 + 5×0 + 2 + 3×0 + F1(2) =2+28 =30 W2(1;0) = 12 + 5×1 + 2 +3×0 + F1(1)=8+17 =25 |
