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

Август 26, 2022

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

Содержание

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

Слайд 2

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

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

/18

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

Слайд 3

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

Слайд 5

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

есть более эффективные способы её решения

/18

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

Слайд 6

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

2007-2011

Слайд 7

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, то i ? i+1; иначе

j ? j+1
Если i>m, то процесс завершён; иначе переход к 2.

√

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

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

√

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

/18

i =1

j =1

i =2

i =3

j =2

j =3

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

Слайд 9

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

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

/18

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

Слайд 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’ оказывается пустым

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

√

-2

√

/18

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

Слайд 11

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

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

/18

Слайд 12

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

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

/18

-3

Слайд 13

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

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

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

/18

Слайд 14

Слайд 15

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

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

/18

Слайд 16

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

Слайд 17

Светлов, 2007-2011

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

Содержание

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

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

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

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

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

5.2.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 находим множество столбцов

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Транспортные задачи и задачи о назначениях © Н.М.

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

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

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

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

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

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

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

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

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

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

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
Транспортные задачи и задачи о назначениях © Н.М.