27. Постановка транспортной задачи. Балансировка задачи.

Имеется двудольный граф

a ,b – объем товара

с – стоимость доставки товара

И.Д.: a_i , i = 1..n (количество единиц товара от поставщиков)

B_j, j = 1..m (количество единиц товара потребителям)

c_ji – стоимость транспортировки единицы товара от i-го поставщика j-ому потребителю (руб./ед.товара)

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

1. Штрафы за недопоставку ед.товара j-ому потребителю С2_j , j = 1..m ( < )

2. Издержки на хранение оставшегося на складе товара (стоимость хранения товара на i-ом складе) С1_i , i = 1..n ( > )

Балансировка задачи:

Под балансировкой транспортной задачи будем понимать задачу, в которой = .

Сведение Т.З. к сбалансированной:

1. <

Вводится фиктивный поставщик, при этом весь недостающий товар - =

С_n+1,j = C_2j

2. >

Вводится фиктивный потребитель, при этом требуемый товар - =

С_i,m+1 = C_1i

28. Сведение транспортной задачи к задаче линейного программирования.

П.З.: Пусть имеются 2 поставщика и три потребителя

С = (стоимость перевозок)

Целевая функция:

Обозначим x_ij – план перевозок, т.е. сколько единиц товара следует перевезти от i-ого поставщика j-ому потребителю.

Ограничения:

29. Постановка транспортной задачи. Поиск допустимого нач.Решения. Метод с-з угла. Метод min стоимости.

(Из предыдущего вопроса)

П.З.: Пусть имеются 2 поставщика и три потребителя

С = (стоимость перевозок)

Найти: план перевозок, т.е. сколько единиц товара следует перевезти от i-ого поставщика j-ому потребителю.

Метод СЗ угла:

= 4·300+5·100+5·0+3·0+6·100+4·400=3900 руб.

Метод min стоимости:

Начинаем с клеточки, где min стоимость (3).

= 4·0+5·200+5·200+3·300+6·0+4·200=3700 руб.

30-31. Метод потенциалов.

Пусть имеются 3 поставщика и 4 потребителя.

U , V – потенциалы.

1. Сбалансируем задачу:

2. Определить начальн. допустимый план:

= 9·200+4·150+6·50+3·250+5·150+3·100+3·100=4800 руб.

3. Определение включаемой в базис переменной.

Определение потенциалов:

Ui, i=1..n; Vj, j=1..m

Базисные переменные:

Для базисных переменных: Ui+Vj=Cij (стоимость перевозки):

U1+V2=9; U2+V1=4; U2+V2=6; U2+V3=3; U2+V4=4;U3+V1=3;

U4+V4=3.

7 уравнений и 8 неизвестных => 1 переменная свободная, принимаем ее = 0.

Н-р: U1=0 => U2=-3; U3=-4; U4=-5; V1=7; V2=9; V3=6; V4=8.

Коэффициенты целевой функции (для Симплекс метода):

Включ. в базис переменная X_11.

4. Определение исключаемой из базиса переменной.

Построение цикла

5. Определение потенциалов:

Включаем в базис переменную С_32.

И сключаем переменную X₁₂ (=0)_.

32. Задача о построении минимального покрытия графа (остова)

ПЗ: Имеется сеть из N узлов. Соединение между узлами оценивается в единицах (н-р, расстояние в м, км, ст. в руб.).

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

Общая протяженность д.б. минимальной. Остовы:

Метод решения: Метод определения минимального остова::

	1	2	3	4	5	6
1	0	12	10	15	0	0
2	12	0	0	8	9	16
3	10	0	0	5	0	10
4	15	8	5	0	9	14
5	0	9	0	9	0	10
6	0	16	10	14	10	0

1. Выбираем самое минимальное соед., заносим соед-ые узлы в список:

P Сп1={(3,4)}; список1={3,4};

2. Пока не все вершины находятся в списке: 2.1

2.1 Определим узел, не принадлежащий списку, из которого имеется самое мин. сиз которого имеется самое мин. ащий списку2.1

до множества узлов, принадлежащих списку. Добавляем это соед. в остов

P Cп2={(3,4);(2,4)} Cп2={3,4,2}

P Cп3={(3,4);(2,4);(2,5)} Сп3 = {3,4,2,5}

P Cп3={(3,4);(2,4);(2,5);(1,3)} Сп4={3,4,2,5,1}

P Cп5={(3,4);(2,4);(2,5);(1,3),(3,6)} Сп5= {3,4,2,5,1,6} P Cп – список ребер!

33.Задача о минимальном пути. Метод потенциалов

Дано:

N узлов сети и дана матрица расстояний (стоимости) соед. между уздами. Требуется найти путь минимальной длины из узла № N1 до узла № N2. Граф может быть ориентированным N1=Y1 N2=Y8

	1	2	3	4	5	6	7	8
1	01	61	71	81	01	01	01	01
2	61	01	4	0	7	10	0	0
3	71	4	01	5	12	8	10	0
4	81	0	5	01	0	12	7	0
5	01	7	12	0	01	3	0	6
6	01	10	8	12	3	01	2	4
7	01	0	10	7	0	2	01	4
8	01	0	0	0	0	4	4	01

Метод потенциалов:

Начальной вершине присваиваем 0-ой потенциал. Потенциал – минимальное расстояние между вершиной, имеющей потенциал, и другой вершиной.

1.Определение потенциала начального узла φ1=0, Сп ={1}, Edges_ij=0, i,j=1..n – это ребра

2. Расчет потенциалов:

2.1. Для каждой вершины k из списка рассмотрим ребра вида Edges_kj=0, Если φ_j > φ_k +C_kj то φ_j = φ_k +C_kj , Edges_kj=0, Сп = Сп +{j}

2.2. Если существует i, j такое что Edges_ij=0, то возврат к п. 2.1.

3. Определение минимального пути. Путь = (N2)

3.1. Для первой вершины имеющегося пути, k ищем j: C_jk = φ_k - φ_j

3.2. Добавляем путь Путь = Путь +{j}

3.3. Если j ≠ N1 то идти к п. 3.1

4. Вывод пути и его стоимости

Пример:

1). Сп={1}, Edges_ij=0, φ₁=0

2). φ₂=6, φ₃=7, φ₄=8. Сп={1,2,3,4}

3). φ₅=13, φ₃=16, φ₃=10 (т.к. φ₃:10>7, то оставляем 7), φ₆=15, φ₇=17, φ₇=15

4). Сп = {1,2,3,4,5,6,7}, φ₈=19.

φ:

1	2	3	4	5	6	7	8
0	6	7	8	13	15	15	19

5. Нахождение оптимального пути:

Путь1=(Y5,Y8)

Путь2=(Y2,Y5,Y8)

Путь3=(Y1,Y2,Y5,Y8)