Результаты оптимизации:

z₁^*(a₁)=3,875a₁; x₁^* = 0;

z₂^*(a₂)=3,75a₂; x₂^* = 0;

z₃^*(a₃)=3,5a₃; x₃^* = 0;

z₄^*(a₄)=3a₄; x₄^* = a₄.

Определим количественное распределение средств по годам.

Т.к. а₁=а=1000, х₁^*=0, получаем а₂=0,5а₁-0,4х₁=500.

х₂^*= 0, а₃= 0,5а₂ - 0,4х₂ = 250

х₃^*= 0, а₄ = 0,5а₃-0,4х₃=125

х₄^*= 0, а₄ = 125

Представим распределение средств в виде табл. 4

Таблица 4

	1 год	2 год	3 год	4 год
Предприятие 1	0	0	0	125
Предприятие 2	1000	500	250	0

При таком распределении средств за 4 года будет получен доход, равный

z_max^* = z₁^*(a₁) = 3,875*1000 = 3875

Задача 2.

Пусть имеется склад вместимости В с начальным запасом V некоторого продукта, цены на который подвержены сезонным изменениям.

В начале i-го сезона часть продукта Y_i можно продать по цене P_i и в конце сезона закупить X_i этого продукта по цене C_i . Образовавшийся на складе запас хранится до следующего сезона. Найти политику продажи-покупки, максимизирующую суммарный доход за N сезонов.

Если пренебречь затратами на хранение, то задачу можно свести к максимизации линейной функции

при условиях 

0<=Y₁<=V, X₁>=0, V₁=V-Y₁+X₁<=B;

0<=Y₂<=V₁, X₂>=0, V₂=V₁-Y₂+X₂<=B;

0<=Y₃<=V₂, X₃>=0, V₃=V₂-Y₃+X₃<=B.

Таким образом, получена задача линейного программирования с 2N неизвестными и 4N ограничениями, которую можно решить при фиксированном значении V.

Рассмотрим задачу с других позиций, для чего введем обозначения:

- k - номер сезона, отстоящего на k шагов до конца N-шагового процесса (k=1 соответствует последнему сезону, k=2 - предпоследнему, k=N - первому);

- Y, X - объемы продажи-покупки в соответствующем сезоне (в первом из k оставшихся сезонов);

- P_k , C_k - цены продажи-покупки в соответствующем сезоне;

- F_k(V) - максимальный доход в k-шаговом процессе при начальном запасе V;

-Y_k(V), X_k(V) - оптимальные объемы продажи-покупки на первом шаге k-шагового процесса с начальным запасом V.

В случае одношагового процесса (с таковым мы столкнемся, когда доберемся до последнего шага, и к тому же будем знать уровень запаса V перед этим шагом)

F₁(V) = max{ P₁*Y - C₁*X } ,

где область максимизации определяется условиями 0<=Y<=V ; X>=0 .

Очевидно, что максимум достигается при Y = V и X=0 (естественно при завершении деятельности по купле-продаже продать весь запас и ничего не покупать), т.е. F₁(V) = P₁V ; Y₁(V) =V ; X₁(V) = 0 .

Обратимся к случаю k-шагового процесса при k > 1, повторив традиционные рассуждения с позиций известного принципа оптимальности Р.Беллмана. Очевидно, что доход в k - шаговом процессе складывается из дохода на первом шаге {P_k*Y - C_k*X} и дохода на оставшихся k-1 шагах. Если мы желаем действовать оптимально, то обязаны руководствоваться принципом оптимальности: независимо от начального состояния (запаса V) и начального поведения (объемов Y, X продажи-покупки на первом шаге) дальнейшая политика должна быть оптимальной, исходя из возникающего состояния (запаса V-Y+X). Тогда доход на оставшихся k-1 шагах будет равен

F_k-1(V-Y+X}

и

F_k(V) = max{ P_k*Y - C_k*X + F_k-1(V-Y+X) } , k<=2,…,N ,

где область максимизации определяется условиями:

0<=Y<=V ; X>=0 ; V -Y + X<=B .

Очевидно, что множество планов - выборов для начального поведения (область максимизации) при любом k – это многоугольник с координатами вершин, линейно з ависящими от V.

Учитывая линейность по V функции F₁(V) = P₁V, при поиске F₂(V) сталкиваемся с максимизацией функции, линейной по X и Y , над указанным множеством планов, т.е. с задачей линейного программирования c экстремумами в вершинах множества.

Аналогичное явление наблюдается при любом k>1. Cоответственно, рекуррентные соотношения упрощается к виду:

Так исходная задача линейного программирования с 2N неизвестными сведена к N элементарным линейным программам с двумя неизвестными. Более того, здесь мы имеем решение при произвольных V и B.

Решение задачи

Пусть N = 5 и цены определены согласно табл. 5.

Таблица 5

Сезон	1	2	3	4	5
Продажная цена (Р)	7	6	4	4	8
Закупочная цена (С)	6	7	5	3	5

Решение задачи дает:

отсюда искомый максимум дохода в 5-шаговом процессе при начальном запасе V равен F₅(V)=7V+5B и оптимальная политика по шагам определяется следующей последовательностью действий .

1-й этап.

Объем продажи = Y₅(V)=V - весь запас.

Объем закупок = X₅(V) = 0 или B - ничего или полный склад.

2-й этап.

Объем продажи = Y₄(0 или B)=0 или B - весь запас, если он есть.

Объем закупок = X₄(V)=0 - ничего не покупать .

3-й этап..

Объем продажи = Y₃(0)=0 - можно все продать, но нечего.

Объем закупок = X₃(0)=0 - ничего не покупать.

4-й этап..

Объем продажи = Y₂(0)=0 - продать запас, но его нет.

Объем закупок = X₂(0)=B - закупить полный склад.

5-й этап..

Объем продажи = Y₁(B) =B - продать весь запас.

Объем закупок = X₁(V)=0 - ничего не покупать.

Оптимальные решения сведены в табл. 6.

Таблица 6

Сезон	1	2	3	4	5
Объем продажи	Y5(V)=V продать весь запас	Y4(0 или B)=0 ничего или B весь запас, если он есть	Y3(0)=0 можно все продать, но нечего	Y2(0)=0 продать запас, но его нет	Y1(B) =B продать весь запас
Объем закупок	X5(V) = 0 или B ничего или полный склад	X4(V)=0 ничего не покупать	X3(0)=0 ничего не покупать	X2(0)=B закупить полный склад	X1(V)=0 ничего не покупать

Таким образом, для построения оптимальной политики использован подход, типичный для решения всех подобных задач.