Задача для самостоятельного решения
Найти маршрут, связывающий города А (1) и В (10), для которого
суммарные затраты на перевозку груза были бы наименьшими, (рис. 1.2)
Использовать метод динамического программирования.
Рис. 1.2
Стоимость перевозки груза по всем направлениям приводится ниже для каждого варианта.
Варианты задания
Вариант 1 (А) Вариант 2 (Б)
направления затраты направления затраты
Вариант 3(В)Вариант 4(Г)
направления затраты направления затраты
Вариант 5(Д)Вариант 6(Е, Ё)
направления затраты направления затраты
Вариант 7 (Ж) Вариант 8 (З)
направления затраты направления затраты
Вариант 9(И)Вариант 10(К)
направления затраты направления затраты
Вариант 11(Л)Вариант 12(М)
направления затраты направления затраты
Вариант 13(Н)Вариант 14(О)
направления затраты направления затраты
Вариант 15(П)Вариант 16(Р)
направления затраты направления затраты
Вариант 17(С)Вариант 18(Т)
направления затраты направления затраты
Вариант 19(У)Вариант 20(Ф)
направления затраты направления затраты
Вариант 21(Х)Вариант 22(Ц)
направления затраты направления затраты
Вариант 23(Ч)Вариант 24(Ш, Щ)
направления затраты направления затраты
Вариант 25 (Э, Ю) Вариант 26 (Я)
направления затраты направления затраты
ПЛАНИРОВАНИЕ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ
Предприятие изготовляет машины 
, спрос на которые в каждом из месяцев равен 
единиц. Запас машин на складе предприятия на начало планируемого периода 
единиц. Общие затраты 
состоят из затрат 
на производство машин и затрат 
на их содержание до отправки потребителю, т. е.
, (2.1)
здесь 
− затраты на хранение единицы продукции. Затраты 
складываются из условно-постоянных К и пропорциональных Lx (L денежных единиц на каждую единицу продукции) т. е.
. (2.2)
Складские площади предприятия ограничены, и хранить можно не более M единиц продукции. Производственные мощности также ограничены, и в каждом месяце можно изготовлять не более B единиц продукции.
Требуется определить производственную программу изготовления машин 
удовлетворяющую спрос в каждом из месяцев планируемого периода и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен 0.
Данную задачу будем решать методом динамического программирования.
Составим основное рекуррентное уравнение для данной задачи.
1. Планируемый период Т разбиваем на шаги по месяцам. Обозначим
через n номер планового отрезка времени (соответствует обратной нумерации месяцев, так как планирование выполняется с конца периода Т).
2. Состояние системы перед каждым шагом будет характеризоваться
параметром 
− уровень запасов на начало отрезка n (шага).
3. Параметром шагового управления задачи будет переменная 
- количество производимой продукции на отрезке n.
4. Выигрыш (эффект) на каждом шаге n определяется общими затратами 
связанными с выпуском − единиц продлении на n отрезке и с содержанием запасов на конец n - го отрезка 
.
5. Состояние, в которое переходит система под влиянием управления на шаге n.
,
где 
- спрос на продукцию (объем продаж) на n-ом отрезке.
Обозначим через 
− условно-оптимальный накопленный эффект за n шагов, то есть минимальные затраты на производство и хранение продукции за n последних месяцев при условии, что уровень запасов на начало n - го месяца равен i − единиц; 
− производство продукции (объем выпуска) на n-м отрезке, если уровень запасов на начало отрезка равен 
.
6. Основное рекуррентное уравнение имеет вид
(2.3)
Параметры и 
удовлетворяет следующим ограничениям:
, (2.4)
так как спрос на данном отрезке должен быть удовлетворен.
, (2.5)
так как запас на конец планового периода равен 0 и производство продукции на любом отрезке не превышает B.
, (2.6)
Так как уровень запасов не должен превышать ограничений на складские площади предприятия.
Пример решения задачи
Исходные данные задачи:
, 
, 
, 
, 
, 
, 
, K=10, 
.
Решение
Условная оптимизация.
Планируемый период разбиваем на три отрезка так как . Вычисления удобно оформлять в виде таблиц, в первом столбце таблицы записываются возможные значения переменной (состояние системы – уровень запаса), удовлетворяющие ограничениям (2.6).
В первой строке – возможные значения объема выпуска 
, удовлетворяющие ограничениям (2.4), (2.5). Каждая клетка таблицы заполняется значениями трех слагаемых.
(2.7)
Если сочетания i и x недопустимы, то в соответствующей клетке ставится «-».
Для 
значение 
выписывается из предыдущей таблицы.
Для 
В столбце 
фиксируется соответствующий оптимальный выпуск продукции.
Вычислим затраты на производство машин 
по формуле (2.2).
Таблица 2.1
| С(0) | С(1) | С(2) | С(3) | С(4) | С(5) | С(6) |
Отметим, что, как правило, задачи динамического программирования на этапе условной оптимизации решаются от конца к началу. Например, если весь плановый период в четверть года разбиваем на отрезки по месяцам, то в решении первым отрезком (n=1) из трех ( ) является месяц март (конец планового периода, самый последний по времени месяц), вторым (n=2) – февраль, и последним, третьим (n=3) соответственно январь (начало планового периода, самый первый по времени месяц).
(март)
Значение i не превышает 
, то есть 
, 
Так как 
(нулевым месяцем здесь является апрель, который мы не рассматриваем, накопленный эффект равен нулю) и запас на складе в конце планируемого периода по условию равен 0, то из трех слагаемых в (2.7) остается 
которое выписывается из табл. 2.1 для каждого 
Таблица 2.2