Задача о загрузке самолета
Материал из Supply Chain Management Encyclopedia
(→Принцип оптимальности Беллмана.) |
(→Принцип оптимальности Беллмана.) |
||
Строка 189: | Строка 189: | ||
|| | || | ||
* ''Оплатить'' предотгрузочную инспекцию, включая те виды, которые требуются в стране, из которой осуществляется экспорт. | * ''Оплатить'' предотгрузочную инспекцию, включая те виды, которые требуются в стране, из которой осуществляется экспорт. | ||
- | } | + | |} |
Версия 12:25, 15 августа 2011
Для описания постановки задачи и метода решения задачи о загрузке самолета используются метод динамического программирования и принцип оптимальности Беллмана
Метод динамического программирования
Методы динамического программирования широко применяются как в задачах оптимального управления и планирования, так и при решении различных технических проблем.
Предположим, что процесс управления некоторой системой продолжается шагов. Пусть задано пространство состояний и пространство управлений с элементами и соответственно. Предполагается, что начальное состояние процесса задано. Пусть также задана функция :
, т.е. .
Функцию часто называют функцией динамики управляемого процесса.
Многошаговый управляемый процесс реализуется следующим образом (см. рис. 1.):
Шаг 1. Система находится в состоянии . В этом состоянии выбирается управление . Отображение переводит систему в новое состояние .
Шаг 2. Система находится в состоянии . В этом состоянии выбираем управление поэтому .
Шаг к. Система находится в состоянии . Выбирается управление , тогда .
Шаг n. Система в состоянии . При выборе управления получаем . Процесс останавливается.
Рис. 1. Реализация многошагового управляемого процесса.
Обозначим через -- управление многошаговым процессом. Тогда данному начальному состоянию и управлению соответствует траектория , где , .
Предполагается, что на управлении и траектории задана аддитивная функция:
.
Обозначим через
.
значение функции на траектории управляемого процесса из начального состояния при управлении .
Теперь можно сформулировать задачу дискретного оптимального управления. Найти оптимальное управление , которое является решением следующей задачи:
.
при динамических ограничениях:
где - заданное начальное состояние процесса.
Заметим, что при выборе управления на шаге нам известно состояние процесса на предыдущем шаге, причем знание определяет будущее состояние процесса и значение функционала. Поэтому естественно рассматривать функции , и набор функций
(1)
где . Этот набор функций - будем называть стратегией или синтезирующим управлением процесса.
Принцип оптимальности Беллмана.
Оптимальная стратегия
обладает тем свойством, что каково бы ни было начальное состояние и начальное управление , она останется оптимальной стратегией в шаговом процессе, начинающемся из реализовавшегося состояния .
Из принципа оптимальности Беллмана можно вывести реккурентное функциональное уравнение Беллмана, которое и лежит в основе вычислительных процедур динамического программирования.
Обозначим - максимальное значение функционала в - шаговой задаче, из начального состояния . Функция часто называется функцией Беллмана. Из принципа оптимальности получаем следующее уравнение.
Уравнение Беллмана.
(2)
при граничном условии
Общая схема метода динамического программирования
Рассмотрим суть метода динамического программирования на следующем примере задачи динамического программирования. Найти:
(3) ,
, --целые, .
Поскольку переменные , независимы, то
,
(4)
Обозначив условии (4) через , получим
(6)
Обозначим также при условии
.
, - целые, .
После преобразований приходим к следующему основному рекуррентному соотношению динамического программирования
(7)
при условии .
Используем (7) для организации вычислительного процесса следующим образом.
Построение функции Беллмана.
Шаг 1. Вычисляем
(8) ,
где - параметр процесса. Заполняем табл. 1 значениями , , для - оптимальное решение задачи (8).
Шаг 2. Вычисляем
(9)
Значения при различных значениях аргумента выбираем из табл. 1. Заполняем табл. 2 следующими результатами: , , где - оптимальное решение задачи (9).
Шаг k. . Вычисляем
(10)
Заполняем таблицу значениями , , , где - оптимальное решение задачи (10).
Расчет оптимального решения.
Полагая и находим и .
Вычислив в (10) оптимальное значение и положив , по значению из таблицы шага определяем оптимальные значения всех остальных переменных , потом аналогично значения .
Перевозка |
|
|
Страхование |
|
|
Поставка – Приемка поставки |
|
|
Переход рисков |
|
|
Расходы |
|
|
Извещение покупателю – Извещение продавцу |
|
|
Поставочные и транспортные документы - Доказательство поставки |
|
|
Проверка, упаковка, маркировка- Инспекция(и) |
|
|
Невозможно разобрать выражение (синтаксическая ошибка): \, \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{}