Линейное программирование. Транспортная задача

Сентябрь 4, 2022

Главная
Алгебра
Линейное программирование. Транспортная задача

Содержание

2. Транспортная задача (ТЗ) В этих задачах, рассматривается операция по перевозке некоторых однородных грузов из пунктов отправления
3. Математическая модель ТЗ Логистическая компания располагает тремя пунктами упаковки косметики расположенными в Твери, Ярославле и Смоленске,
4. Недельная производительность по формированию косметических наборов и потребности в наборах в городах приведены на схеме. С.-Петербург
5. Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к каждому оптовому поставщику приведены в
6. Логистическая компания должна принять решение, сколько наборов с косметикой необходимо отправлять из каждого пункта упаковки каждому
7. Составление математической модели
8. Математическая модель задачи
9. Математическая модель задачи
10. Решение транспортной задачи методом потенциалов Рассмотрим задачу.
11. Алгоритм решения Проверяем условие баланса: запасы должны равняться потребностям. Составляем опорный план методом «северо-западного» угла.
12. Проверка условия баланса
13. Метод северо-западного угла При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге заполняют
14. Поиск опорного плана методом «северо-западного» угла ? Северо-западная клетка. В неё записываем наименьшее из чисел 25
15. 0 20 В таблице этот факт мы обозначаем при помощи прочерков.
16. 0 20 Следующая северо-западная клетка. Записываем в неё наименьшее из чисел 20 и 55. 20
17. 0 20 20 Пересчитываем запасы и потребности 35 0 −
18. Продолжаем находить опорный план 5
19. Продолжаем находить опорный план
20. Шаг 3
21. Проверка невырожденности опорного плана У нас 5 заполненных клеток
22. Шаг 4
23. Вычисление потенциалов
24. Шаг 5
25. Вычисление оценок
26. Шаги 6-7
27. Цикл пересчета Циклом пересчета в таблице ТЗ называется ломаная линия, вершины которой расположены в занятых клетках
28. Построение цикла
29. Шаг 8 8. Производят сдвиг по циклу пересчёта. Для этого каждой клетке таблицы, в которой находится
30. + + - - Расстановка знаков
31. Сдвиг по циклу пересчета 9. Повторяем шаги 4-7.
32. Вновь вычисляем потенциалы
33. Пересчитываем оценки
34. + + - - В клетках с минусами две одинаковые «загрузки» по 20 ед., когда мы
35. Пересчет потенциалов и оценок для нового плана
37. Замечание 1
38. Замечание 1 Так как мы решаем задачу минимизации, то из двух клеток стоит выбрать ту, где
40. Скачать презентацию

Слайд 2

Транспортная задача (ТЗ)
В этих задачах, рассматривается операция по перевозке некоторых однородных

грузов из пунктов отправления в пункты назначения, причём известны стоимости перевозки единицы груза между любыми двумя пунктами отправления и назначения.
Требуется составить оптимальный план перевозок, то есть определить количество груза перевозимого из каждого пункта отправления в каждый пункт назначения, при котором суммарная стоимость всех перевозок будет минимальной.

Слайд 3

Математическая модель ТЗ
Логистическая компания располагает тремя пунктами упаковки косметики расположенными в

Твери, Ярославле и Смоленске, откуда сформированные наборы перевозятся на грузовиках к трём оптовым поставщикам, расположенным в Москве, Санкт-Петербурге и Нижнем Новгороде.

Слайд 4

Недельная производительность по формированию косметических наборов и потребности в наборах в

городах приведены на схеме.

С.-Петербург

Ярославль

Тверь

Ниж. Новгород

Смоленск

Москва

30 тысяч

55 тысяч

25 тысяч

45 тысяч

20 тысяч

Слайд 5

Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к

каждому оптовому поставщику приведены в таблице.

Слайд 6

Логистическая компания должна принять решение, сколько наборов с косметикой необходимо отправлять

из каждого пункта упаковки каждому оптовому поставщику, чтобы:
1) все наборы с каждого пункта упаковки были вывезены;
2) спрос на наборы с косметикой каждого оптового поставщика был полностью удовлетворён;
3) суммарные затраты на транспортировку всех наборов были минимальными.

Слайд 7

Составление математической модели

Слайд 8

Математическая модель задачи

Слайд 9

Математическая модель задачи

Слайд 10

Решение транспортной задачи методом потенциалов
Рассмотрим задачу.

Слайд 11

Алгоритм решения
Проверяем условие баланса: запасы должны равняться потребностям.
Составляем опорный план методом

«северо-западного» угла.

Слайд 12

Проверка условия баланса

Слайд 13

Метод северо-западного угла
При нахождении опорного плана транспортной задачи методом северо-западного угла

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

Слайд 14

Поиск опорного плана методом «северо-западного» угла
?
Северо-западная клетка.
В неё записываем наименьшее из

чисел
25 и 45.

Вычеркиваем израсходованные запасы и потребности.

В клетку (1;1) записали 25 ед., поэтому на первом складе осталось 25-25=0 ед.

Слайд 15

0
20

В таблице этот факт мы обозначаем при помощи прочерков.

Слайд 16

0
20
Следующая северо-западная клетка.
Записываем в неё наименьшее из чисел 20 и 55.
20

Слайд 17

0
20
20
Пересчитываем запасы и потребности
35
0

−

Слайд 18

Продолжаем находить опорный план
5

Слайд 19

Продолжаем находить опорный план

Слайд 20

Шаг 3

Слайд 21

Проверка невырожденности опорного плана
У нас 5 заполненных клеток

Слайд 22

Шаг 4

Слайд 23

Вычисление потенциалов

Слайд 24

Шаг 5

Слайд 25

Вычисление оценок

Слайд 26

Шаги 6-7

Слайд 27

Цикл пересчета
Циклом пересчета в таблице ТЗ называется ломаная линия, вершины которой

расположены в занятых клетках таблицы, а звенья идут вдоль строк и столбцов, причём в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое — в столбце. Цикл всегда начинается и заканчивается в клетке *.
Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

Слайд 28

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

Слайд 29

Шаг 8
8. Производят сдвиг по циклу пересчёта. Для этого каждой клетке

таблицы, в которой находится вершина цикла пересчёта, приписывают определённый знак, причём свободной клетке (клетке *) приписывают знак плюс, а всем остальным клеткам − поочерёдно знак плюс или минус.
В данную свободную клетку переносят меньшее из чисел, стоящих в клетках со знаком минус. Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком плюс, и вычитают из чисел, стоящих в клетках со знаком минус. После пересчета число заполненных клеток должно остаться тем же.

Слайд 30

+
+
-
-
Расстановка знаков

Слайд 31

Сдвиг по циклу пересчета
9. Повторяем шаги 4-7.

Слайд 32

Вновь вычисляем потенциалы

Слайд 33

Пересчитываем оценки

Слайд 34

+
+
-
-
В клетках с минусами две одинаковые «загрузки» по 20 ед., когда

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

Слайд 35

Пересчет потенциалов и оценок для нового плана

Слайд 36

Слайд 37

Замечание 1

Слайд 38

Замечание 1
Так как мы решаем задачу минимизации, то из двух

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

Линейное программирование. Транспортная задача

Содержание

Транспортная задача (ТЗ)В этих задачах, рассматривается операция по перевозке некоторых однородных

Математическая модель ТЗЛогистическая компания располагает тремя пунктами упаковки косметики расположенными в

Недельная производительность по формированию косметических наборов и потребности в наборах в

Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к

Логистическая компания должна принять решение, сколько наборов с косметикой необходимо отправлять

Составление математической модели

Математическая модель задачи

Математическая модель задачи

Решение транспортной задачи методом потенциаловРассмотрим задачу.

Алгоритм решенияПроверяем условие баланса: запасы должны равняться потребностям.Составляем опорный план методом

Проверка условия баланса

Метод северо-западного углаПри нахождении опорного плана транспортной задачи методом северо-западного угла

Поиск опорного плана методом «северо-западного» угла?Северо-западная клетка.В неё записываем наименьшее из

0 20 В таблице этот факт мы обозначаем при помощи прочерков.

020Следующая северо-западная клетка.Записываем в неё наименьшее из чисел 20 и 55.20

02020Пересчитываем запасы и потребности350 −

Продолжаем находить опорный план5

Продолжаем находить опорный план

Шаг 3

Проверка невырожденности опорного планаУ нас 5 заполненных клеток

Шаг 4

Вычисление потенциалов

Шаг 5

Вычисление оценок

Шаги 6-7

Цикл пересчетаЦиклом пересчета в таблице ТЗ называется ломаная линия, вершины которой

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

Шаг 88. Производят сдвиг по циклу пересчёта. Для этого каждой клетке

++--Расстановка знаков

Сдвиг по циклу пересчета9. Повторяем шаги 4-7.

Вновь вычисляем потенциалы

Пересчитываем оценки

++--В клетках с минусами две одинаковые «загрузки» по 20 ед., когда

Пересчет потенциалов и оценок для нового плана

Замечание 1

Замечание 1 Так как мы решаем задачу минимизации, то из двух

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

Транспортная задача (ТЗ)
В этих задачах, рассматривается операция по перевозке некоторых однородных

Математическая модель ТЗ
Логистическая компания располагает тремя пунктами упаковки косметики расположенными в

Решение транспортной задачи методом потенциалов
Рассмотрим задачу.

Алгоритм решения
Проверяем условие баланса: запасы должны равняться потребностям.
Составляем опорный план методом

Метод северо-западного угла
При нахождении опорного плана транспортной задачи методом северо-западного угла

Поиск опорного плана методом «северо-западного» угла
?
Северо-западная клетка.
В неё записываем наименьшее из

0
20

В таблице этот факт мы обозначаем при помощи прочерков.

0
20
Следующая северо-западная клетка.
Записываем в неё наименьшее из чисел 20 и 55.
20

0
20
20
Пересчитываем запасы и потребности
35
0

−

Продолжаем находить опорный план
5

Проверка невырожденности опорного плана
У нас 5 заполненных клеток

Цикл пересчета
Циклом пересчета в таблице ТЗ называется ломаная линия, вершины которой

Шаг 8
8. Производят сдвиг по циклу пересчёта. Для этого каждой клетке

+
+
-
-
Расстановка знаков

Сдвиг по циклу пересчета
9. Повторяем шаги 4-7.

+
+
-
-
В клетках с минусами две одинаковые «загрузки» по 20 ед., когда

Замечание 1
Так как мы решаем задачу минимизации, то из двух