Портал презентаций » Презентации по Математике » Транспортные задачи и задачи о назначениях

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

Транспортные задачи и задачи о назначениях - Скачать презентации PowerPoint бесплатно | Портал бесплатных презентаций school-present.com
Смотреть онлайн
Поделиться с друзьями:
Транспортные задачи и задачи о назначениях:
Презентация на тему Транспортные задачи и задачи о назначениях к уроку математике

Презентация "Транспортные задачи и задачи о назначениях" онлайн бесплатно на портале электронных презентаций school-present.com

Лекция 5. Транспортные задачи и задачи о назначениях Содержание лекции: Формулировка транспортной за
1 слайд

Лекция 5. Транспортные задачи и задачи о назначениях Содержание лекции: Формулировка транспортной задачи Метод потенциалов Особенности решения открытой транспортной задачи Задача о назначениях Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

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

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

5.1. Формулировка транспортной задачи Дано: Множество I, включающее m пунктов отправления груза, имеющегося в количествах ai (i=1…m) Множество J, включающее n пунктов потребления, в каждом из которых имеется спрос на данный груз в количестве bj (j=1…n) Затраты cij на перевозку единицы груза между пунктами i и j Найти: План перевозок X = (xij), согласно которому груз из пунктов отправления перевозится в пункты потребления с минимальными издержками, а спрос удовлетворяется полностью Обычно предполагается, что общий размер запасов груза равен спросу (закрытая транспортная задача). При этом условии задача всегда имеет оптимальное решение. */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

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

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

5.1 Получившаяся задача имеет форму задачи линейного программирования Её можно решить симплексным методом Однако есть более эффективные способы её решения */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

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

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

5.2.1. Начальное распределение транспортных потоков Теоретическая основа Ранг матрицы ограничений транспортной задачи равен n+m–1 В оптимальном плане все переменные, кроме n+m–1, будут свободными Следовательно, равными нулю Метод северо-западного угла Не использует данных о затратах Обычно приводит к распределению, требующему много корректировок Зато самый простой */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

5.2.1 i=1, j=1 xij = min(a’i,b’j) Если xij = a’i, то i i+1; иначе j j+1 Если i>m, то процесс заве
8 слайд

5.2.1 i=1, j=1 xij = min(a’i,b’j) Если xij = a’i, то 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 Потребители За-пас 1 2 3 Потребности 60 40 20 Поставщик 1 30 Поставщик 2 40 Поставщик 3 50 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

5.2.2. Расчёт потенциалов Теоретическая основа Потенциалы приписываются поставщикам (ui) и потребителям (vj). Уравнение потенциалов cij = vj – ui Расчёт потенциалов: подобрать такие vj и ui, чтобы уравнение потенциалов выполнялось для всех базисных клеток (перевозок) */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

5.2.2 i = 1; ui = 0 В строке i находим множество столбцов J’ с ненулевыми перевозками и нерассчитанн
10 слайд

5.2.2 i = 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 Потребители За-пас 1 2 3 ui Потребности 60 40 20 Поставщик 1 30 30 6 9 7 Поставщик 2 40 30 8 10 8 5 Поставщик 3 50 4 30 6 20 12 vj Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

5.2.3. Проверка оптимальности */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2
11 слайд

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

5.2.3 */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 -3 5 9 2 Потребители
12 слайд

5.2.3 */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 -3 5 9 2 Потребители За-пас 1 2 3 ui Потребности 60 40 20 Поставщик 1 30 30 6 9 7 0 Поставщик 2 40 30 8 10 8 5 -2 Поставщик 3 50 4 30 6 20 12 0 vj 6 6 12 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

5.2.4. Корректировка плана Находим наименьшую из величин в клетках со знаком – Вычитаем её из всех к
13 слайд

5.2.4. Корректировка плана Находим наименьшую из величин в клетках со знаком – Вычитаем её из всех клеток «–» и прибавляем ко всем клеткам «+» Одну из клеток, в которых оказался нуль, объявляем свободной. Переходим к проверке критерия оптимальности */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

5.2.4 */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 500 600 500 300 400 200 250 350 400 200 200 300 300 0 400 200 200 500 300 200 600 100 100 400 700 500 200 800 400 50 350 100 200 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

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

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

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

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

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

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

5.4 Переформулируется в транспортную задачу по следующему правилу: имеется n поставщиков, располагаю
18 слайд

5.4 Переформулируется в транспортную задачу по следующему правилу: имеется n поставщиков, располагающих единичными ресурсами работники имеется n потребителей с единичным спросом работы стоимость перевозок равна добавленной стоимости, взятой со знаком «минус» это делается для того, чтобы добавленная стоимость максимизировалась Решается методом потенциалов, как обычно «Перевозки единичного объёма груза» интерпретируются как назначение работника i на работу j Все базисные переменные в этом случае могут принимать только единичные значения */18 Транспортные задачи и задачи о назначениях © Н.М. Светлов, 2007-2011 Транспортные задачи и задачи о назначениях (с) Н.М. Светлов, 2007

Отзывы на school-present.com "Транспортные задачи и задачи о назначениях" (0)
Оставить отзыв
Прокомментировать
Регистрация
Вход
Авторизация