итрати.
Нехай вартість перевезень однієї одиниці продукту з пункту S i у пункт Q i дорівнює c ij . Будемо далі припускати, що при перевезенні х ij одиниць продукту з S i у Q j транспортні витрати рівні c ij x ij.
Назвемо планом перевезень набір чисел х ij c i = 1, ..., m; j = 1, ..., n, що задовольняє обмеженням:
В
x ij ≥ 0, i = 1,2, ..., m; j = 1, ..., n (11)
Змістовний сенс рівнянь (11) полягає в тому, що з пункту S i при плані х ij вивозиться в усі пункти Q j обсяг, який має дорівнювати запасу a i . У пункт Q j надходить з усіх пунктів S i сумарна кількість продукту, яке в точності має дорівнювати потреби b j .
При плані перевезень (х ij ) транспортні витрати складуть величину
(12)
Остаточне формування транспортної задачі таке: серед всіх наборів чисел (х ij ), відповідають обмеженням (11), знайти набір, здатний мінімізувати (12).
2.2 Динамічне програмування
В
2.2.1 Модель динамічного програмування
Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішень може бути розбитий на окремі етапи (кроки). Такі операції називають багатокроковими.
У основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом. Цей принцип і ідея включення конкретного завдання оптимізації в сімейство аналогічних багатокрокових завдань призводять до рекурентним співвідношенням - функціональним рівнянням - відносно оптимального значення цільової функції. Їх рішення дозволяє послідовно отримати оптимальне управління для вихідної задачі оптимізації.
В
Дамо загальний опис моделі динамічного програмування.
Розглядається керована система, яка під впливом управління переходить з початкового стану в кінцевий стан. Припустимо, що процес управління системою можна розбити на n кроків. Нехай,, ..., - стану системи після першого, другого, ..., n-го кроку. Схематично це показано на рис. 1. p> Стан системи після k-го кроку (k = 1,2, ..., n) характеризується параметрами, які називають фазовими координатами. Стан можна зобразити точкою s-мірного простору, званого фазовим простором. Послідовне перетворення системи (по кроках) досягається за допомогою деяких заходів, які складають управління системою U =,
де - Управління на k-му кроці, що переводить систему зі стану в стан (рис.1). Управління на k-му кроці полягає у виборі значень певних керуючих змінних.
Припускаємо надалі, що стан системи наприкінці k-го кроку залежить тільки від попереднього стану системи і управління на даному кроці (рис.1). Таке свойст під отримало назву відсутності наслідки. Позначимо ...
