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

Министерство  транспорта Российской Федерации

Федеральное агентство морского и речного транспорта

ФБОУ ВПО «НГАВТ» 
 
 
 
 
 
 

Курсовая  работа

по дисциплине

«Методы модулирования и оптимизации транспортных процессов» 
 
 
 
 
 

                                                            Выполнил:

               студент

                   группы  

                                                            Проверил:

                                                            преподаватель 
 
 
 

      2011 

    Содержание 

Введение

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

 3

 4

1.1 Исходные данные  4
1.2 Экономическая постановка задачи  5
1.3 Математическая постановка задачи  6
1.4 Алгоритм решения задачи  7
1.5 Расчет   7
2.Оптимальная расстановка разнотипного флота по участкам работы  13
2.1 Исходные данные  13
2.2 Экономическая постановка задачи  14
2.3 Математическая постановка задачи  14
2.4 Алгоритм решения задачи  15
2.5 Расчет   15
Заключение  20
Список  литературы  21
    
 
 
 
 
 
 
 
 

Введение

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

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

    1.1. Исходные данные

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

.           .              .         .          .            .           .           .

Л           К              Е            Д            Г             В              Б          А

1790     1495         1370         1185      1010         785          430           0

Рисунок 1 Схема водного пути 

Таблица 1

Корреспонденция грузовых потоков

пункты род груза масса перевозок, тыс. т расстояние перевозок, км нагрузка по отправлению,
отправления назначения
А Л уголь 16 1790 1,0
Б Л кирпич 22 1360 1,0
Б Е жби 13 940 0,85
Г К трубы 15 485 1,0
К А лесные 19 1495 0,8
К В шпалы 46 710 0,9

  
 
 
 
 
 

    Рис.2 Дислокация грузовых потоков 
 
 

Требуется найти  такое сочетание взаимосвязанных  грузовых потоков, при которых бы обеспечивался минимум порожних тоннаже километров (или пробегов).

1.2. Экономическая постановка задачи.

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

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

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

в)  масса груза, отправляемого от грузополучателя  грузополучателю, не может принимать  отрицательное значение.

1.3. Математическая постановка задачи.

Некоторые математические обозначения:

i- признак прямого направления;

j-признак обратного направления;

Gi-грузопоток прямого направления(тыс.т);

Gj-грузопоток обратного направления (тыс.т);

∑Qp i -тоннаже поток прямого направления (тыс. т-жа);

∑Qp j-тоннаже поток обратного направления (тыс. т-жа);

X ij-количество тонн тоннажа необходимое для полного освоения I-того грузопотока прямого направления, согласованного с j- тым грузопотоком обратного направления (тыс. т-жа);

1ij- размер суммарного порожнего пробега при ij- том сочетании тоннаже потоком (км).

Исходя из этих обозначений, математическая модель задачи запишется следующим образом:

Тоннаже поток прямого направления должен быть освоен полностью:

∑ X ij=∑Qp i (i=1,m)

Тоннаже поток обратного направления должен быть освоен полностью:

X ij=∑Qp i (j=1,n)

Неизвесные должны иметь положительные значения:

X ij0

Критерий оптимальности

      F = min

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

∑Qp i =∑Qp j 

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

      Решение задачи производится методом потенциалов  в следующей последовательности:

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

1.5. Расчет.

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

(ij) = +   68 тыс.тнж

(i) = + тыс.тнж

Т.о. за прямое направление принимается направление вниз, т.к. оно максимальное.

  = тыс.тнж

Полученный тоннажепоток 7 тыс.тнж является порожним.

Б) Формируем  расчетную матрицу

Таблица 2

  А-Л Б-Л Б-Е Г-К порожний  тоннаже поток
16 22 13 15 7
 
К-А
 
19
X11

295

X12

725

X13

555

X14

1010

 
1495
 
К-В
 
46
X21

1080

X22

650

X23

480

X24

225

 
710
 
 

3. Решим матрицу  методом простейших аппроксимаций  Фогеля:

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

Хij = min {Qpi, Qpj}

Х25 = min {51,7}=7

Х24 = min {51,15}= 15

Х11= min {24,16}=16

X12= min {24,22}=8

X22= min {51,22}=14

4. Проверяем на не вырожденность:

L= m+n -1

L= 5+2-1 = 6

Матрица невырожденная. 
 

5. Проверяем  ограничения задачи:

=

16+8+14+15+15+7=16+22+15+15+7=75

    Таблица 3 

    
 
 
А-Л Б-Л Б-Е Г-К Порож.

Тонаже

поток

поля разности по строкам
16 22 15 15 7
295 725 555 300 785
К-А 24 0 16

295

8

725

 
555
 
1010
 
 
1495
260 260 260 170
К-В 51 -75  
1080
14

650

15

480

15

225

7

710

255 255 170 170
поля разности по столбцам 785 75 75 785 785
785 75 75 785 -
785 75 75 - -
- 75 75 - -
 

Считаем значение целевой функции:

F= min

F= 16*295+8*725+650*14+480*15+225*15+710*7=35165 тнжкм

6. Рассчитаем вспомогательные оценочные числа – потенциалы:

для базисных клеток

αi+βj = lij

 принимаем αi = 0, тогда:

β1=295-0=295

β2=725-0=725

α2=650-725= -75

β3=480+75=555

β4=225+75=300

β5=710+75=785

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

по свободным  клеткам

lij=αi+ βj-lij

l13=0+555-555=0

l14= 0+300-1010=-710

l15= 0+785-1485=-700

l21= -75+295-1080=-860

Все значения lij ≤ 0, значит план оптимален

    8.Расчет грузопотока и грузооборота по участкам работ.

    Таблица 4 

№ п/п согласованный тоннажепоток направление перевозок размер тоннажепотока тыс.т-жа нагрузка по отправлению размер грузопотока тыс.т расстояние грузоперевозок км грузооборот млн.ткм
 
1
К-А

А-Л

вниз

вверх

16

16

0,8

1,0

12,8

16

1495

710

19

11,4

2 К-А

Б-Л

Вниз

вверх

8

8

0,8

1,0

6,4

8

1495

710

9,6

10,8

3 К-В

Б-Л

Вниз

вверх

14

14

0,9

1,0

12,6

14

710

1360

8,6

19,0

4 К-В

Б-Е

вниз вверх 15

15

0,9

0,85

13,5

12,75

710

940

9,6

12

5 К-В

Г-К

вниз

вверх

15

15

0,9

1,0

13,5

15

710

485

9,6

7,3

6 К-В

Порож.

вниз

-

7

7

0,9

-

6,3

-

710

-

4,5

-

 

    В результате вычислений образовалось 6 участков работы с грузооборотом: 

    А1 = 30,4 млн.ткм

    А2 = 20,4 млн.ткм

    А3 = 27,9 млн.ткм

    А4 = 21,6 млн.ткм

    А5 = 16,9 млн.ткм

    А6 = 4,5 млн.ткм 
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    Рис 3 Схема согласованных грузопотоков 

    2.Оптимальная  расстановка разнотипного  флота по участкам  работы

    2.1.Исходные данные 

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

    Провозная способность различных  типов флота по участкам работы (млн.ткм) Пij   

      Таблица 5

    тип флота участок работы флота
    1 2 3 4 5 6
    4 7,6 8,4 10,1 10,0 7,9 9,4
    5 6,9 10,0 10,2 9,1 7,8 8,4
    8 9,2 8,0 14,2 13,0 9,6 13,8
 

    Эксплуатационные расходы по одному судну за расчетный период (тыс.рублей) Эij

    Таблица 6

    тип флота участок работы флота
    1 2 3 4 5 6
    4 9,3 9,6 9,9 9,7 9,3 10,1
    5 10,4 11,2 11,0 10,8 11,2 10,4
    8 11,4 10,8 10,4 11,2 10,6 10,0
 

    Требуется найти оптимальный план расстановки трех типов флота по участкам работ.

    Схема участков работы и грузооборот принимается из оптимального плана согласованных тоннажепотоков.

    Наличие каждого  типа флота, принимаемого в расчете, определяется по формулам:

    Ф1=1,1 ( + ), ед

    Ф2=1,1 ( + ), ед

    Ф3=1,1 ( + ), ед

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

    2.2.Экономическая постановка задачи 

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

    1. .Математическая постановка задачи
 

    Некоторые математические обозначения:

    i – признак типа судна или состава;

    j – признак  участка работы флота;

    Фi – наличное количество судов на каждом участке работы;

    Аj – грузооборот, ткм;

    Пij – провозная способность для расчетной клетки матрицы;

    Эij – эксплуатационные расходы или затраты по флоту, руб.;

    Хij – количество судов или составов i – того типа, который можно использовать на j-том участке работы;

    Исходя из этих обозначений, математическая модель задачи запишется следующим образом: 

    1. Условие обязательного  освоения грузооборота на каждом участке  работы:

      = Aij (j= l,m) 
       

    1. Потребное количество флота не должно превышать  его наличие:
 
    1. Неизвестные должны иметь положительные значения:

      Хij

    1. Критерий оптимальности (функция цели)

      F = min 

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

      Решение задачи производится методом потенциалов  в следующей последовательности:

      1.Составляется начальный допустимый план способом эквивалентов.

      2.Рассчитываются вспомогательные оценочные числа – потенциалы.

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

      4.Если план не оптимальный находится звеном с максимальным отклонением от оптимальности.

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

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

    1. .Расчет
 
    1. Рассчитаем  потребность во флоте:
    2. Ф1=1,1 ( + ) = 7,7 ед. Принимаем 8
    3. Ф2=1,1 ( + ) = 5,6 ед. Принимаем 6
    4. Ф3=1,1 ( + ) = 2,29 ед. Принимаем 3
 

              Метод анализа разностей себестоимости.

    Показатель  себестоимости перевозок отражает эффективность использования судна  на разных линиях.

    Рассчитывается  матрица показателей себестоимости  перевозок каждого i-го судна на j-той линии. 

    Sij = , руб/1000 ткм 

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

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

 

 
 
1 2 3 4 5 6 резерв  
30,4 20,4 27,9 21,6 16,9 4,5
1,22 1,12 0,808 0,97 1,177 0,83 0
1 8 0 4,0

1,223

7,6

9,3

 
1,42

8,4

9,6

 
0,98

10,1

9,9

2,16

0,97

10,0

9,7

1,2

1.177

7.9

9.3

 
1.074

9.4

10.1

1.89 

1

0

0.01 0.104 0.197 0.207
2 6 0  
1.507

6.9

10.4

2.04

1.12

10.0

11.2

 
1.078

10.2

11.0

 
1.186

9.1

10.8

 
1.435

7.8

11.2

 
1.238

8.4

10.4

3.96 

1

0

0.066 0.066 0.249 0.249
3 3 -1.45  
1.239

9.2

11.4

 
1.35

8.0

10.8

1.96

0.718

14.2

10.4

 
0.861

13.0

11.2

0.72

1.104

9.6

10.2

0.32

0.724

13.8

10.0

 
 
1

0

0.006 0.137 0.243 0.243
 
 
 
0.016 0.23 0.262 0.109 0.073 0.35
0.016 0.23 - 0.109 0.073 0.35
0.016 0.23 - 0.109 0.073 -
0.016 0.23 - 0.109 0.073 -
Методы модулирования и оптимизации транспортных процессов