Способы решения транспортной задачи

Размещено на http://www.allbest.ru/

13

Размещено на http://www.allbest.ru/

Контрольная работа

по дисциплине Методы моделирования экономики

Тема:

Способы решения транспортной задачи

Выполнила:

Вишнякова Дарья Сергеевна

Введение

транспортный задача распределение

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

Стандартная транспортная задача определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Цель работы - рассмотреть транспортную задачу, решив её двумя способами: при помощи программы MS Excel и с применением метода Фогеля.

1. Постановка задачи

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

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

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

Если сумма запасов равна сумме потребностей, то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была приведена к закрытому виду.

В показанном выше примере, сумма запасов = 30 + 40 + 20 = 90 кг, а сумма потребностей = 20 + 30 + 30 + 10 кг = 90 кг (запасы и потребности равны между собой, задача закрытая).

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

Поиск начального решения:

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

1.2 Метод Фогеля

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

Суть метода:

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек.

2. Решение задачи на примере

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 ден.ед.

Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны.

Решение

Этап 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. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

2. Подсчитаем число занятых клеток таблицы, их 8. Требуется 9.

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

Будем считать, что от поставщика A2 к потребителю B5 доставляем 0 единиц продукции.

S0=5250

Количество базисных ячеек (задействованных маршрутов) равно 9, что и требовалось. Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 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 ден.ед.

Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.

Решение

Найдем начальное решение методом Фогеля.

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

?a = 250+400=650

?b = 100+300+50+200=650

В каждой строке, найдем разность Д_i между двумя ячейками (доступными для выбора) с наименьшими тарифами.

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

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 4. В данном столбце выберем ячейку A1B4, как обладающую наименьшим тарифом. Т.к. стоимость доставки будет меньше на 5 ден. ед.

Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек равно 4. Требуется, чтобы было 5. В свободную ячейку A1B1 запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф. Будем считать, что от поставщика A1 к потребителю B1 доставляем 0 единиц продукции.

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

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S0 = 5 * 50 + 2 * 200 + 3 * 100 + 6 * 300 = 2750

Шаг 1.

Произведем оценку полученного решения.

Поскольку, число базисных клеток - 5, а общее количество потенциалов равно 6, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем u1 = 0.

v1 + u1 = c11 v1 + u1 = 1 v1 = 1 - 0 = 1

v3 + u1 = c13 v3 + u1 = 5 v3 = 5 - 0 = 5

v4 + u1 = c14 v4 + u1 = 2 v4 = 2 - 0 = 2

v1 + u2 = c21 v1 + u2 = 3 u2 = 3 - 1 = 2

v2 + u2 = c22 v2 + u2 = 6 v2 = 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

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

Smin = 5 * 50 + 2 * 200 + 3 * 100 + 6 * 300 = 2750

Список литературы

1. С.Г. Кальней, Ю.В. Тыжнов «Исследование операций» МИЭТ 2009 г.

2. В.А. Филиппов «Лабораторный практикум по курсу «Исследование операций в экономике» МИЭТ 2008 г.

3. http://cyclowiki.org - Сайт Циклопедия

Размещено на Allbest.ru