Поэтому  или zmax ≈ 21,9. ПРИЛОЖЕНИЕ 3 Динамическое программирование
Задача. Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть, распределены между тремя предприятиями.
Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль pi
(x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным:
Инвестирование средств (тыс. ден. ед.) Прибыль (тыс. ден. ед.)
x p1(x) p2(x) p3(x)
1 3,22 3,33 4,27
2 3,57 4,87 7,64
3 4,12 5,26 10,25
4 4 7,34 15,93
5 4,85 9,49 16,12
Решение. Составим математическую модель задачи.
1. Число шагов равно 3.
2. Пусть s – количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.
3. Управление на i-ом шаге (i=1,2,3) выберем xi - количество средств, инвестируемых в i-ое предприятие.
4. Выигрыш pi(xi) на i-ом шаге – это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p1(x1)+ p2(x2)+ p3(x3).
5. Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед.
Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и следовательно, функция перехода в новое состояние имеет вид: fi(s, x) = s-x.
6. На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x3(s)=s, W3(s)=p3(s).
7. Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид
() max{ ( ) ( )} 1
W s p x W s x i i x s
i= + +
Приложение 4 Динамическое программирование
Имеется  пунктов поставщиков  и  пунктов назначения (потребителей) .
 — количество груза в тоннах, сосредоточенное в пункте ;
 — количество груза, ожидаемое в пункте  .
Принимаем условие
|
(6.16)
|
означающее, что суммарный запас груза равен суммарной потребности в нем.
 — стоимость перевозки одной тонны груза из пункта  в пункт  .
 — количество тон груза, перевезенное из пункта в пункт .
Требуется найти оптимальный план перевозок, то есть рассчитать, сколько груза должно быть отправлено из каждого пункта отправления в каждый пункт назначения, с тем условием, чтобы суммарная стоимость перевозок была наименьшей.
Неизвестными в нашей задаче являются  неотрицательных чисел  . Сведем их в таблицу 6.1, назовем ее матрицей перевозок.
Таблица 6.1. Матрица перевозок
|
|
|
|
...
|
|
|
|
|
|
...
|
|
|
|
|
|
...
|
|
|
...
|
...
|
...
|
...
|
...
|
...
|
|
|
|
...
|
|
|
|
|
|
...
|
|
|
Запишем соотношение для пунктов поставщиков и пунктов потребителей .
Будем называть уравнение 0I горизонтальными уравнениями, а 0II – вертикальными. Перевозка из и стоит  , общая стоимость всех перевозок будет
|
(II)
|
где суммирование производится по всем  и всем  . Таким образом, мы пришли к следующей задаче линейного программирования:
Дана система уравнений I и линейная функция II. Требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию II.
Метод северо-западного угла
Разберем метод на примере.
Пусть есть 3 пункта отправления и 4 пункта назначения  .
Запасы в пунктах отправления: .
Потребности:  .
Занесем данные в таблицу.
Таблица 6.2.
|
|
|
|
|
|
Запасы
|
|
40
|
|
|
|
60
|
|
|
|
|
|
80
|
Потребности
|
40
|
60
|
80
|
60
|
100
|
Потребности пункта  удовлетворены полностью и поэтому столбец, соответствующий , можно временно исключить из рассмотрения, то есть переходим к таблице 3.
Таблица 6.3.
|
|
20
|
|
|
 (так как переслали в )
|
|
|
|
|
80
|
|
|
|
|
100
|
|
60
|
80
|
60
|
|
Отметим, что и в таблице 6.3 сумма всех потребностей по-прежнему равна сумме всех запасов. К таблице 6.3 применим тот же прием и попытаемся удовлетворить потребности  пункта .(в таблице 6.3 пункт играет роль первого) запасами  пункта . Очевидно, что потребности эти удается удовлетворить лишь частично, так как  . При этом потребности сократятся до  , а запасы окажутся исчерпаны полностью. В силу этого строку, отвечающую , из таблицы 6.3 можно временно удалить. Получим новую таблицу – таблицу 6.4, в которой имеются уже два пункта отправления и и три пункта назначения  .
Таблица 6.4.
|
|
|
|
|
|
|
40
|
|
|
80
|
|
|
|
|
100
|
|
40
|
80
|
60
|
|
Аналогичным приемом продолжаем сокращать последовательно получаемые таблицы, пока не удовлетворим потребности всех пунктов назначения. В случае, когда новые запасы равны новым потребностям, можно исключить из таблицы по желанию строку и столбец. В процессе сокращения таблиц мы получим следующие значения для некоторых из неизвестных:
 .
Вписав их в таблицу 6.2, получим таблицу 6.5.
Таблица 6.5.
|
|
|
|
|
|
|
40
|
20
|
|
|
|
|
40
|
40
|
|
|
|
|
40
|
60
|
Условимся называть те клетки таблицы 6.5, в которые вписаны значения неизвестных, — базисными, а остальные клетки — свободными. Если считать, что значения неизвестных , которые отвечают свободным клеткам, равны нулю, то получившийся набор значений всех неизвестных дает допустимое решение рассматриваемой задачи.
Действительно, легко проверить, что сумма значений неизвестных в каждой строке таблицы равна запасу в соответствующем пункте отправления, а в каждом столбце – потребности в соответствующем пункте назначения. Поэтому уравнения I, II удовлетворяются.
Обобщенная транспортная задача, задача о взвешенном распределении,  -задача, задача о расстановки флота и др.
Пусть имеется транспортных линий (скажем, пассажирских); по  -й линии нужно выполнить рейсов  . В наличии имеются транспортные единицы m типов. Резервы полезного времени транспортной единицы типа  составляют  . На выполнение транспортной единицей типа рейса требуется время  , а затраты на рейс составляют . Требуется указать наиболее экономную расстановку транспортных единиц по линиям.
Обозначая через количество рейсов, которое транспортная единица должна выполнить по линии , приходим к следующей задаче. Требуется минимизировать
|
(7.1)
|
при условиях
|
(7.2)
|
- целые,  ,
|
(7.3)
|
|
(7.4)
|
Здесь условия (7.3.) выражают ограничения по фондам времени каждой транспортной единицы, а условия (7.4.) говорят о том, что все рейсы должны быть выполнены.
К совершенно аналогичной модели приводит близкая к описанной задача о выборе средства доставки груза.
Задача о выборе средства доставки груза.
Пусть через  обозначены грузообразующие пункты с объемами груза в них . Имеется средств доставки груза (видов транспорта); грузоподъемность - го средства доставки составляет  , а наличный его парк равен  . Грузы подлежат доставке в один центральный пункт (склад); затраты при осуществлении одной единицей средства доставки рейса от пункта до склада равны . Требуется составить наиболее экономный план доставки.
Через обозначим количество средств доставки типа , отправляющееся из пункта . Тогда задача сведется к минимизации целевой функции вида (7.1.) при условиях (7.2.) и
|
(7.5)
|
|
(7.6)
|
Задача распределения производственной программы.
Пусть требуется распределить изготовление деталей между станками. Индексом  будем обозначать детали, индексом — станки с резервами рабочего времени . Пусть плановое задание по деталям задается числами , штучные нормы времени по обработке -м станком -й детали равны , а себестоимость при этом составляет . Требуется составить план распределения работ по станкам, обеспечивающий выполнение задания, не выводящий за пределы резервов времени по каждому станку и минимизирующий суммарную себестоимость.
Обозначим через количество деталей типа , которое следует обработать на станке . Тогда описанная задача распределения программы сведется к модели (7.1.)-(7.4.). Заметим, что во многих интерпретациях распределительной задачи требование цело численности на переменные может и не накладываться.
Распределительная задача с фиксированными доплатами.
Пусть в дополнение к перечисленным выше данным выпуск транспортной единицы типа на линию связан с подготовительными работами, требующими времени  (это время не зависит от числа рейсов, которое предстоит выполнить данной транспортной единице). Денежные затраты на проведение этих подготовительных работ составляют  .
Для отыскания наиболее экономной расстановки транспортных единиц по линиям, как и выше, введем целочисленные переменные . Тогда суммарные затраты составят
|
(7.7)
|
где
|
(7.8)
|
Ограничения по фонду времени каждой транспортной единицы будут теперь иметь вид
|
(7.9)
|
где
|
(7.10)
|
Ограничения по рейсам (7.4.), равно как и очевидные ограничения (7.2.), при этом сохраняются. Таким образом, задача заключается в минимизации (7.7.) при условиях (7.2.), (7.4.) и (7.9.)
Из (7.7.) и (7.8.) легко усмотреть, что перед нами задача с фиксированными доплатами; ее отличие от рассматривающийся ранее задач этого рода состоит в том, что здесь фиксированные доплаты входят не только в целевую функцию, но и в ограничения (7.9.). Однако и этот вариант задачи можно свести к целочисленная задача линейного программирования.
Задача о выборе средств доставки грузов.
Пусть грузовой флот имеет в своем составе суда типов. Количество судов типа равно  , а затраты при использовании одного судна типа в планируемом периоде составляют . Каждое судно обладает грузовыми емкостями типов (трюмы, танки, палубы и тому подобное); грузоподъемность емкости на судне типа равна . Подлежат перевозке  видов грузов. Груз вида  имеется в количестве  . Требуется выбрать наиболее экономичный комплекс средств доставки этих грузов, совместимый с грузовыми возможностями судов.
Учитывая неделимость транспортных единиц, введем целочисленные переменные  , которые обозначают количество судов типа , выделяемое для перевозки. Кроме того, введем переменные  , которые обозначают количество грузов вида , подлежащее загрузке в емкость  . Тогда мы придем к задаче минимизации
|
(7.11)
|
при условиях
|
(7.12)
|
- целое; 
|
(7.13)
|
|
(7.14)
|
Здесь ограничения (7.13.) показывают, что общее количество груза, загружаемое в емкости каждого типа, не должно превышать суммарной грузоподъемности этих емкостей по всем судам, а ограничения (7.14.) говорят о том, что перевозки по всем грузам должны быть полностью осуществлены. Отметим, что на переменные требование целочисленности, вообще говоря, не накладывается, так что здесь мы имеем дело с частично целочисленной задачей.
|
