Решение транспортных задач с помощью средств MS Excel

                                       ГОУ ВПО

                     <<Дальневосточный государственный  университет

путей сообщения>>

 

 

 

 

 

Кафедра:<<САПР>>

 

 

 

 

 

 

 

Лабораторная работа

 

Тема: Решение  транспортных задач с помощью  средств MS Excel

 

 

 

 

 

 

Выполнил: ..

группа 32К

Проверил: Ланец  С.А.

 

 

 

 

 

 

 

 

                   Хабаровск 2012

Определение №1

Транспортная  задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Определение №2

 

Транспортная  задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы. Пример подобной таблицы приведен ниже:

 

Цена перевозки (например, в рублях за 1 килограмм груза) C_ij записывается в ячейки таблицы на пересечении соответствующего потребителя и поставщика (цена может быть и отрицательной — в этом случае она представляет собой прибыль). Неизвестной (искомой) величиной в задаче являются такие объемы перевозки x_ij от поставщиков к потребителям, чтобы минимизировать общие затраты на транспортировку.. В табличной записи цены отделяют от объемов перевозки косой чертой или квадратным уголком, в этой статье из соображений лучшей доходчивости они подписаны. При решении транспортной задачи единственными необходимыми арифметическими действиями являются сложение и вычитание. Для поиска начального решения применяют метод северо-западного угла,

Методы решения

Классическую  транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза  из   в   груза  , а в маленькие клетки — соответствующие тарифы  .

Итерационное улучшение плана перевозок

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла»,«наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

Метод северо-западного угла (диагональный)

На каждом этапе  максимально возможным числом заполняют  левую верхнюю клетку оставшейся части таблицы. Заполнение таким  образом, что полностью выносится  груз из   или полностью удовлетворяется потребность  .

Метод наименьшего элемента

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

Алгоритм:

1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

После нахождения опорного плана перевозок, нужно  применить один из алгоритмов его  улучшения, приближения к оптимальному.

• Метод падающего камня 
• Метод потенциалов.

Решение с помощью теории графов

Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока  .

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично  к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. Привозврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за   операций. (  — количество рёбер,   — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка   операций.

При решении  несбалансированной транспортной задачи применяют приём, позволяющий сделать  ее сбалансированной. Для этого вводят фиктивные пункты назначения или  отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы  иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.

Обобщения

Транспортная задача в сетевой постановке

В этом варианте пункты не делятся на пунктов отправления  и пункты потребления, все пункты равноправны, но производство задается положительным числом, а потребление - отрицательным. Перевозки осуществляются по заданной сети, в которой дуги могут соединять любые пункты (включая производитель -> производитель, потребитель -> потребитель). Задача решается слегка измененным методом потенциалов, практически тем же, что и классическая постановка.

Транспортная задача с ограничениями пропускной способности

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

Многопродуктовая Транспортная задача

Вариант транспортной задачи, в которой присутствует несколько  продуктов (пункты могут производить/потреблять несколько продуктов). Для некоторых дуг задается ограничение на пропускную способность (без этого ограничения задача распадается на отдельные задачи по продуктам). Задача решается симплекс-методом (используется разложение Данцига-Вулфа, в качестве подзадач используются однопродуктовые транспортные задачи)

    

 

 

Метод Северо-западного  угла

Исходная таблица с учётам суммы данных и двух последних цифр в зачётке (99)

 

 

	м1	м2	м3	м4	производство
пр1	104	114	112	101	299
пр2	114	113	100	104	599
пр3	101	112	114	109	399
Потребность	299	399	399	299	1297

  Построим вспомогательную таблицу в которой будут расписаны доставки товара в  магазины

для вычисления плановых объемов потребления и производства используется функция СУММ. Функция  СУММ суммирует все числа в  интервале ячеек. К данным ячейкам(кар.ниже) применили функцию СУММ

	м1	м2	м3	м4	испльзавоно	производство
пр1	0	0	0	0	0	299
пр2	0	0	0	0	0	599
пр3	0	0	0	0	0	399
объём доставки	0	0	0	0	общие суммы	1297
ПОТРЕБНОСТЬ	299	399	399	299	1396	не совпадает
						0

 

Далее в ячейку G14  используем функцию =если для значения в  ячейках

F14=G13;''совпадает'';''не совпадает''

 

 

 

 Выполните команду Сервис →Поиск решения . Ввели целевую ячейку, свести все к минимальному значению и поставили ограничения. В вкладке параметры следует поставить галочки Линейная и Неотрицательные значения.

 

Окно Поиск решения. 

 

 

Устанавливаем параметры: линейная модель, неотрицательные значения.

 Нажмите кнопку  Выполнить. Средство Поиск решения  найдет оптимальный план поставок  горючего и соответствующие ему транспортные расходы.

 

 

 

 

 

 

 

 

	м1	м2	м3	м4	испльзавоно	производство
пр1	0	99	200	0	299	299
пр2	299	300	-7,1E-15	0	599	599
пр3	0	0	199	200	399	399
объём доставки	299	399	399	200	общие суммы	1297
ПОТРЕБНОСТЬ	299	399	399	299	1396	не совпадает
						146158