АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

Читайте также:
  1. В линейном программировании.
  2. Вопрос 4: Траектория движения. Криволинейное движение. Нормальное и тангенциальное ускорения при криволинейном движении.
  3. Вывод: Уравнение Бернулли с помощью замены сводится к линейному неоднородному уравнению первого порядка
  4. Вызов линейному управлению
  5. Двойственность в линейном программировании
  6. Двойственность истории и игры.
  7. И технологии программировании
  8. Кинематика материальной точки при криволинейном движении.
  9. Кинематика материальной точки при прямолинейном движении.
  10. О пророчествах, прогнозах и программировании
  11. Относительное равновесие жидкости при равномерном прямолинейном движении. Относительное равновесие при переносном вращательном движении с постоянной угловой скоростью.

 

Имеем две задачи:

 

  СЗЛП  

 

Системы и – пара симметрических двойственных задач. Из одной задачи всегда можно получить другую задачу.

 

Правила построения двойственной задачи:

1. Необходимо согласовать знаки целевой функции и линейных ограничений:

· соответствует

· соответствует

· Если это не так, то помножаем на -1 либо , либо ограничения

2. Каждому линейному неравенству ставится в соответствие неотрицательная переменная. В нашем примере у нас было неравенств, в соответствии которым мы получили ’ки

3. Каждому уравнению ставится в соответствие переменная без ограничения в знаке (произвольная)

4. Каждой неотрицательной переменной ставится в соответствие неравенство

5. Каждой переменной без ограничения в знаке ставится в соответствие уравнение

 

 

Основное неравенство двойственности:

Для любого и любого справедливо .

 

Доказательство:

, ч. т. д.

 

Достаточно условие оптимальности:

Для любых планов и таких, что , то планы и оптимальны в своих задачах.

 

Первая теорема двойственности:

Если одна из пары двойственных задач разрешима, что разрешима и друга, причём .

 

Доказательство:

Пусть задача разрешима. Построим эквивалентную ей задачу : и все неравенства умножим на -1. Т. е. вся левая часть умножается на -1, и вместо будет , а у неравенств знаки изменятся на противоположные. Таким образом, задача стала стандартной. Т. е. задача разрешима. Значит, разрешима двойственная к ней. Двойственная к задаче эквивалентна , т. е. задача разрешима.

 

Определение:

Говорят, что планы и удовлетворяют условиям дополняющей нежёсткости (УДН), если в каждой паре сопряжённых неравенств одно обязательно выполняется как равенство.

 

На данном определении основана вторая теорема двойственности:

Планы и оптимальны тогда и только тогда, когда удовлетворяют условиям дополняющей нежёскости.

 

Доказательство:

В одну сторону: докажем, что выполняются УДН. Пусть планы и – оптимальны. Тогда по первой теореме двойственности . Раз так, то неравенство становится равно 0: .

 

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

 

или

или

 

Т. е. и удовлетворяют условиям дополняющей надёжности.

 

 

12.10.2012 Лекция

 

Продолжим рассмотрение двойственных задач.

Вернёмся к задаче, которую решали первым способом:

 

 

Мы уже нашли оптимальное решение этой задачи:

 

Строим двойственную к ней задачу:

 

   

 

Подставим оптимальное решение задачи в ограничение задачи:

 

Если ограничение выполняется как равенство, то сопряжённое – как неравенство, и наоборот.

 

(по условию УДН)

 

Выберем из получившихся сопряжённых равенства, получим:

 

 

 

Получили ответ: , , , .

 

Таким образом мы продемонстрировали метод решения двойственной задачи. Вернёмся к эконмическому смыслу задачи. Правые части ограничений – 3, 4, 5 – выражены в денежных единицах. Тогда и левые – также в денежных единицах. Коэффициенты при переменных и в ограничениях – это нормы затрат ресурсов каждого вида на единицу продукции одного вида. Поэтому и – это цены ресурсов. Значит, ответ задачи – это план оптимальных цен ресурсов.

 

Правые части ограничений – это доход от реализации продукции конкретного вида, а левые части – это затраты на её производство. В УДН свидетельствуют о том, что производится только так продукция (, ), для которой затраты равны доходу (видим равенства). Если затраты превышают доход (), то такую продукцию производить невыгодно: .

 

Коэффициенты при и в целевой функции – это запасы ресурсов, а сами ’ки, как мы сказали, это цены ресурсов. Таким образом, – это суммарные затраты на приобретение всех ресурсов.

 

 

Задача 1.

Решим прямую задачу вторым способом записи симплекс-таблицы.

 

 

Целевая функция выражены как через базисные, так и через небазисные переменные, что значит, мы сможем решить её только вторым способом записи симплекс-таблицы. Помним, что базисные переменные – это те, которые входят только в одно уравнение и при том с коэффициентом 1. У нас это переменные , , . В целевой функции этих переменных нет, поэтому в столбце у нас нули.

 

Выберем ведущий столбец. Им будет тот, в котором в строке стоит отрицательный элемент. Выберем в данном столбце ведущую строку. Для этого элементы столбца делим на элементы ведущего столбца, но помним о том, что делим только на неотрицательные элементы:

 

 

Отрицательный элемент -12 убираем, получаем

 

 

 

Тогда ведущий элемент будет в строке столбца .

 

Меняем местами базисную переменную и элемент .

 

Теперь начинаем занулять элементы ведущего столбца с помощью обычных преобразований матриц, умножая строки на число и складывая их друг с другом. Нам нужно занулить все элементы кроме ведущего. Ведущий элемент должен принять значение 1. Например, для зануления элемента -12 умножим элементы строки на 4 и сложим со строкой . Чтобы ведущий элемент принял значение 1, строку умножим на 1/3 и запишем результат в новой таблице. Чтобы занулить элемент 1, умножим элементы строки на -1/3 и сложим со строкой .

 

Базисные перемен.   -6        
    -2 -1 -2 -1     -12  
    -2       -5  
    -1 2/3 -1/3 -1 1 2/3 -2/5 -9 1/3 -1/3 1/3    
    -3 2/3 2 2/3   5/8    

 

Проверим таблицу на оптимальность и разрешимость. Столбец не имеет неотрицательных элементов, и находится над отрицательным элементом в строке , значит, задача не имеет решения.

 

 

Задача 2.

Решим прямую задачу вторым способом записи симплекс-таблицы.

 

 

 

Базисные перемен.     -1   -1
-1 -1            
  -3          
-1            
               

 

17.10.2012 Практика

 

Задача 1:

Решить прямую и двойственную задачу

 

 

В нашей задаче только две переменные, поэтому решим графически:

 

Выразим из первого уравнения:

 

Из второго:

 

 

 

Найдём наибольшую точку области :

 

 

 

 

Наша точка:

 

 

Найдём значение целевой функции в этой точке:

 

 

Составим двойственную к ней задачу:

 

 

Решим её:

 

 

Решим как систему:

 

 

 

Нашли точку:

 

 

По теореме двойственности целевая функция в этой задаче имеет то же значение, что и у прямой задачи.

 

 

07.11.2012 Практика + самостоятельная в конце пары

 

Решить задачу:

 

 

Чтобы решить задачу вторым симплекс-методом, нам требуются базисные переменные. Их у нас нет. Добавить их нельзя – в уравнениях стоят уже равенства. Поэтому решить задачу известными симплекс-методами нельзя. Тогда составим двойственную задачу, и на основании её решения решим прямую задачу.

 

Составим двойственную задачу:

 

 

Теперь, когда задача составлена, её легко решить графически. Т. к. и имеют произвольный знак по отношению к 0, координатные оси не задают ограничений, т. е. мы строим нашу область на всей плоскости.

 

Найдём точки, через которые проходит прямая

 

 

Точка минимума функции:

 

 

 

 

Решением будет найденное значение целевой функции в точке . Подставим эту точку в целевую функцию и найдём решение обратной задачи.

 

Теперь мы можем найти решение прямой задачи. Для этого, по второй теореме двойственности, нам необходимо доказать, что найденные планы удовлетворяют УДН, т. е. что в каждой паре сопряжённых неравенств одно обязательно выполняется как равенство. Сопряжённые неравенства – это соответствующие неравенства прямой задачи и обратной задачи. Подставим в условия обратной задачи найденные оптимальные планы:

 

 

 

 

Задача 2:

Определить, является ли вектор оптимальным решением следующей задачи:

 

 

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

 

Составим обратную задачу

 

 

Теперь делаем примерно то же самое, что и в конце предыдущей задачи – подставляем план в сопряжённые равенства. Т. к. план принадлежит прямой задачи, в неё и подставляем:

 

 

Теперь выделим из получившихся только равенства и решим их:

 

 

Сложим первое и третье:

 

 

Теперь подставим в первое:

 

 

 

Самостоятельная работа.

Вариант 1.

 

 

13.11.2012 Лекция

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Поиск по сайту:



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