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

Задача Z2.

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

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

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

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

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

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

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

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

;

    =    ,   ;

I₁ – список источников;

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

I₃ – список точек стока;

,     ;

;

,     ;

,     ;

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

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

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

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

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