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

Автор работы: Пользователь скрыл имя, 08 Февраля 2014 в 08:51, курсовая работа

Краткое описание

Целью работы является анализ применения транспортной задачи и метода потенциалов линейного программирования для решения задачи по планированию перевозок и минимизации расходов на транспортировку кирпича от поставщика к покупателям. Задачами курсовой работы являются: • изучить литературу по теме транспортной задачи и линейного программирования; • сформулировать постановку транспортной задачи; • обоснование выбора метода потенциалов для проверки оптимального плана грузоперевозок; • описание метода решения задачи; • построить транспортную модель задачи и обосновать оптимальный вариант; • проанализировать полученный результат.

Содержание

Введение 3
1. Обзор литературы по теме исследования 4
2. Постановка и формализация задачи 8
3. Построение математической модели задачи 9
3.1. Целевая функция и критерий оптимизации 9
3.2. Система ограничений 9
4. Решение задачи на ЭВМ с помощью программы 10
5. Анализ результатов решения задачи 18
Заключение 19
Список использованных источников 20

Скачать полностью (415.41 Кб) Сколько стоит заказать работу?

Прикрепленные файлы: 1 файл

курс.docx

— 441.40 Кб (Скачать документ)

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

Примем u₄ = 0.

A₄B₂ : v₂ + u₄ = 6 v₂ = 6 - 0 = 6

A₄B₅ : v₅ + u₄ = 7 v₅ = 7 - 0 = 7

A₄B₆ : v₆ + u₄ = 14 v₆ = 14 - 0 = 14

A₁B₆ : v₆ + u₁ = 8 u₁ = 8 - 14 = -6

A₂B₅ : v₅ + u₂ = 6 u₂ = 6 - 7 = -1

A₃B₂ : v₂ + u₃ = 4 u₃ = 4 - 6 = -2

A₁B₁ : v₁ + u₁ = 8 v₁ = 8 - ( -6 ) = 14

A₁B₃ : v₃ + u₁ = 5 v₃ = 5 - ( -6 ) = 11

A₂B₄ : v₄ + u₂ = 7 v₄ = 7 - ( -1 ) = 8

A₅B₁ : v₁ + u₅ = 9 u₅ = 9 - 14 = -5

₁₂ = 7 - ( -6 + 6 ) = 7

₁₄ = 10 - ( -6 + 8 ) = 8

₁₅ = 12 - ( -6 + 7 ) = 11

₂₁ = 13 - ( -1 + 14 ) = 0

₂₂ = 8 - ( -1 + 6 ) = 3

₂₃ = 10 - ( -1 + 11 ) = 0

₂₆ = 13 - ( -1 + 14 ) = 0

₃₁ = 12 - ( -2 + 14 ) = 0

₃₃ = 11 - ( -2 + 11 ) = 2

₃₄ = 9 - ( -2 + 8 ) = 3

₃₅ = 10 - ( -2 + 7 ) = 5

₃₆ = 11 - ( -2 + 14 ) = -1

₄₁ = 14 - ( 0 + 14 ) = 0

₄₃ = 12 - ( 0 + 11 ) = 1

₄₄ = 13 - ( 0 + 8 ) = 5

₅₂ = 12 - ( -5 + 6 ) = 11

₅₃ = 14 - ( -5 + 11 ) = 8

₅₄ = 15 - ( -5 + 8 ) = 12

₅₅ = 8 - ( -5 + 7 ) = 6

₅₆ = 13 - ( -5 + 14 ) = 4

План неоптимален.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

80
	8


	7

130
	5


	10


	12

30
	8

240

A ₂


	13


	8


	10

170
	7

190
	6


	13

360

A ₃


	12

180 - 80
	4


	11


	9


	10

+ 80
-1	11

180

A ₄


	14

40 + 80
	6


	12


	13

0
	7

80 - 80
	14

120

A ₅

150
	9


	12


	14


	15


	8


	13

150

Потребность

230

220

130

170

190

110

Получаем новый план грузоперевозок.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

B ₆

A ₁

80
	8


	7

130
	5


	10


	12

30
	8

240

A ₂


	13


	8


	10

170
	7

190
	6


	13

360

A ₃


	12

100
	4


	11


	9


	10

80
	11

180

A ₄


	14

120
	6


	12


	13

0
	7


	14

120

A ₅

150
	9


	12


	14


	15


	8


	13

150

Потребность

230

220

130

170

190

110

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

Примем u₁ = 0.

A₁B₁ : v₁ + u₁ = 8 v₁ = 8 - 0 = 8

A₁B₃ : v₃ + u₁ = 5 v₃ = 5 - 0 = 5

A₁B₆ : v₆ + u₁ = 8 v₆ = 8 - 0 = 8

A₃B₆ : v₆ + u₃ = 11 u₃ = 11 - 8 = 3

A₅B₁ : v₁ + u₅ = 9 u₅ = 9 - 8 = 1

A₃B₂ : v₂ + u₃ = 4 v₂ = 4 - 3 = 1

A₄B₂ : v₂ + u₄ = 6 u₄ = 6 - 1 = 5

A₄B₅ : v₅ + u₄ = 7 v₅ = 7 - 5 = 2

A₂B₅ : v₅ + u₂ = 6 u₂ = 6 - 2 = 4

A₂B₄ : v₄ + u₂ = 7 v₄ = 7 - 4 = 3

₁₂ = 7 - ( 0 + 1 ) = 6

₁₄ = 10 - ( 0 + 3 ) = 7

₁₅ = 12 - ( 0 + 2 ) = 10

₂₁ = 13 - ( 4 + 8 ) = 1

₂₂ = 8 - ( 4 + 1 ) = 3

₂₃ = 10 - ( 4 + 5 ) = 1

₂₆ = 13 - ( 4 + 8 ) = 1

₃₁ = 12 - ( 3 + 8 ) = 1

₃₃ = 11 - ( 3 + 5 ) = 3

₃₄ = 9 - ( 3 + 3 ) = 3

₃₅ = 10 - ( 3 + 2 ) = 5

₄₁ = 14 - ( 5 + 8 ) = 1

₄₃ = 12 - ( 5 + 5 ) = 2

₄₄ = 13 - ( 5 + 3 ) = 5

₄₆ = 14 - ( 5 + 8 ) = 1

₅₂ = 12 - ( 1 + 1 ) = 10

₅₃ = 14 - ( 1 + 5 ) = 8

₅₄ = 15 - ( 1 + 3 ) = 11

₅₅ = 8 - ( 1 + 2 ) = 5

₅₆ = 13 - ( 1 + 8 ) = 4

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

С = 80*8+130*5+30*8+170*7+190*6+100*4+80*11+120*6+0*7+150*9 = 7210

5. Анализ результатов решения задачи

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

При первом построении плана грузоперевозок методом минимального тарифа стоимость перевозки составила 7410 ден. ед. Далее был применен метод потенциалов для проверки плана на оптимальность.

Метод потенциалов показал, что план перевозок можно улучшить, что показывает его стоимость 7210 ден.ед. Разница стоимости грузоперевозок показывает, что метод потенциалов позволяет оптимизировать первоначальный план грузоперевозок на 200 ден.ед.

Заключение

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

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

Информация о работе Транспортная задача