Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






В. 50 Обоснование решения задачи о коммивояжере методом ветвей и границ (2 теоремы)





Когда решаем задачу предполагаем, что все цены сij≥0.

ui =min cij, j=1…n - в каждой i-ой строке найдем минимальное число и сделаем преобразование. Назначим новые цены.

сij’=сij-ui вычитаем из сij минимальный элемент.

vj=min сij’ j=1…n в каждом столбце ищем минимум

сij”= сij’-vj. Новая матрица называется приведенной матрицей

- константа приведения.

Т1: решение задачи с матрицей сij совпадает с решением задачи с матрицей с.

Док-во: ;

Значение целевой функции для приведенной матрицы отличается от значения целевой функции для исходной матрицы на постоянную величину. Это означает, что оптимальное значение с приведенной матрицы будет отличаться от оптимального значения исходной матрицы на эту же величину. Получается, что оптимальное значение будет доставлять минимум как для одной, так и для другой целевой функции.

Т2: Константа φ является нижней границей решения задачи, т.е оптимальное значение ≥φ (Z*≥φ). Z* - оптимальное значение целевой функции (если мы решаем задачу о коммивояжере, то ответ будет точно не меньше, чем это значение).

Док-во: сij”≥0 В частности последнее неравенство верно и для Z*

Заключение: Таким образом, задачу о коммивояжере можно решить методом ветвей и границ, используя в качестве границы константу приведения.

Date: 2015-12-12; view: 354; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию