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


Полезное:

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


Категории:

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






Основные теоремы двойственности





 

Теоремы двойственности устанавливают взаимосвязь между оптимальными решениями пары двойственных задач. По решению одной из задач можно указать решение двойственной к ней задачи.

Теорема 1. Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причём оптимальные значения целевых функций совпадают: Fmax = Zmin. Если же одна из пары двойственных задач не имеет решения из-за неограниченности целевой функции (Fmax → ∞ или Zmin → - ∞), то и другая не имеет решения ввиду несовместности системы ограничений.

Теорема 2. Допустимые решения Х = и Y = являются оптимальными решениями пары двойственных задач тогда и только тогда, когда выполняются следующие равенства:

;

.

Из теоремы 2 следует, что если при подстановке оптимального решения в систему ограничений i -е ограничение исходной задачи выполняется как строгое неравенство, то i -я координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i -я координата оптимального решения двойственной задачи не равна нулю, то i -е ограничение исходной задачи выполняется как равенство при подстановке в него оптимального решения.

 

Пример 11. Решить ЗЛП:

F (Х) = → max,

.

Решение. Составим для данной ЗЛП двойственную. Так как она будет зависеть от двух переменных, то решим её графическим методом. Затем, используя теоремы двойственности найдём решение исходной задачи.

Исходная ЗЛП является канонической (в системе ограничений только уравнения), поэтому, пользуясь алгоритмом составления несимметричной двойственной задачи, получим следующую пару двойственных задач:

 

Исходная ЗЛП Двойственная ЗЛП
F (Х) = → max, Z (Y) = → min,

 

Решение двойственной задачи графическим методом представлено на рис. 3.

ОДР данной задачи – неограниченная область с вершиной A; на рис. 3 она заштрихована.

Нормальный вектор = (9; 25). Перпендикулярно вектору строим линию уровня = 0. Перемещаем её в направлении вектора до первой точки А (7,2; 2,8), в которой она касается ОДР.

 

А

 

Рис. 3. Решение двойственной задачи графическим методом

Минимум достигается в вершине А. .

По 1-й теореме двойственности .

По 2-й теореме двойственности найдём оптимальное решение (х 1, х 2, х 3) исходной задачи. Для этого подставим найденное оптимальное решение двойственной задачи y 1 =7,2; y 2 = 2,8 в систему ограничений двойственной задачи:

Так как х 1 = 0, то система ограничений исходной задачи принимает вид:

Решение данной системы: х 2 = 12,2; х 3 = 15,4. Следовательно, получено оптимальное решение исходной задачи: (0; 12,2; 15,4). При этом

.

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



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