Презентация на тему: Решение транспортной задачи на графах

Реклама. Продолжение ниже
Решение транспортной задачи на графах
Транспортная задача
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Обозначения
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Общий план метода потенциалов
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
Решение транспортной задачи на графах
1/25
Средняя оценка: 4.1/5 (всего оценок: 56)
Код скопирован в буфер обмена
Скачать (145 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Решение транспортной задачи на графах

Изображение слайда
1/1
2

Слайд 2: Транспортная задача

Одна из задач линейного программирования. Она возникает при планировании наиболее рациональных перевозок груза.

Изображение слайда
1/1
3

Слайд 3

Имеется три пункта производства А 1, А 2, А 3 и три пункта потребления В 1, В 2, В 3. Запасы пунктов производств и потребность пунктов потребления указаны. Производство будем интерпретировать как отрицательную потребность. а 1 = 50 а 2 = 150 а 3 = 200 b 1 = 100 b 2 = 100 b 3 = 200

Изображение слайда
1/1
4

Слайд 4

Требуется перевести товар с минимальной стоимостью, учитывая стоимость перевозки одной единицы товара по указанной дороге. пункты поставки пункты потребления В 1 В 2 В 3 А 1 3 2 1 А 2 6 3 5 А 3 4 3 6

Изображение слайда
1/1
5

Слайд 5: Обозначения

Имеется m пунктов производства некоторого одного продукта, задан a i – объем производства в i -м пункте производства. Есть n пунктов потребления этого продукта, задан b j – объем потребления в j -м пункте потребления.

Изображение слайда
1/1
6

Слайд 6

Перевозку из i -го пункта производства к j -му пункту потребления обозначим дугой ij. X ij – количество перевозимых товаров из i в j. C ij – стоимость перевозки единицы продукции по дуге ij.

Изображение слайда
1/1
7

Слайд 7

-50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Общий план метода потенциалов

Изображение слайда
1/1
9

Слайд 9

1) Определить начальный базисный план (дерево). Дерево – это граф без циклов, число дуг которого на единицу меньше числа вершин, или связный граф без циклов.

Изображение слайда
1/1
10

Слайд 10

Считаем стоимость перевозки S 0. S 0 =50*1+100*6+50*3+50*3+150*6= 1850 -50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 100 50 50 50 150 1 6 3 3 6

Изображение слайда
1/1
11

Слайд 11

2) Вычисляем потенциал вершин, полагая, что один потенциал равен нулю, и двигаемся по дугам дерева, используя формулы: v к = v н + c v н = v к - c

Изображение слайда
1/1
12

Слайд 12

-50 -150 -200 100 100 200 100 50 50 50 150 1 6 3 3 6 0 1 -5 -2 -5 1

Изображение слайда
1/1
13

Слайд 13

3) Выбираем дугу, которая не принадлежит плану (дереву) и не удовлетворяет условию дополняющей нежесткости (УДН). v к - v н c

Изображение слайда
1/1
14

Слайд 14

-50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 0 -5 -5 1 -2 1

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15

Вводим ее в базисный план с перевозкой Q. Q=min{ 150 ; 50 }= 50 -50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 0 -5 -5 1 -2 1 + _ + _ 100 50 50 50 150

Изображение слайда
1/1
16

Слайд 16

4) Пересчитываем стоимость S 1. S 1 = S 0 + Q (стоимость перевозок по дугам цикла с учетом ориентации) S 1 = 1850 + 50 ( 5 - 6 + 3 - 3 )= 1850 + 50 (- 1 )= 1800 -50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 + _ + _ 100 50 50 50 150

Изображение слайда
1/1
17

Слайд 17

5) Выводим дугу, на которой выявился минимум из плана, вместо нее вводим Q. Пересчитываем количество перевозки по дугам цикла с учетом ориентации. -50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 100 50 100 50 100 1 6 5 3 6

Изображение слайда
1/1
18

Слайд 18

Пересчитываем стоимость перевозки S 1 = 50*1+100*6+50*5+100*6+100*3 = 1800 -50 -150 -200 100 100 200 100 50 100 50 100 1 6 5 3 6

Изображение слайда
1/1
19

Слайд 19

6) Получаем новый план-дерево. -50 -150 -200 100 100 200 100 50 100 50 100 1 6 5 3 6

Изображение слайда
1/1
20

Слайд 20

Повторяем 2-6 до тех пор, пока все дуги, входящие в дерево, не будут удовлетворять УДН. -50 -150 -200 100 100 200 100 50 100 50 100 1 6 5 3 6 0 -5 -4 1 -2 2

Изображение слайда
1/1
21

Слайд 21

-50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 0 -5 -4 1 -2 2

Изображение слайда
1/1
22

Слайд 22

-50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 0 -5 -4 + _ + _ 100 50 100 50 100 1 -2 2 Q=min{ 100 ; 100 }= 100 S 1 = 1800 + 100 ( 4 - 6+ 5- 6 )= 1800+100(-3) = 1500

Изображение слайда
1/1
23

Слайд 23

S 1 = 50*1 +150* 5 +100* 4 + 100 * 3 + 0*6 = 1500 -50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 100 150 100 50 0 1 5

Изображение слайда
1/1
24

Слайд 24

-50 -150 -200 100 100 200 3 2 1 6 3 5 4 3 6 100 150 100 50 0 0 -5 -4 -1 1 -2

Изображение слайда
1/1
25

Последний слайд презентации: Решение транспортной задачи на графах

Оптимальная стоимость перевозок 1500

Изображение слайда
1/1
Реклама. Продолжение ниже