Транспортная задача

Лекция: Транспортная задача Вопросы: 1. Постановка задачи 2. Математическая модель транспортной задачи 3. Методы решения - нахождение опорного плана - итерации по улучшению плана - метод потенциалов 4. Понятие о циклах 5. Улучшение плана перевозок 6. Признак оптимального плана перевозок 7. Практический пример решения транспортной задачи Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Постановка задачи Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). История поиска методов решения Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году[3]. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[4]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича. Постановка транспортной задачи Важным частным случаем задачи линейного программирования является транспортная задача. Постановка задачи: Пусть имеется m поставщиков и n потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей. поставщики потребители В1 В2 … Вj … Bn Мощность поставщиков A1 С11 С12 С1j С1n a1 A2 С21 С22 С2j С2n a2 … … … … … Ai Сij Сij Сij Сin ai … … … … … Am Cm1 Cm2 Cmj Cmn am Спрос потребителей b1 b2 bj bn Найти объемы перевозок каждой пары «поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросы всех потребителей были удовлетворены; суммарные затраты на перевозку были бы минимальны. Особенности математической модели транспортной задачи: • система ограничений есть система уравнений, то есть задача ЛП в каноническом виде; • коэффициенты при неизвестных системы ограничений равны единицы или нулю; • каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз – в систему ограничений спроса. Математическая модель транспортной задачи. Пусть хij – количество груза, перевозимого с i-го в j-й пункт. Целевая функция: Система ограничений: Для решения задачи составляется таблица. В клетки таблицы записывается стоимость соответствующих перевозок сij и в них же заносятся значения перевозок xij, удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками транспортная задача называется сбалансированной или несбалансированной. Сбалансированная ТЗ: Несбалансированная ТЗ: Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной. Сведение открытой транспортной задачи к закрытой Решение транспортной задачи начинается с выяснения вопроса о том, является ли задача открытой или закрытой. Если задача является открытой, то необходимо провести процедуру за- крытия задачи. С этой целью при a < b добавляем фиктивного поставщика 1 'm+ A с запасом груза a b a m +1 = - ' . Если же a > b , то добавляем фиктивного потребителя 1 'n+ B с заказом груза b a b n +1 = - ' . В обоих случаях соответствующие фиктивным объектам тарифы пере- возок ij c' полагаем равными нулю. В результате суммарная стоимость пере- возок z не изменяется. Первоначальный план перевозок Транспортная задача относится к задачам линейного программирования, и ее можно было бы решить симплекс-методом. Но поскольку система огра- ничений транспортной задачи проще, чем система ограничений ОЗЛП, то это дает возможность вместо использования объемных симплекс-таблиц при- менить более удобный метод, который состоит из следующих этапов: 1. Составление первоначального плана перевозок; 2. Последовательные улучшения плана перевозок (перераспределение поставок) до тех пор, пока план перевозок не станет оптимальным. Методы решения Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности). Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза , а в маленькие клетки — соответствующие тарифы . Итерационное улучшение плана перевозок Нахождение опорного плана Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля. Метод северо-западного угла (диагональный) На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность . Метод наименьшего элемента Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями. Алгоритм: 1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел. 2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются. 3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена. Методы решения транспортной задачи. МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. Заполнение клеток происходит последовательно по следующему алгоритму: сначала вывозится груз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваивается максимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1 еще остается груз, то он вывозится в пункт В2 и т.д. Если в пункте А1 недостаточно было груза для В1, то недостающий груз берется из А2 и т.д. После того как спрос потребителя А1 удовлетворен, он выпадает из рассмотрения и т.д. В1 В2 В3 В4 Запасы А1 15 5( от 1 поставщика к потребителю) 5 7 6 8 20-15=5 А2 6 25 7 8 5 25 А3 5 5 4 25 6 7 30-5=25 А4 6 5 10 7 5 4 15-10=5 А5 5 6 6 10 6 10 Заявки 15 35-5= 30-25=5 35-25=10 15-5=10 100 Стоимость перевозки: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605 Существенным недостатком метода северо-западного угла является то, что он построен без учета стоимости перевозок. МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Заполнение клеток транспортной таблицы начинается с той клетки, в которой значение минимально. В нее записывается максимально возможное значение перевозки хij, которое может быть равно либо запасу аi, либо заявке вj. Если заявка вj выполнена полностью, то j-й столбец больше не рассматривается. Если не вывезенный груз еще остался, то он вывозится в пункт с наименьшим тарифом. В1 В2 В3 В4 Запасы U A1 5 15 7 6 5 8 20-15=5 0 всегда А2 6 7 8 -25 5 + 25 2 А3 5 4 30 6 7 30 -2 А4 6 5 +0 7 4 -15 15-15=0 -1 А5 5 6 -5 6 +5 6 10-5=5 Заявки 15 35-30=5-0=5 35-5=30-5=25 15 100 V 5 6 6 5 Стоимость перевозки: W = 15*5+5*6+25*8+30*4+15*4+5*6+5*6= 545 ∆1,2 = 7-(6+0) = 1 ∆1,4 = 8- (5+0) = 3 ∆2,1 = 6- (2+5) = -1 ∆2,2 = -1 ∆2,4 = -2 min (25 ; 5 ; 15) = 5 В1 В2 В3 В4 Запасы U A1 5 15 7 6 5 8 20 А2 6 7 8 20 5 5 25 2 А3 5 4 30 6 7 30 А4 6 5 5 7 4 10 15 1 А5 5 6 6 10 6 10 Заявки 15 35 35 15 100 V 5 4 6 3 ∆2,1 = -1 В1 В2 В3 В4 Запасы U A1 5 7 6 20 8 20 А2 6 15 7 8 5 5 5 25 2 А3 5 4 30 6 7 30 А4 6 5 5 7 4 10 15 1 А5 5 6 6 10 6 10 Заявки 15 35 35 15 100 V 4 4 6 3 0 0 20 0 15 0 5 5 0 30 0 0 = X 0 5 0 10 0 0 10 0 20*6+15*6+5*8+5*5+30*4+5*5+10*4+10*6 = 520 Итерации После нахождения опорного плана перевозок, нужно применить один из алгоритмов его улучшения, приближения к оптимальному. • Метод падающего камня • Метод потенциалов Метод потенциалов Вычисление потенциалов U – потенциалы строк V- потенциалы столбцов Принимаем u1 = 0 На основе, что для базисных клеток должно сохраняться соотношение c = u + v вычисляем потенциалы строк и столбцов Проверка оптимальности плана Для каждой свободной клетки плана вычислим разности ∆ = c - (u + v) . Заметим, что для базисных клеток выполнено соотношение ∆ = 0, и этим фактом можно пользоваться для контроля правильности нахождения потенциалов. План является оптимальным, если все разности ∆ ≥ 0. Перераспределение поставок Если есть разности ∆ < 0, то решение не оптимально. Найдем клетку с наибольшей по абсолютной величине отрицательной разностью ∆ и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ломаная линия может иметь точки самопересечения, но не в клетках цикла. Запись оптимального плана перевозок