Способы решения транспортной задачи
Контрольная работа
по дисциплине Методы моделирования экономики
Тема:
Способы решения транспортной задачи
Выполнила:
Вишнякова Дарья Сергеевна
Введение
транспортный задача распределение
Транспортная задача - это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.
Стандартная транспортная задача определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.
Цель работы - рассмотреть транспортную задачу, решив её двумя способами: при помощи программы MS Excel и с применением метода Фогеля.
1. Постановка задачи
.1 Транспортная задача
Транспортная задача - задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы.
Цена перевозки (например, в рублях за 1 килограмм груза) Cij записывается в ячейки таблицы на пересечении соответствующего потребителя и поставщика (цена может быть и отрицательной - в этом случае она представляет собой прибыль). Неизвестной (искомой) величиной в задаче являются такие объемы перевозки xij от поставщиков к потребителям, чтобы минимизировать общие затраты на транспортировку. В табличной записи цены отделяют от объемов перевозки косой чертой или квадратным уголком, в этой статье из соображений лучшей доходчивости они подписаны. При решении транспортной задачи единственными необходимыми арифметическими действиями являются сложение и вычитание. Для поиска начального решения применяют метод северо-западного угла, метод минимальных тарифов или метод Фогеля, а для окончательной оптимизации - метод потенциалов. В то же время, транспортная задача является подмножеством задач линейного программирования и может решаться симплекс-методом. Транспортную задачу можно решать также в Excel.
Если сумма запасов равна сумме потребностей, то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была приведена к закрытому виду.
В показанном выше примере, сумма запасов = 30 + 40 + 20 = 90 кг, а сумма потребностей = 20 + 30 + 30 + 10 кг = 90 кг (запасы и потребности равны между собой, задача закрытая).
Если это равенство не соблюдено, необходимо ввести фиктивного поставщика или фиктивного потребителя на недостающий или избыточный объем товара, которому нужно приписать нулевую цену доставки. Этот объем будет соответствовать недопоставке или, напротив, избытку товара на складе.
Поиск начального решения:
Решение транспортной задачи начинается с поиска допустимого начального решения (плана перевозок), чтобы все запасы поставщиков были распределены по потребителям. Допустимое начальное решение не обязательно оказывается оптимальным, а метод его нахождения может быть как простейшим (метод северо-западного угла или аналоги) или более сложным и приближенным к оптимальному решению (метод минимальных тарифов, метод Фогеля), или же вообще произвольным.
Метод Фогеля- один из методов получения начального решения транспортной задачи. В отличие от метода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.
Суть метода:
Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек.
2. Решение задачи на примере
.1 Решение задачи в MS Excel
У поставщиков A1 , A2 , A3 , A4 , A5 , находится соответственно 100 , 150 , 350 , 200 , 200 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количестве 100 , 200 , 200 , 300 , 200 единиц соответственно.
Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 4 , 3 , 5 , 2 , 3 ден.ед.
Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 7 , 1 , 2 , 3 , 1 ден.ед.
Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 9 , 2 , 4 , 5 , 6 ден.ед.
Стоимость доставки единицы продукции от поставщика A4 к указанным потребителям равна 1 , 3 , 6 , 4 , 10 ден.ед.
Стоимость доставки единицы продукции от поставщика A5 к указанным потребителям равна 5 , 8 , 15 , 6 , 15 ден.ед.
В1В2В3В4В5ЗапасыА143523100А271231150А392456350А4136410200А55815615200Потребности100200200300200
Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны.
Решение
Этап I. Поиск первого опорного плана.
Метод минимальной стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100+150+350+200+200=1000
∑b = 100+200+200+300+200=1000
В ячейке B3:F7 запишем стоимость доставки единицы продукции от поставщиков к потребителям.
В ячейке B11:F15 запишем единицы продукции поставленные потребителям.
В ячейке H13 запишем
=СУММПРОИЗВ(B3:F7;B11:F15)
1.Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
В1В2В3В4В5ЗапасыА1 435100 23100А27150 1231150А3950 2200 4100 56350А4100 136100 410200А558156200 15200Потребности100200200300200
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
. Подсчитаем число занятых клеток таблицы, их 8. Требуется 9.
В свободную ячейку A2B5 запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф.
Будем считать, что от поставщика A2 к потребителю B5 доставляем 0 единиц продукции.
В1В2В3В4В5ЗапасыА1435100 23100А27150 1230 1150А3950 2200 4100 56350А4100 136100 410200А558156200 15200Потребности100200200300200S0=5250
Количество базисных ячеек (задействованных маршрутов) равно 9, что и требовалось. Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 2 * 100 + 1 * 150 + 2 * 50 + 4 * 200 + 5 * 100 + 1 * 100 + 4 * 100 + 15 * 200 = 5250
2.2 Решение задачи методом Фогеля
У поставщиков A1 , A2 , находится соответственно 250 , 400 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 в количестве 100 , 300 , 50 , 200 единиц соответственно.
Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 1 , 4 , 5 , 2 ден.ед.
Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 3 , 6 , 8 , 7 ден.ед.
Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.
В1В2В3В4ЗапасыА11452250А23687400Потребности10030050200
Найдем начальное решение методом Фогеля.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
∑a = 250+400=650
∑b = 100+300+50+200=650
В каждой строке, найдем разность Δi между двумя ячейками (доступными для выбора) с наименьшими тарифами.
В1В2В3В4ΔiА114521А236873
В каждом столбце, найдем разность j между двумя ячейками (доступными для выбора) с наименьшими тарифами.
В1В2В3В4А11452А23687Δj2235
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 4. В данном столбце выберем ячейку A1B4, как обладающую наименьшим тарифом. Т.к. стоимость доставки будет меньше на 5 ден. ед.
В1В2В3В4ЗапасыА11450 5200 2250А2100 3300 687400Потребности10030050200
Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек равно 4. Требуется, чтобы было 5. В свободную ячейку A1B1 запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф. Будем считать, что от поставщика A1 к потребителю B1 доставляем 0 единиц продукции.
В1В2В3В4ЗапасыА10 1450 5200 2250А2100 3300 687400Потребности10030050200
Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.= 5 * 50 + 2 * 200 + 3 * 100 + 6 * 300 = 2750
Шаг 1.
Произведем оценку полученного решения.
Поскольку, число базисных клеток - 5, а общее количество потенциалов равно 6, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем u1 = 0.
v3 + u1 = c13 v3 + u1 = 5v3 = 5 - 0 = 5+ u1 = c14 v4 + u1 = 2v4 = 2 - 0 = 2+ u2 = c21 v1 + u2 = 3u2 = 3 - 1 = 2+ u2 = c22 v2 + u2 = 6v2 = 6 - 2 = 4
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
Δ12 = c12 - ( u1 + v2 ) = 4 - ( 0 + 4 ) = 0
Δ23 = c23 - ( u2 + v3 ) = 8 - ( 2 + 5 ) = 1
Δ24 = c24 - ( u2 + v4 ) = 7 - ( 2 + 2 ) = 3
В1В2В3В4UjА10 10 450 5200 2u 1=0А2100 3300 61 83 7u 2=2Viv 1=1v 2=4v 3=5v 4=2
Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение.
Smin = 5 * 50 + 2 * 200 + 3 * 100 + 6 * 300 = 2750
Список литературы
1. С.Г. Кальней, Ю.В. Тыжнов «Исследование операций» МИЭТ 2009 г.
. В.А. Филиппов «Лабораторный практикум по курсу «Исследование операций в экономике» МИЭТ 2008 г.
. http://cyclowiki.org - Сайт Циклопедия