Решение транспортной задачи распределительным методом

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

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

Введение

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

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

Один из классов математических моделей - задачи линейного программирования. Одной из задач линейного программирования является транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). Транспортная задача, как и задача линейного программирования, была впервые поставлена советским экономистом А.Н. Толстым в 1930 году. Разработка общих методов решения задачи линейного программирования и их математическое исследование связано с именем советского ученого Л.В. Канторовича. В 1939 году методам решения задачи линейного программирования посвящено также большое число работ зарубежных ученых.

Транспортная задача делится на два вида: транспортная задача по критерию стоимости - определение плана перевозок, при котором стоимость груза была бы минимальна; транспортная задача по критерию времени - более важным является выигрыш по времени. Транспортная задача по критерию стоимости является частным случаем задачи линейного программирования.

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

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

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

Объектом изучения являются материальные и соответствующие финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

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

Для достижения поставленной цели следует решить следующие задачи:

· Анализ понятия «Транспортная задача», выявление её сущности и методов решения.

· Изучение основных способов построения опорного плана.

· Изучение распределительного метода при решении транспортной задачи.

· Анализ алгоритма распределительного метода.

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

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

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

Простейшая задача на перевозки по критерию стоимости формулируется следующим образом.

В m пунктах производства А1, …, Аm находится однородный продукт (уголь, картофель и т.д.) в количествах соответственно a1, …, am ед., который должен быть доставлен n потребителям B1, …, Bn в количествах b1, …, bn ед. Известны транспортные издержки c_ij (расходы), связанные с перевозкой единицы продукта из пункта Аi в пункт Bj. Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами поставки.

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

= (1.1.1)

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

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

Если суммарный запас продукта превышает общий спрос, т.е.

 > ,

то в рассмотрение вводится фиктивный (n + 1) - й пункт потребления Bn+1 со спросом, равным небалансу, т.е.

= -,

и одинаковыми тарифами, полагаемыми обычно равными нулю. Теперь условие разрешимости выполняется, а величина целевой функции остается прежней, поскольку цены на дополнительные перевозки равны нулю. При этом грузы, которые должны быть перевезены в пункт Bn+1, фактически останутся в пункте отправления.

Если же общий спрос потребителей больше суммарного запаса продукта, то вводится фиктивный (m + 1) - й пункт отправления Am+1 с запасом продукта

= -.

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

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

В таблице количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения, обозначено xij. Мы будем предполагать, что все xij 0, т.е. обратные перевозки (например, по рекламации) не рассматриваются.

Таблица 1

Поставщик	Потребитель	Запас груза
	B1	B2	…	Bn
A1	c11 x11	c12 x12	…	c1n x1n	a1
A2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	Am
Потребность в грузе	b1	b2	…	bn

Матрицу (c_ij) mn называют матрицей тарифов, а числа c_ij - тарифами.

Планом транспортной задачи называют матрицу X = (x_ij) mn. Ее называют еще матрицей перевозок.

Составим математическую модель задачи. Целевая функция f, выражающая суммарные транспортные затраты, связанные с реализацией плана X перевозок, запишется в виде

f = c11 x11 + c12 x12 + … + cmn xmn =. (1.1.2)

Переменные x_ij должны удовлетворять ограничениям по запасам

xi1 + xi2 + … + xin = = ai (i =) (1.1.3)

и ограничениям по потребностям

x1j + x2j + … + xmj = = bj (j =). (1.1.4)

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

0 (i =, j =). (1.1.5)

Таким образом, математически транспортная задача (1.1.2) - (1.1.5) ставится следующим образом. Среди множества решений системы линейных уравнений (1.1.3), (1.1.4) и неравенств (1.1.5) найти такое решение (x*11; x*12; …; x*mn), которое доставляет минимум линейной функции (1.1.2). Отсюда видно, что транспортная задача является задачей линейного программирования и ее можно решать симплекс-методом. Однако специфические особенности системы ограничительных уравнений (1.1.3), (1.1.4) позволили разработать для транспортной задачи более простые методы решения.

Эти особенности состоят в следующем:

1) коэффициенты при переменных во всех уравнениях равны либо единице, либо нулю;

2) каждая переменная встречается в двух и только двух уравнениях: один раз в системе ограничений по запасам и один раз в системе ограничений по потребностям;

3) система уравнений симметрична относительно всех переменных x_ij.

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

Структура опорного плана.

Ранг матрицы системы ограничительных уравнений транспортной задачи (1.1.2) - (1.1.5) на единицу меньше числа уравнений, т.е. r = m + n - 1.

Система ограничительных уравнений содержит mn переменных и m + n уравнений. Из сформулированной теоремы следует, что каждый опорный план задачи имеет m + n - 1 базисных переменных и mn - (m + n - 1) свободных переменных, равных нулю.

План перевозок будем строить непосредственно в транспортной таблице. Если переменная x_ij принимает значение a_ij, отличное от нуля, т.е. x_ij = a_ij 0, то в соответствующую клетку (i; j) таблицы будем вписывать это значение; если же x_ij = 0, то клетку (i; j) оставляем свободной. Согласно формулированной теореме, каждый опорный план будет «загружать» m + n - 1 клеток, а остальные останутся свободными. Это не единственное требование к опорному плану, требование связано с циклами в транспортной таблице.

Циклом в транспортной таблице называют набор клеток, в котором две и только две соседние клетки расположены в строке или одном столбце и последняя клетка набора в той же строке или столбце, что и первая.

Упомянутый набор клеток можно записать в виде

(i1; j1) (i1; j2) (i2; j2) … (is; js) (is; j1).

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

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

Способы построения начального опорного плана

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т.д. пунктах производства, по первому, второму и т.д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей - bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi(0)= аi, bj(0)= bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: хi, j=min {аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

аi (q+1)= аi(q) - xi, j, bj (q+1)= bj(q) - xi, j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi (q+1)= 0 или bj (q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т.е. переместиться к следующей клетке вниз по столбцу. Если же bj (q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn - (m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)=bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения ci, j. В связи с этим на практике для получения исходного плана используется другой способ - метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

Преобразование опорного плана в другой опорный план

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

2. Транспортная задача распределительным методом

2.1 Транспортная задача как частный случай общей распределительной задачи

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1, А2,…, Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2,…, аm единиц. Имеется n пунктов назначения В1, В2,…, Вn подавшие заявки соответственно на b1, b2,…, bn единиц груза. Известны стоимости Сi, j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj. Все числа Сi, j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Решение транспортной задачи начинается с нахождения опорного плана. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Составляя план по способам минимальных стоимостей в отличие от плана по способу «северо-западного угла» мы учитываем стоимости перевозок Ci, j, но все же не можем утверждать, что составленный нами план является оптимальным. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломанной линией, которая в каждой клетке совершает поворот на 90.

Существует несколько вариантов цикла:

1.) 2.) 3.)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком «+» те вершины цикла, в которых перевозки необходимо увеличить, а знаком «- «те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть «означенным». Перенести какое-то количество единиц груза по означенному циклу - это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется. По прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце - заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком «+», а в отрицательных со знаком «- «. Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

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

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

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

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

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

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

(2.1.4)

Обозначим алгебраическую сумму тарифов следующим образом:

. (2.1.5)

Тогда равенство (2.1.4) запишется в виде:

+

. (2.1.6)

Из равенства (2.1.5) видно, что величина зависит от значений тарифов cij и однозначно определяется структурой цикла клетки (k; s). Поэтому называется оценкой свободной клетки (k; s).

Из равенства (2.1.6) следует, что < 0, если < 0 (всегда величина неотрицательная), т.е. если оценка свободной клетки отрицательная, то ее следует загружать. Такие клетки называются перспективными. Если же оценки всех свободных клеток неотрицательные, то содержащийся в распределительной таблице опорный план является оптимальным. Если в распределительной таблице, содержащей оптимальный план, имеются свободные клетки с нулевыми оценками, то задача имеет не единственный опорный план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптимальный план.

2.2 Алгоритм распределительного метода

Ниже приведен алгоритм распределительного метода.

1. Условия задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас груза с суммарным спросом и случае нарушения равенства вводят в рассмотрение фиктивного поставщика (потребителя).

3. Строят начальный опорный план.

4. Вычисляют оценки свободных клеток по формуле (2.1.5). Если оценки всех свободных клеток неотрицательны, то построенный опорный план является оптимальным и остается подсчитать минимальные расходы . Если среди оценок есть отрицательные, то выбирают клетку наибольшей по абсолютной величине отрицательной оценкой и переходят к следующему пункту алгоритма.

5. Загружают выделенную в предыдущем пункте свободную клетку, получают новый опорный план и возвращаются к пункту 4 алгоритма.

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

2.3 Пример решения транспортной задачи распределительным методом

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

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

	1	2	3	4	Запасы
1	6	6	3	5	80
2	5	4	4	3	105
3	6	5	6	4	125
4	8	4	2	4	90
Потребности	110	130	160	120

Проверим необходимое и достаточное условие разрешимости задачи.

? a = 80 + 105 + 125 + 90 = 400

? b = 110 + 130 + 160 + 120 = 520

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 120 (520-400). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. 
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	6	6	3	5	80
2	5	4	4	3	105
3	6	5	6	4	125
4	8	4	2	4	90
5	0	0	0	0	120
Потребности	110	130	160	120

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.

Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(c_ij), способу Фогеля и по способу Лебедева-Тихомирова.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	Запасы
1	6 [10]	6	3 [70]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4	2 [90]	4	90
5	0 [100]	0 [20]	0	0	120
Потребности	110	130	160	120

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

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть

m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 6*10 + 3*70 + 3*105 + 5*110 + 4*15 + 2*90 + 0*100 + 0*20 = 1375

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

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина Д_ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х_ij=1 от поставщика А_i к потребителю В_j.

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

Величина Д _ij называется оценкой свободной клетки (или характеристика).

В исходном решении задачи имеются клетки свободные от поставок.

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

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

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

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

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

Следующий этап решения транспортной задачи заключается в улучшении опорного плана.

Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками Д_ij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции.

4. Определяем оценку для каждой свободной клетки.

В свободную клетку (1; 2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [-]	6 [+]	3 [70]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4	2 [90]	4	90
5	0 [100] [+]	0 [20] [-]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (1,2; 1,1; 5,1; 5,2;).

Оценка свободной клетки равна Д₁₂ = (6) - (6) + (0) - (0) = 0

В свободную клетку (1; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [-]	6	3 [70]	5 [+]	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4	2 [90]	4	90
5	0 [100] [+]	0 [20] [-]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (1,4; 1,1; 5,1; 5,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₁₄ = (5) - (6) + (0) - (0) + (5) - (4) = 0

В свободную клетку (2; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10]	6	3 [70]	5	80
2	5 [+]	4	4	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4	2 [90]	4	90
5	0 [100] [-]	0 [20] [+]	0	0	120
Потребности	110	130	160	120

Оценка свободной клетки равна Д₂₁ = (5) - (3) + (4) - (5) + (0) - (0) = 1

В свободную клетку (2; 2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	Запасы
1	6 [10]	6	3 [70]	5	80
2	5	4 [+]	4	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4	2 [90]	4	90
5	0 [100]	0 [20]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2;).

Оценка свободной клетки равна Д₂₂ = (4) - (3) + (4) - (5) = 0

В свободную клетку (2; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [+]	6	3 [70] [-]	5	80
2	5	4	4 [+]	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4	2 [90]	4	90
5	0 [100] [-]	0 [20] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (2,3; 2,4; 3,4; 3,2; 5,2; 5,1; 1,1; 1,3;).

Оценка свободной клетки равна Д₂₃ = (4) - (3) + (4) - (5) + (0) - (0) + (6) - (3) = 3

В свободную клетку (3; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10]	6	3 [70]	5	80
2	5	4	4	3 [105]	105
3	6 [+]	5 [110] [-]	6	4 [15]	125
4	8	4	2 [90]	4	90
5	0 [100] [-]	0 [20] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (3,1; 3,2; 5,2; 5,1;). 
Оценка свободной клетки равна Д₃₁ = (6) - (5) + (0) - (0) = 1 
В свободную клетку (3; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [+]	6	3 [70] [-]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [-]	6 [+]	4 [15]	125
4	8	4	2 [90]	4	90
5	0 [100] [-]	0 [20] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (3,3; 3,2; 5,2; 5,1; 1,1; 1,3;).

Оценка свободной клетки равна Д₃₃ = (6) - (5) + (0) - (0) + (6) - (3) = 4

В свободную клетку (4; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [-]	6	3 [70] [+]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8 [+]	4	2 [90] [-]	4	90
5	0 [100]	0 [20]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (4,1; 4,3; 1,3; 1,1;).

Оценка свободной клетки равна Д₄₁ = (8) - (2) + (3) - (6) = 3

В свободную клетку (4; 2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [-]	6	3 [70] [+]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4 [+]	2 [90] [-]	4	90
5	0 [100] [+]	0 [20] [-]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (4,2; 4,3; 1,3; 1,1; 5,1; 5,2;).

Оценка свободной клетки равна Д₄₂ = (4) - (2) + (3) - (6) + (0) - (0) = -1

В свободную клетку (4; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [-]	6	3 [70] [+]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4	2 [90] [-]	4 [+]	90
5	0 [100] [+]	0 [20] [-]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (4,4; 4,3; 1,3; 1,1; 5,1; 5,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₄₄ = (4) - (2) + (3) - (6) + (0) - (0) + (5) - (4) = 0

В свободную клетку (5; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10] [+]	6	3 [70] [-]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4	2 [90]	4	90
5	0 [100] [-]	0 [20]	0 [+]	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (5,3; 5,1; 1,1; 1,3;).

Оценка свободной клетки равна Д₅₃ = (0) - (0) + (6) - (3) = 3

В свободную клетку (5; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [10]	6	3 [70]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4	2 [90]	4	90
5	0 [100]	0 [20] [-]	0	0 [+]	120
Потребности	110	130	160	120

Цикл приведен в таблице (5,4; 5,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₅₄ = (0) - (0) + (5) - (4) = 1

Опорный план является неоптимальным, поскольку имеются отрицательные оценки клеток (4,2;) равные: (-1).

Переход от неоптимального опорного плана к лучшему.

Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (4; 2) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.

Из грузов х _ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4 [10]	2 [80]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

F(x) = 3*80 + 3*105 + 5*110 + 4*15 + 4*10 + 2*80 + 0*110 + 0*10 = 1365

4. Определяем оценку для каждой свободной клетки.

В свободную клетку (1; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6 [+]	6	3 [80] [-]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4 [10] [-]	2 [80] [+]	4	90
5	0 [110] [-]	0 [10] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (1,1; 1,3; 4,3; 4,2; 5,2; 5,1;).

Оценка свободной клетки равна Д₁₁ = (6) - (3) + (2) - (4) + (0) - (0) = 1

В свободную клетку (1; 2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6 [+]	3 [80] [-]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4 [10] [-]	2 [80] [+]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (1,2; 1,3; 4,3; 4,2;). Оценка свободной клетки равна Д₁₂ = (6) - (3) + (2) - (4) = 1

В свободную клетку (1; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80] [-]	5 [+]	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4 [10] [-]	2 [80] [+]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (1,4; 1,3; 4,3; 4,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₁₄ = (5) - (3) + (2) - (4) + (5) - (4) = 1

В свободную клетку (2; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5 [+]	4	4	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4 [10]	2 [80]	4	90
5	0 [110] [-]	0 [10] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (2,1; 2,4; 3,4; 3,2; 5,2; 5,1;).

Оценка свободной клетки равна Д₂₁ = (5) - (3) + (4) - (5) + (0) - (0) = 1

В свободную клетку (2; 2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4 [+]	4	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4 [10]	2 [80]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2;).

Оценка свободной клетки равна Д₂₂ = (4) - (3) + (4) - (5) = 0

В свободную клетку (2; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4 [+]	3 [105] [-]	105
3	6	5 [110] [-]	6	4 [15] [+]	125
4	8	4 [10] [+]	2 [80] [-]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (2,3; 2,4; 3,4; 3,2; 4,2; 4,3;).

Оценка свободной клетки равна Д₂₃ = (4) - (3) + (4) - (5) + (4) - (2) = 2

В свободную клетку (3; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6 [+]	5 [110] [-]	6	4 [15]	125
4	8	4 [10]	2 [80]	4	90
5	0 [110] [-]	0 [10] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (3,1; 3,2; 5,2; 5,1;).

Оценка свободной клетки равна Д₃₁ = (6) - (5) + (0) - (0) = 1

В свободную клетку (3; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [-]	6 [+]	4 [15]	125
4	8	4 [10] [+]	2 [80] [-]	4	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (3,3; 3,2; 4,2; 4,3;).

Оценка свободной клетки равна Д₃₃ = (6) - (5) + (4) - (2) = 3

В свободную клетку (4; 1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8 [+]	4 [10] [-]	2 [80]	4	90
5	0 [110] [-]	0 [10] [+]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (4,1; 4,2; 5,2; 5,1;).

Оценка свободной клетки равна Д₄₁ = (8) - (4) + (0) - (0) = 4

В свободную клетку (4; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4 [10] [-]	2 [80]	4 [+]	90
5	0 [110]	0 [10]	0	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (4,4; 4,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₄₄ = (4) - (4) + (5) - (4) = 1

В свободную клетку (5; 3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110]	6	4 [15]	125
4	8	4 [10] [+]	2 [80] [-]	4	90
5	0 [110]	0 [10] [-]	0 [+]	0	120
Потребности	110	130	160	120

Цикл приведен в таблице (5,3; 5,2; 4,2; 4,3;).

Оценка свободной клетки равна Д₅₃ = (0) - (0) + (4) - (2) = 2

В свободную клетку (5; 4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	6	6	3 [80]	5	80
2	5	4	4	3 [105]	105
3	6	5 [110] [+]	6	4 [15] [-]	125
4	8	4 [10]	2 [80]	4	90
5	0 [110]	0 [10] [-]	0	0 [+]	120
Потребности	110	130	160	120

Цикл приведен в таблице (5,4; 5,2; 3,2; 3,4;).

Оценка свободной клетки равна Д₅₄ = (0) - (0) + (5) - (4) = 1

Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.

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

Минимальные затраты составят:

F(x) = 3*80 + 3*105 + 5*110 + 4*15 + 4*10 + 2*80 + 0*110 + 0*10 = 1365

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

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп - (m+n-1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 - 361 цикл.

Заключение

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

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

Решение задачи распределительным методом производиться поэтапно:

· разработка начального плана (опорного решения);

· расчет потенциалов;

· проверка плана на оптимальность;

· поиск максимального звена неоптимальности;

· составление контура перераспределения ресурсов;

· определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

· получение нового плана.

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

Для транспортной задачи существует несколько способов отыскания начального плана (опорного решения): способ северо-западного угла; способ минимального элемента и т.д.

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

Список использованных источников

1. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. - М.: Высш. шк., 2001. - 129 с.

2. Безгинов А.Н. Экономико-математические модели в землеустройстве (линейные модели). - М.: ГУЗ, 1994. - 96 с.

3. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. - М.: Наука, 1976. - 103 с.

4. Карманов В.Г. Математическое программирование. - М.: Наука, 1986. - 74 с.

5. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 1986

6. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982

7. Кузнецов Ю.Н., Кузубов В.И., Волощснко А.Б. Математическое программирование. М.: Высшая школа, 1980

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