Линейное программирование

   Будем считать, что величины запасов к  началу первого месяца y₁ задана, а к концу последнего y_n+1  = 0.

   Задача  состоит в том, чтобы найти  план производства  (x₁, x₂, ..., x_n) и план хранения запасов (y₂, y₃,….,y_n), компоненты которых удовлетворяют условиям материального баланса

   

x_j + y_j - d_j = y_j+1 j = 1,n 

и минимизируют суммарные затраты за весь планируемый  период

                   min

   причем  по смыслу задачи x_j ≥0  y_j≥0,  j= 1,n 

   Решение задачи осуществляется методом динамического  программирования.

За параметр состояния S, характеризующий решение в каждом месяце, примем запас в конце k-ого месяца

S = y_k+1,

a функцию состояния F_k(S) определим как минимальные затраты на первые k месяцев

F_k(S) =

где минимум  берется по неотрицательным целым  значениям x₁,...,x_k удовлетворяющим условиям:

x_j + y_j - d_j = y_j+1 , j = 1,2,…,k-1

x_k + y_k – d_k = S 

Учитывая, что

=    f_k (x_k, y_k+1) +  

и, так  как величина запаса y_k к концу (k-1) периода, как видно из уравнения равно

  y_k = s + d_k -x_k

  

мы приходим к рекуррентному соотношению

F_k(S) =    f_k (x_k,s) + F_k-1(s+d_k-x_k)     ,

где минимум  берется по единственной переменной x_k , которая может изменяться в пределах

0 ≤  x_k ≤ d_k+s 

принимая  целые значения, причем верхняя граница  зависит от параметра состояния, изменяющегося в пределах 

0 ≤  s ≤ d_k+1+d_k+2+…+d_n 

а индекс k может принимать значения

k = 2,3,…,n 

Если k=1, то

F₁(s=y₂)= f₁(x₁,s),где

x₁ = s+d₁-y₁

0 ≤  s ≤ d₂+d₃+…+d_n, 

т.е. на начальном этапе при заданном значении y₁ исходного запаса каждому значению параметра s отвечает только одно значение переменной x₁. 

Затраты на производство (закупку) x_j-ых единиц изделия в j-ом месяце имеют следующий вид:

φ_j(x_j) = ax_j² + bx_j + c 

Затраты на хранение запаса y_j+1 , переходящего из этапа j  в этап j+1

h_j*y_j+1,

где h_j – затраты на хранение единиц в j-ом месяце.  

Тогда затраты  на производство и хранение в j-ом месяце равны:

f_j(x_j,y_j+1) = φ_j(x_j)+h_jy_j+1 = ax_j² + bx_j + c + h_jy_j+1

 
Рекуррентное отношение в этом случае принимает вид:

F_k(s = y_k+1) =     ax_k² + bx_k + c + h_ks + F_k-1 (y_k)

Если k=1, то

F₁(s = y₂) = (ax₁² + bx₁ + c + h₁y₂)

Рассмотрим  задачу для трёх месяцев (n=3). Пусть заказ на изделия на каждый месяц имеет соответственно следующие значения d₁=2, d₂=2, d₃=2. В конце третьего месяца запас на изделия должен быть равен нулю, т.е. y₄=0. К началу первого месяца на складе имеется 2 изделия, т.е. y₁=2. Затраты на хранение единицы изделия для каждого месяца составляют соответственно h₁=1, h₂ = 2, h₃ = 4. Затраты на производство x_j изделий в каждом месяце φ_j(x_j) = x_j² + x_j + 5. Требуется определить, сколько единиц изделий  каждом месяце нужно производить и хранить (для удовлетворения заказов на последующие месяцы), чтобы затраты на производство и хранение изделий за все эти три месяца были наименьшими. 

Исходные  данные задачи можно кратко записать одной строкой: 

     d₁ d₂ d₃  a b c  h₁ h₂ h₃      y₁

           2 2 2  1 1 5  1 2 4         2

  Воспользовавшись  рекуррентными соотношениями, последовательно  вычисляем  F₁ (S = y₂),  F₂ (S = y₃), F₃ (S = y₄ = 0). Результаты вычислений представляем в виде таблиц.

Положим k = 1.

   x₁ = s + 0; 0 ≤ s ≤ 4; = x₁² + x₁ + 5 + y₂

   Результаты  вычисления представлены в Таблице 1

                                                                                      Таблица 1

 

Переходим ко второму этапу. Полагая k=2, вычисляем значения функции

    F₂(s=y₃)

   F₂(s=y₃)=   (x₂²+x₂+5) + h₂s + F₁(y₂) 

0 ≤  x₂ ≤ 4; 0 ≤ s ≤ 2; y₂ = s + 2 + x₂ 

Результаты вычисления F₂(s=y₃) представлены в таблице 2, где с учетом ранее сказанного, каждое значение рекуррентного соотношения представлено в виде суммы трех слагаемых. Кроме значений рекуррентного соотношения, в таблице включены оптимальные значения x₂(s) изделий и оптимальные значения рекуррентного соотношения F₂(s), соответствующие значению запаса s. 
 
 
 
 
 
 

   Таблица 2

     

Переходим к последнему этапу (K=3). Поскольку на последнем этапе S = y₄ = 0 и y₃ = 2 - x₃ ; 0 ≤ x₃ ≤ 2, то таблица для вычисления значений рекуррентного соотношения

   F₃(s=0)=   (x₃²+x₃+5) + 0 + F₂(y₃)

для этого  этапа имеет вид, представленный в Таблице 3

Таблица3

 

   Таким образом, минимум целевой функции  затрат на производство изделий и  хранение их запасов на три месяца равен 26 и достигается при значении производства в третьем месяце x₃ = 2, т.е. задача имеет 1 решение.

   Найдем  это решение, последовательно двигаясь от последнего этапа (третьего месяца) к первому, пользуясь вычислениями рекуррентных соотношений в Таблице 3 и условием баланса. При x₃ = 2 при значении K=3 с учетом исходных данных получаем:

y₃ = s+d₃-x₃

y₃ = 0+2-2=0

Из Таблица2 находим, что для y₃ = 0 (s=0) x₂ = 1

При K=2 получаем:

y₂ = 1+2-2 = 1

Из Таблицы 1 находим, что для y₂ = 1, x₁ = 1

y₁ = y₂+d₁-x₁= 1+2-1 = 2, что совпадает с исходным значением.

Итак, оптимальный  план производственных запасов имеет  вид:

x₁ = 1; y₁ =2;  x₂ = 1;  y₂ = 1;  x₃ = 2;  y₃ = 0

и минимальные  общие затраты составляют 26 единиц.

x* = (1;1;2) – будем хранить

y* = (2;1;0) – будем производить

F_min = 26 (д.е.) 

     Проверим  полученный результат. Для этого  по исходным данным и найденному плану проверяем выполнение условий баланса для каждого месяца. Для первого месяца находим x₁+y₁-d₁=y₂, 1+2-2=1; для второго месяца x₂+y₂-d₂=y₃, 1+1-2=0; для третьего месяца x₃+y₃-d₃= y₄ = 0, 2+0-2=0. Важно проверить равенство φ(x₁) + φ(x₂) + φ(x₃) + h₁y₂ + h₂y₃ = F₃(y₄=0),

              7      +    7    +    11  +   1   +    0   = 26

     7. Анализ доходности  и риска финансовых  операций

     Финансовой  называется операция, начальное и  конечное состояния которой имеет денежную оценку и цель проведения которой заключается в максимизации дохода – разности между конечной и начальной оценками.

     Почти всегда финансовые операции проводятся в условиях неопределенности, и поэтому из результат невозможно предсказать заранее. Поэтому финансовые операции рискованны, т.е. при их проведении возможны как прибыль, так и убыток (или не очень большая прибыль по сравнению с той, на что надеялись проводившие эту операцию).

     Наиболее  распространенный способ оценки операции с точки зрения её доходности и риска – представление дохода операции как случайно величины и оценки риска операции как среднего квадратического отклонения этого случайного дохода.

     Исходные  данные:

     N = 17, берем данные с номерами N, N+1, N+2, N+3, т.е. данные с номерами 17,18,19,20:

17. (0,1/2) (4,1/4) (8,1/8) (32, 1/2)

18. (-6,1/2) (-4,1/4) (-2,1/8) (10, 1/8)

19. (0,1/4) (8,1/4) (12,1/3) (24, 1/6)

20. (-6,1/4) (-2,1/4) (0,1/3) (-6, 1/6) 

     Следовательно, операции будут: 
 

           Q₁: 
 

       

     Q₂: