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

Федеральное агентство по образованию

Пермский  государственный технический университет  
 
 
 
 
 
 
 
 
 
 
 

  КУРСОВАЯ РАБОТА 

по  Методам оптимизации

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

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

Факультета  прикладной математики и механики

Заочного отделения

Специальность:

Математические  методы в экономике

Группа  ММЭ-08з

Кокшаров  Д. М.

Проверила преподаватель:

Третьякова  Н. Г. 
 
 
 
 
 
 
 
 

Пермь, 2012

Содержание

1.Постановка  задачи........................................................................................3

2.Обоснование  математической модели.......................................................4

3.Краткие сведения  о методе решения задачи..............................................5

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

3.2.Метод потенциалов...................................................................................6

3.3.Вариант метода  потенциалов, при дополнительных  условиях,

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

4.Проверка достоверности  полученных результатов..................................9

5.Алгоритм решения  задачи.........................................................................10

6.Листинг фрагмента  программы, реализующего алгоритм решения

задачи.........................................................................................................................11

7.Руководство  пользователя.........................................................................19

7.1.Системные  требования...........................................................................19

7.2.Описание  возможностей.........................................................................19

7.3.Основное  окно программы.....................................................................20

7.4.Главное меню  программы......................................................................20

7.5.Использование.........................................................................................21

7.5.1.Ввод данных  и результаты работы.....................................................21

7.5.2.Использование  инженерного режима.................................................24

8.Решение задачи  курсовой работы на ПЭВМ по  исходным данным

индивидуального варианта.......................................................................................25

9.Список использованной  литературы........................................................28

2

1. Постановка задачи

Имеется m пунктов отправления, в каждом из которых сосредоточено

определенное  количество единиц однородного продукта, предназначенного к

отправке: в  первом пункте имеется a1 единиц этого продукта, во втором - a2

единиц, в i− м пункте ai единиц, и, наконец, в m− м пункте am единиц

продукта. Этот продукт следует доставить в n пунктов назначения

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

продукта, во второй - b2 единиц, в j− й пункт b j единиц, и, наконец, в n− й

пункт bn единиц продукта.

Каждый пункт  отправления соединен с каждым пунктом назначения

некоторым маршрутом (число таких маршрутов m×n ), причем известна

удельная стоимость cij перевозки одной единицы продукта из i− го пункта

отправления в j− й пункт назначения. Общая стоимость перевозки по любому

маршруту пропорциональна  количеству перевозимого продукта. Известно

также время tij перевозки продукта из i− го пункта отправления в j− й пункт

назначения, причем это время не зависит от количества перевозимого груза.

Удельные стоимости cij и время перевозок tij приведены в таблице,

при этом:

1) на пропускные  способности коммуникаций ограничения  не

накладываются;

2) ai и b j - количество условных единиц продукта;

3) в верхних  отделениях клеток таблицы помещены  удельные стоимости

cij в рублях, а в нижних - время перевозок tij в часах.

Таблица 4

Bj 

Ai  B1 B2 B3 B4 B5 B6 B7 B8 ai

A1

96

18

9

16

3

21

3716

4

11

10

15

3 180

A2

16

14

5

17

7

16

20

19

21

8

2

11

7

19

14

3 140

A3

36

22

7

11

10

12

19

23

36

9

18

17

11

10

29 50

A4

21

12

10

19

9

16

13

6

10

12

14

20

4

83

150

A5

15

13

16

17

3

10

11

15

6

23

11

5

18

8

20

23 80

A6

7

33

3

13

12

2

66

18

8

58

8

20

20

23 80

A7

21

21

10

9

16

12

21

22

16

3

15

12

11

5

5

24 70

bj 50 80 10 40 140 110 130 150

Составить план перевозок, при котором весь груз будет доставлен

потребителям в кратчайший срок; определить для этого плана стоимость

перевозок; произвести, если это возможно, дооптимизацию  по критерию

стоимости. Первую часть задачи решить, применяя вариант  метода

3

потенциалов, при  дополнительных условиях, вводимых последовательно в

процесс решения.

Разработанный программный продукт должен обрабатывать числовые

значения из заданного диапазона:

а) количество пунктов отправления может быть или 6, или 7, или 8;

б) количество пунктов отправления может быть или 7, или 8, или 9;

в) количество единиц продукта, предназначенного к отправке может

быть взято  из диапазона 50≤аi≤190 ;

г) количество единиц продукта, которое следует  доставить в пункты

назначения  может быть взято из диапазона 10≤bj≤160 ;