logo search
Metod_kurs

Сетевые модели

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

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

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

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

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

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

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

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

Исходными данными: графическое отображение всех возможных маршрутов, в виде графа. Узлами могут быть автобусные остановки. И обязательно должно быть указано расстояние (затраты) между узлами.