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

вузов / Под ред. В.В. Федосеева. — 2-е изд.

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

/18

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

отправления груза, имеющегося в количествах ai (i=1…m)
Множество J, включающее

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

Обычно предполагается, что общий размер запасов груза равен спросу (закрытая транспортная задача).
При этом условии задача всегда имеет оптимальное решение.

/18

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

Н.М. Светлов, 2007-2011

решить симплексным методом
Однако есть более эффективные способы её решения
/18
Транспортные

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

© Н.М. Светлов, 2007-2011

транспортной задачи равен n+m–1
В оптимальном плане все переменные,

кроме n+m–1, будут свободными
Следовательно, равными нулю
Метод северо-западного угла
Не использует данных о затратах
Обычно приводит к распределению, требующему много корректировок
Зато самый простой 

/18

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

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

потребителям (vj).
Уравнение потенциалов
cij = vj – ui
Расчёт потенциалов:
подобрать

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

/18

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

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

в «ценах» (потенциалах) у потребителя j и у поставщика

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

/18

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

всем неиспользуемым перевозкам не больше стоимости перевозки
В нашем примере

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

/18

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

-3

5

9

2

и поставщика над стоимостью транспортировки
как правило, с наибольшим
Строим контур

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

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

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

/18

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

Светлов, 2007-2011

угадать правильный путь
В больших задачах отыскание циклов вручную может

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

/18

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

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

назначениях © Н.М. Светлов, 2007-2011