Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Математическая модель задачи Коммивояжера
|
|
Коммивояжер - это бродячий торговец, который должен обойти несколько городов, побывав в каждом ровно 1 раз, причем суммарное пройденное расстояние должно быть min.
Имеется n пунктов, cij- стоимость или время или расстояние для перехода из i пункта в j. Требуется обойти все пункты по 1 разу, и вернутся в исходную точку, иными словами нужно отыскать цикл минимального веса (стоимостью).
Математическая модель:
Напишем целевую функцию:
Нужно 1 раз зайти и выйти: хij –входим из i пункта в j
сумма всех городов, из которых можем выйти
Например, у нас 5 городов. Но тех условий недостаточно. Это не цикл, поэтому нужно добавить ещё 1 условие:
(*), причём i, j =2…n
Пояснение к условию: предположим мы отыскали цикл длиной k<n, тогда просуммируем все неравенства (*) вдоль цикла:
; 
=1, т. к идем вдоль цикла.
Получили противоречивое неравенство, т.к предположили, что в решение оказался цикл длиной меньше, чем n. Условие (*) гарантирует отсутствие такого цикла.
Date: 2015-12-12; view: 815; Нарушение авторских прав