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

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

Перейти к: навигация, поиск

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

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

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

Предположим, что процесс управления некоторой системой \,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} $\textit{ -- }заданное начальное состояние процесса.


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


\begin{equation} \label{GrindEQ__1_} q(\cdot )=(q_{1} (\cdot ),...,q_{k} (\cdot ),...,q_{n} (\cdot )) \end{equation}


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


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

\textit{Оптимальная стратегия }

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

\textit{}

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


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

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

\textbf{}

\textbf{Уравнение Беллмана.}

\textbf{}

\begin{equation} \label{GrindEQ__2_} F_{n} (p)=\mathop{\max }\limits_{q_{1} \in Q} [f_{1} (p,q_{1} )+F_{n-1} (T(p,q_{1} ))] \end{equation}

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

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

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


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

\textbf{\textit{}}

\begin{equation} \label{GrindEQ__3_} \mathop{\max }\limits_{x_{1} ...x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} ), \end{equation}


$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]$, \eqref{GrindEQ__4_}

\begin{equation} \label{GrindEQ__5_} \sum _{j=1}^{n-1}a_{j} x_{j} \le b-a_{n} x_{n} \end{equation}


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


\begin{equation} \label{GrindEQ__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] \end{equation}


Обозначим также $\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}$.

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


\begin{equation} \label{GrindEQ__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} \end{equation}

\textit{}

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

Используем \eqref{GrindEQ__7_} для организации вычислительного процесса следующим образом.

\textbf{}

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

\textbf{Шаг 1}. Вычисляем

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


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


\textbf{Шаг 2}. Вычисляем

\begin{equation} \label{GrindEQ__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] \end{equation}

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


\textbf{Шаг \textit{к}}\textit{. $(1\le k\le n-1)$. }Вычисляем


\begin{equation} \label{GrindEQ__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] \end{equation}

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

\textbf{}

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

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

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



\begin{tabular}{|p{0.3in}|p{0.6in}|p{0.6in}|} \hline $\xi $ & $F_{1} (\xi )$ & $x_{1}^{0} (\xi )$ \\ \hline 0 & $F_{1} \eqref{GrindEQ__0_}$ & $x_{1}^{0} \eqref{GrindEQ__0_}$ \\ \hline 1 & $F_{1} \eqref{GrindEQ__1_}$ & $x_{1}^{0} \eqref{GrindEQ__1_}$ \\ \hline $\vdots $ & $\vdots $ & $\vdots $ \\ \hline $b-1$ & $F_{1} (b-1)$ & $x_{1}^{0} (b-1)$ \\ \hline $b$ & $F_{1} (b)$ & $x_{1}^{0} (b)$ \\ \hline \end{tabular}


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


\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. Таблица для второй итерации.}



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

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


\textbf{Задача о загрузке самолета}


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


\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$ -- целые.


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


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


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

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}.

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} $.

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


\[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} $\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, $f_{3} \eqref{GrindEQ__1_}$ = 30.


Этап \textit{1.}

\textit{}

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

\begin{tabular}{|p{0.2in}|p{1.4in}|p{0.6in}|p{0.7in}|p{0.5in}|p{0.7in}|} \hline

& \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}



\textit{}

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

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