чином, геометрично задача лінійного програмування являє собою відшукання такої точки багатогранника рішень, координати якої доставляють лінійної функції мінімальне значення, причому допустимими рішеннями служать всі крапки багатогранника рішень.
1.3 Вибір методу реалізації моделі
Кожній вершині з V зіставимо мітку - мінімальне відоме відстань від цієї вершини до a. Алгоритм працює покроково - на кожному кроці він В«відвідуєВ» одну вершину і намагається зменшувати мітки. Робота алгоритму завершується, коли всі вершини відвідані. p align="justify"> Ініціалізація. Мітка самої вершини a покладається рівною 0, мітки інших вершин - нескінченності. Це відображає те, що відстані від a до інших вершин поки невідомі. Всі вершини графа позначаються як невідвідані. p align="justify"> Крок алгоритму. Якщо всі вершини відвідані, алгоритм завершується. В іншому випадку, із ще не відвіданих вершин вибирається вершина u, що має мінімальну позначку. Ми розглядаємо всілякі маршрути, в яких u є передостаннім пунктом. Вершини, в які ведуть ребра з u, назвемо сусідами цієї вершини. Для кожного сусіда вершини u, крім позначених відвідані, розглянемо нову довжину шляху, що дорівнює сумі значень поточної мітки u і довжини ребра, що з'єднує u з цим сусідом. Якщо отримане значення довжини менше значення мітки сусіда, замінимо значення мітки отриманим значенням довжини. Розглянувши всіх сусідів, пометим вершину u як відвідану і повторимо крок алгоритму. p align="justify"> Опис різних задач на графах.
Розвиток теорії графів в основному зобов'язана великому числу всіляких додатків. Мабуть, з усіх математичних об'єктів графи займають одне з перших місць в якості формальних моделей реальних систем. p align="justify"> Графи знайшли застосування практично у всіх галузях наукових знань: фізиці, біології, хімії, математики, історії, лінгвістиці, соціальних науках, техніці і т.п. Найбільшою популярністю теоретико-графові моделі використовуються при дослідженні комунікаційних мереж, систем інформатики, хімічних і генетичних структур, електричних ланцюгів і інших систем мережевої структури. p align="justify"> Далі перерахуємо деякі типові задачі теорії графів і їх програми:
Задача про найкоротшою ланцюга
заміна обладнання
складання розкладу руху транспортних засобів
розміщення пунктів швидкої допомоги
розміщення телефонних станцій
Задача про максимальний потік
аналіз пропускної здатності комунікаційної мережі
організація руху у динамічній мережі
оптимальний підбір інтенсивностей виконання робіт
синтез двополюсної мережі із заданою структурної надійністю
завдання про розподіл робіт
