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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ………………………………………………………………….……3

1. ТРАНСПОРТНАЯ ЗАДАЧА………….......……………………………........5
1. Транспортная задача по критерию стоимость в матричной постановке………………………………………………………………...5
2. Опорный план транспортной задачи и его построения……………….8
2. ТРАНСПОРТНАЯ ЗАДАЧА РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ…..11

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

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

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

ЗАКЛЮЧЕНИЕ………………………………………………………………….25

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………...…….…....26

 

ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

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

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

• Анализ понятия «Транспортная задача», выявление её сущности и методов решения.
• Изучение основных способов построения опорного плана.
• Изучение распределительного метода при решении транспортной задачи.
• Анализ алгоритма распределительного метода.

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

 

 

 

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

 

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

 

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

В m пунктах производства А1, … , Аm находится однородный продукт (уголь, картофель и т.д.) в количествах соответственно a1, …, am ед., который должен быть доставлен n потребителям B1, …, Bn в количествах b1, …, bn ед. Известны транспортные издержки cij (расходы), связанные с перевозкой единицы продукта из пункта А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

 

Матрицу (cij) m n называют матрицей тарифов, а числа cij — тарифами.

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

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

 

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

 

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

 

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)система  уравнений симметрична относительно  всех переменных xij. 
1.2 Опорный план транспортной задачи и его построение

 

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

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

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

План перевозок будем строить непосредственно в транспортной таблице. Если переменная xij принимает значение aij, отличное от нуля, т.е. xij = aij 0, то в соответствующую клетку (i; j) таблицы будем вписывать это значение; если же xij = 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)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину: