Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
39 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
1.60 MB
Просмотров:
143
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Первухин Михаил Александрович
Доцент кафедры
математики и моделирования
№2 слайд
Содержание слайда: Транспортная задача (ТЗ)
В этих задачах, рассматривается операция по перевозке некоторых однородных грузов из пунктов отправления в пункты назначения, причём известны стоимости перевозки единицы груза между любыми двумя пунктами отправления и назначения.
Требуется составить оптимальный план перевозок, то есть определить количество груза перевозимого из каждого пункта отправления в каждый пункт назначения, при котором суммарная стоимость всех перевозок будет минимальной.
№3 слайд
Содержание слайда: Математическая модель ТЗ
Логистическая компания располагает тремя пунктами упаковки косметики расположенными в Твери, Ярославле и Смоленске, откуда сформированные наборы перевозятся на грузовиках к трём оптовым поставщикам, расположенным в Москве, Санкт-Петербурге и Нижнем Новгороде.
№4 слайд
Содержание слайда: Недельная производительность по формированию косметических наборов и потребности в наборах в городах приведены на схеме.
Недельная производительность по формированию косметических наборов и потребности в наборах в городах приведены на схеме.
№5 слайд
Содержание слайда: Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к каждому оптовому поставщику приведены в таблице.
Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к каждому оптовому поставщику приведены в таблице.
№6 слайд
Содержание слайда: Логистическая компания должна принять решение, сколько наборов с косметикой необходимо отправлять из каждого пункта упаковки каждому оптовому поставщику, чтобы:
Логистическая компания должна принять решение, сколько наборов с косметикой необходимо отправлять из каждого пункта упаковки каждому оптовому поставщику, чтобы:
1) все наборы с каждого пункта упаковки были вывезены;
2) спрос на наборы с косметикой каждого оптового поставщика был полностью удовлетворён;
3) суммарные затраты на транспортировку всех наборов были минимальными.
№7 слайд
Содержание слайда: Составление математической модели
Обозначим пункты отправления индексом , так что соответствует Твери, — Ярославлю и — Смоленску, а пункты назначения — индексомj,при этомсоответствует Москве,j— Санкт-Петербургу, — Нижнему Новгороду.
Переменными математической модели являются объёмы ежедневных перевозок наборов между пунктами отправления () и пунктами назначения
№8 слайд
Содержание слайда: Математическая модель задачи
Цель: Минимизировать суммарные затраты
на транспортировку.
№9 слайд
Содержание слайда: Математическая модель задачи
С условиями:
№10 слайд
Содержание слайда: Решение транспортной задачи
методом потенциалов
Рассмотрим задачу.
№11 слайд
Содержание слайда: Алгоритм решения
Проверяем условие баланса: запасы должны равняться потребностям.
Составляем опорный план методом «северо-западного» угла.
№12 слайд
Содержание слайда: Проверка условия баланса
№13 слайд
Содержание слайда: Метод северо-западного угла
При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге заполняют клетку транспортной таблицы, находящуюся в левом верхнем углу, т.е. на пересечении первого из оставшихся складов и первого из оставшихся магазинов.
№14 слайд
Содержание слайда: Поиск опорного плана методом «северо-западного» угла
?
№15 слайд
№16 слайд
№17 слайд
№18 слайд
Содержание слайда: Продолжаем находить опорный план
№19 слайд
Содержание слайда: Продолжаем находить опорный план
№20 слайд
Содержание слайда: Шаг 3
3. Проверяем, чтобы число заполненных клеток равнялось где – число складов, – число магазинов.
В нашем примере, Значит, число заполненных клеток должно равняться
№21 слайд
Содержание слайда: Проверка невырожденности опорного плана
№22 слайд
Содержание слайда: Шаг 4
4. По заполненным клеткам находим потенциалы поставщиков и потенциалы потребителей из следующей формулы:
где - тарифы на перевозку с -го склада в -й магазин.
№23 слайд
Содержание слайда: Вычисление потенциалов
№24 слайд
Содержание слайда: Шаг 5
5. Для пустых клеток находим оценки по следующей формуле:
№25 слайд
Содержание слайда: Вычисление оценок
№26 слайд
Содержание слайда: Шаги 6-7
6. Если среди чисел нет положительных, то получен оптимальный план; если же они имеются, то переходят к новому плану.
7. Среди положительных чисел выбираем максимальное. Пусть максимальная из оценок - Строим для клетки (обозначим ее *)цикл пересчёта.
№27 слайд
Содержание слайда: Цикл пересчета
Циклом пересчета в таблице ТЗ называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья идут вдоль строк и столбцов, причём в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое — в столбце. Цикл всегда начинается и заканчивается в клетке *.
Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.
№28 слайд
Содержание слайда: Построение цикла
№29 слайд
Содержание слайда: Шаг 8
8. Производят сдвиг по циклу пересчёта. Для этого каждой клетке таблицы, в которой находится вершина цикла пересчёта, приписывают определённый знак, причём свободной клетке (клетке *) приписывают знак плюс, а всем остальным клеткам поочерёдно знак плюс или минус.
В данную свободную клетку переносят меньшее из чисел, стоящих в клетках со знаком минус. Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком плюс, и вычитают из чисел, стоящих в клетках со знаком минус. После пересчета число заполненных клеток должно остаться тем же.
№30 слайд
Содержание слайда: Расстановка знаков
№31 слайд
Содержание слайда: Сдвиг по циклу пересчета
9. Повторяем шаги 4-7.
№32 слайд
Содержание слайда: Вновь вычисляем потенциалы
№33 слайд
Содержание слайда: Пересчитываем оценки
№34 слайд
№35 слайд
Содержание слайда: Пересчет потенциалов и оценок для нового плана
№36 слайд
Содержание слайда: Среди чисел нет положительных, значит получен оптимальный план.
Среди чисел нет положительных, значит получен оптимальный план.
Ответ:
№37 слайд
Содержание слайда: Замечание 1
№38 слайд
Содержание слайда: Замечание 1
№39 слайд
Содержание слайда: Замечание 2
Если на шаге 7 получилось несколько максимальных оценок , то лучше выбрать ту в соответствующей клетке которой тариф меньше.
Если соответствующих клеток с наименьшим тарифом несколько, то можно выбрать любую из них.