100. Одномерная задача динамического программирования.

Задача динамического программирования – это частный случай задачи нелинейного программирования, когда решение может быть получено соответствующим методом. Одной из наиболее простых является следующая нелинейная одномерная распределительная задача.

Необходимо оптимальным образом распределить ресурс в объеме x_o по n вариантам (объектам, схемам, этапам) при целевой функции

и ограничениях

,

где x_i – объем ресурса, назначаемый по i-му варианту;

0 £x_i £ x_о;

f (x ) – нелинейная функция, определяющая эффект (затраты) в зависимости от значений x;

n – общее число вариантов; x_о – общий объем распределяемого ресурса.

Этой моделью описывается задача оптимального распределения однородного ограниченного по количеству ресурса (сырья, денег, машин и т.д.).

Обозначим через x_ci – количество ресурса, назначаемого суммарно по i-му варианту и всем предыдущим вариантам. При этом объем ресурса по предыдущим вариантам распределен оптимально исходя из минимума затрат или максимума эффекта.

Тогда целевая функция Z_i при рассмотрении i-го этапа решения определяется по выражению

Z_i(x_ci, x_i )= f_i(x_i) + f* _i-1 (x_ci - x_i ),

где 0 £x_сi £ x_о при i £ n-1 и x_сi= x_о при i = n;

f*_i-1 – функция, определяющая эффект (затраты) оптимальным образом по предыдущим вариантам в зависимости от объема ресурса x_ci-1;

Значение f*_i определяется по Z_i :

для i =1;

, i =2,n.

Определение и соответствующих им при данном x_сi производятся поэтапно от i=2 до i=n.

По окончательному результату поэтапных расчетов формируется оптимальное решение x_{о i}:

x_{о i} = (для i = n);

x_{о i} = при (для i = n,2,-1);

(для i=1).

Вариант алгоритма решения однопродуктовой задачи динамического программирования приведен ниже. Решение предусмотрено для целевой функции, подлежащей оптимизации на максимум. Для решения задачи на минимум необходимо ввести исходные значения s_вji с отрицательным знаком или внести изменения в блоках 12 (заменить 1E+12 на -1E+12) и 15 (условие < на >).

Выводимые j, k_jid_x , s_nm представляют соответственно номер варианта, объем ресурса по варианту и значение целевой функции для оптимального решения.

101. Задача СПУ. Расчет критического времени и нахождения критического пути.

Задача упорядочения – это задача определения оптимальной последовательности событий, а задачи согласования охватывают сетевое планирование и управление.

Основа решения первых – теория расписаний, вторых – теория графов.

Предметом сетевого планирования и управления (СПУ) является разработка и оптимизация сетевых графиков.

Сетевой график – это ориентированный граф, дуги которого имеют одну или несколько числовых характеристик. Дугами изображают работы, а вершинами – события.

Работа – это процесс, сопровождающийся затратами времени и ресурсов. Если имеются затраты только времени – это фиктивные работы (естественная сушка и т.п.).

Событие – это итог процесса или его части. Оно совершается, когда закончены все предшествующие ему работы.

Путь – это любая непрерывная последовательность работ от исходного события до завершающего (т.е. до конечной цели).

Длина пути определяется суммой продолжительности лежащих на нем работ.

1. Критическое время сетевого графика - минимальный период времени в течении кторого может быть выполнен весь комплекс работ сетевого графика.

t_кр = T_рm = Т_рi

2. Определяется критический путь. Это путь, продолжительность которого равна критическому времени – минимальному времени, в течение которого может быть выполнен весь процесс и проходит через события с нулевым резервом времени и включает работы с нулевым полным резервом.

102.Постановка задачи о коммивояжере.

Имеется n пунктов, в которых должен побывать коммивояжер. Задана матрица стоимостей (расстояний, времени и т.п.) на переход между пунктами c_ij , i=1,2,...,n и j=1,2,...,n. Коммивояжер должен выйти из одного из пунктов, побывать во всех остальных пунктах по одному разу и вернуться в начальный пункт.

Необходимо найти порядок обхода, дающий минимальную суммарную стоимость посещения всех пунктов.

Введем переменную K_jj

1, при переходе между пунктами i и j

K_ij = .

0, если нет перехода между пунктами и j

Необходимо найти множество {K_ij }, i=1,2,...,n и j=1,2,...,n, дающее минимум

и выполнение ограничений

; (*)

; (**)

U_i -U_j +nK _ij  n-1, i  j, (***)

где U_i , U_j – целые неотрицательные числа, представляющие собой номер этапа, на котором посещается пункт.

Условие (*) означает, что коммивояжер выходит из каждого пункта один раз, а условие (**) – что он входит в каждый пункт только один раз. Условие (***) обеспечивает замкнутость цикла (контура) только на n-м этапе решения задачи.

Задача без учета условия (***), представляет постановку, аналогичную задаче о назначениях и отличается тем, что целевая функция стремится к минимуму (Z→min). Если при ее решении получен замкнутый контур, то это оптимальное решение, а иначе полученное значение целевой функции является той оценкой, которая всегда меньше или равна целевой функции (длине пути) с учетом условия (***).

Точное решение задачи дает метод ветвей и границ, а приближенные – метод ближайшего соседа, метод сумм (изложен ранее для составления сборочно-развозочных маршрутов), метод Кларка-Райта.

103.Приближённые методы решения транспортных задач.

Эвристические методы – это приближенные методы решения оптимизационных задач на основе "опытных предположений". Преимуществом таких методов является ускорение получения рационального решения с одновременным учетом всех установленных ограничений.

Такие методы применяются для решения:

транспортной задачи линейного программирования – метод Фогеля;

маршрутизации перевозок ресурсов мелкими отправками по сборочно-развозочным маршрутам – метод на основе кратчайшей связывающей сети и метод на основе расчета выигрышей (метод Кларка-Райта);

маршрутизации перевозок ресурсов помашинными отправками – метод "гарантированного эффекта" и методы на основе расчета выигрышей по типу метода Кларка-Райта.