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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Принцип оптимальности Беллмана.)
(Принцип оптимальности Беллмана.)
Строка 189: Строка 189:
||  
||  
* ''Оплатить'' предотгрузочную инспекцию, включая те виды, которые требуются в стране, из которой осуществляется экспорт.
* ''Оплатить'' предотгрузочную инспекцию, включая те виды, которые требуются в стране, из которой осуществляется экспорт.
-
}
+
|}

Версия 12:25, 15 августа 2011

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

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

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

Предположим, что процесс управления некоторой системой \,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)
Перевозка
  • У продавца нет обязательств [1]► по обеспечению перевозки товара.
  • Обеспечить перевозку товара от названного места поставки до места назначения покупателя.
  • У покупателя нет обязательств [1]► перед продавцом по перевозке товара.
Страхование
  • У продавца нет обязательств [1]► по обеспечению страхования товара.
  • Обеспечить покупателя, по запросу покупателя (если таковой имеет место) и за его счет, информацией, требуемой для обеспечения страхования.
  • У покупателя нет обязательств [1]► перед продавцом по страхованию товара.
Поставка – Приемка поставки
  • Предоставить товар покупателю в названном месте и точке поставки в срок обговоренный в контракте купли-продажи.
  • Если покупатель не обговорил конкретную точку в названном месте поставки, продавец может выбрать такую точку, которая выгодна продавцу.
  • Принять поставку товара в соответствии с условиями контракта купли-продажи.
Переход рисков
  • Принимать на себя все риски потери или порчи товара пока товар не предоставлен покупателю в названном месте поставки, в согласованный срок обговоренный в контракте купли-продажи.
  • Принимать на себя все риски потери или порчи товара с того момента, когда товар поставлен (предоставлен) в названном месте поставки в соответствии с условиями контракта купли-продажи.
  • Принимать на себя все риски потери или порчи товара, если товар не забран в согласованный срок и в согласованном месте.
Расходы
  • Оплатить все расходы до тех пор, пока товар не предоставлен в распоряжение покупателя в названном месте поставки.
  • Оплатить все расходы с того момента, когда товар поставлен (предоставлен в распоряжение покупателя) в названном месте поставки.
  • Оплатить все расходы, связанные с перевозкой товара от названного места поставки то точки конечного назначения покупателя.
  • Оплатить все расходы, проистекающие из неспособности принять поставку в названном месте и в названный срок.
  • Оплатить все расходы, связанные с экспортными и импортными формальностями, пошлинами, сборами и налогами, а также иные платежи, включая оплату перегрузки.
Извещение покупателю – Извещение продавцу
  • Обеспечить извещение, которое дает возможность покупателю принять поставку товара.
  • Выдать продавцу обоснованное извещение,
    • если, согласно условий данного контракта купли-продажи, покупателю предоставлено право специфицировать срок для приема поставки
    • или точку приема поставки в названном месте поставки.
Поставочные и транспортные документы - Доказательство поставки
  • У продавца нет обязательств [1]► по обеспечению покупателя каким-либо документом свидетельствующем о поставке.
  • Предоставить продавцу доказательство приемки поставки.
Проверка, упаковка, маркировка- Инспекция(и)
  • Оплатить все расходы, связанные с проверкой количества и качества товара, чтобы он был в соответствии с условиями данного контракта купли-продажи.
  • Упаковать товар, если только данный тип товара не продается общепринято в неупакованном виде.
  • Упаковать товар так, как полагает необходимым продавец для данной транспортировки, если только покупатель, до завершения оформления данного контракта купли-продажи, не выдал особые требования.
  • Обеспечить маркировку соответствующую данной упаковке.
  • Оплатить предотгрузочную инспекцию, включая те виды, которые требуются в стране, из которой осуществляется экспорт.


Невозможно разобрать выражение (синтаксическая ошибка): \, \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


\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