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

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

[Введите текст]

АННОТАЦИЯ

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



ВВЕДЕНИЕ

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

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

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



1. ХАРАКТЕРИСТИКА КЛАССА ЗАДАЧ

1.1 МЕТОДЫ НАХОЖДЕНИЯ ОПОРНЫХ ПЛАНОВ

Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла - наихудшее. Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована. Метод северо-западногоугла На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце . Если существующий запас позволяет перевезти всю потребность, то в клетку (i,j) в качестве перевозки вписывается значение потребности ;

j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

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



.

Если существующий запас не позволяет перевезти всю потребность, то

в клетку (i,j) в качестве перевозки вписывается значение запаса ;

i-я строка вычеркивается, поскольку ее запас уже исчерпан;

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

.

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

1.2 ОБЩИЙ ВИД РЕШЕНИЯ И ОБОБЩЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Пусть требуется перевезти груз из пункта А1, А2,…,Аn в пункты В1, В2,…,Вn.

а11, а12,…,аnk - стоимость перевозки из пункта Аi в пункт Вj.

А1=100; А2=200; А3=150; В1=80; В2=90; В3=120; В4=160.

Распределить продукцию так со склада, чтобы затраты были минимальные.

Построим начальную таблицу для заполнения ячеек:

Таблица 1 - Начальная таблица для заполнения ячеек

		4		7		7		1	100
80		20
	12		3		8		8	200
	70	120	10
	8		10		16		5	150
			150
80	90	120	160

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

Сумма запаса и сумма потребления были равны:

100+200+150=80+90+120+160; 450=450.

Принцип заполнения ячеек состоит в том, чтобы в выбранную ячейку заносилось минимальное число из стоящих напротив ячеек с параметрами, например: для заполнения ячейки 1-А берутся значения 80 и 100: min= (80;100). Затем меньшее число вычитается из обеих ячеек-значений.

После заполнения необходимо найти целевую функцию:

Z=80*4+20*7+70*3+120*8+10*8+150*5=3180

Получение начального опорного плана

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

- метод минимального элемента

I. Метод минимального элемента:

Определим ячейку с наименьшей стоимостью;

Распределим как можно больше единиц в эту ячейку и вычеркнем строку или столбец, который исчерпан;

Найдем ячейку с наименьшей стоимостью из оставшихся;

Повторим пункт 2 и 3 пока все единицы не будут распределены.

Таблица 2 - Определение ячеек методом наименьшей стоимости

	4		7		7		1	100
			100
	12		3		8		8	200
	90	110
	8		10		16		5	150
80		10	60
80	90	120	160

Находим целевую функцию:

100*1+90*3+110*8+80*8+10*16+60*5=2350

Получили начальное решение.

II. Проверка решения на оптимальность:

- метод по камням

- метод Modi.

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

Метод по камням:

Камни - заполненные ячейки

Поставим знак «+», в ячейку которую оцениваем;

Двигаясь горизонтально или вертикально к заполненной ячейке(при этом можем пропустить заполненную или пустую ячейку которая, разрешит следующий переход к заполненной ячейке), поставим знак «-»;

Изменяем направление и перемещаемся к другой заполненной ячейке, выбираем ту разрешит следующий переход, ставим в нее знак «+»;

Процесс перемещения в заполненной ячейке и чередование знаков продолжаем пока не вернемся к первоначальной.

Таблица 3 - Оценивание ячеек

1-А
1А+4	-8 3А
3D+5	-1 1D
0
1-C
1C+7	-1 1D
3D+5	-16 3C
-5

Оценка пустых ячеек методами возможна при условии: число заполненных ячеек равна сумме строк и столбцов и -1:

k=R+L-1

Значение оценки показывает на сколько сократятся(увеличатся) затраты на перевозку единиц продукции если в эту ячейку переместить значение.

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

Таблица 4 - Изменение начальной таблицы

		4		7		7		1	100
			10	90
	12		3		8		8	200
	90	110
	8		10		16		5	150
80			70
80	90	120	160

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

Метод MODI (модифицированное распределение).

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

Этот метод состоит из шагов:

1) Сделать начальное распределение (интуитивный подход), проверить матрицу на полноценность, в случае необходимости провести корректировку.

2) Получить номер индекса для каждой строки и столбца. Делая это используя только заполненные ячейки. Всегда есть по крайней мере одна заполненная ячейка в каждом столбце и строке.

а) начинаем, назначая ноль в первой строке

б) определить индекс столбца для любой заполненной ячейки в строке 1, используя следующие соотношения:

индекс столбца = U;

индекс строки = V;

затраты ячейки = С;



U = C-V

в) Каждое новое значение столбца позволит вычислить по крайней мере 1 новое значение строки и наоборот. Продолжайте эту процедуру пока все строки и столбцы будут заполнены индексами.

3) Получить оценки для пустых ячеек

W - оценка ячейки

W = C- (U+V)

1 - C: W = 7-(0+9) = -2

2 - A: W = 4-(1+3)= 0

4) Получение наилучшего решения

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



2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

Информация необходимая для использования модели включает следущее:

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

- список мест назначения и их показатели спроса;

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



3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Пусть Xij - количество груза перевозимого из пункта i в пункт j.

А1=40; А2=50; В1=20; В2=30; В3=40;

3 5 7

С = 4 6 10

Таблица 5 - Начальные параметры

	B1	B2	B3
A1		3		5		7
				40
A2		4		6		10	50
	20	30	40

Целевая функция имеет вид:

Ограничение по запасам:

Х11 + Х12 + Х13 <= 40

Х21 + Х22 + Х23 <= 50

Xij>=0

Ограничение по спросу:

Х11 + Х21 <= 20

Х12 + Х22 <= 30



Х13 + Х23 <= 40

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

Получение начального решения

Проверка решений на оптимальность

Усовершенствование несовершенных решений

Интуитивный подход.

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

Таблица 6 - Заполнение ячеек

	B1	B2	B3
A1		3		5		7
	20	20		40
A2		4		6		10	50
		10	40
	20	30	40

Целевая функция:

Z=3*20+5*20+6*10+10*40=60+100+60+400=620

4. РЕШЕНИЕ ЗАДАЧИ

4.1 МАТЕМАТИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ

Задача №5.01 Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие: . Решение Проверка сбалансированности задачи показывает, что суммарный объем запасов равен суммарному объему потребностей, т.е. введение фиктивных столбцов или строк не потребуется Таблица 5.1

Транспортная таблица с опорным планом северо-западного угла

Пункт назначения	B1	B2	B3	B4	Запасы
Пункт отправки
A1	5	8	1	2	210
A2	2	5	4	9	170
A3	9	2	3	1	65
Потребности	125	90	130	100

Опорный план , найденный методом северо-западного угла [ед.товара]. Соответствующая ЦФ (общие затраты на перевозку) [руб.].



Транспортная таблица с опорным планом минимального элемента

Пункт назначения B1 B2 B3 B4 Запасы Пункт отправки A1 5 8 1 2 210 A2 2 5 4 9 170 A3 9 2 3 1 65 Потребности 125 90 130 100

Опорный план , найденный методом минимального элемента

Транспортная таблица с опорным планом Фогеля

На первом шаге нахождения опорного плана методом Фогеля возникает ситуация равенства значений максимальных штрафов транспортной матрицы (см. табл. 5.3) .

Пункт назначения B1 B2 B3 B4 Запасы Пункт отправки A1 5 8 1 2 210 A2 2 5 4 9 170 A3 9 2 3 1 65 Потребности 125 90 130 100

Опорный план , найденный методом Фогеля



[ед.товара], [руб.].

4.2 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ MICROSOFT EXCEL

Программным продуктом, незаменимым в офисной работе, является электронная таблица Microsoft Excel. При помощи этого продукта можно анализировать большие массивы данных. В Excel можно использовать более 400 математических, статистических, финансовых и других специализированных функций, связывать различные таблицы между собой, выбирать произвольные форматы представления данных, создавать иерархические структуры. Воистину безграничны методы графического представления данных: помимо нескольких десятков встроенных типов диаграмм, можно создавать свои, настраиваемые типы, помогающие наглядно отразить тематику диаграммы. Те, кто только осваивает работу с Excel, по достоинству оценят помощь "мастеров" - вспомогательных программ, помогающих при создании диаграмм.

Рисунок 1 - Создание общей таблицы

Рисунок 2 - Поиск решения



Рисунок 3 - Добавление ограничений

Рисунок 4 - Вывод целевой функции



5. АНАЛИЗ РЕЗУЛЬТАТОВ

При решении задачи были получены результаты удовлетворяющие условию:

Решая задачу математически, получили значения:

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

	7		12		4		6		5	180
		120	60
	1		8		6		5		3	350
110	90		20	130
	6		13		8		7		4	20
				20
110	90	120	80	150

Z=120*4+60*6+110+90*8+20*5+130*3+20*4=2240

При решении задачи в программе Excel получили значения:

Рисунок 5

В программе, созданной для решения задачи, получили тот же результат.

Соответственно можно сделать вывод, что задача была решена правильно.



ЗАКЛЮЧЕНИЕ

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

В данной курсовой работе поставлена задача: минимизировать затраты на транспортировку продукции потребителям. При выполнении курсовой работы были использованы знания по предметам: «Математические методы», «Пакеты прикладных программ». Решение было проведено с помощью пакетов прикладных программ Microsoft Excel и Microsoft Word. Результаты ручного просчёта сравнивались с результатами, полученными в Microsoft Excel.

Курсовая работа выполнена в полном объёме в соответствии с требованиями ГОСТ.



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

1. ГОСТ 7.1-84. Библиографическое описание документа. Общие требования и правила составления.

2. ГОСТ 7.9-95. Реферат и аннотация. Общие требования.

3. Акулич И.Л. Математическое программирование в примерах и задачах, 2010 г.

4. Бутаков Е.А. Методы создания качественного программного обеспечения ЭВМ, 2009 г.

5. Ван-Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ, 2010 г.

6. Жоголев Е.А. Введение в технологию программирования; Конспект лекции, 2008 г.

7. Орлов В.В. Технологии разработки программных продуктов, 2008 г.

8. Вендров А.М. Практикум по проектированию программного обеспечения экономических информационных систем, 2009 г.

9. Информатика: Учебник . 3-е издание. Переработано. / Под ред. Н.В. Монаровой, 2010 г.

10. Партыка Т.Л., Попов И.И. Информационная безопасность, 2008 г.

11. Шишкин В.В. Методические указания к курсовому проекту, 2010 г.

12. Шураков В.В. Надежность программного обеспечения, 2008 г.

13. Канторович Л.В., Горстко А.Б. «Математическое оптимальное программирование в экономике», Знание, 2010 г.

14. Конюховский П.В. «Математические методы исследования операций в экономике», Питер, 2008 г.

15. Кузнецов А.В., Новикова Г.И., Холод И.И. - «Сборник задач по математическому программированию». Минск, Высшая школа, 2009 г.

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

...