Что такое 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
  • Количество просмотров: 113
  • Количество скачиваний: 0
- Предыдущая Презентацию подготовила ученица группы 1115:Никитина Дарья
Следующая - Корневая система. Виды корней

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

Интерактивный тренажёр Сложение и вычитание в пределах 20 Интерактивный тренажёр Сложение и вычитание в пределах 20 96
Начальные сведения из стереометрии Начальные сведения из стереометрии 122
Одночлены и многочлены Одночлены и многочлены 174
Презентация по математике на тему Уравнения (2 класс) Презентация по математике на тему Уравнения (2 класс) 111
Непосредственно образовательная деятельность по образовательной области: ПОЗНАНИЕ во второй младшей группе Тема: Чудесное дерево презентация к занятию по математике (средняя группа) Непосредственно образовательная деятельность по образовательной области: ПОЗНАНИЕ во второй младшей группе Тема: Чудесное дерево презентация к занятию по математике (средняя группа) 122
Презентация по матем. Сравнение и счет предметов Презентация по матем. Сравнение и счет предметов 104
Конспект урока по математике. Тема Сложение и вычитание десятками. 3 класс. Адаптированная программа. план-конспект урока по математике (3 класс) Конспект урока по математике. Тема Сложение и вычитание десятками. 3 класс. Адаптированная программа. план-конспект урока по математике (3 класс) 113
Двузначные числа от 11 до 20 Двузначные числа от 11 до 20 94
Тренажёр к уроку по теме Умножение и деление десятичных дробей -3 Тренажёр к уроку по теме Умножение и деление десятичных дробей -3 109
Подготовка к итоговой аттестации по математике Подготовка к итоговой аттестации по математике 144
Внеклассное мероприятие Математический КВН план-конспект занятия (математика, 4 класс) по теме Внеклассное мероприятие Математический КВН план-конспект занятия (математика, 4 класс) по теме 133
Математика для детей Математика для детей 144
Степенная функция Степенная функция 114
Презентация к уроку по теме Дроби 4 класс презентация к уроку по математике (4 класс) Презентация к уроку по теме Дроби 4 класс презентация к уроку по математике (4 класс) 131
Презентация. Творческий проект Cборник математических загадок и задач Презентация. Творческий проект Cборник математических загадок и задач 218
Презентация Противоположности. презентация к уроку по математике (старшая группа) Презентация Противоположности. презентация к уроку по математике (старшая группа) 92
Таблица умножения на 4 презентация к уроку по математике (2 класс) Таблица умножения на 4 презентация к уроку по математике (2 класс) 113
Презентация проекта: формирование функциональной грамотности на уроках математики Презентация проекта: формирование функциональной грамотности на уроках математики 296
Уравнения Уравнения 119
История возникновения числа История возникновения числа 217
Фестиваль Е-М 2011 матем Фестиваль Е-М 2011 матем 210
Происхождение римских цифр и десятичного счёта Происхождение римских цифр и десятичного счёта 98
Действия с многозначными числами Действия с многозначными числами 163
Решение задач Решение задач 96
Первый признак равенства треугольников Первый признак равенства треугольников 94
Объектное моделирование фаций. Методы моделирования дискретных свойств в Petrel Объектное моделирование фаций. Методы моделирования дискретных свойств в Petrel 151
Параллельность Параллельность 97
umenshit v2 umenshit v2 153
Требования к математической подготовке учащихся к началу основной школы Требования к математической подготовке учащихся к началу основной школы 143
Вычитание. Решение задач с помощью действия вычитания Вычитание. Решение задач с помощью действия вычитания 110