Пример решения транспортной задачи (закрытая модель). Исследование операций

Сентябрь 11, 2022

Главная
Экономика
Пример решения транспортной задачи (закрытая модель). Исследование операций

Содержание

2. Задача Составить оптимальный план перевозок груза из трех пунктов отправления с запасами 30, 48, 24 т
3. Рассмотрим методы построения опорных планов (опорного решения) ТЗ
4. Метод северо-западного угла Заполняют клетку A1B1, (левый верхний угол), поставив в него min(a1b1). Если min совпадает
5. Решение задачи методом северо-западного угла 102 18 1шаг 12 2 шаг 15 3 шаг 33 4
6. Опорное решение задачи
7. Метод аппроксимации Фогеля 1. На каждом шаге находят разности между двумя наименьшими тарифами (даже если они
8. Решение задачи методом аппроксимации Фогеля 102 Х Х Х Х Х Х 15 6 шаг 15
9. Опорное решение задачи
10. Метод минимальной стоимости для нахождения опорного плана Предполагает заполнение на каждом шаге клеток с минимальным тарифом,
11. Решение задачи методом наименьшей стоимости 102 15 3 шаг 12 4 шаг 36 6 шаг 6
12. Опорное решение задачи
13. Метод потенциалов базируется на следующей теореме (признак оптимальности решения): Для заполненных ячеек таблицы должно выполняться условие:
14. Проверим план, полученный с помощью метода наименьшей стоимости, на оптимальность n+m-1=4+3-1=6 Должно быть заполнено 6 ячеек.
15. Составим систему уравнений для заполненных ячеек: u1 + v2 = 7 u1 + v4 = 5
16. Проверим второе условие теоремы для незаполненных ячеек u1 + v1 = 6 ≤ C11 = 13
17. осуществляется с помощью циклического сдвига Перераспределение грузов Цикл - ломанная, вершины которой находятся в заполненных ячейках,
18. Построим цикл: Построение цикла u1 + v3 = 12 > C13 = 11 Всем вершинам ломанной
19. В свободную клетку помещаем груз величиной α, равной минимальному значению из всех чисел в отрицательных клетках
20. Составим систему уравнений для заполненных ячеек: u1 + v3 = 11 u1 + v4 = 5
21. Проверим второе условие теоремы для незаполненных ячеек u1 + v1 = 5 ≤ C11 = 13
22. Оптимальное решение: Zmin=15*11+15*5+27*8+21*13+18*6+6*12=909
24. Скачать презентацию

Слайд 2

Задача
Составить оптимальный план перевозок груза из трех пунктов отправления с запасами

30, 48, 24 т в четыре пункта назначения с потребностями 18, 27, 42, 15 т. Тарифы перевозок сij (в ден/ед.) из (i= 1,2,3) в (j=l,..,4) приведены в матрице

Слайд 3

Рассмотрим методы построения опорных планов (опорного решения) ТЗ

Слайд 4

Метод северо-западного угла
Заполняют клетку A1B1, (левый верхний угол), поставив в него

min(a1b1). Если min совпадает с A1, то запасы пункта A1 считают исчерпанными и переходят к удовлетворению потребностей b1 начиная с ячейки А2В1.
Затем переходят к заполнению клетки А2В2. Перемещаясь так по диагонали, доходят до последней клетки АmВn. При этом все грузы будут исчерпаны, и потребности пунктов удовлетворены.
Замечание: если на некотором шаге исчерпаны запасы, то переходим к удовлетворению потребностей как это было описано выше. Если же были удовлетворены потребности, то приступают к исчерпыванию запасов аналогичным способом.

Слайд 5

Решение задачи методом
северо-западного угла
102
18
1шаг
12
2 шаг
15
3 шаг
33
4 шаг
9
5 шаг
15
6 шаг
Х
Х
Х
Х
Х
Х
12
15
33
9
15

Слайд 6

Опорное решение задачи

Слайд 7

Метод аппроксимации Фогеля
1. На каждом шаге находят разности между двумя наименьшими

тарифами (даже если они одинаковые) во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
2. Из найденных разностей выбирают максимальную и заполняют клетку, которой соответствует данная разность.
Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям.

Слайд 8

Решение задачи методом аппроксимации Фогеля
102
Х
Х
Х
Х
Х
Х
15
6 шаг
15
2 шаг
27
3 шаг
21
4 шаг
18
1 шаг
6
5 шаг
5
1
1
2
2
1
3
6
В
2
1
1
15
В
4
5
2
В
21
В
В
В
В
11
13
12

Слайд 9

Опорное решение задачи

Слайд 10

Метод минимальной стоимости для нахождения опорного плана
Предполагает заполнение на каждом шаге

клеток с минимальным тарифом, что даст, очевидно, меньшие суммарные затраты на перевозку груза.

Слайд 11

Решение задачи методом наименьшей стоимости
102
15
3 шаг
12
4 шаг
36
6 шаг
6
5 шаг
Х
Х
Х
Х
Х
18
2 шаг
15
1 шаг
Х
15
6
12
36
36

Слайд 12

Опорное решение задачи

Слайд 13

Метод потенциалов
базируется на следующей теореме (признак оптимальности решения):
Для заполненных ячеек таблицы должно

выполняться условие:

Для незаполненных ячеек условие:

(причем количество заполненных ячеек в опорном плане должно быть равно n+m-1, где m – число поставщиков, n – число потребителей)

Слайд 14

Проверим план, полученный с помощью метода наименьшей стоимости, на оптимальность
n+m-1=4+3-1=6
Должно быть

заполнено 6 ячеек.

Реально заполненных ячеек тоже 6.

Слайд 15

Составим систему уравнений для заполненных ячеек:
u1 + v2 = 7
u1 + v4

= 5
u2 + v2 = 8
u2 + v3 = 13
u3 + v1 = 6
u3 + v3 = 12

Полагая u1 = 0, найдем:

Так как v2 = 7, то

v2 = 7

v4 = 5

u2 = 1

Так как u2 = 1, то

v3 = 12

Так как v3 = 12, то

u3 = 0

Так как u3 = 0, то

v1 = 6

Итак, u1 = 0, u2 = 1, u3 = 0, v1 = 6, v2 = 7, v3 = 12, v4 = 5

Слайд 16

Проверим второе условие теоремы для незаполненных ячеек
u1 + v1 = 6 ≤

C11 = 13 +

План X1 не оптимальный, поэтому необходимо перераспределение грузов

u1 = 0, u2 = 1, u3 = 0,
v1 = 6, v2 = 7, v3 = 12, v4 = 5

u1 + v3 = 12 > C13 = 11 (−1)

u2 + v1 = 7 ≤ C21 = 11 +

u2 + v4 = 6 ≤ C24 = 7 +

u3 + v2 = 7 ≤ C32 = 10 +

u3 + v4 = 5 ≤ C34 = 9 +

Слайд 17

осуществляется с помощью циклического сдвига
Перераспределение грузов
Цикл - ломанная, вершины которой находятся

в заполненных ячейках, кроме одной. Это одна вершина должна находиться в незаполненной ячейке, для которой ui + vj > Cij.

При этом звенья ломанной должны удовлетворять следующим условиям:
Параллельность строкам и столбцам
В каждой строке и каждом столбце не более двух вершин

Слайд 18

Построим цикл:
Построение цикла
u1 + v3 = 12 > C13 = 11
Всем

вершинам ломанной припишем + или –, начиная с проблемной ячейки:

Слайд 19

В свободную клетку помещаем груз величиной α, равной минимальному значению из

всех чисел в отрицательных клетках цикла.

Циклический сдвиг

Min (15,36)=15

Новый план:

Сдвиг по циклу: Во все положительные клетки прибавляем α, из отрицательных – вычитаем α.

Проверим новый план на оптимальность

Слайд 20

Составим систему уравнений для заполненных ячеек:
u1 + v3 = 11
u1 + v4

= 5
u2 + v2 = 8
u2 + v3 = 13
u3 + v1 = 6
u3 + v3 = 12

Полагая u1 = 0, найдем:

Так как v3 = 11, то

v3 = 11

v4 = 5

u2 = 2

Так как u2 = 2, то

v2 = 6

Так как v3 = 11, то

u3 = 1

Так как u3 = 1, то

v1 = 5

Итак, u1 = 0, u2 = 2, u3 = 1, v1 = 5, v2 = 6, v3 = 11, v4 = 5

Слайд 21

Проверим второе условие теоремы для незаполненных ячеек
u1 + v1 = 5 ≤

C11 = 13 +

План X2 оптимальный

u1 = 0, u2 = 2, u3 = 1,
v1 = 5, v2 = 6, v3 = 11, v4 = 5

u1 + v2 = 6 ≤ C12 = 7 +

u2 + v1 = 7 ≤ C21 = 11 +

u2 + v4 = 7 ≤ C24 = 7 +

u3 + v2 = 7 ≤ C32 = 10 +

u3 + v4 = 6 ≤ C34 = 9 +

Слайд 22

Пример решения транспортной задачи (закрытая модель). Исследование операций

Содержание

ЗадачаСоставить оптимальный план перевозок груза из трех пунктов отправления с запасами

Рассмотрим методы построения опорных планов (опорного решения) ТЗ

Метод северо-западного углаЗаполняют клетку A1B1, (левый верхний угол), поставив в него

Решение задачи методом северо-западного угла102181шаг122 шаг153 шаг334 шаг95 шаг156 шагХХХХХХ121533915

Опорное решение задачи

Метод аппроксимации Фогеля1. На каждом шаге находят разности между двумя наименьшими

Решение задачи методом аппроксимации Фогеля102ХХХХХХ156 шаг152 шаг273 шаг214 шаг181 шаг65 шаг51122136В21115В452В21ВВВВ111312

Опорное решение задачи

Метод минимальной стоимости для нахождения опорного планаПредполагает заполнение на каждом шаге

Решение задачи методом наименьшей стоимости102153 шаг124 шаг366 шаг65 шагХХХХХ182 шаг151 шагХ156123636

Опорное решение задачи

Метод потенциаловбазируется на следующей теореме (признак оптимальности решения):Для заполненных ячеек таблицы должно

Проверим план, полученный с помощью метода наименьшей стоимости, на оптимальностьn+m-1=4+3-1=6Должно быть

Составим систему уравнений для заполненных ячеек:u1 + v2 = 7u1 + v4

Проверим второе условие теоремы для незаполненных ячеекu1 + v1 = 6 ≤

осуществляется с помощью циклического сдвигаПерераспределение грузовЦикл - ломанная, вершины которой находятся

Построим цикл:Построение циклаu1 + v3 = 12 > C13 = 11Всем

В свободную клетку помещаем груз величиной α, равной минимальному значению из

Составим систему уравнений для заполненных ячеек:u1 + v3 = 11u1 + v4

Проверим второе условие теоремы для незаполненных ячеекu1 + v1 = 5 ≤

Оптимальное решение:Zmin=15*11+15*5+27*8+21*13+18*6+6*12=909

Похожие презентации

Задача
Составить оптимальный план перевозок груза из трех пунктов отправления с запасами

Метод северо-западного угла
Заполняют клетку A1B1, (левый верхний угол), поставив в него

Решение задачи методом
северо-западного угла
102
18
1шаг
12
2 шаг
15
3 шаг
33
4 шаг
9
5 шаг
15
6 шаг
Х
Х
Х
Х
Х
Х
12
15
33
9
15

Метод аппроксимации Фогеля
1. На каждом шаге находят разности между двумя наименьшими

Решение задачи методом аппроксимации Фогеля
102
Х
Х
Х
Х
Х
Х
15
6 шаг
15
2 шаг
27
3 шаг
21
4 шаг
18
1 шаг
6
5 шаг
5
1
1
2
2
1
3
6
В
2
1
1
15
В
4
5
2
В
21
В
В
В
В
11
13
12

Метод минимальной стоимости для нахождения опорного плана
Предполагает заполнение на каждом шаге

Решение задачи методом наименьшей стоимости
102
15
3 шаг
12
4 шаг
36
6 шаг
6
5 шаг
Х
Х
Х
Х
Х
18
2 шаг
15
1 шаг
Х
15
6
12
36
36

Метод потенциалов
базируется на следующей теореме (признак оптимальности решения):
Для заполненных ячеек таблицы должно

Проверим план, полученный с помощью метода наименьшей стоимости, на оптимальность
n+m-1=4+3-1=6
Должно быть

Составим систему уравнений для заполненных ячеек:
u1 + v2 = 7
u1 + v4

Проверим второе условие теоремы для незаполненных ячеек
u1 + v1 = 6 ≤

осуществляется с помощью циклического сдвига
Перераспределение грузов
Цикл - ломанная, вершины которой находятся

Построим цикл:
Построение цикла
u1 + v3 = 12 > C13 = 11
Всем

Составим систему уравнений для заполненных ячеек:
u1 + v3 = 11
u1 + v4

Проверим второе условие теоремы для незаполненных ячеек
u1 + v1 = 5 ≤

Оптимальное решение:
Zmin=1511+155+278+2113+186+612=909