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


Полезное:

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


Категории:

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






Двойственный симплексный метод

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

Теорема 1. Пусть – некоторый базис, , вектор удовлетворяет системе уравнений (7.2), тогда справедливы равенства

. (1)

Доказательство. Воспользуемся разложением

. Для любого имеем

.

Что и требовалось.

 

Заметим, что из теоремы 1 следует, что множество (5) совпадает с .

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

0. Построение исходной симплексной таблицы .

1. Проверка признака оптимальности

. (2)

Если все неравенства (2) выполняются, то – решение задачи, и метод прекращает работу.

2. Выбор . Положим : . (Очевидно, что .)

3. Построение (см. теорему 1).

4. Если множество , то прямая задача не имеет решения в силу пустоты допустимого множества, а двойственная задача не имеет решения в силу неограниченности снизу целевой функции на допустимом множестве. На этом работа метода прекращается.

5. Выбор номера . Положим

.

6. Построение нового базиса , где .

 

7. Пересчет симплексной таблицы по формулам (1) – (4) из параграфа 3.

8. Замена базиса на базис и симплексной таблицы на таблицу . Переход к следующей итерации, к первому ее этапу.

В заключение этого параграфа обсудим вопрос об отыскании исходного двойственно допустимого базиса. Для прямого метода, как мы знаем, исходный базис можно находить при помощи метода искусственного базиса. Для двойственного метода его применять нельзя, так как он разработан специально для отыскания допустимых базисов и соответствующих им опорных планов. Существуют специальные приемы, которые позволяют, решая некоторые вспомогательные задачи линейного программирования, отыскивать двойственно допустимые базисы и соответствующие им псевдопланы. Мы не будем знакомиться с этими приемами, так как двойственный симплексный метод непосредственно к решению задач линейного программирования на практике не применяется. Однако весьма эффективно совместное применение прямого и двойственного симплексного метода для решения задач линейного программирования в рамках разнообразных схем «отсечений». Под «отсечением» мы понимаем такое линейное огра-ничение, вводимое в условия задачи после получения ее решения, которое делает его недопустимым. При этом оптимальный базис становится недопустимым, но остается двойственно допустимым (таким образом, вопрос об его отыскании становится неактуальным). Различные отсечения вводятся, например, в процессе моделирования тех или иных проблем, в методах декомпозиции, при-меняемых при решении задач линейного программирования с большим числом ограничений, при решении вспомогательных задач линейного программирования в методах целочисленного программирования, нелинейного программирования и в некоторых других случаях.

 


<== предыдущая | следующая ==>
Примеры тестовых заданий. 1. Укажите, какие из перечисленных эмбриональных зачатков являются | 

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



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