* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

Оптимизация и линейное программирование в системе Mathcad 683 8.12.7. Задача поиска кратчайшего пути Для представления различных технических объектов, описания процессов и фун кционирования систем часто используются модели, построенные на основе гра фов. К модели в виде графа можно свести и многие практические экономические задачи. К таким проблемам относятся задача поиска кратчайшего пути в заданной транспортной системе, задачи о распределении потока в сети, сетевые модели пла нирования последовательности работ, задача коммивояжера и др. В общем виде задача формулируется следующим образом. Имеется некоторое количество пунктов, соединенных определенным образом одно или двунаправ ленными связями. Каждая связь имеет определенный вес – длину. Требуется най ти кратчайший путь из пункта i в пункт j. При составлении математической модели задачи необходимо учитывать, что маршрут должен быть непрерывным, а каждый промежуточный пункт на пути следования может быть посещен только один раз. Транспортная система в задаче является ориентированным графом – двухполюсной сетью, где N1 – вход, Nn – выход, весовые коэффициенты cij ребер ?ij являются длинами пути между пункта ми i и j, требуется определить кратчайший путь из N1 в Nn. Сопоставим каждому ребру графа булеву переменную, то есть ?ij ? {0, 1}. Если ребро входит в маршрут, то ?ij = 1, иначе ?ij = 0. Тогда целевая функция, которая минимизируется при поис ке кратчайшего пути, имеет вид: Все пункты маршрута можно разделить на начальный, промежуточный и ко нечный. Очевидно, что в каждом промежуточном пункте должно быть по одному входящему и исходящему ребру, а для начального и конечного пунктов может быть только одно исходящее или входящее ребро соответственно. Математически эти ограничения могут быть записаны следующим образом: • для перечисления всех k, входящих в i й пункт маршрута ребер • для перечисления всех j, исходящих из i го пункта ребер Если же i й пункт не входит в кратчайший маршрут, то соответствующая сум ма как для входящих, так и исходящих из вершины графа ребер должна быть рав на нулю. Тогда для любого пункта сети, кроме начального и конечного, должно выполнять условие В начальном пункте