Задачи выбора маршрута или сетевые задачи

Этап 3. Если полученное распределение  ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

Данный итеративный  процесс повторяется до тех пор, пока не будет получено оптимальное  решение.

 

 

Пример решения транспортной задачи.

 

 

Задача 1. Из трех холодильников Ai, i=1..3, вмещающих мороженную рыбу в  количествах ai т, необходимо последнюю доставить в пять магазинов Bj, j=1..5 в количествах bj т. Стоимости перевозки 1т рыбы из холодильника Ai в магазин Bj заданы в виде матрицы Cij, 3x5.

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

        

 

 

 

H

Решение.

Составим математическую модель задачи. Пусть x_i,j - количество т рыбы, перевозимой из холодильника (поставщика) A_i в магазин (потребитель) B_j. Тогда задача заключается в минимизации общих транспортных расходов

 

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

 

Задача имеет  закрытый тип, т.к. запасы груза 320+280+250 = 850 т равны суммарным потребностям магазинов 150+140+110+230+220 = 850 т.

Составим опорный план по правилу минимального элемента.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 0	23 0	20 0	15 0	24 0	320
A2	29 0	15 0	16 0	19 0	29 0	280
A3	6 0	11 0	10 0	9 0	8 0	250
Потребн.	150	140	110	230	220

Введем некоторые обозначения: Ai* - излишек нераспределенного груза  от

поставщика Ai, Bj* - недостача  в поставке груза потребителю Bj.

Находим незанятую клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=250 и B1*=150.

Находим незанятую клетку с минимальным тарифом: (3,5). Помещаем туда меньшее из чисел A3*=100 и B5*=220.

Находим незанятую клетку с минимальным тарифом: (1,4). Помещаем туда меньшее из чисел A1*=320 и B4*=230.

Находим незанятую клетку с минимальным тарифом: (2,2). Помещаем туда меньшее из чисел A2*=280 и B2*=140.

Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=140 и B3*=110. Находим незанятую клетку с минимальным тарифом: (1,5).

Помещаем туда меньшее  из чисел A1*=90 и B5*=120.

Находим незанятую клетку с минимальным тарифом: (2,5). Помещаем туда меньшее из чисел A2*=30 и B5*=30

Пришли к  таблице:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20	23 0	20 0	15 230	24 90	320
A2	29 0	15 140	16 110	19 0	29 30	280
A3	6 150	11 0	10 0	9 0	8 100	250
Потребн.	150	140	110	230	220

Транспортные  расходы составят z = 12040.

Решим задачу методом  потенциалов. Т.к. m+n-1=7 и имеем 7 загруженных  клеток, план ацикличный. Пусть Ui и Vj - потенциалы i-го склада и j-го магазина соответственно.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения U_i+V_j=C_i,_j, просматривая все занятые клетки. Получим:

Для свободных  клеток определим значения оценок (разностей между прямыми и косвенными тарифами).

Имеем две клетки с отрицательными оценками – (1,1) и (2, 4). Выбираем клетку с наименьшей оценкой (1, 1) и строим для нее цикл.

 

 

 

 

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	+         20	23	20	15 230	-           24 90	320
A2	29	15 140	16 110	19	29 30	280
A3	-             6 150	11	10	9	+            8 100	250
Потребн.	150	140	110	230	220

Перемещаем по циклу  груз величиной в 90 единиц, прибавляя  эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 90	23	20	15 230	24	320
A2	29	15 140	16 110	19	29 30	280
A3	6 60	11	10	9	8 190	250
Потребн.	150	140	110	230	220

Целевая функция (транспортные расходы) z = 11860. Значение целевой функции изменилось на 180 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

Определяем  значения оценок S_i,j=C_i,j-(U_i+V_j) для всех свободных клеток:

Имеем клетку (2, 4) с отрицательной оценкой, план не оптимален. Строим для этой клетки цикл.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	+          20 90	23	20	-           15 230	24	320
A2	29	15 140	16 110	+          19	-           29 30	280
A3	-            6 60	11	10	9	+           8 190	250
Потребн.	150	140	110	230	220

Перемещаем  по циклу груз величиной в 30 единиц, прибавляя эту величину к грузу  в клетках со знаком «плюс» и отнимая ее от груза в клетках со знаком «минус». В результате перемещения по циклу получим новый план:

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 120	23	20	15 200	24	320
A2	29	15 140	16 110	19 30	29	280
A3	6 30	11	10	9	8 220	250
Потребн.	150	140	110	230	220

Целевая функция (транспортные расходы) z= 11770, значение уменьшилось на 90 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

Определяем  значения оценок для всех свободных  клеток:

Так как все  оценки S_i,j>=0, то полученный план является оптимальным, минимальные транспортные расходы равны 11770. Оптимальный план перевозок представлен ниже.

Склад	Магазин					Запасы  груза
	B1	B2	B3	B4	B5
A1	20 120	23	20	15 200	24	320
A2	29	15 140	16 110	19 30	29	280
A3	6 30	11	10	9	8 220	250
Потребн.	150	140	110	230	220

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Сетевые задачи.

 

 

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

Ориентированным графом  называется тройка (I, D, G), в которой I – непустое множество вершин, D – множество дуг и G – отображение, которое каждой дуге d принадлежащей к D ставит в соответствие упорядоченную пару вершин (i, j), где i, j  принадлежит I. 

Неориентированным графом называется тройка (I, D, G), в которой I – непустое множество вершин, D – множество ребер и G – отображение, которое каждому ребру d принадлежащей к D ставит в соответствие неупорядоченную пару вершин [i, j], где i, j принадлежит I. 

Граф (I, D, G) называется конечным, если множества I и D конечны. 

 

Геометрически граф может  быть представлен в виде множества точек (изображающих вершины) и соединяющих их линий (со стрелками), соответствующих ребрам (дугам) (рис. 3.3, 3.4). Очевидно, что с каждым ориентированным графом можно однозначно связать неориентированный, заменив дуги на ребра. Если любые две вершины графа соединяются не более чем одной дугой (ребром), то граф называется простым и может быть задан с помощью пары (I, D). В этом случае каждая дуга (ребро) d полностью определяется парой соединяемых вершин (i, j), что условно записывается в виде: d=(i,j). Упорядоченная пара вершин (i, j), которая ставится в соответствие некоторой дуге d, задает ее ориентацию: i называется началом дуги, а j – ее концом, а сама дуга считается инцидентной данным вершинам.

Путем длины π в ориентированном графе (I, D) называется упорядоченная последовательность различных дуг (d1, d2,..., dn), для которых начало каждой последующей совпадает с концом предыдущей. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.

Для неориентированного графа аналогом понятия путь является цепь, а контура – цикл.

Если две любые вершины неориентированного графа могут быть соединены цепью, то он называется связным. Ориентированный граф называется связным, если ему отвечает связный неориентированный граф.

Связный неориентированный граф, не содержащий циклов, называется деревом.

Если Y D, а отображение GY является сужением отображения G на множество Y, то граф (I, Y, GY) называют частичным графом (реберным подграфом) графа (I, D, G).