29. Задача о замене как задача поиска кратч пути

Данная задача явл-ся актуальной для мн.практич приложений и м.б.решена методом динамического программирования с исп-нием критерия пути. Задача о замене: Компа о замене: Комп-ия автомобилей разраб план по обновлению парка своих машин на 5-летний период.Характ-ки затрат, связ с эксплуатацией и заменой старой машины на новую,заданы в табл.1.Для простоты считаем,что оп-ция по замене может произвся 1 раз в год в его начале.

Возраст машины,лет	Ст-ть замены на новую,т.р.	Ст-ть годов. Обслуж(в.т.р)
1	80	3
2	90	8
3	110	18
4	140	30
5	180	45

Треб-ся опр-ть момент замены старых машин на новые при усл,что пределом «возраста» машины явл-ся 5 лет.Решение:

Представим все возможные вар-ты замен в виде сетей, вершины к-ых соответ. моментам принятия и осущ-ия решений по заменам или эксплуатации, с дуги – операциям, связанным либо с заменой,либо с дальнейшей эксплуат. Стрелки, направленные вправо-вверх,означ.дальнейшую эксплуат.; стрелки,направл.вниз, означ.замену машины на новую.Рядом с каждой стрелкой проставлено число, означающее ст-ть соотв. операции. Интерпретируем числа стоящие у дуг, как длины этих дуг. И тогда задача по оптимизации замен в течение всего периода сводится к поиску кратчайшего пути м/у нач. и кон. вершинами пути. Кратч.путь найдем методом прогонки. На первом этапе обратной прогонкой каждой вершине сети найдем длину наикротчайшего пути м/у этой вер-ой и кон.вершиной сети. После чего прямой прогонкой определим оптим.путь. По ходу решения неоптим.дуги будем зачеркивать двойными штрихами, а оптим.-отразим жир.стрелками. Оптимальная длина кратчайшего маршрута равна 240. Что соответ. оптим. стратегиям по заменам машины, отмеченной на рис. жир. стрелками. Получим 2 варианта оптим.цикла по эксплуатации и замене

1 цикл: 5=3(экспл)+(замена)+2(экспл)

2 цикл: 5 = 2(экспл)+(замена)+3(экспл)

Общие издержки для обоих циклов равны 240 т.р.

30. Задача поиска мин остовного дерева

Треб-ся построить граф, все вершины кот. соед-ся путями наим суммарной длины.

Шаг 1: выб-ся ¥ вершина исходной сети в качестве начальной вершины строящегоя графа.

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

32. Задача о потоке наименьшей ст-ти.

Пусть задана сеть с графом Г(X,A) и м-цей G=(g_ij)_m*n. Пусть кажд. дуге α_i сопост 2 числа c_i и p_i, означающ. пропускную спос-ть и ст-ть пропуска ед-цы потока соотв-но. Треб-ся найти потоки наим суммарной ст-ти по данной сети при усл., что величина потока, втекающ. в узел-приёмник x_q не меньше заданной в-ны τ. Обозначим ч/з z_i в-ну потока по дуге α_i. Тогда задача прин.вид:

f(z^→)=∑^m_i=1 p_iz_i→min,(1)

∑^m_i=1 (g_ip+g_iq)z_i=0

∑^m_i=1 g_iqz_i ≥ τ

z_i ≤ c_i, z_i ≥0, i=1,¯m

Второе огран-е означает, что суммарный поток по узлу-приёмнику не меньше заданной в-ны τ.