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

Материал из 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} - заданное начальное состояние процесса.

Заметим, что при выборе управления \, 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


\, i \, F_{i} \,  v_{i}
\, 1 \, 2 \, 65
\, y_{3} \, v_{3} k_{3} =0 \, 30 \, 60 \, 90 \, 120 \, 150 \, f_{2} (y_{3}) \,k_{3}^{*}
\, 0 \, 0 \, - \, - \, - \, - \, - \, 30 \, 1
\, 3 \, 1 \, 30


\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