Нахождение кратчайшего маршрута на заданной сети произвольного вида одиночного груза

Страницы работы

3 страницы (Word-файл)

Содержание работы

Задача Z2.

Нахождение кратчайшего маршрута на заданной сети произвольного вида одиночного груза.

Вербальная постановка задачи Z2.

Целью задачи Z2 является нахождение кратчайшего маршрута на заданной лесотранспортной сети (Рис.1) груза.

Морфология транспортных сетей задаётся графом связей. Связи описываются матрицей инциденций (представлена ниже). В случае использования матрицы инциденций, запись условий баланса грузопотоков в рассматриваемом пункте сети получается компактной, а также возможна организация условий неразрывности и автоматического сложения потоков в узлах сети.

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

Каждая строка представляет собой уравнение баланса грузопотоков для узла, имя которого находится в первом поле строки.

Рис. 1. Схема связей сети.

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

;

    =    ,   ;

I1 – список источников;

I2 – список транзитных пунктов;

I3 – список точек стока;

,     ;

;

,     ;

,     ;

Решение задачи Z2.

Решение задачи Z2 производится при помощи пакета программ LPX – 88.

Результаты решения приведены ниже.

x21

x32

x35

x42

x43

x45

x51

x62

x63

x76

x78

x89

x84

x95

cost

9

6

4

3

8

6

5

8

7

5

4

5

8

7

1

-1

-1

=-16000

2

1

-1

-1

-1

<=2500

3

1

1

-1

-1

<=3000

4

1

1

1

-1

<=5000

5

-1

-1

1

-1

<=4000

6

1

1

-1

<=2200

7

1

1

<=2700

8

-1

1

1

<=3200

9

-1

1

<=4500

Рис.2. Матрица инциденций графа связей лесотранспортной сети (Рис.1).

На основе подготовленных данных (Рис.2) было выполнено решение задачи Z2 при помощи пакета LPX – 88. Отчёт о полученном решении приведён ниже.

Solution is optimal

Cost 130500

BASIS

x95

x21

x35

x45

x51

S.6

S.7

S.8

S.9

PRIMAL

500

2500

3000

5000

12500

2200

2700

3200

4000

0

DUAL

-12

-3

-3

-1

-7

0

0

0

0

0

Похожие материалы

Информация о работе