Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Решение задачи о кратчайшем пути в графе на основе ЛП

Читайте также:
  1. D) РЕКОНСТРУКЦИЯ И ИНТЕГРАЦИЯ КАК ЗАДАЧИ ГЕРМЕНЕВТИКИ
  2. I. ЦЕЛИ И ЗАДАЧИ
  3. I. Цель и задачи
  4. I. Цель и задачи Комплекса
  5. II Цель, задачи, функции и принципы портфолио.
  6. II. Цели и задачи
  7. II. Цели и задачи организации учебно-воспитательной работы кадетского класса

Модель ЛП для задачи о кратчайшем пути строится следующим образом: пусть Хij – наличие пути из i-ой вершины в j–ю. Если Хij=1, то путь есть, если Хij=0, то пути нет. Dij-стоимость перемещения из i-ой вершины в j–ю (расстояние). Тогда движение по всем путям должно быть минимально, т.е.

N N

Z= ∑ ∑ dijXij→min.

I=1 j=1

Из исходного пункта в любой другой везем продукт 1, а сумма всех входящих поездок равна сумме всех выходящих. Для конечной вершины из всех вершин должна придти 1.

Исходный граф имеет следующий вид

 

Х2 Система ограничений

Х1 - Х2=0

Х1 d=7 Х2 + Х3=1

К Х4 – Х3=0

D=5 Х1 + Х4=1

Х3

Н d=3 Целевая функция

F=5Х1+7Х2+3Х3+10Х4

Х4 d=10 Хj≥0, Хi-целочис-

ленные

 

Тогда в программе Excel получим следующее решение данной задачи, которое полностью совпадает с решением задачи методом Форда. Критерием будет являться целевая функция.

 

 


Дата добавления: 2015-08-21; просмотров: 84 | Нарушение авторских прав


Читайте в этой же книге: Принятие решения о работоспособности объекта | Получение уравнения гиперплоскости, проходящей через n заданных точек. | Алгоритм Прима определение минимального остовного дерева(случай многоуровнего графа) | Расчет сетевого графа на основе линейного программирования | Минимизация булевых функций в классе КНФ (Конъюнктивная нормальная форма). | Конечный автомат | Алгоритм венгерского метода | Решение задачи коммивояжера | Алгоритм метода ветвей и границ |
<== предыдущая страница | следующая страница ==>
Сетевой график| Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательности ребер или дуг

mybiblioteka.su - 2015-2024 год. (0.005 сек.)