ЛАБОРАТОРНАЯ РАБОТА № 6 Сетевые модели
В некоторых практических ситуациях для наглядности удобно использовать схемы, которые называют графами. Граф состоит с однородных объектов, которые называются узлами,
и линий, которые называются дугами и связывают пары узлов между собой. Эти объекты – узлы и дуги – могут исполнять только роль схемы, определяя связи, в других случаях они имеют определенные характерные оценки, которые соответствуют поставленной задаче. В ориентированном графе эти линии имеют вид стрелок, указывая на ориентацию между узлами. Подобная сетевая схема используется для наглядного представления транспортной задачи с узлами-поставщиками и узлами-потребите-лями, где направленные дуги в виде стрелок определяют возможные маршруты перевозок (потоков) (рис. 6.1).
Рис. 6.1
Ключевое слово «поток» определило в математическом программировании класс моделей потокового (сетевого) программирования.
Формирование этого направления приходится на 60-е годы ХХ в. и определено публикацией фундаментальной работы Дж. Данцига, Л. Форда и Д. Фалкерсона.
Оказалось, что если задачу подать в графической форме в виде сетки, тогда можно с помощью довольно эффективных потоковых алгоритмов получить ее оптимальное решение на основе математических графов с меньшими затратами компьютерных ресурсов.
Ориентированный граф называют сеткой, где определяют:
внешний узел-источник, который имеет только выходящие дуги;
внешний узел-сток, который имеет только входящие дуги;
все остальные узлы – внутренние (промежуточные, транзитные), у которых есть входящие и выходящие дуги и которые связывают узлы.
Для дуги могут быть характерны: пропускная способность канала, расстояние между парой узлов, стоимость перевозок, вероятность прохождения сигнала по цепи, количество необходимых ресурсов для исполнения операции и т.д. Поскольку задачи на графах относят к оптимизационным задачам, они составляют самостоятельный и очень распространенный класс сетевых моделей оптимизации. Дуга со стрелкой и определенным значением соответствующего параметра определяет универсальное понятие – поток (flow), что движется с начального узла в конченый. Объектом потоков в практических задачах выступают жидкость, груз, сигналы связи, темп исполнения операций из залученных ресурсов, энергия, газ, пассажиры, капитал, транспортные средства и тому подобное.
Способы представления сетки в Еxcel следующие.
Матрица смежности – квадратная матрица связи типа «каждый-с-каждым» размером n х n, где n – число узлов. Элемент такой матрицы принимает не нулевое значение (расстояние, затраты), если существует дуга между узлами, или 0 в противоположном случае. Эта матрица полностью определяет структуру сетки.
Для анализа и расчётов используется аппарат матричной и линейной алгебры. Этот способ используется при решении классической транспортной задачи, задачи коммивояжера, то есть там, где количество дуг значительно превышает количество узлов. Например, для описания графа, который состоит из 15 узлов и, соответственно, 225 дуг, лучше применить матрицу для компактной записи данных.
Вектор координат и характеристик коэффициентов дуг – таблица с тремя и больше столбцами (начало дуги, конец дуги, одна и больше характеристик дуги, например, ее длина) и строк. Этот способ применяют там, где число узлов и дуг приблизительно одинаковое. Например, в сетевой транспортной задаче с промежуточными пунктами лучше и более естественно использовать векторную форму представления транспортной сети, чем матричную.
Для сетевых моделей оптимизации фундаментальным является принцип сохранения потока в любом узле (экономисты называют это балансом), а именно сумма потоков на выходе узла равна сумме потоков на его входе плюс потенциал узла: (+) – предложение; (-) – спрос).
Ниже рассмотрен практический пример задачи, которая относится к сетевой модели.
|
