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

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

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

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

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

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

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

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

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

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

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

Группа  ММЭ-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 ;

д) удельные стоимости  могут быть назначены из диапазона 2≤cij≤38 ;

е) значения времени  перевозок могут быть назначены  из диапазона

1≤tij≤35 .

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

Имеется m пунктов производства ( A1 , A2 , ... , Am ) и n пунктов

потребления ( B1 , B2 ,... , Bn ). В пункте Ai производится ai единиц

продукта ( i=11m ), а в пункте B j потребляется b j единиц этого же

продукта ( j=11n ).

Пусть

сij - стоимость доставки из i -го пункта производства в j -ый пункт

потребления (элементы матрицы C );

tij - время, которое требуется для перевозки продукта из i -го пункта

производства  в j -ый пункт потребления (элементы матрицы T );

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

пункта производства в j -ый пункт потребления (элементы матрицы X ).

Необходимо  получить такие значения переменных xij ( i=11m ,

j=11n )(то есть составить такой план перевозок), что выполнялись бы

следующие условия:

Σj

=1

n

xij=ai , i=11m; (1)

Σi

=1

m

xij=b j , j=11n (2)

- и целевая  функция T=max

xij0

tij ,i=11m , j=11n достигала бы минимума.

Условие (1) означает, что из каждого пункта производства должен быть

вывезен весь продукт. Условие (2) означает, что потребности каждого пункта

потребления в  этом продукте должны быть удовлетворены.

Целевая функция T=max

xij0

tij ,i=11m , j=11nmin указывает на то,

что нам необходимо минимизировать время самой длительной ненулевой

перевозки.

Условия (1) и (2) можно объединить и представить  в виде

Σi

=1

m

ai=Σ

j =1

n

b j . (3)

4

Условие (3) называется условием баланса и означает, что  объем

производства  должен быть равен объему потребления. Если данное условие не

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

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

задачу, её приводят к закрытой модели введением фиктивного пункта

производства Am1 с объемом производства am1=Σ

j =1

n

b j−Σ

i=1

m

ai (если

Σi

=1

m

aiΣ

j=1

n

b j ) или фиктивного пункта потребления Bn1 с объемом

потребления bn1=Σ

i=1

m

ai−Σ

j=1

n

b j (если Σ

i =1

m

aiΣ

j =1

n

b j ). В первом случае

транспортные  издержки и временные затраты сm1, j и tm1, j принимают

равными M , где M≫cij и M≫tij ,i=11m, j=11n . Во втором случае

транспортные  издержки и временные затраты сi ,n1 и ti ,n1 также

принимают равными M , где M≫cij и M≫tij ,i=11m, j=11n . В