Инфоурок Другое ПрезентацииТранспортные задачи и задачи о назначениях

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

Скачать материал
Скачать материал "Транспортные задачи и задачи о назначениях"

Получите профессию

Секретарь-администратор

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Методические разработки к Вашему уроку:

Получите новую специальность за 3 месяца

Директор музея

Описание презентации по отдельным слайдам:

  • Лекция 5. Транспортные задачии задачи о назначенияхСодержание лекции:

Форму...

    1 слайд

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

    Формулировка транспортной задачи
    Метод потенциалов
    Особенности решения открытой транспортной задачи
    Задача о назначениях

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

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

    2 слайд

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

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

    3 слайд

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

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

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

    4 слайд

    5.1.


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

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

    5 слайд

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

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

    6 слайд

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

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

    7 слайд

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

  • 5.2.1i=1, j=1
xij = min(a’i,b’j)
Если xij = a’i, то i  i+1;иначе j  j+1
Е...

    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.
    30

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

    10

    30
    20
    Начальное распределение получено!
    8/18
    i =1
    j =1
    i =2
    i =3
    j =2
    j =3
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

  • 5.2.2. Расчёт потенциаловТеоретическая основа
Потенциалы приписываются постав...

    9 слайд

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

  • 5.2.2i  = 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
    10/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

  • 5.2.3. Проверка оптимальностиТеоретическая основа
По используемым перевозкам...

    11 слайд

    5.2.3. Проверка оптимальности
    Теоретическая основа
    По используемым перевозкам cij разница в «ценах» (потенциалах) у потребителя j и у поставщика i равна стоимости перевозки
    это следует из способа расчёта потенциалов
    Неиспользуемая перевозка cij выгодна, если разница в «ценах» (потенциалах) у потребителя j и у поставщика i больше стоимости перевозки
    Условие оптимальности
    Разница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам не больше стоимости перевозки
    11/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

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

    12 слайд

    5.2.3
    Условие оптимальности
    Разница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам не больше стоимости перевозки
    В нашем примере выполняется не по всем неисп. перевозкам
    Выполняется только для 1  2.
    Значит, требуется переход к п.4. – корректировка плана
    12/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011
    -3
    5
    9
    2

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

    13 слайд

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

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

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

  • 5.2.4–+–+–+–+–+–++–Тупик+–+––+–+–++–+–14/18Транспортные задачи и задачи о наз...

    14 слайд

    5.2.4

    +

    +

    +

    +

    +

    +
    +

    Тупик
    +

    +


    +

    +

    +
    +

    +

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

  • 5.2.4ОСОБЕННОСТИ

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

    15 слайд

    5.2.4
    ОСОБЕННОСТИ

    Контур можно построить всегда, но не всегда удаётся угадать правильный путь
    В больших задачах отыскание циклов вручную может оказаться проблематичным
    Для компьютерных программ это не составляет проблемы
    Контур может оказаться вырожденным
    Так случается, если наименьшим значением в клетке со знаком – оказывается нуль
    Пересчёт по такому циклу не улучшает план, вследствие чего метод может зациклиться
    в этом случае выбирают другую свободную клетку в качестве начальной
    Если после пересчёта получились нули в нескольких клетках, в качестве свободной можно выбрать любую из них
    Остальные считаются базисными с нулевым объёмом перевозки
    15/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

  • 5.3. Особенности решения открытой транспортной задачи Транспортная задача наз...

    16 слайд

    5.3. Особенности решения открытой транспортной задачи
    Транспортная задача называется открытой, если не выполняется условие равенства запасов спросу
    Если спрос больше запасов, вводят фиктивного поставщика, располагающего недостающим количеством груза
    Стоимость «перевозки груза» от фиктивного поставщика принимается равным потерям, возникающих из-за неудовлетворённого спроса
    «Перевозки» от фиктивного поставщика интерпретируются как величины неудовлетворённого спроса соответствующих потребителей
    Если имеется избыточный запас у поставщиков, вводят фиктивного потребителя, потребляющего избыток
    Стоимость перевозки груза фиктивному потребителю принимается равной потерям при хранении либо нулю
    «Перевозки» фиктивному потребителю интерпретируются как остатки на складах
    16/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

  • 5.4. Задача о назначенияхДано:n работниковn работдобавленная стоимость, созда...

    17 слайд

    5.4. Задача о назначениях
    Дано:
    n работников
    n работ
    добавленная стоимость, создаваемая работником i на работе j
    Найти:
    оптимальное назначение работников на работы, максимизирующее добавленную стоимость
    17/18
    Транспортные задачи и задачи о назначениях
    © Н.М. Светлов, 2007-2011

  • 5.4Переформулируется в транспортную задачу по следующему правилу:
имеется n п...

    18 слайд

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

Получите профессию

HR-менеджер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 625 761 материал в базе

Скачать материал

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 13.12.2020 602
    • PPTX 3.5 мбайт
    • Оцените материал:
  • Настоящий материал опубликован пользователем Кальченко Елена Анатольевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Кальченко Елена Анатольевна
    Кальченко Елена Анатольевна
    • На сайте: 3 года и 3 месяца
    • Подписчики: 0
    • Всего просмотров: 81988
    • Всего материалов: 210

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

Бухгалтер

Бухгалтер

500/1000 ч.

Подать заявку О курсе

Курс профессиональной переподготовки

Библиотечно-библиографические и информационные знания в педагогическом процессе

Педагог-библиотекарь

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 458 человек из 66 регионов

Курс повышения квалификации

Специалист в области охраны труда

72/180 ч.

от 1750 руб. от 1050 руб.
Подать заявку О курсе
  • Сейчас обучается 40 человек из 19 регионов

Курс профессиональной переподготовки

Организация деятельности библиотекаря в профессиональном образовании

Библиотекарь

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 282 человека из 66 регионов

Мини-курс

Российское движение школьников (РДШ): воспитательная работа

3 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Проектный анализ: стратегии и инструменты управления успешными проектами

6 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Фитнес: особенности занятий и специфика питания

4 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 78 человек из 33 регионов