Задача о загрузке самолета

Материал из Supply Chain Management Encyclopedia

(Различия между версиями)
Перейти к: навигация, поиск
(Принцип оптимальности Беллмана.)
 
(25 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
'''English: [http://scm.gsom.spbu.ru/Load-planning_problem Load-planning problem]'''
 +
Для описания постановки задачи и метода решения задачи о загрузке самолета используются метод динамического программирования и принцип оптимальности Беллмана
Для описания постановки задачи и метода решения задачи о загрузке самолета используются метод динамического программирования и принцип оптимальности Беллмана
Строка 145: Строка 147:
|}
|}
 +
''Табл.1. Таблица для первой итерации''
-
<math>\,
+
{| border="1"
-
\hline
+
| align="center" | <math>\,\xi</math>|| align="center" | <math>\,F_{2}(\xi )</math> || align="center" | <math>\, x_{2}^{0}(\xi)</math>
-
$\xi $ & $F_{1} (\xi )$ & $x_{1}^{0} (\xi )$ \\ \hline
+
|-
-
0 & $F_{1} \eqref{GrindEQ__0_}$ & $x_{1}^{0} \eqref{GrindEQ__0_}$ \\ \hline
+
| align="center" |<math>\, 0 </math> || align="center" | <math>\, F_{2}(0)</math>  || align="center" | <math>\, x_{2}^{0}(0)</math>
-
1 & $F_{1} \eqref{GrindEQ__1_}$ & $x_{1}^{0} \eqref{GrindEQ__1_}$ \\ \hline
+
|-
-
$\vdots $ & $\vdots $ & $\vdots $ \\ \hline
+
| align="center" |<math>\, 1 </math> || align="center" | <math>\, F_{2}(1)</math>  || align="center" | <math>\, x_{2}^{0}(1)</math>
-
$b-1$ & $F_{1} (b-1)$ & $x_{1}^{0} (b-1)$ \\ \hline
+
|-
-
$b$ & $F_{1} (b)$ & $x_{1}^{0} (b)$ \\ \hline
+
| align="center" | <math>\, \ldots </math>|| align="center" | <math>\, \ldots </math> || align="center" | <math>\, \ldots </math>
-
</math>
+
|-
-
 
+
| align="center" | <math>\, b-1 </math> || align="center" | <math>\, F_{2} (b-1) </math> || align="center" | <math>\, x_{2}^{0} (b-1)</math>
-
\textit{Табл.1. Таблица для первой итерации}
+
|-
-
 
+
| align="center" | <math>\, b </math> || align="center" | <math>\, F_{2} (b)</math> || align="center" | <math>\,x_{2}^{0}(b)</math>
-
 
+
|}
-
 
+
-
\begin{tabular}{|p{0.3in}|p{0.6in}|p{0.6in}|} \hline
+
-
$\xi $ & $F_{2} (\xi )$ & $x_{2}^{0} (\xi )$ \\ \hline
+
-
0 & $F_{2} \eqref{GrindEQ__0_}$ & $x_{2}^{0} \eqref{GrindEQ__0_}$ \\ \hline
+
-
1 & $F_{2} \eqref{GrindEQ__1_}$ & $x_{2}^{0} \eqref{GrindEQ__1_}$ \\ \hline
+
-
$\vdots $ & $\vdots $ & $\vdots $ \\ \hline
+
-
$b-1$ & $F_{2} (b-1)$ & $x_{2}^{0} (b-1)$ \\ \hline
+
-
$b$ & $F_{2} (b)$ & $x_{2}^{0} (b)$ \\ \hline
+
-
\end{tabular}
+
-
 
+
-
\textit{}
+
-
 
+
-
\textit{Табл.2. Таблица для второй итерации.}
+
-
 
+
-
 
+
-
 
+
 +
''Табл.2. Таблица для второй итерации''
Для применения метода динамического программирования необходимо, чтобы выполнялись условия:
Для применения метода динамического программирования необходимо, чтобы выполнялись условия:
-
  процесс поиска оптимальных решений должен допускать интерпретацию как многошаговый процесс принятия решений;
+
* процесс поиска оптимальных решений должен допускать интерпретацию как многошаговый процесс принятия решений;
-
  для каждого шага должно быть определено множество параметров состояния $\xi $, которое не зависит от номера шага;
+
* для каждого шага должно быть определено множество параметров состояния <math>\, \xi </math>, которое не зависит от номера шага;
-
  оптимальное решение на шаге \textit{к }зависит только от текущего состояния и не зависит от предыстории процесса.
+
* оптимальное решение на шаге <math>\, k </math> зависит только от текущего состояния и не зависит от предыстории процесса.
 +
==Задача о загрузке самолета==
 +
Самолет загружается предметами <math>\, N </math> различных типов. Каждый предмет типа <math>\, i </math> имеет вес <math>\, F_{i} </math> и страховую стоимость <math>\, v_{i} </math>, (<math>\,i=\overline{1,N}</math>). Максимальная грузоподъемность самолета равна <math>\, W</math>. Требуется определить максимальную стоимость груза, вес которого не должен превышать максимально допустимой грузоподъемности самолета. Для определенности предположим, что <math>\, W = 5 </math> и всего имеются три типа предметов, сведения о которых приведены в таблице:
-
\textbf{Задача о загрузке самолета}
+
{| border="1"
 +
| align="center" | <math>\, \, \, \, i \, \, \, </math>|| align="center" | <math>\, \, \, \, F_{i}\, \, \, </math> || align="center" | <math>\, \, \, \, v_{i} \, \, \, </math>
 +
|-
 +
| align="center" |<math>\, 1 </math> || align="center" | <math>\, 2 </math>  || align="center" | <math>\, 65 </math>
 +
|-
 +
| align="center" |<math>\, 2 </math> || align="center" | <math>\, 3 </math>  || align="center" | <math>\, 80 </math>
 +
|-
 +
| align="center" | <math>\, 3 </math>|| align="center" | <math>\, 1 </math> || align="center" | <math>\, 30 </math>
 +
|}
 +
Рассмотрим задачу в общей постановке. Обозначим количество предметов типа <math>\, i </math> через <math>\, k_{i} </math>. Тогда задача загрузки самолета может быть записана в виде:
 +
<math>\, \max z=\max (v_{1} k_{1} +v_{2} k_{2} +...+v_{N} k_{N} ) </math>
-
Самолет загружается предметами \textit{N }различных типов. Каждый предмет типа $i$\textit{ }имеет вес $F_{i} $ и страховую стоимость $v_{i} $, ($i=\overline{1,N}$). Максимальная грузоподъемность самолета равна \textit{W. }Требуется определить максимальную стоимость груза, вес которого не должен превышать максимально допустимой грузоподъемности самолета. Для определенности предположим, что \textit{W }= 5 и всего имеются три типа предметов, сведения о которых приведены в таблице:
+
<math>\, \left\{\begin{array}{l} {F_{1} k_{1} +F_{2} k_{2} +...+F_{n} k_{n} \le W,} \\ {k\ge 0,\, \, i=\overline{1,N,}} \end{array}\right. </math>
-
 
+
-
 
+
-
 
+
-
\begin{tabular}{|p{0.1in}|p{0.3in}|p{0.3in}|} \hline
+
-
\textit{i} & $F_{i} $ & $v_{i} $ \\ \hline
+
-
1 & 2 & 65 \\ \hline
+
-
2 & 3 & 80 \\ \hline
+
-
3 & 1 & 30 \\ \hline
+
-
\end{tabular}
+
-
 
+
-
 
+
-
 
+
-
Рассмотрим задачу в общей постановке. Обозначим количество предметов типа $i$\textit{ }через $k_{i} $. Тогда задача загрузки самолета может быть записана в виде:
+
-
 
+
-
\[\max z=\max (v_{1} k_{1} +v_{2} k_{2} +...+v_{N} k_{N} )\]
+
-
 
+
-
\[\left\{\begin{array}{l} {F_{1} k_{1} +F_{2} k_{2} +...+F_{n} k_{n} \le W,} \\ {k\ge 0,\, \, i=\overline{1,N,}} \end{array}\right. \]
+
-
 
+
-
где $k$ -- целые.
+
-
 
+
 +
где <math>\, k </math> - целые.
Если бы возможно было бы отбросить требование целочисленности, то это задача линейного программирования и ее можно было бы решить симплекс-методом.  
Если бы возможно было бы отбросить требование целочисленности, то это задача линейного программирования и ее можно было бы решить симплекс-методом.  
-
 
-
 
Выделим три основных элемента динамической модели.
Выделим три основных элемента динамической модели.
 +
'''1.''' Этап <math>\,j</math> ставится в соответствие типу <math>\, j,  j = 1,2,..., </math>
 +
'''2.'''  Состояние <math>\,y_j</math> на этапе <math>\,j</math> выражает суммарный вес предметов, решение о погрузке которых приняты на этапах <math>\,j, j + 1, \dots , \textit{N}</math>; при этом <math>\,y_j</math> может принимать значения <math>\, 0,1,\dots ,W </math> при <math>\,j =1,2,\dots ,N</math>.
-
1. \textit{Этап j }ставится в соответствие типу \textit{j, j = }1,2,...,
+
'''3.''' Варианты решения. Величины <math>\,k_{j}</math> на этапе <math>\,j</math> описывают количеством предметов типа <math>\,j</math>. Значение <math>\,k_{j} \in [0,[W/F_{j} ]]</math>, где <math>\,[W/F_{j} ]</math> - целая часть числа <math>\,W/F_{j} </math>.
-
2.  \textit{Состояние yj }на этапе \textit{j }выражает суммарный вес предметов, решение о погрузке которых приняты на этапах \textit{j, j + }1, \dots , \textit{N}; при этом \textit{yj }может принимать значения 0,1,\dots ,\textit{W} при \textit{j} =1,2,\dots ,\textit{N}.
+
Пусть <math>\,f_{j} (y_{j} )</math> - максимальная суммарная стоимость предметов, решения о погрузке которых приняты на этапах <math>\, j, j+1,..,N</math> при заданном состоянии <math>\,y_{j}</math>.
-
 
+
-
3. \textit{Варианты решения.  }Величины $k_{j} $ на этапе $j$ описывают количеством предметов типа \textit{j}. Значение $k_{j} \in [0,[W/F_{j} ]]$, где $[W/F_{j} ]$ --  целая часть числа $W/F_{j} $\textit{.}
+
-
 
+
-
\textit{}
+
-
 
+
-
Пусть $f_{j} (y_{j} )$ \textit{-- }максимальная суммарная стоимость предметов, решения о погрузке которых приняты на этапах \textit{j, j+}1\textit{,..,N }при заданном состоянии $y_{j} $.
+
Рекуррентное соотношение имеет следующий вид:
Рекуррентное соотношение имеет следующий вид:
 +
<math>\,f_{N} (y_{N} )=\mathop{\max }\limits_{\begin{array}{l} {k_{N} \in \{ 0,1,...,N\} ,} \\ {v_{N} =0,1,...,W} \end{array}} \{ v_{N} y_{N} \} </math>
 +
<math>\,f_{j} (y_{j} )=\mathop{\max }\limits_{\begin{array}{l} {k_{j} =0,1,...,[W/F_{j} ]} \\ {v_{j} =0,1,...,W} \end{array}} \{ v_{j} y_{j} +f_{j+1} (y_{j} -F_{j} k_{j} )\} ,\, \, \, \, j=1,2,...,N-1</math>
-
\[f_{N} (y_{N} )=\mathop{\max }\limits_{\begin{array}{l} {k_{N} \in \{ 0,1,...,N\} ,} \\ {v_{N} =0,1,...,W} \end{array}} \{ v_{N} y_{N} \} \]
+
Максимальное значение <math>\,k_{j} </math> ограничено величиной <math>\, W/F_{j} </math>, что позволяет отсекать все не являющиеся допустимыми варианты при заданном значении переменного состояния <math>\, y_{j} </math>.
-
 
+
-
\[f_{j} (y_{j} )=\mathop{\max }\limits_{\begin{array}{l} {k_{j} =0,1,...,[W/F_{j} ]} \\ {v_{j} =0,1,...,W} \end{array}} \{ v_{j} y_{j} +f_{j+1} (y_{j} -F_{j} k_{j} )\} ,\, \, \, \, j=1,2,...,N-1\]
+
-
 
+
-
 
+
-
 
+
-
Максимальное значение $k_{j} $\textit{ }ограничено величиной $[W/F_{j} ]$, что позволяет отсекать все не являющиеся допустимыми варианты при заданном значении переменного состояния \textit{$y_{j} $.}
+
-
 
+
-
 
+
-
 
+
-
\textbf{Решение примера}
+
-
 
+
-
 
+
-
 
+
-
Для\textit{ }нашего примера поэтапные расчеты начинаются с третьего этапа и осуществляются следующим образом.
+
-
 
+
-
 
+
-
 
+
-
\textit{Этап 3.}
+
-
 
+
-
\textit{}
+
-
 
+
-
\[f_{3} (y_{3} )=\mathop{\max }\limits_{k_{3} } (30k_{3} ), \max k_{3} =[5/1]=5\]
+
-
 
+
-
 
+
-
 
+
-
\begin{tabular}{|p{0.2in}|p{0.6in}|p{0.3in}|p{0.3in}|p{0.3in}|p{0.3in}|p{0.3in}|p{0.5in}|p{0.7in}|} \hline
+
-
& \multicolumn{6}{|p{2.0in}|}{30$k_{3} $} & \multicolumn{2}{|p{1.2in}|}{Оптимальное решение} \\ \hline
+
-
& $k_{3} $=0 & 1 & 2 & 3 & 4 & 5 & \multicolumn{2}{|p{1.2in}|}{} \\ \hline
+
-
$y_{3} $ & $v_{3} k_{3} =0$ & 30 & 60 & 90 & 120 & 150 & $f_{2} (y_{3} )$ & $k_{3}^{*} $ \\ \hline
+
-
0 & 0 & - & - & - & - & - & 0 & 0 \\ \hline
+
-
1 & 0 & 30 & - & - & - & - & 30 & 1 \\ \hline
+
-
2 & 0 & 30 & 60 & - & - & - & 60 & 2 \\ \hline
+
-
3 & 0 & 30 & 60 & 90 & - & - & 90 & 3 \\ \hline
+
-
4 & 0 & 30 & 60 & 90 & 120 & - & 120 & 4 \\ \hline
+
-
5 & 0 & 30 & 60 & 90 & 120 & 150 & 150 & 5 \\ \hline
+
-
\end{tabular}
+
-
 
+
-
 
+
-
 
+
-
\textit{Этап 2.}
+
-
 
+
-
+
-
 
+
-
\[f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80k_{3} +f_{2} (y_{2} +3k_{2} )), \max k_{2} =[5/3]=1\]
+
-
 
+
-
 
+
-
 
+
-
\begin{tabular}{|p{0.2in}|p{1.1in}|p{0.9in}|p{0.5in}|p{0.7in}|} \hline
+
-
& \multicolumn{2}{|p{2.0in}|}{$80k_{3} +f_{2} (y_{2} +3k_{2} )$} & \multicolumn{2}{|p{1.2in}|}{Оптимальное решение} \\ \hline
+
-
& $k_{2} $=0 & 1 & \multicolumn{2}{|p{1.2in}|}{} \\ \hline
+
-
$y_{3} $ & $v_{2} k_{2} =0$ & 80 & $f_{2} (y_{2} )$ & $k_{2}^{*} $ \\ \hline
+
-
0 & 0+0=0 & - & 0 & 0 \\ \hline
+
-
1 & 0+30=30 & - & 30 & 0 \\ \hline
+
-
2 & 0+60=60 & - & 60 & 0 \\ \hline
+
-
3 & 0+90=90 & 80+0=80 & 90 & 0 \\ \hline
+
-
4 & 0+120=120 & 80+30=110 & 120 & 0 \\ \hline
+
-
5 & 0+150=150 & 80+60=140 & 150 & 0 \\ \hline
+
-
\end{tabular}
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
Значения в столбцах получаются при использовании рекуррентных соотношений. Например, значение в столбце $v_{2} k_{2} =0$ при $y_{2} =1$ получаем следующим образом:
+
-
\[f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80\cdot 0+f_{3} (1+3\cdot 0))=0+f_{3} (1)=0+30,\]
+
==Решение примера==
 +
Для нашего примера поэтапные расчеты начинаются с третьего этапа и осуществляются следующим образом.
 +
'''Этап 3'''.
-
поскольку из таблицы этапа 3, $f_{3} \eqref{GrindEQ__1_}$ = 30.
+
<math>\,f_{3} (y_{3})=\mathop{\max }\limits_{k_{3}} (30k_{3}), \max k_{3}=[5/1]=5 </math>
 +
[[File:zPic52.jpg]]
 +
'''Этап 2'''.
-
Этап \textit{1.}
+
<math>\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80k_{3} +f_{2} (y_{2} +3k_{2} )), \max k_{2} =[5/3]=1 </math>
-
\textit{}
+
[[File:zPic53.jpg]]
-
\[f_{1} (y_{1} )=\mathop{\max }\limits_{k_{1} } (65k_{1} +f_{2} (y_{1} +2k_{1} )), \max k_{1} =[5/2]=1\]
+
Значения в столбцах получаются при использовании рекуррентных соотношений. Например, значение в столбце <math>\,v_{2} k_{2} =0</math> при <math>\,y_{2} =1</math> получаем следующим образом:
-
\begin{tabular}{|p{0.2in}|p{1.4in}|p{0.6in}|p{0.7in}|p{0.5in}|p{0.7in}|} \hline
+
<math>\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80\cdot 0+f_{3} (1+3\cdot 0))=0+f_{3} (1)=0+30</math>,
-
& \multicolumn{3}{|p{2.7in}|}{$65k_{1} +f_{2} (y_{1} +2k_{1} )$} & \multicolumn{2}{|p{1.2in}|}{Оптимальное решение} \\ \hline
+
-
& $k_{1} $=0 & 1 & 2 & \multicolumn{2}{|p{1.2in}|}{} \\ \hline
+
-
$y_{1} $ & $v_{1} k_{1} =0$ & 65 & 130 & $f_{2} (y_{3} )$ & $k_{3}^{*} $ \\ \hline
+
-
0 & 0+0=0 & - & - & 0 & 0 \\ \hline
+
-
1 & 0+30=30 & - & - & 30 & 1 \\ \hline
+
-
2 & 0+60=60 & 65+0=65 & - & 65 & 1 \\ \hline
+
-
3 & 0+90=90 & 65+30=95 & - & 95 & 1 \\ \hline
+
-
4 & 0+120=120 & 65+60=125 & 130+0=130 & 130 & 2 \\ \hline
+
-
5 & 0+150=150 & 65+90=155 & 130+30=160 & 160 & 2 \\ \hline
+
-
\end{tabular}
+
 +
поскольку из таблицы этапа 3, <math>\,f_{3}(1)  = 30</math>.
 +
'''Этап 1'''.
 +
<math>\,f_{1} (y_{1} )=\mathop{\max }\limits_{k_{1} } (65k_{1} +f_{2} (y_{1} +2k_{1} )), \max k_{1} =[5/2]=1</math>
 +
[[File:zPic54.jpg]]
-
\textit{}
+
При заданном <math>\,y_{1} =W=5</math> оптимальным решение является <math>\,(k_{1}^{*} ,k_{2}^{*} ,k_{3}^{*} )=(2,0,1)</math>, а суммарная стоимость груза равна 160.
-
При заданном $y_{1} =W=5$ оптимальным решение является $(k_{1}^{*} ,k_{2}^{*} ,k_{3}^{*} )=(2,0,1)$\textbf{, }а\textbf{ }суммарная стоимость груза равна 160.\textbf{}
+
[[Category:Управление запасами]]

Текущая версия на 18:51, 23 августа 2011

English: Load-planning problem

Для описания постановки задачи и метода решения задачи о загрузке самолета используются метод динамического программирования и принцип оптимальности Беллмана

Содержание

Метод динамического программирования

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

Предположим, что процесс управления некоторой системой \,X продолжается \, n шагов. Пусть задано пространство состояний \, P и пространство управлений \, Q с элементами \, p и \,q соответственно. Предполагается, что начальное состояние \, p_0 процесса задано. Пусть также задана функция \, T :

\, P\times Q\to P, т.е. \, T(p,q)=p',\, \, \, (p,q)\in P\times Q,\, \, p'\in P.

Функцию \, T часто называют функцией динамики управляемого процесса.

Многошаговый управляемый процесс реализуется следующим образом (см. рис. 1.):

Шаг 1. Система находится в состоянии \,p_{0} \in P. В этом состоянии выбирается управление \, q_{1} \in Q . Отображение \, T переводит систему в новое состояние \,T(p_{0} ,q_{1} )=p_{1} .

Шаг 2. Система находится в состоянии \,p_{1} \in P. В этом состоянии выбираем управление \,q_{2} \in Q поэтому \,T(p_{1} ,q_{2} )=p_{2} .

Шаг к. Система находится в состоянии \,p_{k-1} \in P. Выбирается управление \,q_{k} \in Q , тогда \,T(p_{k-1} ,q_{k} )=p_{k} .

Шаг n. Система \,X в состоянии \, p_{n-1} \in P . При выборе управления \,q_{n} \in Q получаем \,T(p_{n-1} ,q_{n} )=p_{n} . Процесс останавливается.

ZPic51.jpg

Рис. 1. Реализация многошагового управляемого процесса.

Обозначим через \,q=(q_{1} ,...,q_{k} ,...,q_{n} ),\, \, \, \, q_{k} \in Q,\, \, \, \, k=\overline{1,n} -- управление многошаговым процессом. Тогда данному начальному состоянию \, p_{0} и управлению \, q соответствует траектория \,p=(p_{0} ,...,p_{k-1} ,p_{k} ,p_{k+1} ,...,p_{n} ), где \,p_{k} =T(p_{k-1} ,q_{k} ), \,k=\overline{1,n}.

Предполагается, что на управлении \, q и траектории \, p задана аддитивная функция:

\, \bar{K}(p,q)=f_{1} (p_{0} ,q_{1} )+...+f_{i} (p_{i-1} ,q_{i} )+...+f_{n} (p_{n-1} ,q_{n} )+f_{n+1} (p_{n} )= \sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} ) .

Обозначим через

\, K(p_{0} ,q)=\sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} ).

значение функции \, \bar{K}(p,q) на траектории управляемого процесса из начального состояния \,p_{0} при управлении \, q .

Теперь можно сформулировать задачу дискретного оптимального управления. Найти оптимальное управление \,q^{*} , которое является решением следующей задачи:

\, \mathop{\max }\limits_{q} K(p_{0} ,q)=\max \left[\sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} )\right].

при динамических ограничениях:

\, \left\{\begin{array}{l} {p_{i} =T(p_{i-1} ,q_{i} ),\, \, \, q_{i} \in Q,\, \, \, i=\overline{1,n}} \\ {p_{0} =p^{0}} \end{array}\right.

где \, p_{0} - заданное начальное состояние процесса.

Заметим, что при выборе управления \, q_{i} на шаге \, i нам известно состояние процесса \, p_{i-1} на предыдущем шаге, причем знание \,(p_{i-1} ,q_{i} ) определяет будущее состояние процесса и значение функционала. Поэтому естественно рассматривать функции \,q_{i} =q_{i} (p_{i-1} ), \,i=\overline{1,n} и набор функций

(1) \, q(\cdot )=(q_{1} (\cdot ),...,q_{k} (\cdot ),...,q_{n} (\cdot ))

где \,q_{k} (\cdot ): q_{k} =q_{k} (p_{k-1} ) . Этот набор функций \,q(\cdot ) - будем называть стратегией или синтезирующим управлением процесса.

Принцип оптимальности Беллмана.

Оптимальная стратегия

\, q^{*} (\cdot )=(q_{1}^{*} (\cdot ),...,q_{k}^{*} (\cdot ),...,q_{n}^{*} (\cdot ))

обладает тем свойством, что каково бы ни было начальное состояние \,p и начальное управление \,q_{1}, она останется оптимальной стратегией в \, n-1 шаговом процессе, начинающемся из реализовавшегося состояния \, p_{1} =T(p,q).

Из принципа оптимальности Беллмана можно вывести реккурентное функциональное уравнение Беллмана, которое и лежит в основе вычислительных процедур динамического программирования.

Обозначим \, F_n(p) - максимальное значение функционала в \,n - шаговой задаче, из начального состояния \, p . Функция \, F_n(p) часто называется функцией Беллмана. Из принципа оптимальности получаем следующее уравнение.

Уравнение Беллмана.

(2) \, F_{n} (p)=\mathop{\max }\limits_{q_{1} \in Q} [f_{1} (p,q_{1} )+F_{n-1} (T(p,q_{1} ))

при граничном условии

\, F_{0} (p)=f_{n+1} (p).

Общая схема метода динамического программирования

Рассмотрим суть метода динамического программирования на следующем примере задачи динамического программирования. Найти:

(3) \, \mathop{\max }\limits_{x_{1} ...x_{n} } \sum _{j=1}^{n}f_{j}  (x_{j} ),

\, x_{j} \ge 0, \,x_{j} --целые, \,j=\overline{1,n}.

Поскольку переменные \,x_{j}, \,j=\overline{1,n} независимы, то

\, \mathop{\max }\limits_{x_{1} ,...,x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} ) =\mathop{\max }\limits_{x_{n} } \left[f_{n} (x_{n} )+\mathop{\max }\limits_{x_{1} ,...,x_{n-1} } \sum _{j=1}^{n-1}f_{j} (x_{j} ) \right],

(4) \, \sum _{j=1}^{n-1}a_{j} x_{j}  \le b-a_{n} x_{n}

Обозначив \, \mathop{\max }\limits_{x_{1} ,...,x_{n-1} } \sum _{j=1}^{n}f_{j} (x_{j} ) условии (4) через \, F_{n-1} (b-a_{n} x_{n} ), получим

(6) \, \mathop{\max }\limits_{x_{1} ,...,x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} ) =\mathop{\max }\limits_{x_{n} } \left[f_{n} (x_{n} )+F_{n-1} (b-a_{n} x_{n} )\right]

Обозначим также \, \mathop{\max }\limits_{x_{1} ,...,x_{k} } \sum _{j=1}^{k}f_{j} (x_{j} ) =F_{k} (\xi ) при условии

\, \sum _{j=1}^{k}a_{j} x_{j}  \le \xi .

\, x_{j} \ge 0 , \,x_{j} - целые, \,j=\overline{1,n}.

После преобразований приходим к следующему основному рекуррентному соотношению динамического программирования

(7) \, F_{k} (\xi )=\mathop{\max }\limits_{x_{k} } \left[f_{k} (x_{k} )+F_{n-1} (\xi -a_{n} x_{n} )\right],\, \, \, k=\overline{1,n}

при условии \,0\le x_{k} \le \frac{\xi }{a_{k} } .

Используем (7) для организации вычислительного процесса следующим образом.

Построение функции Беллмана.

Шаг 1. Вычисляем

(8) \,F_{1} (\xi )=\mathop{\max }\limits_{x_{1} } f_{1} (x_{1} ),\, \, \, x_{1} \le \xi ,

где \,\xi =\overline{0,b} - параметр процесса. Заполняем табл. 1 значениями \,F_{1} (\xi ) , \,x_{1}^{0} (\xi ), для \,\xi =\overline{0,b} \,x_{1}^{0} (\xi ) - оптимальное решение задачи (8).

Шаг 2. Вычисляем

(9) \, F_{2}(\xi )=\mathop{\max }\limits_{0\le x_{2} \le \frac{\xi }{a_{2}}} \left[f_{2}(x_{2})+F_{1}(\xi-a_{2} x_{2})\right]

Значения \,F_{1} (\xi -a_{2} x_{2} ) при различных значениях аргумента \,\xi -a_{2} x_{2} выбираем из табл. 1. Заполняем табл. 2 следующими результатами: \,F_{2} (\xi ), \,x_{2}^{0} (\xi ), где \,x_{2}^{0} (\xi ) - оптимальное решение задачи (9).

Шаг k. \,(1\le k\le n-1). Вычисляем

(10) \, F_{k}(\xi )=\mathop{\max }\limits_{0\le x_{k} \le \frac{\xi}{a_{k}}} \left[f_{k}(x_{k})+F_{k-1}(\xi-a_{k}x_{k})\right]

Заполняем таблицу значениями \, F_{k} (\xi ), \,x_{k}^{0} (\xi ), \,\xi =\overline{0,b}, где \,x_{k}^{0} (\xi ) - оптимальное решение задачи (10).

Расчет оптимального решения.

Полагая \,\xi =b и \,k=n находим \,F_{n} (b) и \,x_{n}^{0}=x_{n}^{0}(\xi).

Вычислив в (10) оптимальное значение \,x_{n}^{0}=x_{n}^{0}(\xi ) и положив \,\xi_{1}^{0}=b-a_{n} x_{n}^{0} , по значению \,\xi _{1}^{0} из таблицы шага \, n-1 определяем оптимальные значения всех остальных переменных \,x_{n-1}^{0} (\xi _{1}^{0} ), потом аналогично значения \,x_{n-2}^{0}(\xi_{1}^{0}),\dots , x_{1}^{0} (\xi _{1}^{0} ).

\,\xi \,F_{1}(\xi) x_{1}^{0} (\xi )
\, 0 \, F_{1}(0) \, x_{1}^{0}(0)
\, 1 \, F_{1}(1) \, x_{1}^{0}(1)
\, \ldots \, \ldots \, \ldots
\, b-1 \, F_{1} (b-1) \, x_{1}^{0} (b-1)
\, b \, F_{1} (b) \,x_{1}^{0}(b)

Табл.1. Таблица для первой итерации

\,\xi \,F_{2}(\xi ) \, x_{2}^{0}(\xi)
\, 0 \, F_{2}(0) \, x_{2}^{0}(0)
\, 1 \, F_{2}(1) \, x_{2}^{0}(1)
\, \ldots \, \ldots \, \ldots
\, b-1 \, F_{2} (b-1) \, x_{2}^{0} (b-1)
\, b \, F_{2} (b) \,x_{2}^{0}(b)

Табл.2. Таблица для второй итерации

Для применения метода динамического программирования необходимо, чтобы выполнялись условия:

  • процесс поиска оптимальных решений должен допускать интерпретацию как многошаговый процесс принятия решений;
  • для каждого шага должно быть определено множество параметров состояния \, \xi , которое не зависит от номера шага;
  • оптимальное решение на шаге \, k зависит только от текущего состояния и не зависит от предыстории процесса.

Задача о загрузке самолета

Самолет загружается предметами \, N различных типов. Каждый предмет типа \, i имеет вес \, F_{i} и страховую стоимость \, v_{i} , (\,i=\overline{1,N}). Максимальная грузоподъемность самолета равна \, W. Требуется определить максимальную стоимость груза, вес которого не должен превышать максимально допустимой грузоподъемности самолета. Для определенности предположим, что \, W = 5 и всего имеются три типа предметов, сведения о которых приведены в таблице:

\, \, \, \, i \, \, \, \, \, \, \, F_{i}\, \, \, \, \, \, \, v_{i} \, \, \,
\, 1 \, 2 \, 65
\, 2 \, 3 \, 80
\, 3 \, 1 \, 30

Рассмотрим задачу в общей постановке. Обозначим количество предметов типа \, i через \, k_{i} . Тогда задача загрузки самолета может быть записана в виде:

\, \max z=\max (v_{1} k_{1} +v_{2} k_{2} +...+v_{N} k_{N} )

\, \left\{\begin{array}{l} {F_{1} k_{1} +F_{2} k_{2} +...+F_{n} k_{n} \le W,} \\ {k\ge 0,\, \, i=\overline{1,N,}} \end{array}\right.

где \, k - целые.

Если бы возможно было бы отбросить требование целочисленности, то это задача линейного программирования и ее можно было бы решить симплекс-методом.

Выделим три основных элемента динамической модели.

1. Этап \,j ставится в соответствие типу \, j,  j = 1,2,...,

2. Состояние \,y_j на этапе \,j выражает суммарный вес предметов, решение о погрузке которых приняты на этапах \,j, j + 1, \dots , \textit{N}; при этом \,y_j может принимать значения \, 0,1,\dots ,W при \,j =1,2,\dots ,N.

3. Варианты решения. Величины \,k_{j} на этапе \,j описывают количеством предметов типа \,j. Значение \,k_{j} \in [0,[W/F_{j} ]], где \,[W/F_{j} ] - целая часть числа \,W/F_{j} .

Пусть \,f_{j} (y_{j} ) - максимальная суммарная стоимость предметов, решения о погрузке которых приняты на этапах \, j, j+1,..,N при заданном состоянии \,y_{j}.

Рекуррентное соотношение имеет следующий вид:

\,f_{N} (y_{N} )=\mathop{\max }\limits_{\begin{array}{l} {k_{N} \in \{ 0,1,...,N\} ,} \\ {v_{N} =0,1,...,W} \end{array}} \{ v_{N} y_{N} \}

\,f_{j} (y_{j} )=\mathop{\max }\limits_{\begin{array}{l} {k_{j} =0,1,...,[W/F_{j} ]} \\ {v_{j} =0,1,...,W} \end{array}} \{ v_{j} y_{j} +f_{j+1} (y_{j} -F_{j} k_{j} )\} ,\, \, \, \, j=1,2,...,N-1

Максимальное значение \,k_{j} ограничено величиной \, W/F_{j} , что позволяет отсекать все не являющиеся допустимыми варианты при заданном значении переменного состояния \, y_{j} .

Решение примера

Для нашего примера поэтапные расчеты начинаются с третьего этапа и осуществляются следующим образом.

Этап 3.

\,f_{3} (y_{3})=\mathop{\max }\limits_{k_{3}} (30k_{3}), \max k_{3}=[5/1]=5

ZPic52.jpg

Этап 2.

\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80k_{3} +f_{2} (y_{2} +3k_{2} )), \max k_{2} =[5/3]=1

ZPic53.jpg

Значения в столбцах получаются при использовании рекуррентных соотношений. Например, значение в столбце \,v_{2} k_{2} =0 при \,y_{2} =1 получаем следующим образом:

\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80\cdot 0+f_{3} (1+3\cdot 0))=0+f_{3} (1)=0+30,

поскольку из таблицы этапа 3, \,f_{3}(1)  = 30.

Этап 1.

\,f_{1} (y_{1} )=\mathop{\max }\limits_{k_{1} } (65k_{1} +f_{2} (y_{1} +2k_{1} )), \max k_{1} =[5/2]=1

ZPic54.jpg

При заданном \,y_{1} =W=5 оптимальным решение является \,(k_{1}^{*} ,k_{2}^{*} ,k_{3}^{*} )=(2,0,1), а суммарная стоимость груза равна 160.

Личные инструменты
Our Partners