![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример 3.3.
Прямая задача:
Прямая задача с ограничениями в канонической форме: S1 ≥ 0
Двойственная задача: y 1, 2 не ограничены в знаке.
Ограничение у 2 не ограничена в знаке. Если формулировать ДЗ к ИЗ, минуя ее приведение к КЗЛП, то на основании примера 3.3. можно сделать следующие выводы: 1. Если ограничение ИЗ является нестрогим, то соответствующая двойственная переменная ограничена в знаке; 2. Если ограничение ИЗ является строгим, то соответствующая двойственная переменная не ограничена в знаке.
Пример 3.4. Прямая задача: min(5X1 – 2X2); –X1 + X2 ≥ –3; 2X1 + 3X2 ≤ 5; X1, 2 ≥ 0.
Прямая задача с ограничениями в канонической форме: min(5X1 – 2X2 + 0S1 + 0S2); –X1 + X2 – S1 = –3; 2X1 + 3X2 + S2 = 5;
Двойственная задача: max(–3У1 + 5У2); –У1 + 2У2 ≤ 5; У1 + 3У2 ≤ –2; –У1 + 0У2 ≤ 0; 0У1 + У2 ≤ 0. У1, 2 не ограничены в знаке.
Отбрасывая избыточные ограничения, получаем: max(–3У1 + 5У2); –У1 + 2У2 ≤ 5; У1 + 3У2 ≤ –2; У1 ≥ 0, У2 ≤ 0.
Из решения примера 3.4 следует: если в ИЗ ограничение является «неправильным» (в задаче на минимум - ≤, в задаче на максимум - ≥), то соответствующая двойственная переменная будет неположительной (У2 ≤ 0). Пример 3.5. ИЗ: max(5X1 + 6X2); X1 + 2X2 = 5; –X1 + 5X2 ≥ 3; 4X1 + 7X2 ≤ 8. X1 не ограничена в знаке, X2 ≥ 0.
ИЗ в канонической форме: max(5
4
ДЗ: min(5У1 + 3У2 + 8У3); У1 – У2 + 4У3 ≥ 5; –У1 + У2 – 4У3 ≥ –5; 2У1 + 5У2 + 7У3 ≥ 6; 0У1 – У2 + 0У3 ≥ 0; 0У1 + 0У2 + У3 ≥ 0. У1, 2, 3 не ограничены в знаке. Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У2 и У3 можно отбросить. В итоге получаем: min(5У1 + 3У2 + 8У3); У1 – У2 + 4У3 = 5; 2У1 + 5У2 + 7У3 ≥ 6; У1 не ограничена в знаке; У2 ≤ 0, У3 ≥ 0. Из решения примера 3.5 следует: если переменная ИЗ не ограничена в знаке, то соответствующее ограничение ДЗ будет иметь вид строгого равенства. Теорема 3.1. Задача, двойственная к двойственной, совпадает с исходной, т.е. На основании выводов, сделанных при решении примеров 3.1.-3.5., можно формулировать общие правила построения ДЗ для ИЗ, записанной в произвольной форме. 1. Если целевая функция ИЗ максимизируется, то целевая функция ДЗ минимизируется, и наоборот. 2. Если в ИЗ на максимум (минимум) i-е ограничение имеет вид ≥ (≤) («неправильное»), то в ДЗ i-я переменная будет неположительной. 3. Если i-е ограничение ИЗ имеет вид строгого равенства, то i-я переменная ДЗ будет не ограничена в знаке.
|