- •Содержание
- •1 Построение математической модели
- •2 Теоретическая часть
- •2.1 Обзор численных методов решения задач лп
- •2.2 Алгоритм симплекс-метода для задачи на минимум
- •2.3 Двойственный симплекс-метод
- •2.4 Метод Гомори
- •2.4.1 Методы отсечения и их сущность
- •2.4.2 Общий алгоритм метода Гомори
- •3Расчетная часть
- •Заключение
- •Список использованных источников
2.3 Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс - метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис.
Вычислительная схема двойственного симплекс – метода
Шаг 0. Начинаем с симплексной таблицы
|
B |
… | ||
L |
… | |||
… | ||||
… |
… |
………….. | ||
… |
где .
Шаг 1.Проверка на оптимальность. Если, то решение- оптимальное.
Шаг 2.Выбор ведущей строки. Выбираем среди номеровi, для которых, номерkс максимальным по модулю значением
Строка kобъявляется ведущей.
Шаг 3.Проверка на неразрешимость. Если в строкенет отрицательных элементов, то двойственная целевая функция неограниченна и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.
Шаг 4.Выбор ведущего столбцаs. Выбираем среди отрицательных элементов строкиэлемент с номеромs, для которого выполняется равенство
Столбец sобъявляется ведущим, а элемент- ведущим элементом.
Шаг 5.Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).
2.4 Метод Гомори
Метод Гомори для нахождения целочисленного решения относится к большой группе методов, называемых методами отсечений. Эти методы основаны на введении в задачу дополнительных ограничений, позволяющих учесть требование целочисленности. Основная идея методов отсечений состоит в том, что на полученное оптимальное нецелочисленное решение накладывается дополнительное ограничение, которое делает это решение недопустимым, но и не отсекает ни одного целочисленного решения от области допустимых решений.
2.4.1 Методы отсечения и их сущность
Рассмотрим общую задачу целочисленного программированияв постановке:
, назовем эту задачу — задачей.
Задача без учета целочисленности:
, назовем -задачей.
Теорема:
Пусть G- многогранник, -множество его целых точек, R- выпуклая линейная
оболочка множества , тогда:
-целочисленный многогранник;
;
- множество опорных планов задачи содержится в
2.4.2 Общий алгоритм метода Гомори
Правильное отсечение - отсечение, которое удовлетворяют следующим требованиям:
линейно;
отсекает часть области, не содержащей допустимых решений
целочисленной задачи
не отсекает ни одного целочисленного оптимального плана.
Этапы решения:
Решается -задача, соответствующая исходнойзадаче.
Если -задача не имеет решения, т.е. G пуста или неограниченна в положительном направлении возрастания (убывания) F, то устанавливается неразрешимость целочисленной задачи.
Оптимальное решение -задачи проверяется на целочисленность.
Если решение целочисленное, то задача решена.
В противном случае, если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу.
Дополнительное ограничение, которое
линейно;
отсекает часть области, не содержащей допустимых решений целочисленной - задачи;
не отсекает ни одного целочисленного оптимального плана, который входит в систему ограничений..
Шаг 0.Пусть оптимальная таблица имеет вид:
|
b |
… | ||
L |
… | |||
… | ||||
… |
… |
………….. | ||
/ |
… |
Среди элементов – есть дробные числа.
Шаг 1.Среди дробных компоненттаблицы выбираем элементс максимальной дробной частьюи по строкеiсоставляем дополнительное ограничение:
Здесь - целая часть числа(наибольшее целое число, не превышающее число).
Шаг 2.Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к шагу 2.