Главная  
  • Программы  
  • Методички  
  • Рефераты  
  • Дипломы  
  • Разное  
  • Фото  
  • Контакты  
  • Карта сайта  

  • Я:
    Найти:
    Возраст:
    -

    Пример выполнения лабораторной работы по Теории систем и системному анализу

    HashFlare


    Лабораторная работа №1
    "Нахождение кратчайшего пути".

    Цель работы: "Выработать у студентов практические навыки работы с пакетом networks для решения задач на нахождение кратчайшего пути".

    Задание: "Определить кратчайшие пути, соединяющие узел V1 с остальными узлами сети и их длины".

    Вариант № 13




    Теоретическая часть

          Простым примером такого типа задач является задача выбора наиболее экономичного пути для доставки единицы транспортируемого продукта из узлов множества S, называемых источниками в узлы другого множества Т, называемого стоками.

          Пусть задана сеть G, стоящая из узлов V и множества дуг Е. В которой каждая дуга соответствует упорядоченной паре различных узлов i и j.
    Потоком называется вектор вдоль дуги, удовлетворяющий некоторой совокупности ограничений, определяемых с помощью понятия чистого потока f из узла i.

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

    > with(networks);

    > G:=void(8);

    > E:=[[1,2],[1,3],[1,4],[2,3],[2,5],[2,6],[2,7],[3,4],[3,6],[4,6],[5,6],[5,7],[6,7],[6,8],[7,8]];

    > W:=[10,20,15,38,13,8,10,4,5,13,1,12,15,5,1];

    > addedge(E,weights=W,G);

    > T:=shortpathtree(G,1);






    > draw(T);

    > seq(path([1,i],T),i=2..8);

    Находим расстояние от узла 1 до каждого из узлов дерева Т:
    > vweight(T);

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



    © Copyright 2006-2017. Все права защищены. Сайт бесплатно.