![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теория двойственности в линейном программировании
Любой задаче математического программирования можно поставить в соответствие так называемую двойственную задачу оптимизации. Между этими задачами обнаруживаются тесные связи, изучение которых составляет предмет теории двойственности. Эта теория тесно связана с теорией условий оптимальности. В данной книге мы рассмотрим теорию двойственности только применительно к задачам линейного программирования. Что касается общей теории двойственности, ее основы обстоятельно изложены в книге [1]. 1. Общая схема построения двойственной задачи. Двойственная задача к задаче линейного программирования также является задачей линейного программирования, причем, как будет видно из определения, ее можно выписать в явном виде с помощью данных исходной задачи.
Из определения 3.8 вытекает важное свойство - симметричность отношения двойственности, т.е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей. Тем самым имеет смысл говорить о паре взаимно двойственных задач. Подчеркнем, что перед тем как строить двойственную задачу, исходную задачу ЛП следует привести к виду (3.20). Правила построения задачи, двойственной по отношению к общей задаче ЛП, наглядно представлены схемой, показанной на рис. 3.2.
Рис. 3.2.
Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной: 1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот. 2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами. 3. Матрица ограничений А транспонируется. 4. Множество индексов переменных, на которые наложено условие неотрицительности в прямой задаче (например, xj ³ 0) определяют номера ограничений, имеющих форму неравенств в двойственной задаче. 5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче, определяют множество индексов переменных в двойственной задаче, на которые налагается ограничение неотрицательности, (иi ³ 0). Особо отметим как выглядят двойственные задачи к ЗЛП в упомянутых ранее частных формах. 1. Двойственной к ЗЛП в основной форме является ЗЛП в канонической форме 2. Двойственной к ЗЛП в канонической форме является ЗЛП в основной форме 2. Теоремы двойственности. В следующей теореме собраны воедино основные факты теории двойственности в линейном программировании, называемые теоремами двойственности. Все они являются прямыми следствиями соответствующих утверждений общей теории двойственности. Теорема 3.6. 1) Для любых точек х Î Х, u Î U справедливо неравенство 2) точки x* Î X u u* Î U являются решениями задач (3.20) и (3.21) соответственно тогда и только тогда, когда справедливо соотношение двойственности
3) задача (3.20) имеет решение тогда и только тогда, когда имеет решение задача (3.21), при этом, в соответствии с (3.22), значения их целевых функций в точках оптимума совпадают; 4) если допустимые множества задач (3.20) и (3.21) непусты то обе они имеют решение; 5) если допустимое множество прямой задачи (3.20) непусто, а задачи (3.21) пусто, то целевая функция прямой задачи неограничена снизу, и наоборот, если допустимое множество двойственной задачи (3.21) непусто, а задачи (3.20) пусто, то целевая функция двойственной задачи неограничена сверху; 6) пусть х* и и* - решения задач (3.20) и (3.21), тогда если j-я компонента точки х* строго положительна (хj > 0), то соответствующее j-е ограничение двойственной задачи (3.21) выполняется как равенство; если же j-я компонента точки х* имеет нулевое значение (хj = 0), то j-е ограничение задачи (3.21) выполняется как неравенство. Полное доказательство утверждений этой теоремы можно найти, например, в книгах [1] или [3]. Утверждение 2) теоремы 3.6 имеет ключевое значение в теории линейного программирования, так как оно дает необходимые и достаточные условия оптимальности, т. е. критерий оптимальности для данного класса задач. Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения прямой задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, допустимое множество которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные.
|