Что такое 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
  • Количество просмотров: 162
  • Количество скачиваний: 0
- Предыдущая novomar_school
Следующая - Механическое движение. Плотность

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

Математические диктанты 2 класс презентация к уроку по математике (2 класс) Математические диктанты 2 класс презентация к уроку по математике (2 класс) 186
Презентация по теме Решение задач с помощью формул 3-4 класс презентация к уроку математики (3,4 класс) по теме Презентация по теме Решение задач с помощью формул 3-4 класс презентация к уроку математики (3,4 класс) по теме 118
Деление У-3 Деление У-3 119
презентация к уроку математики 4 класс Объем прямоугольного параллелепипеда презентация к уроку по математике (4 класс) по теме презентация к уроку математики 4 класс Объем прямоугольного параллелепипеда презентация к уроку по математике (4 класс) по теме 130
Счет на пальцах Счет на пальцах 181
Умножение дробей Умножение дробей 85
Конспект урока по математике нас тему :Табличное умножение и деление. Решение задач. презентация к уроку по математике (3 класс) Конспект урока по математике нас тему :Табличное умножение и деление. Решение задач. презентация к уроку по математике (3 класс) 148
Консультация для педагогов ДОУ. консультация по математике (подготовительная группа) Консультация для педагогов ДОУ. консультация по математике (подготовительная группа) 145
ЕГЭ В7. Преобразование логарифмических выражений ЕГЭ В7. Преобразование логарифмических выражений 117
Презентация В царстве смекалки Презентация В царстве смекалки 190
Сложение и вычитание Сложение и вычитание 109
Приёмы сложения и вычитания презентация к уроку по математике Приёмы сложения и вычитания презентация к уроку по математике 111
Презентация к уроку математики в 1 классе на тему: Решение задач Презентация к уроку математики в 1 классе на тему: Решение задач 88
Презентация к уроку математики Презентация к уроку математики 94
Признаки параллельности прямых Признаки параллельности прямых 174
Презентация по математике Весёлый математический поезд Презентация по математике Весёлый математический поезд 100
Презентация урока математики Таблица единиц площади 4 класс Презентация урока математики Таблица единиц площади 4 класс 182
Золотой ключик презентация к уроку по математике (подготовительная группа) Золотой ключик презентация к уроку по математике (подготовительная группа) 118
Презентация по математике на тему Доли (3 класс) Презентация по математике на тему Доли (3 класс) 110
Виды треугольников 4 класс Виды треугольников 4 класс 123
Конспект интегрированной НОД в подготовительной группе план-конспект занятия по математике (подготовительная группа) Конспект интегрированной НОД в подготовительной группе план-конспект занятия по математике (подготовительная группа) 93
Число и цифра 4 презентация к уроку по математике (1 класс) Число и цифра 4 презентация к уроку по математике (1 класс) 188
Процентные вычисления и расчёты Процентные вычисления и расчёты 135
Прямая и обратная пропорциональная зависимость Прямая и обратная пропорциональная зависимость 110
Все действия с десятичными дробями 5 класс Все действия с десятичными дробями 5 класс 100
Задачи по геометрии Задачи по геометрии 112
Презентация к уроку математики по теме: Величины (УМК Школа 2100) 4 класс презентация к уроку по математике (4 класс) Презентация к уроку математики по теме: Величины (УМК Школа 2100) 4 класс презентация к уроку по математике (4 класс) 111
Разложение многочлена на множители с помощью различных способов Разложение многочлена на множители с помощью различных способов 126
m urok69 m urok69 134
Учебно-методический комплекс по математике :На сколько больше? На сколько меньше? 1 класс Перспектива (конспект+презентация) план-конспект урока по математике (1 класс) по теме Учебно-методический комплекс по математике :На сколько больше? На сколько меньше? 1 класс Перспектива (конспект+презентация) план-конспект урока по математике (1 класс) по теме 135