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

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

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

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

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

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

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

Потребители За- пас 123 Потребности Поставщик 1 30 Поставщик 2 40 Поставщик i=1, j=1 2. x ij = min(a i,b j ) 3. Если x ij = a i, то i i+1; иначе j j+1 4. Если i>m, то процесс завершён; иначе переход к Ещё не вывезенный остаток Ещё не удовлетво- рённый спрос / 18 i =1 j =1 i =2 i =3 j =2 j =3 Транспортные задачи и задачи о назначениях © Н.М. Светлов,

Расчёт потенциалов Теоретическая основа Теоретическая основа Потенциалы приписываются поставщикам (u i ) и потребителям (v j ). Потенциалы приписываются поставщикам (u i ) и потребителям (v j ). Уравнение потенциалов Уравнение потенциалов c ij = v j – u i Расчёт потенциалов: Расчёт потенциалов: подобрать такие v j и u i, чтобы уравнение потенциалов выполнялось для всех базисных клеток (перевозок) подобрать такие v j и u i, чтобы уравнение потенциалов выполнялось для всех базисных клеток (перевозок) 9/ 18 Транспортные задачи и задачи о назначениях © Н.М. Светлов,

Потребители За- пас 123uiui Потребности Поставщик Поставщик Поставщик vjvj i = 1; u i = 0 2. В строке i находим множество столбцов J с ненулевыми перевозками и нерассчитанными потенциалами 3. Для всех j J выполняем v j u i + c ij 4. В столбце j находим множество строк I с ненулевыми перевозками и нерассчитанными потенциалами. 5. Для всех i I выполняем u i v j – c ij 6. Выполняем (2) Процесс закончен, когда I или J оказывается пустым / 18 Транспортные задачи и задачи о назначениях © Н.М. Светлов,

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

5.2.3 Потребители За- пас 123uiui Потребности Поставщик Поставщик Поставщик vjvj 66 12/ 18 Транспортные задачи и задачи о назначениях © Н.М. Светлов,

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

– +– + – – +– +– + +– Тупик + –+ – – + –+ –+ + –+ – 14/ 18 Транспортные задачи и задачи о назначениях © Н.М. Светлов,

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

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

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

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