Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Транспортные задачи и задачи о назначениях

Содержание

ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — раздел 3.2.Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.:
Лекция 5. Транспортные задачи и задачи о назначенияхСодержание лекции:Формулировка транспортной задачиМетод потенциаловОсобенности ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. 5.1. Формулировка транспортной задачиДано:Множество I, включающее m пунктов отправления груза, имеющегося в 5.1. Математическая запись/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 5.1Получившаяся задача имеет форму задачи линейного программированияЕё можно решить симплексным методомОднако есть 5.2. Метод потенциалов/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 5.2.1. Начальное распределение транспортных потоковТеоретическая основаРанг матрицы ограничений транспортной задачи равен n+m–1 √5.2.1i=1, j=1xij = min(a’i,b’j)Если xij = a’i, то i ? i+1; иначе 5.2.2. Расчёт потенциаловТеоретическая основаПотенциалы приписываются поставщикам (ui) и потребителям (vj).Уравнение потенциалов cij = 5.2.2i = 1; ui = 0В строке i находим множество столбцов J’ 5.2.3. Проверка оптимальностиТеоретическая основаПо используемым перевозкам cij разница в «ценах» (потенциалах) у 5.2.3Условие оптимальностиРазница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам не 5.2.4. Корректировка планаВыбираем клетку с превышением разности потенциалов потребителя и поставщика над стоимостью 5.2.4/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 5.2.4ОСОБЕННОСТИКонтур можно построить всегда, но не всегда удаётся угадать правильный путьВ больших 5.3. Особенности решения открытой транспортной задачи /18Транспортные задачи и задачи о назначениях 5.4. Задача о назначениях/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 5.4Переформулируется в транспортную задачу по следующему правилу:имеется n поставщиков, располагающих единичными ресурсами
Слайды презентации

Слайд 2 Литература
Экономико-математические методы и прикладные модели: Учеб. пособие для

ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под

вузов / Под ред. В.В. Федосеева. — 2-е изд.

М.: ЮНИТИ-ДАНА, 2005. — раздел 3.2.
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.: Финансы и статистика, 2005. — раздел 2.2.6.
Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 3 5.1. Формулировка транспортной задачи
Дано:
Множество I, включающее m пунктов

5.1. Формулировка транспортной задачиДано:Множество I, включающее m пунктов отправления груза, имеющегося

отправления груза, имеющегося в количествах ai (i=1…m)
Множество J, включающее

n пунктов потребления, в каждом из которых имеется спрос на данный груз в количестве bj (j=1…n)
Затраты cij на перевозку единицы груза между пунктами i и j
Найти:
План перевозок X = (xij), согласно которому груз из пунктов отправления перевозится в пункты потребления с минимальными издержками, а спрос удовлетворяется полностью

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

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 4 5.1.
Математическая запись
/18
Транспортные задачи и задачи о назначениях ©

5.1. Математическая запись/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Н.М. Светлов, 2007-2011

Слайд 5 5.1
Получившаяся задача имеет форму задачи линейного программирования
Её можно

5.1Получившаяся задача имеет форму задачи линейного программированияЕё можно решить симплексным методомОднако

решить симплексным методом
Однако есть более эффективные способы её решения
/18
Транспортные

задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 6 5.2. Метод потенциалов
/18
Транспортные задачи и задачи о назначениях

5.2. Метод потенциалов/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

© Н.М. Светлов, 2007-2011

Слайд 7 5.2.1. Начальное распределение транспортных потоков
Теоретическая основа
Ранг матрицы ограничений

5.2.1. Начальное распределение транспортных потоковТеоретическая основаРанг матрицы ограничений транспортной задачи равен

транспортной задачи равен n+m–1
В оптимальном плане все переменные,

кроме n+m–1, будут свободными
Следовательно, равными нулю
Метод северо-западного угла
Не использует данных о затратах
Обычно приводит к распределению, требующему много корректировок
Зато самый простой ☺

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 8 √

5.2.1
i=1, j=1
xij = min(a’i,b’j)
Если xij = a’i, то

√5.2.1i=1, j=1xij = min(a’i,b’j)Если xij = a’i, то i ? i+1;

i ? i+1; иначе j ? j+1
Если i>m, то процесс

завершён; иначе переход к 2.


√

Ещё не вывезенный остаток

Ещё не удовлетво-рённый спрос

√

√

20









Начальное распределение получено!

/18

i =1

j =1

i =2

i =3

j =2

j =3

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 9 5.2.2. Расчёт потенциалов
Теоретическая основа
Потенциалы приписываются поставщикам (ui) и

5.2.2. Расчёт потенциаловТеоретическая основаПотенциалы приписываются поставщикам (ui) и потребителям (vj).Уравнение потенциалов cij

потребителям (vj).
Уравнение потенциалов
cij = vj – ui
Расчёт потенциалов:
подобрать

такие vj и ui, чтобы уравнение потенциалов выполнялось для всех базисных клеток (перевозок)

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 10 5.2.2
i = 1; ui = 0
В строке i

5.2.2i = 1; ui = 0В строке i находим множество столбцов

находим множество столбцов J’ с ненулевыми перевозками и нерассчитанными

потенциалами
Для всех j ∈ J’ выполняем vj ? ui + cij
В столбце j находим множество строк I’ с ненулевыми перевозками и нерассчитанными потенциалами.
Для всех i ∈ I’ выполняем ui ? vj – cij
Выполняем (2)
Процесс закончен, когда I’ или J’ оказывается пустым


Расчёт потенциалов завершён!

0


√


6


√


-2


√


6


√


0


√


12



/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 11 5.2.3. Проверка оптимальности
Теоретическая основа
По используемым перевозкам cij разница

5.2.3. Проверка оптимальностиТеоретическая основаПо используемым перевозкам cij разница в «ценах» (потенциалах)

в «ценах» (потенциалах) у потребителя j и у поставщика

i равна стоимости перевозки
это следует из способа расчёта потенциалов
Неиспользуемая перевозка cij выгодна, если разница в «ценах» (потенциалах) у потребителя j и у поставщика i больше стоимости перевозки
Условие оптимальности
Разница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам не больше стоимости перевозки

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 12 5.2.3
Условие оптимальности
Разница в потенциалах потребителя и поставщика по

5.2.3Условие оптимальностиРазница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам

всем неиспользуемым перевозкам не больше стоимости перевозки
В нашем примере

выполняется не по всем неисп. перевозкам
Выполняется только для 1 ⮊ 2.
Значит, требуется переход к п.4. – корректировка плана

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

-3

5

9

2

Слайд 13 5.2.4. Корректировка плана
Выбираем клетку
с превышением разности потенциалов потребителя

5.2.4. Корректировка планаВыбираем клетку с превышением разности потенциалов потребителя и поставщика над

и поставщика над стоимостью транспортировки
как правило, с наибольшим
Строим контур

(см. схему), начиная с данной клетки
Помечаем вершины контура знаками + и –
начинаем со знака + в выбранной свободной клетке

Находим наименьшую из величин в клетках со знаком –
Вычитаем её из всех клеток «–» и прибавляем ко всем клеткам «+»
Одну из клеток, в которых оказался нуль, объявляем свободной.

Переходим к проверке критерия оптимальности

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 14 5.2.4

/18
Транспортные задачи и задачи о назначениях © Н.М.

5.2.4/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Светлов, 2007-2011

Слайд 15 5.2.4
ОСОБЕННОСТИ

Контур можно построить всегда, но не всегда удаётся

5.2.4ОСОБЕННОСТИКонтур можно построить всегда, но не всегда удаётся угадать правильный путьВ

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

оказаться проблематичным
Для компьютерных программ это не составляет проблемы
Контур может оказаться вырожденным
Так случается, если наименьшим значением в клетке со знаком – оказывается нуль
Пересчёт по такому циклу не улучшает план, вследствие чего метод может зациклиться
в этом случае выбирают другую свободную клетку в качестве начальной
Если после пересчёта получились нули в нескольких клетках, в качестве свободной можно выбрать любую из них
Остальные считаются базисными с нулевым объёмом перевозки

/18

Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 16 5.3. Особенности решения открытой транспортной задачи
/18
Транспортные задачи

5.3. Особенности решения открытой транспортной задачи /18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

и задачи о назначениях © Н.М. Светлов, 2007-2011

Слайд 17 5.4. Задача о назначениях
/18
Транспортные задачи и задачи о

5.4. Задача о назначениях/18Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011

назначениях © Н.М. Светлов, 2007-2011

  • Имя файла: transportnye-zadachi-i-zadachi-o-naznacheniyah.pptx
  • Количество просмотров: 145
  • Количество скачиваний: 0
- Предыдущая novomar_school
Следующая - Механическое движение. Плотность

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

часть 1 часть 1 169
Математика – гимнастика ума Математика – гимнастика ума 247
Жай бөлшектерге есептер шығару математикадан 5-сыныпта ашық сабақ жоспары Жай бөлшектерге есептер шығару математикадан 5-сыныпта ашық сабақ жоспары 135
Таблицы. Периметр, площадь, объём учебно-методическое пособие по математике (4 класс) по теме Таблицы. Периметр, площадь, объём учебно-методическое пособие по математике (4 класс) по теме 145
Урок математики по теме Решение задач презентация к уроку по математике (3 класс) по теме Урок математики по теме Решение задач презентация к уроку по математике (3 класс) по теме 97
Гравитационные силы. Спутники Гравитационные силы. Спутники 96
Развитие логического мышления на уроках математики(презентация) презентация к уроку по математике Развитие логического мышления на уроках математики(презентация) презентация к уроку по математике 20
Урок открытия новых знаний Плоскость. Прямая. Луч. 5 класс Урок открытия новых знаний Плоскость. Прямая. Луч. 5 класс 95
Викторина по математике. Вычисления Викторина по математике. Вычисления 101
Презентация по математике на тему Упрощение выражений (5 класс) Презентация по математике на тему Упрощение выражений (5 класс) 85
Степени Степени 88
Приемы устного умножения и деления Приемы устного умножения и деления 99
ВПР по математике 5 класс. Задание 5. 2019-2020 ВПР по математике 5 класс. Задание 5. 2019-2020 71
Умножение натуральных чисел Умножение натуральных чисел 122
Презентация к уроку на тему Упрощение выражений Презентация к уроку на тему Упрощение выражений 121
Нахождение числа по его дроби Нахождение числа по его дроби 91
Авария на промышленном объекте Авария на промышленном объекте 92
Сложение и вычитание дробей с одинаковыми знаменателями Сложение и вычитание дробей с одинаковыми знаменателями 82
сучасний урок сучасний урок 180
Презентация по математике к проекту Решай-ка! Презентация по математике к проекту Решай-ка! 102
Уроки математики план-конспект урока по математике Уроки математики план-конспект урока по математике 94
Вся правда о золотом сечении Вся правда о золотом сечении 209
Вычисляем в пределах 20 презентация к уроку по математике (1 класс) по теме Вычисляем в пределах 20 презентация к уроку по математике (1 класс) по теме 91
chislo itsyfra 10 chislo itsyfra 10 92
Презентация: Ах, уж эти дроби! Презентация: Ах, уж эти дроби! 142
четырехугольники2 четырехугольники2 122
Площади и объёмы Площади и объёмы 79
Уравнения презентация к уроку по математике Уравнения презентация к уроку по математике 80
Презентация к интегрированному уроку математики и окружающего мира в 1 классе по теме Литр презентация к уроку (математика, 1 класс) Презентация к интегрированному уроку математики и окружающего мира в 1 классе по теме Литр презентация к уроку (математика, 1 класс) 91
Сложение и вычитание 3 презентация к уроку по математике (1 класс) Сложение и вычитание 3 презентация к уроку по математике (1 класс) 99