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

Автор работы: Пользователь скрыл имя, 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 Кб (Скачать документ)

 

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

110

 

 

8  


 

 

 

7  


130

 

 

5  


 

 

 

10  


 

 

 

12  


 

 

 

8  


240   0

A 2

 

 

 

13  


 

 

 

8  


 

 

 

10  


170

 

 

7  


190

 

 

6  


 

 

 

13  


360   0

A 3

 

 

 

12  


180

 

 

4  


 

 

 

11  


 

 

 

9  


 

 

 

10  


 

 

 

11  


180   0

A 4

 

 

 

14  


40

 

 

6  


 

 

 

12  


 

 

 

13  


 

 

 

7  


80

 

 

14  


120   0

A 5

120

 

 

9  


 

 

 

12  


 

 

 

14  


 

 

 

15  


 

 

 

8  


30

 

 

13  


150   0

Потребность

230   0

220   0

130   0

170   0

190   0

110   0

 

 

Стоимость доставки продукции, для начального решения

С = 110 * 8 + 130 * 5 + 170 * 7 + 190 * 6 + 180 * 4 + 40 * 6 + 80 * 14 + 120 * 9 + 30 * 13 =   7410 ден. ед.

Далее задача проверяется на вырожденность

m+n–1

Требуется, чтобы количество загруженных ячеек  равнялось 10.

В данной задаче, количество загруженных ячеек  равняется 9.

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

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

Это ячейка А4В5

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

110

 

 

8  


 

 

 

7  


130

 

 

5  


 

 

 

10  


 

 

 

12  


 

 

 

8  


240

A 2

 

 

 

13  


 

 

 

8  


 

 

 

10  


170

 

 

7  


190

 

 

6  


 

 

 

13  


360

A 3

 

 

 

12  


180

 

 

4  


 

 

 

11  


 

 

 

9  


 

 

 

10  


 

 

 

11  


180

A 4

 

 

 

14  


40

 

 

6  


 

 

 

12  


 

 

 

13  


0

 

 

7  


80

 

 

14  


120

A 5

120

 

 

9  


 

 

 

12  


 

 

 

14  


 

 

 

15  


 

 

 

8  


30

 

 

13  


150

Потребность

230

220

130

170

190

110

  

 

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

Примем u4 = 0.


A4B2 :         v2 + u4 = 6         v2 = 6 - 0 = 6


A4B5 :         v5 + u4 = 7         v5 = 7 - 0 = 7


A4B6 :         v6 + u4 = 14       v6 = 14 - 0 = 14


A5B6 :         v6 + u5 = 13       u5 = 13 - 14 = -1


A2B5 :         v5 + u2 = 6         u2 = 6 - 7 = -1


A3B2 :         v2 + u3 = 4         u3 = 4 - 6 = -2


A5B1 :         v1 + u5 = 9         v1 = 9 - ( -1 ) = 10


A1B1 :         v1 + u1 = 8         u1 = 8 - 10 = -2


A1B3 :         v3 + u1 = 5         v3 = 5 - ( -2 ) = 7


A2B4 :         v4 + u2 = 7         v4 = 7 - ( -1 ) = 8


  

Далее необходимо найти оценки незадействованных маршрутов. Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя)

12 = 7 - ( -2 + 6 ) = 3


14 = 10 - ( -2 + 8 ) = 4


15 = 12 - ( -2 + 7 ) = 7


16 = 8 - ( -2 + 14 ) = -4


21 = 13 - ( -1 + 10 ) = 4


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


23 = 10 - ( -1 + 7 ) = 4


26 = 13 - ( -1 + 14 ) = 0


31 = 12 - ( -2 + 10 ) = 4


33 = 11 - ( -2 + 7 ) = 6


34 = 9 - ( -2 + 8 ) = 3


35 = 10 - ( -2 + 7 ) = 5


36 = 11 - ( -2 + 14 ) = -1


41 = 14 - ( 0 + 10 ) = 4


43 = 12 - ( 0 + 7 ) = 5


44 = 13 - ( 0 + 8 ) = 5


52 = 12 - ( -1 + 6 ) = 7


53 = 14 - ( -1 + 7 ) = 8


54 = 15 - ( -1 + 8 ) = 8


55 = 8 - ( -1 + 7 ) = 2


  

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

110 - 30

 

 

8  


 

 

 

7  


130

 

 

5  


 

 

 

10  


 

 

 

12  


+ 30

-4

8  


240

A 2

 

 

 

13  


 

 

 

8  


 

 

 

10  


170

 

 

7  


190

 

 

6  


 

 

 

13  


360

A 3

 

 

 

12  


180

 

 

4  


 

 

 

11  


 

 

 

9  


 

 

 

10  


 

 

 

11  


180

A 4

 

 

 

14  


40

 

 

6  


 

 

 

12  


 

 

 

13  


0

 

 

7  


80

 

 

14  


120

A 5

120 + 30

 

 

9  


 

 

 

12  


 

 

 

14  


 

 

 

15  


 

 

 

8  


30 - 30

 

 

13  


150

Потребность

230

220

130

170

190

110

  

 

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

B 5

B 6

A 1

80

 

 

8  


 

 

 

7  


130

 

 

5  


 

 

 

10  


 

 

 

12  


30

 

 

8  


240

A 2

 

 

 

13  


 

 

 

8  


 

 

 

10  


170

 

 

7  


190

 

 

6  


 

 

 

13  


360

A 3

 

 

 

12  


180

 

 

4  


 

 

 

11  


 

 

 

9  


 

 

 

10  


 

 

 

11  


180

A 4

 

 

 

14  


40

 

 

6  


 

 

 

12  


 

 

 

13  


0

 

 

7  


80

 

 

14  


120

A 5

150

 

 

9  


 

 

 

12  


 

 

 

14  


 

 

 

15  


 

 

 

8  


 

 

 

13  


150

Потребность

230

220

130

170

190

110

  

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