Пакет программ для решения задач оптимизации распределения дискретных потоков в многопродуктовых сетях большой размерности рабочий м - pismo.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Тематическое планирование уроков технологии Вариант для девочек Разработано... 1 103.4kb.
Лабораторная работа №1 Трансляция, компоновка и отладка программ 1 1 73.45kb.
Предисловие к русскому изданию 15 2204.38kb.
1. Представление о программировании: язык программирования (на примере... 1 62.51kb.
Программа формирования универсальных учебных действий 2 362.6kb.
Трудовая деятельность как объект мотивации План 1 44.19kb.
Лабораторная работа №2 Пакеты прикладных программ 1 267.69kb.
Методические указания по внедрению комплексной бухгалтерской программы... 3 664.47kb.
Перечень необходимых для осуществления воспитательно-образовательного... 1 65.47kb.
Эволюция систем сигнализации в сетях с кк 1 82.28kb.
Мультиэвристический подход к задачам дискретной оптимизации1 5 475.47kb.
Банди Б. Методы оптимизации. Вводный курс 1 105.35kb.
Урок литературы «Война глазами детей» 1 78.68kb.
Пакет программ для решения задач оптимизации распределения дискретных потоков в многопродуктовых - страница №1/1



ПАКЕТ ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ ДИСКРЕТНЫХ ПОТОКОВ В МНОГОПРОДУКТОВЫХ СЕТЯХ БОЛЬШОЙ РАЗМЕРНОСТИ
РАБОЧИЙ МАКЕТ ПАКЕТА ПРОГРАММ
Руководство пользователя



  1. Общие положения

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




    1. Области приложения пакета программ

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

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

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

проектирование и оптимизация развития и функционирования транспортных сетей и сетей передачи данных.

1.2. Возможные пользователи
Государственные или коммерческие организации, компании, фирмы,  заинтересованные в

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


1.3. Среда программирования и требования к конфигурации PC
Пакет программ написан на языке Фортран Compaq Visual Fortran Pro v. 6.1 в операционной среде Windows 98. Для работы пакета программ с задачами оптимизации на сетях, содержащих более 100 узлов ( N>100 ), лучше использовать компьютер с быстродействием не менее 1,5 Ггц и оперативной памятью не менее 256 Мгб.


    1. Сведения об авторском праве

Пакет программ зарегистрирован в Государственном департаменте интеллектуальной собственности Украины при Министерстве образования и науки Украины ( Свидетельство про регистрацию авторского права за № 5978 © Vasyanin V. A. 2001 ).




2. Математическое описание задач
Инфраструктура транспортных сетей и сетей передачи данных имеет пространственный характер, что обуславливает возможность использования эффективного инструмента экономико-математического описания процессов их функционирования и развития.

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

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

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

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


2.1. Задача оптимизации формирования потоков
Содержательная постановка задачи заключается в cледующем. Имеется неориентированная сеть G( N, P ) с множеством узлов N, n = | N | и множеством дуг P, p = | P |, на которой задана целочисленная матрица A = || a i j || n x n единичных потоков грузов или сообщений. Потоки a i j подлежат единовременной передаче из источников i в стоки j , i, j = 1, n в некоторых транспортных блоках унифицированного размера ( контейнерах, различных пленочных упаковках, пакетах сообщений ). Грузы или сообщения, адресованные разным потребителям должны перевозиться или передаваться по сети в общих транспортных блоках с заданной периодичностью. Известны емкость блока

w >> a i j , заданная количеством вмещающихся в него единиц потока и дискрета времени планирования отправления потоков.

Требуется минимизировать функционал

n n


  1. F = f i j ( u i j ,d i j ) + f i ( x i , q i ) + i ( u i ) ,

i j є S i =1 i =1

при ограничениях:


(2) t i j <= T i j , для всех i j є S;


  1. x i <= h i , i = 1, n .


Где n



x i = ( x i j + x j i ) ;

j =1

n

q i = i j , i j если u i j /= 0 ,

j =1 i j если u i j = 0 , i = 1, n ;
n

u i = ( u i j + u j i ) , i = 1, n ;

j =1

S - множество упорядоченных пар индексов потоков, определенное на декартовом произведении n x n;

u i j = ceiling (x i j / w ) - поток транспортных блоков из i в j (первоначально все

x i j = a i j ), ceiling - означает округление числа до большего целого;

d i j - расстояние между узлами i и j;

• f i j , f i , i - в общем случае некоторые нелинейные и невыпуклые функции затрат на передачу и обработку потоков;

t i j , T i j - расчетное и заданное время на передачу единичных потоков из i в j;

h i - пропускная способность i -го узла.
Сформулированная задача относится к классу комбинаторных задач оптимизации и является NP- полной. Поэтому для ее решения в пакете программ реализованы приближенный метод, основанный на схеме последовательного анализа вариантов, и ряд эвристических алгоритмов. Разработка эвристических алгоритмов обоснована тем, что для реальных коммуникационных сетей трудно определить функции f i j , f i , i достаточно адекватно характеризующие затраты на обработку и передачу потоков.

2.2. Задача оптимизации распределения потоков
Содержательная постановка задачи заключается в следующем.

Требуется минимизировать функционал

l n n l

(4) F =f k (( x i j , k ) ,d k ) +  ( ( y i j  ,k + y i j,k )) ,

k =1  є q k i j є S =1 =1 k =1 i j є S

при ограничениях:

n l n l a i j , при i = 

(5) y i j , k - y i j, k = 0 , при i / = j / = 

=1 k =1 =1 k =1 - a i j , при j =  ,
для  = 1, n , i j є S;
n l n n

(6) ( y i j , k + y i j, k ) - ( a j + a j ) < = 2b ,= 1, n ;

=1 k =1 i j є S j =1 j =1

(7) x i j , k < = W k , для всех  є q k , k = 1, l ;



i j є S

n

(8) ( ( y i j  , k + y i j, k) ) t o < = t k , є k , k = 1, l ; 



=1 i j є S

(9) t i j < = T i j , i j є S ;

(10) y i j  , k , x i j , k - целые неотрицательные числа .

В записи (4) - (10) приняты следующие обозначения:

• { m k }, k = 1, l - множество маршрутов транспортных средств или каналов связи, каждый из которых состоит из последовательности узлов и топологических дуг сети G и соединяет начальный и конечный узлы маршрута или канала связи;

• G M ( N , PM ) - маршрутная сеть, где N - множество узлов сети, PM - множество ее ориентированных маршрутных дуг (между любыми узлами i и j сети G M существует маршрутная дуга, если они связаны хотя бы одним маршрутом транспортного средства или каналом связи из { m k });

• A = || a i j || n x n - матрица потоков транспортных блоков ( контейнеров или пакетов сообщений );

• B = || b i || , i = 1, n - вектор пропускных способностей узлов по обработке транзитных потоков;

y i j  , k - поток по дуге p  є PM полученной из маршрута m k ( y i j  , k определяют дуговые потоки на маршрутной сети G M );

x i j , k - поток по топологической дуге p  є P на маршруте m k;

• q k - упорядоченное множество дуг из P , составляющих маршрут m k;

• k - упорядоченное множество узлов из N на маршруте m k;

•  : y i j  , k  { x i j , k } , p  є PM , p  є P , i j є S , k = 1, l , где

 - некоторый оператор, отображающий поток по маршрутной дуге на соответствующее подмножество топологических дуг;

• f k - кусочно-выпуклая функция, определяющая зависимость затрат от количества транспортных блоков, передаваемых по маршруту m k и длины маршрута d k;

•  - нелинейная функция затрат на обработку транспортных блоков в узле ;

• W k - пропускная способность маршрута m k ( грузоподъемность транспортного средства на маршруте m k или пропускная способность канала m k );

• t o - время на перегрузку одного контейнера или перекоммутацию одного пакета сообщений;

• t k - ограничения на время стоянки транспортного средства или занятость канала на маршруте m k в узле ;

t i j , T i j - расчетное и заданное время транспортировки контейнеров или передачи пакетов сообщений из i в j .

Условия (5) обеспечивают неразрывность потока, а (6) - (9) представляют собой соответственно ограничения на пропускные способности узлов, пропускные способности маршрутов, время перегрузки транзитных контейнеров с одного транспортного средства на другое или время на перекоммутацию транзитных пакетов сообщений во всех узлах каждого маршрута.

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

Задачи такого типа являются NP - полными и для их решения неизвестны точные полиномиально ограниченные по трудоемкости алгоритмы. В связи с этим, был предложен метод сведения исходной задачи (4) - (10) к последовательному решению совокупности линейных многомерных задач о ранце вида:


k– l k 

(11) a* i j k x jkmax , k = 1l 

i=1 j = 1

k 



  1. a* i j k x j k < = W k , i = 1,  k - 1 , k = 1, l ,

j =1

k 

(13) ( a** i j k x j k ) t o < = t i k , i = 1,  k - 1 , k = 1, l ,

j =1


со связывающими ограничениями:

l n n


(14) k = a j + a j  ,= 1, n ,

k =1 j =1 j =1


l


  1.   k < = b , = 1, n ,

k =1

l

(16) y k i < = 1,i= 1,  ,



k =1
и ограничениями (9), где:
•  k = | k | - число узлов в маршруте m k;

• k = | {y i j  , k} | и определяет число потоков a i j є s , которые могут быть переданы по маршруту m k;

l

• = | U {y i j  , k } | , где знак U означает объединение множеств {.};



k=1
• A* k = || a* i j k || (k - l ) x k , A** k = || a** i j k || k x k , подматрицы, определенным образом полученные из матрицы A ;

x j k = 1 , если поток j выбран для передачи по маршруту m k и x j k = 0 в противном случае , j = 1, k;

•  k , k , y k i , k = 1, l ,= 1, n , i= 1,  - некоторые линейные функции от переменных x j k , j = 1, k .

Ограничения (14) и (15) соответствуют ограничениям (5) и (6), а условия (16) - запрещают дробление потоков.

Для решения задачи (11) - (16), (9) в пакете программ реализован алгоритм, основанный на эвристических подходах к решению многомерной задачи о ранце и эффективной технике представления структур данных задачи.
3. Описание основных программ пакета и режимов их работы
3.1. Программа оптимизации формирования потоков



      1. Структура программы

Программа оптимизации формирования потоков состоит из главной программы, включающей 4 процедуры-функции и 2 подпрограммы, и 8 внешних подпрограмм, которые скомпилированы вместе и объединены редактором связей в единый загрузочный модуль. Процедуры-функции используются для вычисления затрат на передачу и обработку потоков

f i j , f i , i и могут быть настроены в соответствии с требованиями заказчика.


      1. Входные данные

Все входные данные для программы генерируются датчиком псевдослучайных чисел. При запуске, программа сначала запрашивает, нужно ли дублировать вывод данных в последовательный набор данных OUT1, а затем требует ввода количества узлов в сети – N>=3, количества исходящих из каждого узла сети неориентированных дуг - VAL <=N-1 и минимального и максимального значений - MINVAL,MAXVAL для длин дуг сети в километрах, которые могут принимать целые положительные числа. Далее программа требует ввода через запятую следующих параметров: W,WC, Z3, KF, AT, E, VT, FS, RGM, где

W - емкость транспортного блока ( пакета сообщений, контейнера ) в единицах потока (байтах, килобайтах, мегабайтах или коробках стандартного размера );

WC- максимальная пропускная способность канала (максимальная грузоподъемность транспортного средства ) в транспортных блоках;

Z3 - стоимость одного транспортного блока в каких-либо денежных единицах;

KF - коэффициент прогнозирования потоков, на который будет умножена исходная заданная матрица потоков A = || a i j || n x n ;

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

E - максимально допустимое время на перекоммутацию транзитных пакетов сообщений (перегрузку транзитных контейнеров с одного транспортного средства на другое) в узле сети в секундах или сутках ;

VT - средняя скорость передачи потоков в сети в км/час или км/сек ( для сетей передачи данных VT=25000км/сек );

FS - максимальное число слияний любого потока с другими потоками. Значение этого параметра используется в блоке оптимизации совместно с ограничениями на контрольное время передачи единичных потоков адресатам и ограничивает число дополнительных обработок единичных потоков в транзитных узлах ;

RGM - номер режима вывода данных программы,

RGM=1 - выводятся все сообщения программы, входные и выходные данные ;

RGM=2 - запрещает вывод некоторых данных;

RGM=3 - максимально ограничивает вывод результирующих данных.

Далее в программе генерируется топологическая матрица сети G, которая выводится на экран монитора и на диск в набор данных с именем r.txt.

Формируется матрица маршрутов в соответствии с топологической матрицой сети G

( матрица маршрутов представлена перечнем всех неориентированных дуг сети в виде p1 p2, где p1- начальный узел, p2 - конечный узел, причем номер p2 > p1 ). Матрица маршрутов, их число и длина по количеству узлов в маршруте, выводятся на диск соответственно в наборы sm.txt и lmkm.txt. В демонстрационном варианте программы длины маршрутов ограничены двумя узлами. Реально, маршрут может быть задан перечнем номеров узлов любой длины, например, - 2, 6, 12, 307, 514, 64,32, и т. д.

Генерируются наименования узлов и выводятся в набор t.txt.

Далее осуществляется задание типов узлов в сети G и вывод их на диск в набор данных v.txt. В сети могуть существовать узлы 1,2, и 3-го типов. В узлах 3-го типа запрещена обработка транзитных контейнеров или пакетов сообщений и сортировка транзитных единичных потоков. В узлах 2-го типа запрещена только сортировка транзитных единичных потоков. Исходящие и входящие потоки узлов 2 и 3-го типов обрабатываются в соответствующих им узлах 1 типа.

Узлы 2-го и 3-го типов для демонстрационной программы не вводятся.

Далее задается количество направлений сортировки на внутренние узлы обслуживания для каждого узла в сети G. Эти узлы не представлены в сети G, но число направлений сортировки потоков на них, должно учитываться в функциях затрат на обработку потоков

в сети. Узлы из внутренней зоны обслуживания создают адресные потоки для сети G и должны входить в информационную автоматизированную сеть сбора данных.

На следующем шаге программа просит ввести значения MINVAL и MAXVAL для генерации заданной потоковой матрицы A = || a i j || n x n, вектора ограничений на пропускные способности узлов h i , i = 1, n и матрицы контрольных сроков передачи потоков T= || t i j || n x n . Данные соответственно записываются в наборы a.txt, xz.txt, tz.txt. Следует учитывать, что значения a i j << W, а значения h i должны быть на несколько порядков больше значений a i j . Например, для матрицы A можно указать MINVAL =1 и MAXVAL=50 ( задав в программе 1,50 ), а для вектора h i установить MINVAL =500 и MAXVAL=1000 ( задав в программе 500,1000 ). При этом следует помнить, что для сетей передачи данных величину W лучше устанавливать кратной пропускной способности каналов связи. При решении задачи формирования потоков учитываются ограничения на контрольные сроки передачи потоков. Однако, следует понимать, что такие ограничения могут быть изначально заданы некорректно, так как заранее не известно по каким путям будут переданы потоки. Поэтому, в программе осуществляется проверка соответствия заданных значений tij расчетным trij, полученным при условном распределении всех потоков по кратчайшим путям по ступенчатому критерию – минимум транзитных узлов на пути следования потока, минимум длины пути. При некорректном задании отдельных значений tij , программа просит ввести соответствующую поправку для корректировки этих значений. Поскольку начальное задание контрольных сроков имеет принципиальные объективные трудности, в программе предусматривается расчет времени передачи всех потоков по кратчайшим путям по указанному выше критерию с последующим увеличением полученных значений на вводимую константу ZP. Изменение контрольных сроков передачи потоков на величину ZP (например, кратную AT) означает разрешение дополнительных сортировок на путях следования потока. Поэтому, ZP надо задавать кратным AT, плюс время на транспортировку на более длинных путях. Например, ZP=7.*AT+10. , означает, что допускается до 7 ( включительно ) дополнительных сортировок потока и увеличено время на поиск других, более длинных путей, на 10 единиц.

В любом случае, необходимо помнить, что при решении задачи формирования потоков время передачи потоков рассчитывается предварительно. Фактический расчет может быть выполнен только после решения задачи распределения потоков с учетом провозных возможностей транспортных средств или пропускных способностей каналов связи.

Если задано RGM=1 на экран монитора выводятся исходная потоковая матрица A и A*KF. Далее программа запрашивает, учитывать или не учитывать ограничения на пропускные способности узлов и ограничения на контрольные сроки передачи потоков. При отказе от учета заданных ограничений на контрольные сроки передачи потоков возможен их расчет по кратчайшим путям с последующей корректировкой так, как описано выше. Заданные или расчетные сроки передачи потоков выводятся на экран монитора.

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




      1. Выходные данные

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


AT – заданное время задержки ( обработки ) потоков в узле сети в сутках или секундах;

E - заданное время перегрузки или перекоммутации транзитных транспортных блоков в узле сети в сутках или секундах ;

VT - средняя скорость передачи потоков в км/час или км/сек ;

TMIN - минимальное время передачи потока в сутках или секундах ;

TMAX – максимальное время передачи потока в сутках или секундах ;

TCM - среднее время передачи потока в сутках или секундах ;

SQ2 - дисперсия ;

SQ - среднеквадратическое отклонение.

Для затрат на передачу и обработку потоков, до и после оптимизации, выводятся следующие показатели :
ZP – полные затраты ;

ZTR – транспортные затраты ;

ZSORT – затраты на сортировку ( обработку ) потоков в узлах сети ;

ZPER - затраты на погрузку-выгрузку транспортных блоков в узлах сети ;

ZCONT – затраты на приобретение транспортных блоков ;

SCONT - общее количество транспортных блоков в сети, необходимое для единовременного отправления всех потоков в сети .

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

Наряду с рассчитанными затратами, программа выводит также таблицы обработки потоков в узлах сети, которые содержат следующую информацию:


номер узла;

наименование узла;

тип узла;

объем внутриузлового потока;

общий объем исходящего потока из узла в единицах потока;

общий объем исходящего потока из узла в транспортных блоках;

общий объем входящего потока в узел в единицах потока;

общий объем входящего потока в узел в транспортных блоках;

общий объем транзитного потока в узле в единицах потока;

ограничения на объем транзитного потока в узле в единицах потока;

средний коэффициент загрузки транспортного блока в узле;

количество направлений сортировки потоков в узле на другие узлы, в адрес которых сформированы транспортные блоки;

суммарные и усредненные вышеприведенные показатели для сети в целом.
Кроме того, программа выводит до и после оптимизации величину Tsr – среднее время задержки потоков в сети. Если Tsr=infinit, то максимальной пропускной способности, заданной параметром WC, недостаточно для распределения всех потоков по маршрутам транспортных средств или каналам связи. В этом случае, программа подсказывает до какого уровня может быть увеличено значение WC. При увеличении значения WC, значение Tsr уменьшается, транспортные затраты также уменьшаются ( уменьшается эффект от оптимизации ).
После решения задачи формирования потоков программа выводит сводные результирующие параметры:
DELF - результат оптимизации ( эффект от оптимизации );

KZS – средний коэффициент загрузки транспортного блока в сети;

NSS – среднее количество направлений сортировки из узла в сети;

SX1 – общий объем транзитного потока в узлах сети в единицах потока;

SCONT - общее количество транспортных блоков в сети, необходимое для единовременного отправления всех потоков в сети;

TMIN - минимальное время передачи потока в сети в сутках или секундах;

TMAX - максимальное время передачи потока в сети в сутках или секундах;

TCM - среднее время передачи потока в сети в сутках или секундах;


и значения текущих параметров оптимизации : AT, E, VT, FS, W,WC, KF, RGM.

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

потоковой матрицы в транспортных блоках ( ac.txt );

расчетной матрицы времени передачи потоков ( tr.txt );

справочной матрицы сортировки потоков ( sr.txt ).

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

По желанию проектировщика, при различных значениях параметра RGM, программа может вывести на экран монитора и на печать:

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

исходную заданную матрицу потоков в единичных потоках;

справочную матрицу сортировки потоков;

расчетную матрицу времени передачи потоков;

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


Схема формирования потоков транспортных блоков для каждого узла сети содержит:

ощий исходящий поток;

общий входящий поток;

общий транзитный поток и ограничения на пропускную способность;

средний коэффициент загрузки транспортного блока;

количество направлений сортировки потоков.

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


      1. Режимы работы программы

В программе формирования потоков реализован ряд алгоритмов для метода последовательного анализа вариантов и ряд эвристических алгоритмов. Первая группа алгоритмов используется для решения задачи в случае, когда можно утверждать, что заданные функции затрат на транспортировку ( передачу ) и обработку потоков адекватно отражают стоимостные зависимости реальных процессов от основных изменяемых параметров ( аргументов ). Эвристические алгоритмы ипользуются в случае, когда нет твердой уверенности в адекватности используемых функций затрат, а также в случае, когда функции затрат вообще не заданы ( для реальных коммуникационных сетей трудно определить функции f i j , f i , i достаточно адекватно характеризующие затраты на обработку и передачу потоков ) . Эвристические алгоритмы не используют в своей работе функции затрат, но полученное ими решение задачи все равно оценивается. Для оценки используются встроенные в программу конкретные функции годовых приведенных затрат на обработку и транспортировку ( передачу ) потоков, математический вид которых

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

Для выбора нужной группы алгоритмов, программа запрашивает проектировщика о том, будут ли использоваться функции затрат? Внутри групп, те или иные алгоритмы, реализующие различные стратегии оптимизации, выбираются автоматически в зависимости от заданного числа узлов в сети. Для сетей с числом узлов N>100 для сокращения времени счета задачи автоматически выбираются более быстрые алгоритмы оптимизации, дающие несколько худшие результаты, чем основной, "оптимальный", режим оптимизации. Работа эвристических алгоритмов проверялась на сетях размерностью до 1000 узлов. При этом, самый быстрый алгоритм оптимизации давал отклонение от значения целевого функционала, полученного наилучшим алгоритмом, не более 7%.

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

• максимальное допустимое время обработки (задержки) единичных потоков в узлах сети;

• максимальное допустимое время обработки (задержки) транзитных транспортных блоков в узлах сети (время на перегрузку контейнеров с одного транспортного средства на другое или время на перекоммутацию транзитных пакетов сообщений);

• скорость передачи потоков в сети;

• емкость транспортного блока ( контейнера или пакета сообщений);

• грузоподъемность транспортных средств или пропускную способность каналов связи;

• допустимое число транзитных обработок единичных потоков в узлах сети.

В результате решения задачи проектировщик получает:

• значения целевого функционала (1) до и после оптимизации;

• эффект от оптимизации;

• средний коэффициент загрузки ( наполнения ) транспортного блока;

• среднее количество направлений в узле, в адрес которых формируются транспортные блоки;

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

• количество транспортных блоков ( контейнеров или пакетов сообщений ), подлежащих единовременной передаче по сети за дискрету времени планирования отправления потоков (сутки – для транспортных сетей, секунда – для сетей передачи данных );

• суммарный объем транзитной обработки единичных потоков во всех узлах сети.

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

При решении задачи в режиме проектирования, т. е. когда одно или оба ограничения задачи не учитываются, целесообразно использовать параметр FS, который задает максимальное число слияний любого потока с другими потоками. Значение этого параметра используется в блоке оптимизации совместно с ограничениями на контрольное время передачи единичных потоков адресатам и ограничивает число дополнительных обработок единичных потоков в транзитных узлах. При работе с алгоритмами, использующими функции затрат, можно сразу задавать максимальное значение FS - алгоритм найдет наилучшее решение. В этом можно убедиться, задавая последовательно FS=1,2,3,4,..., пока значение эффекта от оптимизации перестанет расти (т.е. после порогового значения FS, дальнейшее увеличение FS не даст лучшего варианта ).Для эвристических алгоритмов необходимо задавать последовательно FS=1,2,3,4,5,... , пока не будет найден наилучший вариант оптимизации. Следует отметить, что при дальнейшем возрастании FS, также будет достигнуто состояние, когда значение функции цели перестанет изменяться. Однако это значение может быть не наилучшим. Алгоритмы с функциями дают лучшие результаты чем эвристические, но на сетях N>100 очень долго считают.

Для ознакомления с программой и режимами ее работы рекомендуется ограничить число узлов в сети N в пределах 10 – 16, дублировать вывод данных в набор OUT1 для дальнейшего их просмотра и анализа, а также во время выполнения программы открыть настоящую инструкцию в окне редактора WINWORD.




      1. Запуск программы

Запуск программы осуществляется вызовом программы PLFOR_SAV_EVR10 из каталога


D:\DEMONSTRATION SOFTWARE PACKAGE



3.2. Программа оптимизации распределения потоков



      1. Структура программы

Программа оптимизации распределения потоков состоит из главной программы, включающей 3 процедуры-функции и 6 подпрограмм, и 9 внешних подпрограмм, которые скомпилированы вместе и объединены редактором связей в единый загрузочный модуль. Процедуры-функции используются для вычисления затрат на передачу и обработку потоков

f k ,  и могут быть настроены в соответствии с требованиями заказчика.


      1. Входные данные

Все входные данные для программы генерируются датчиком псевдослучайных чисел. При запуске, программа сначала запрашивает, нужно ли дублировать вывод данных в последовательный набор данных OUT2, а затем выводит начальные параметры сети N,LM,KM,AT,E,VT,W,WC. Где LM- количество маршрутов транспортных средств или каналов связи, каждый из которых состоит из последовательности узлов и топологических дуг сети G и соединяет начальный и конечный узлы маршрута или канала связи, а KM- максимальное количество узлов в маршруте. В памяти компьютера хранятся только прямые маршруты. По маршруту I можно двигаться в прямом и обратном направлениях, если в соответствующей ему строке параметров маршрута, значение MASV(I,10) = 0. Если значение MASV(I,10) = 1, то по маршруту I можно двигаться только в прямом направлении.

В демонстрационной программе для всех маршрутов разрешено движение в обоих направлениях.

Далее программа требует ввода через запятую следующих параметров: LMP,RGM,FLREG. Где: LMP-максимальное число новых вводимых маршрутов в процессе решения задачи;

RGM-номер режима вывода данных программы,

RGM=1 - выводятся все сообщения программы, входные и выходные данные ;

RGM=2 - запрещает вывод некоторых данных;

RGM=3 - максимально ограничивает вывод результирующих данных.

FLREG-номер режима ослабления ограничений в процессе решения задачи,

FLREG=1 – разрешается ослабление всех нарушаемых ограничений;

FLREG=2 – запрещается ослабление всех нарушаемых ограничений;

FLREG=3 – запрашивается разрешение на ослабление тех или иных нарушаемых ограничений.

Далее вводится и , если RGM=1, выводится на дисплей и печать исходная топологическая матрица сети G. В программе предусмотрена возможность генерации множества проектируемых маршрутов для распределения всех потоков заданных на сети по критерию-минимум транзитных узлов на пути следования потока, минимум длины пути. Проектировщик может выбрать эту возможность вводом ‘Y’ на соответствующий запрос программы. Если проектируемые маршруты генерируются, то программа выводит новые значения LM и KM. Далее программа может вывести исходные или сгенерированные маршруты на экран монитора и печать, если задано RGM=1.

Каждому маршруту I транспортного средства или каналу связи соответствует строка параметров - MASV(I,10), в которой может быть указано до 10 значений:

дополнительные критерии оптимизации в полях MASV(I,1)- MASV(I,3), (кроме главного, определяемого в выражении (11) );

пропускная способность маршрута в поле MASV(I,4) ( грузоподъемность транспортного средства или пропускная способность канала связи );

стоимость перевозки или передачи потоков по маршруту;

признак направления движения по маршруту, поле MASV(I,10);

приоритет и другие характеристики маршрута.

Программа построена так, что при одинаковых значениях (11) на нескольких маршрутах, потоки будут распределяться на те маршруты, у которых, последовательно, значения MASV(I,1), MASV(I,2) – больше, а значения MASV(I,3) – меньше. В демонстрационном варианте программы такой дополнительный ступенчатый критерий не используется, т. е. у всех маршрутов генерируются одинаковые значения полей MASV(I,1), MASV(I,2), MASV(I,3). Поэтому, для формирования массива MASV(I,10) программа запрашивает только ввода нижней и верхней границ MINVAL, MAXVAL пропускных способностей маршрутов.

Если RGM=1, то выводится массив MASV(I,10) .

Далее программа запрашивает, нужна ли процедура редукции маршрутов для уменьшения используемой оперативной памяти компьютера в процессе решения задачи. Редукция маршрутов может потребоваться тогда, когда число заданных маршрутов на сети очень велико ( например, в случае генерации множества проектируемых маршрутов). Редукция маршрутов может быть однородной или смешанной, а также по дугам или узлам маршрутов. Признаки выполнения однородной или смешанной редукции выбираются из полей типа маршрута в массиве MASV(I,10) – в демонстрационной программе они не используются. При редукции по дугам, редукции подвергаются все машруты, содержащие одинаковые последовательности дуг, а при редукции по узлам - все машруты, содержащие одинаковые последовательности узлов.

Далее вводится ( из набора данных ac.txt ) и , если RGM=1, выводится на дисплей и печать массив потоковой матрицы в транспортных блоках, полученной после решения задачи формирования потоков.

Далее программа запрашивает, нужно ли учитывать ограничения (13) ( в программе массивы: OF(LM,KM) - для движения по маршруту в прямом направлении; OB(LM,KM) - для движения по маршруту в обратном направлении ) на объемы погрузки-выгрузки транспортных блоков на внутренних узлах маршрута для транспортных сетей или объемы коммутируемых пакетов сообщений на внутренних узлах канала связи для сетей передачи данных. Если эти ограничения учитывать не нужно ( в случае проектирования сетей с искомыми значениями таких величин ), массивы OF(I,KM) и OB(I,KM) для каждого маршрута I будут содержать максимальные значения 2*WC для всех узлов маршрута. При необходимости учета ограничений, программа требует ввести только нижнюю границу - MINVAL для значений ограничений, т. к. верхняя граница – MAXVAL определяется значением W k для каждого k-го маршрута. Если нужно запретить обмен грузами или коммутацию пакетов сообщений на всех внутренних узлах маршрутов, необходимо на соответствующий запрос программы ответить ‘Y’. Если RGM=1, то выводятся массивы ограничений OF(LM,KM) и OB(LM,KM).

Далее программа запрашивает, нужно ли учитывать ограничения (15) ( в программе - массив B(N)) на пропускные способности узлов. Если учитывать ограничения нужно, то необходимо ввести ‘Y’ и на следующий запрос программы, ввести нижнюю и верхнюю границы MINVAL,MAXVAL для значений пропускных способностей узлов. В противном случае ( при проектировании сетей с искомыми пропускными способностями узлов ), ограничения на пропускные способности узлов не учитываются ( принимаются равными бесконечности ). Для узлов 3-го типа соответствующие значения B(I)=0. Если RGM=1, то массив ограничений B(N) выводится на дисплей и печать.

На следующем шаге программа запрашивает, нужно ли учитывать ограничения (9) ( в программе - массив TZ(N,N)) на время транспортировки или передачи потоков. Если ограничения нужно учитывать, вводится ( из набора данных tr.txt ) и , если RGM=1, выводится на дисплей и печать расчетный массив времен передачи потоков, полученный после решения задачи формирования потоков. Далее программа выдает запрос, требуется ли увеличить все значения массива TZ(N,N) на некоторую величину ZP, задаваемую проектировщиком. Проектировщик, по желанию, может увеличить или уменьшить все значения TZ(N,N), введя в вещественном формате( например, 0.05 или –0.07 ) нужную поправку. Если RGM=1, то скорректированный массив TZ(N,N) выводится на дисплей и печать. Если ограничения на время транспортировки или передачи потоков учитывать не нужно ( при проектировании сетей с искомыми значениями этих параметров ), проектировщик должен указать ‘N’.

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


      1. Выходные данные

Для заданных и рассчитанных сроков передачи потоков, если задано RGM=1 или RGM=2, программа выводит до оптимизации и после оптимизации следующие показатели:


AT – заданное время задержки ( обработки ) потоков в узле сети в сутках или секундах;

E - заданное время перегрузки или перекоммутации транзитных транспортных блоков в узле сети в сутках или секундах ;

VT - средняя скорость передачи потоков в км/час или км/сек ;

TMIN - минимальное время передачи потока в сутках или секундах ;

TMAX – максимальное время передачи потока в сутках или секундах ;

TCM - среднее время передачи потока в сутках или секундах ;

SQ2 - дисперсия ;

SQ - среднеквадратическое отклонение.

Далее программа выводит таблицу обработки потоков в узлах сети, которая содержит следующую информацию:

номер узла;

наименование узла;

тип узла;

общий объем исходящего потока из узла в транспортных блоках;

общий объем входящего потока в узел в транспортных блоках;

общий объем транзитного потока в узле в транспортных блоках;

ограничения на объем транзитного потока в узле в транспортных блоках;

рабочий парк транспортных блоков ( контейнеров ) в узле для транспортных сетей, необходимый для беcперебойного отправления потоков с заданной периодичностью (для транспортных сетей – 1 сутки );

суммарные вышеприведенные показатели для сети в целом.

Отдельно выводятся: общий рабочий парк транспортных блоков в сети и общие затраты на обработку ( погрузку-выгрузку, коммутацию ) входящих, исходящих и транзитных транспортных блоков в узлах сети.

Если RGM=1, то программа выводит схему сортировки единичных потоков ( схему формирования потоков транспортных блоков ) для каждого узла сети в отредактированном виде. В отличие от схемы сортировки единичных потоков, полученной после решения задачи формирования потоков, в выводимой схеме приведены реальные значения времен транспортировки или передачи всех потоков в сети ( TZR ), а также другие дополнительные расчетные параметры .

Если RGM=1 или RGM=2, то для каждого I-го маршрута выводятся:

значения полей из строки параметров MASV(I,10);

объемы загрузки дуг маршрута в транспортных блоках в прямом и обратном направлениях;

объемы погрузки-выгрузки транспортных блоков или объемы коммутации пакетов сообщений и соответствующие им ограничения в узлах маршрута в прямом и обратном направлениях;

рабочий парк транспортных средств на маршруте ( для транспортных сетей);

наибольший коэффициент загрузки транспортного средства или канала связи;

общий объем потоков в транспортных блоках, перевезенных или переданных по маршруту;

длина маршрута в километрах.


Далее программа выводит обобщенные расчетные показатели сети:

рабочий парк транспортных средств на заданной сети маршрутов ( для транспортных сетей);

рабочий парк транспортных средств на оптимизированной (расчетной ) сети маршрутов

( для транспортных сетей);

средний коэффициент загрузки транспортного средства или канала связи в сети;

средний объем потоков в транспортных блоках, перевезенных или переданных по одному маршруту;

заданное количество маршрутов;

количество маршрутов, введенное в процессе решения задачи;

максимально допустимое количество маршрутов на сети ( величина LM+LMP);

количество загруженных маршрутов;

транспортные затраты;

затраты на обработку ( сортировку ) входящих, исходящих и транзитных единичных потоков в узлах сети ;

затраты на обработку ( погрузку-выгрузку, коммутацию ) входящих, исходящих и транзитных потоков в транспортных блоках в узлах сети;

полные затраты на сети.

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

Для определения эффекта от оптимизации, полученного от последовательного решения задач формирования и распределения потоков для какой либо заданной сети GA , необходимо:

решить задачу формирования потоков для сети GA с определенными заданными параметрами при ограничениях на пропускные способности узлов h i =0 , i = 1, n ( т. е. без оптимизации формирования потоков);

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

параметрами и получить полные затраты на сети;

решить задачу формирования потоков для сети GA с теми же параметрами, но при ограничениях на пропускные способности узлов h i =bi , i = 1, n ( т. е. с оптимизацией формирования потоков);

решить задачу распределения потоков для сети GA с теми же параметрами и получить полные затраты на сети;

получить разницу между предыдущим и последним значением полных затрат на сети (получить эффект от оптимизации).

После решения задачи всегда выводятся также потоки, не распределенные на маршруты из-за нарушения заданных ограничений на всех возможных путях и их общее количество.

Если RGM=1, то программа выводит для каждого маршрута :

потоки, распределенные на маршрут в прямом направлении;

потоки, распределенные на маршрут в обратном направлении.

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


      1. Режимы работы программы

В программе распределения потоков реализован ряд алгоритмов, основанных на эвристических подходах к решению многомерной задачи о ранце и эффективной технике представления структур данных задачи. Как видно из постановки задачи (11) - (16), (9) , при ее решении не используются в явном виде функции затрат. Однако, так же, как и при решении задачи формирования потоков с помощью эвристических алгоритмов, полученная в результате оптимизации схема распределения потоков, оценивается. Для оценки используются встроенные в программу обобщенные функции годовых приведенных затрат на эксплуатацию маршрутов транспортых средств или каналов связи , математический вид которых характерен для большинства реальных транспортных сетей и сетей передачи данных. Для решения задач распределения потоков на реальных сетях в пакете программ предусмотрена возможность задания для каждого исходного и вводимого маршрута транспортного средства или канала связи конкретных функций затрат.

Программа, реализующая решение задачи (11) - (16), (9), может работать в нескольких режимах и предусматривает диалог с проектировщиком. Режимы работы программы соответствуют различным вариантам решения задачи (11)-(16), (9), при которых одни ограничения учитываются, другие ослабляются. Для ослабления ограничений используется значение параметра FLREG.В процессе решения задачи некоторые потоки не могут быть распределены на маршруты на всех возможных путях из-за нарушения заданных ограничений:

на время транспортировки или передачи потоков;

на пропускные способности узлов;

на объемы погрузки-выгрузки транспортных блоков на внутренних узлах маршрута для транспортных сетей или объемы коммутируемых пакетов сообщений на внутренних узлах канала связи для сетей передачи данных;

на пропускные способности маршрутов.

Если FLREG=1, то в процессе решения задачи разрешается ослабление всех нарушаемых ограничений. В этом случае, все потоки заданные на сети будут распределены, а некоторые ограничения – нарушены. При FLREG=2 запрещается ослабление всех нарушаемых ограничений и после решения задачи будут выведены все нераспределенные потоки. Если задано FLREG=3, то в процессе решения задачи программа будет запрашивать у проектировщика разрешение на ослабление тех или иных нарушаемых ограничений. При нарушении ограничений на пропускные способности маршрутов на всех возможных путях, для распределения потока может быть создан новый маршрут (максимальное количество вводимых новых маршрутов определяется значением параметра LMP ). Новый маршрут создается на пути распределения потока с минимальным числом транзитных узлов и минимальным расстоянием.

Если проектировщик выбрал режим генерации множества проектируемых маршрутов, то генерируется ( N*N-N )/2 маршрутов. При этом, все потоки заданные на сети могут быть распределены на проектируемые маршруты без транзитных перегрузок при условии, что не нарушаются ограничения задачи. При проектировании новых маршрутов целесообразно использовать процедуры редукции маршрутов.

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

проектировать расписание движения транспортных средств на существующих маршрутах с изменением условий обмена грузами в узлах сети;

строить новые маршруты транспортных средств при заданных пропускных способностях узлов;

определять новые требования к узлам по переработке потоков грузов при возможной модернизации узлов;

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

Аналогично, для сетей передачи данных возможно:

проектирование новой схемы коммутации каналов связи в узлах сети;

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

определение требуемой производительности телекоммуникационного оборудования в узлах сети;

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

Для ознакомления с программой и режимами ее работы рекомендуется ограничить число узлов в сети N в пределах 10 – 16, дублировать вывод данных в набор OUT2 для дальнейшего их просмотра и анализа, а также во время выполнения программы открыть настоящую инструкцию в окне редактора WINWORD.





      1. Запуск программы

Запуск программы осуществляется вызовом программы DISTR_FLOWS_KNAP1 из каталога D:\DEMONSTRATION SOFTWARE PACKAGE


4. Комплект поставки рабочего макета пакета программ
Рабочий макет пакета программ для решения задач оптимизации распределения дискретных потоков в многопродуктовых сетях большой размерности поставляется на магнитных носителях в папке DEMONSTRATION SOFTWARE PACKAGE. В папке содержатся:

загрузочный модуль программы формирования потоков - PLFOR_SAV_EVR10 (468 Кб );

загрузочный модуль программы распределения потоков - DISTR_FLOWS_KNAP1 (484 Кб);

папка COMDAT с рабочими наборами данных, которые используют основные программы оптимизации при своей работе;



папка The documentation с настоящим руководством пользователя.