Методы нахождения начального решения транспортной задачи

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

ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ИРКУТСКИЙ ТЕХНИКУМ АРХИТЕКТУРЫ И СТРОИТЕЛЬСТВА»

Курсовая работа

по дисциплине «Математические методы»

на тему: «Транспортная задача. Методы нахождения начального решения транспортной задачи»

Выполнила студентка

Группа ПО-10-434

Н.В. Павлова

Научный руководитель

Комбатова И.В.

Иркутск 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Математическая постановка

1.2 Классическая транспортная задача

1.3 Линейная транспортная задача

2. МЕТОДОМ ПОТЕНЦИАЛОВ

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

2.2 Метод наименьшей стоимости

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Данная тема на сегодняшний день является актуальной, т. к. каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием.

Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского.

По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

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

Задачи курсовой работы:

· Изучить литературу по теме «Транспортная задача»;

· Рассмотреть и проанализировать методы нахождения начального решения транспортной задачи;

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплекс - методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплекс - метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

1.1 Математическая постановка

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

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

Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

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

, i 1, …, m

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

, j 1, …, n

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

xij 0, i 1, ..., m; j 1, ..., n

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

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

Всякое неотрицательное решение системы линейных уравнений

, j 1, …, n и , i 1, …, m, определяемое матрицей X=(xij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.

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

План X*=(x*ij)(i 1, …, m; j 1, ..., n), при котором функция

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

Обычно исходные данные записываются в виде таблицы 1.

Таблица 1.

Пункты отправления	Пункты назначения	Запасы
	В1	…	Bj	…	Bn	А1
A1	C11 X11	…	C1j X1j	…	C1n X1n	a1
…	…	…	…	…	…	…
оAi	Ci1 Xi1	…	Cij Xij	…	Cin Xin	ai
…	…	…	…	…	…	…
Am	Cm1 Xm1	…	Cmj Xmj	…	Cmn Xmn	am
Потребности	b1	…	bj	…	bn

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

,

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

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

, i 1, ..., m.

Введение этого условия приводит к открытой транспортной модели.

1.2 Классическая транспортная задача

Классическая транспортная задача-- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

1.3 Линейная транспортная задача

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n, который потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k Сij.

Далее, где ai-есть количество продукции, находящееся на складе i, и bj - потребность потребителя j.

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

2. МЕТОДОМ ПОТЕНЦИАЛОВ

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим себе, что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму ai; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму bj. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим ai + bj = иij (i=1. m; j=1. n) и будем называть величину иij “псевдостоимостью" перевозки единицы груза из Ai в Bj. Заметим, что платежи ai и bj не обязательно должны быть положительными; не исключено, что “перевозчик" сам платит тому или другому пункту какую-то премию за перевозку.

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

Алгоритм решения транспортной задачи методом потенциалов

1. Взять любой опорный план перевозок, в котором отмечены m +n - 1 базисных клеток (остальные клетки свободные).

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

3. Подсчитать псевдостоимостииi,j = ai + bj для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

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

Рассмотрим пример транспортной задачи

Исходная транспортная матрица

В табл. 2.2 по строкам матрицы представлены пункты (станции) отправления от А1 до А4 и объемы погрузки в тоннах - 100, 150, 90, 30 т, а по столбцам - пункты (станции) назначения от В1 до В5 и объемы выгрузки - 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (ai = bj = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А1 и станцией выгрузки В1, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом - 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, - оптимальным планом перевозок.

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

Составление первоначального плана перевозок начнем с перевозки запасов поставщика A1. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя B1, затем B2 и так далее.

Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика A1 не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика A2, то есть переместимся на следующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика A2, затем A3 и так далее. линейный транспортный задача перевозка

Пример:

Заказы запасы	В1	В2	В3	В4
	100	40	80	60
А1	160	100	4	40	8	20	10		5
А2	30		4		6	30	2		3
А3	90		4		4	30	6	60	5

Таким образом:

Теперь можем посчитать полную стоимость перевозок по данному плану:

, т.е.

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

2.2 Метод наименьшей стоимости

Рассмотрим этот метод на примере:

Если , то запасы поставщика Аiисчерпаны, а потребителю Вjтребуется еще единиц груза.

Далее не принимая во внимание i-ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей.

В случае из рассмотрения исключается j-й столбец, а запасы Аi, полагаются равными .

Заказы запасы	В1	В2	В3	В4
	100	40	80	60
А1	160	100	4		8		10	60	5
А2	30		4		6	30	2		3
А3	90		4	40	4	50	6		5

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

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

Клетка, содержащая наименьший тариф (число 2) - (2,3). Запишем в эту клетку элемент . Тогда , а вторую строчку можно больше не учитывать. Среди оставшихся клеток имеются три клетки с наименьшим тарифом 4: (1,1), (3,1), (3,2). Выберем, например, клетку (1,1) и запишем в нее число , получаем, что , а первый столбец таблицы больше не рассматриваем. Теперь наименьший тариф 4 проставлен в клетке (3,2), поэтому , второй столбец больше не нужен. Далее выбираем клетку (1,4) с тарифом 5 и пишем в нее . Исключив из рассмотрения 1-ю строку и 4-й столбец, переходим к последней клетке (3,3) и вписываем .

магазин склад	В1	В2	В3	В4	B5	U
	150	140	110	230	220
А1	320		20	13	23	9	20	230	15	90	24	0
А2	280	2	29	140	15	110	16	-1	19	30	29	5
А3	250	150	6	17	11	15	10	10	9	100	8	-16
V		22		10		11		15	24

Найдем суммарную стоимость перевозок по этому плану

ПРАКТИЧЕСКАЯ ЧАСТЬ

Решение задачи методом наименьшей стоимости

Задача:

Из трех холодильников А1, А2, А3 , вмещающих мороженную рыбу в количествах ai , необходимо доставить в 5 магазинов B1, B2, B3 ,B4 ,B5

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

Z=15•230+90•24+140•15+110•16+30•29+150•6+100•8=12040

m+n-1=3+5-1=7

U1+V5=24 V5=24

U1+V4=15 V4=15

U2+V2=15 V2=10

U2+V3=16 V3=11

U2+V5=29 V1=22

U3+V1=6 V2=5

U3+V5=8 V3=-16

U1=0

Cij=Cij-(Ui+Vj)

C11=20-(0+22)=-2

C12=23-(0+10)=13

C13=20-(0+11)=9

C21=29-(5+22)=2

C24=19-(5+15)=-1

C32=11-(-16+10)=17

C33=10-(-16+11)=15

C34=9-(-16+15)=10

магазин склад	В1	В2	В3	В4	B5	U
	150	140	110	230	220
А1	320	90	20	15	23	11	20	230	15	2	24	0
А2	280	2	29	140	15	110	16	-3	19	30	29	7
А3	250	60	6	17	11	15	10	8	9	190	8	-14
V		20		8		9		15	22

U1 + V1 =20 V1=20 U3=-14

U1+ V4 =15 V4=15 U2=7

U2+ V2=15 V5=22

U2+ V3=16 V3=9

U2+ V5=29 V2=8

U3+ V1=6

U3+V5=8

U1 =0

C12=23-(0+8) =15

C13=20-(0+9) =11

C15=24-(0+22) =2

C21=29-(7+20) =2

C24=19-(7+15) =-3

C32=11-(-14+8) =17

C33=10-(-14+9) =15

C34=9-(-14+15) =8

m+n-1 =7

магазин склад	В1	В2	В3	В4	B5	U
	150	140	110	230	220
А1	320	120	20		23		20	200	15		24	0
А2	280		29	140	15	110	16	30	19		29	4
А3	250	30	6		11		10		9	220	8	-14
V		20		11		12		15	22

U1 + V1 =20 U1 =0 V1=20

U1 + V4 =15 U2 =4 V2 =11

U2+ V2 =15 U3 =-14 V3 =12

U2+ V3 =16 V4 =15

U2+ V4 =19 V5 =22

U3+ V1=6

U3+ V5 =8

C12=23-(0+11) =12

C13 =20-(0+12) =8

C15 =24-(0+22) =2

C21 =29-(4+20) =5

C25 =29-(4+22) =3

C32 =11-(-14+11) =14

C33 =10-(-14+12) =12

C34 =9-(-14+15) =8

Z=120•20+200•15+140•15+110•16+30•19+30•6+220•8=11770

Ответ: При плане перевозок, записанном в последней таблице, стоимость перевозок будет минимальной, стоимость составляет 11770.

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Астафьев Н.Н., Еремин И.И. Введение в теорию линейного и выпуклого программирования М.; Наука, 2000. - 387 с.

2. Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука,2001. -298 с.

3. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник/Под общ.ред. д.э.н., проф. Сидоровича А.В.; МГУ им. Ломоносова М.В. 3-е изд., перераб. - М.: Издательство «Дело и Сервис», 2001. - 368 с.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука,2003. - 453 с.

5. Карманов В.Г. Математическое программирование. - М.; Наука, 2000. - 342 с.

6. Ларионов Ю.И., Хажмурадов М.А., Кутуев Р.А. Методы исследований операций: Часть 1, 2010. - 312 с.

7. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. -М.; Наука, 2002. - 340 с.

8. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб.пособие. - М.: Дело, 2000. - 440 с.

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

...