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

Алгоритм решения задач ЦП методами отсечения.

Гомори предложил алгоритмы решения задач ЦП, которые в общем виде можно записать так:

1. Решается задача, соответствующая исходной обычным симплекс-методом.

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

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

Новые дополнительные ограничения должны обладать следующими свойствами:

1. Они должны быть линейны.

2. Должны быть правильными, то есть отсекать область, где находится оптимальное решение и при этом не терять целочисленного решения.

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

Методы последовательного анализа вариантов.

Общая схема таких методов: Среди некоторой совокупности объектов xÎG. Найти то зачение при котором целевая функция f(x) достигает минимума, множество G конечно и в общем случае произвольно.

Пускай исходное множество будет множество G0«Z0=f(0). Далее разобьем всё множество G0 на конечное число не пересекающихся подмножеств: G0: G1,G2,…,Gk:Ç^k_i=1Gi=0; È^k_i=1Gi=G0

Для каждого из подмножеств Gi по некоторому правилу, определяем оценку Zi и строим процедуру выбора подмножеств следующим образом:

Из множества G0 можно перейти в множество G1 и G2. Из них выбираем например такое, где их оценка меньше, пусть это будет Z2. Имеется ввиду, что решение задачи на данном пути более вероятно. Среди совокупности вариантов оптимальным решением x* будет то для которого оценка подмножества не превосходит оценок еще не ветвленых множеств Gv. x*ÎGv f(x*)=Z(Gv)£Z(Gi) È_iGi=Gv

Gv – множество неветвленных множеств. Какова степень близости найденного варианта к оптимальному: Пусть множество G=È^k_i=1Gi и x =minZ(Gi), если x’ является неким допустимым решением, то выполняется следующее неравенство: x£ minf(x)£f(x’). Тогда D=f(x’)- x - является грубой оценкой точности приближения.

Рассматривая данную схему решения необходимо решить следующие вопросы:

1. Как строить подмножество Gi

2. Как проводить оценку.

Ответы на эти вопросы получают из специфики решаемых задач.