3 Алгоритм гомори

3.1 Постановка полностью целочисленной задачи линейного программирования

Минимизировать ф-ю  при ограничениях , где

3.2 Краткое описание алгоритма Гомори

Сначала находим оптимальное решение непрерывной задачи (применяется прямой или двойственный симплекс-метод).

Пусть бащисные переменные выражены через свободные след. образом:

, где G – множество индексов свободных переменных в оптимальном решении непрерывной задачи.

Это может быть записано как

, где [x] – целая часть х, а х⁰ – дробная.

Тогда, если предположить, что l-ая переменная оптимального решения приняла др. значение, то введем новое ограничение

, где

Это будет дополнительная строка в симплекс-таблице.

Далее решаем задачу двойственным симплекс-методом (при выборе отрицательного элемента в столбце свободных членов это будет )

Методы сканирования.Случ поиска м-д Нельдера-Нида.

суть: послед-ный просмотр значений целев. ф-ции в ряде точек, принадлежащих допуст области и наход-е среди них точки, в кот достигается экстремум. Основ достоинство метода при достаточно густом расположении удается найти глобальный экстремум . Недостаток много точек след-но много вычислений .

Модифицированный метод сканирования с большим шагом просмотр р-н разбив- е на мелкие шаги.

Симплекс метод( Нельдера-Нида) . Основная идея заключается пор извест знач-ям целев ф-ии в вершинах выпуклого многогранника , называемого симплексом, опред-ся направ , в кот требуется сделать очередной шаг, чтобы получить наибольшее уменьшение или увеличение целев. ф-ии.

Схема поиска при этом основана на слежении за изменением значений целев ф-ии в вершинах симплекса . Главным здесь яв-ся процесс нахождение вершины нового симплекса , распол. симметрично относительно плоскости , проходящий через одну из сторон исходного симплекса.Выбор направления поиска вершины нов симплекса определяется положением той вешины исходного симплекса, в кот целевая ф-ия имеет наихудшее значение.Нов точка наз-ся дополнением наихудшей точки.

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

Есть модифицированный симплекс м-д , в кот процесс нахождения нов. вешины в сторону симплекса или сжимается или растягивается.

М-д случайного поиска.

Согласно этому методу перебор случайных значений независ. переменных найти оптимум ц. ф. или направление к нему.

- слепрой поиск:

из допустимой области берется случайная точка выполняется в ней значение ф-ии, далее берем след случ. точку, значение в двух точках сравниваем и запоминаем где лучик, далее очередную точку.До тех пор не найдем оптимум.

- метод случайных направлений.

= +h* , k- 0,1,2,3...., - случ. вектор.

Неопределенности операции(обстановки)

(Прир.неопред)

Говоря о прир.неопред. при исслед. операций ,имеется в виду выбор действий в усл-х ,когда целев. ф-я задана ,но не совсем точно(содерж. неопред.парам)

(1)

-неопред. параметр,α G(неопред. модели и иском.данных)

Решая (1)получим \

Принцип наилуч. гарантир. рез-та.

любой : (2.1)

любой α : (2.2)

-гарантир.оценка

- гарант.стратегия

Для наихуд. в-та находим max,но при этом всегда остается возмож. получить лучший рез-т,если в момент реш. задачи известно знач. парам.

, i= (3) – задача многокритер. Оптимизации

Неопред. действия партнеров.

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

max ( ) (4)

у кажд. i-го есть своя цель и ресурсы xi,часть Gi.

н-р,имеются 2 субъекта:

А: (5)

Б: (6)

когда f= -φ – антогонистич.ситуация, (7)

В этом случае выдвиг. гипотеза информир. субъектов:

1) в момент принятия решения А,известно действие субъекта Б.

2)наоборот

3)ни А,ни Б ничего не знают.

1.использ. принципа Парето для принятия компромисс. решения

2. принцип анализ ситуации равновесия. В данной ситуации берется седловая точка,к-я опред:

(8)

причем

(9)

т. - седловая точка

Из всех min вариантов берем max-ый min-м.

Осн. подходы к решению задач многокритериальной оптимизации

1. априорные процедуры – сведение многокритериальных задач к однокритериальным с помощью копромисса и решающих правил.

2. построение множества по паретто альтернатив и выбор из этого множества альтернативы наиболее предпочтительной с т.зр. ЛПР

3. апостериорные процедуры (аксиоматический подход на базе теории полезностей для построения ф-ций предпочтения ЛПР)

4. адаптивный подход – человекомашинные процедуры для выявления предпочтения ЛПР одновременно с исследованием множества альтернатив в интерактивном режиме.

разбираем из них первые 2.