3. Показателем эффективности является суммарный эффект W, достигаемый на всех m этапах 
, wi – эффект, достигаемый на i -ом этапе.
В основе метода лежит принцип оптимальности: Каково бы ни было состояние системы Si в начале i -го этапа, на этом этапе следует принять такое решение, чтобы эффект, достигаемый на i -ом этапе в сумме с оптимальным эффектом на всех последующих этапах, был максимальным. Его представляют в виде основного функционального уравнения Беллмана:
, (9)
где Wi(Si) – условный оптимальный эффект на i-ом и всех последующих этапах до конца процесса при условии, что в начале i-го этапа система находилась в состоянии Si;
ui – условное оптимальное решение на i-ом этапе;
Ui – множество всех возможных решений (ОДР);
Si+1 – состояние системы в конце i-го и в начале i+1-го этапа.
Для последнего m -го этапа
. (10)
2.2. Оптимальное распределение ресурсов
Постановка задачи
Имеется некоторый начальный капитал К0. В течение m этапов его нужно распределять между двумя предприятиями так, чтобы получить максимальный суммарный эффект. На каждом этапе имеющийся капитал Ki необходимо распределить: Xi – вложение в первое предприятие, Yi – вложение во второе предприятие; Ki=Xi+Yi, Yi=Ki - Xi. Эффект, достигаемый на первом предприятии f(Xi) = a×Xi, на втором – g(Yi) = b×Y i. Остаток средств после завершения работ i-го этапа на первом предприятии j (Xi) = a ×Xi, на втором – y (Yi) = b ×Y i.
Решение задачи
В задаче распределения ресурсов состояние системы – это располагаемый капитал Si «Ki, решение (управление) – это распределение средств ui «Xi (Yi=Ki - Xi).
wi(KiXi)= f(Xi)+ g(Yi) = a×Xi,+ b×Y i= a×Xi,+ b× (Ki - Xi)= b×Ki+ (a- b)× Xi
Ki+1=j(Xi)+ y(Yi)= a×Xi+b×Y i = a×Xi+b× (Ki - Xi) = b×Ki+(a-b)× Xi
С учётом сказанного, основные функциональные уравнения Беллмана для задачи распределения ресурсов имеет вид:
, (11)
. (12)
Так как на последнем этапе оптимальное решение зависит только от этого этапа, задачу решают с конца. Находят условное оптимальное решение на m - ом, m-1 –ом и т.д. 1 – ом этапах. Решения являются условными, так как заранее неизвестно какими ресурсами мы будем располагать на всех последующих этапах, кроме первого. Поэтому вторая часть решения сводится к последовательному нахождению ресурсов и их распределения, начиная с первого этапа.
Пример 2.
Дано: K 0 = 20; a = 1; b = 2; a = 0,9; b = 0,5.
Решение:
f (xi) = 1× xi = xi; g (yi) = b×yi = 2× yi = 2×(Ki – xi) = 2× Ki - 2× xi;
j(xi) = a× xi = 0,9× xi; y(yi) = b× yi = 0,5× yi = 0,5×(Ki – xi) = 0,5× Ki – 0,5× xi;
w (Ki,xi) = f (xi) + g (yi) = xi +2× Ki - 2× xi = 2× Ki -1× xi;
Ki +1 = j(xi) + y(yi) = 0,9× xi + 0,5× Ki – 0,5× xi = 0,5× Ki + 0,4× xi.
Условно оптимальное распределение ресурсов (звёздочкой отмечены оптимальные значения).
i = m = 4: W 4(K 4) = 
{ w (K 4, x 4)} = {2× K 4- x 4)} = 2× K 4,
х *4 = 0, у *4 = К 4.
i =3: W 3(K 3) = 
{ w (K 3, x 3) + W 4(K 4)} = {2× K 3- x 3) +2×(0,5× K 3+0,4× х 3)} = = 
{3× K 3 - 0,2× x 3 } = 3× K 3.
х *3 = 0, у *3 = К 3.
i =2: W 2(K 2) = 
{ w (K 2, x 2) + W 3(K 3)} = {2× K 2- x 2) + 3×(0,5× K 2+0,4× х 2)}= = 
{3,5× K 2 + 0,2× x 2 } = 3,7× K 2.
х *2 = К 2, у *2 = 0.
i =1: W 1(K 1) = 
{ w (K 1, x 1) + W 2(K 2)} = {2× K 1- x 1) + 3,7×(0,5× K 1+0,4× х 1)}= = 
{3,85× K 1 + 0,48× x 1 } = 4,33× K 1 = 86,6.
х *1 = К 1, у *1 =0.
Оптимальное распределение ресурсов:
К 1= К 0=20 ® х *1=20, у *1=0 ®
К 2=0,5× K 1 + 0,4× x 1= 18 ® х *2=18, у *2=0 ®
К 3=0,5× K 2 + 0,4× x 2 =16,2 ® х *3=0, у *3=16,2 ®
К 4=0,5× K 3 + 0,4× x 3 =8,1 ® х *4=0, у *4=8,1.
Увеличение пропускной способности по направлениям:
х сумм = 20 + 18 = 38, у сумм = 16,2 + 8,1 = 24,3,
f (х сумм) = 38; g (у сумм) = 2× 24,3 = 48,6.
Проверка. Общее увеличение пропускной способности
W1(K1) = 38 + 48,6 = 86,6.
3 Решить транспортную задачу методом потенциалов.
Варианты заданий.
ЗАДАЧА №1
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №2
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №3
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №4
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №5
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №6
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №7
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №8
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №9
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №10
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №11
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №12
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №13
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №14
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №15
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №16
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №17
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №18
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №19
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №20
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №21
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №22
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №23
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №24
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №25
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №26
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №27
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №28
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №29
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №30
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |
ЗАДАЧА №31
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А3 | |||||
| Объём заказов |
ЗАДАЧА №32
| Пункты отправления | Пункты назначения | Объём поставок | |||
| В 1 | В 2 | В 3 | В 4 | ||
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| Объём заказов |