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

ДОКАЗАТЕЛЬСТВО. Воспользуемся леммой 2 и следствием теоремы 1:

Читайте также:
  1. Абсолютное доказательство
  2. Глава 4. Социальное доказательство.
  3. Доказательство
  4. Доказательство
  5. Доказательство
  6. Доказательство
  7. Доказательство
  8. Доказательство
  9. Доказательство
  10. ДОКАЗАТЕЛЬСТВО
  11. ДОКАЗАТЕЛЬСТВО
  12. ДОКАЗАТЕЛЬСТВО

1) Необходимость

Воспользуемся леммой 2 и следствием теоремы 1:

Получим


2) Достаточность

Распишем скалярное произведение


Т.к. правые части совпадают, что левые совпадают. По следствию теоремы 1 получаем требования ¤

ЗАМЕЧАНИЕ

Для канонической задачи и двойственной к ней условия «дополняющей нежесткости» имеют вид:

1)

2)

ПРИМЕР

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


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

Строим симплекс таблицу:


           
         
  -1       -
           
    -1      
             
  -4 -2      
           

 

           
         
  1/3 5/3     33/5
  -1/3 4/3      
  1/3 -1/3     -
             
  4/3 -10/3      
         

 

 

 

       
  3/4 -5/4    
  -1/4 3/4    
  1/4 1/4    
           
  1/2 5/2    

Оптимальное решение прямой задачи .

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


Чтобы построить оптимальное решение двойственной задачи, воспользуемся формулой

дополнительные переменные из таблицы. Количество уравнений равно рангу матрицы

 

2) Иллюстрация применения теоремы 2.

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


Эта задача ЛП с параметром . Применим 2ю теорему двойственности и условия «дополняющей нежесткости».

Напомним формулировку:

оптимальные решения задач

I) II)  

1) Если

2) Если

3) Если

4) Если

Нам нужны условия 1 и 2:

1) Проверим, что – допустимое решение задачи. Легко убедится, что так оно и сеть.

2) Выписать систему линейных уравнение из условия «дополняющей нежесткости» относительно неизвестной двойственной переменной .

Анализируем координаты вектора :

Нам нужна двойственная задача. Строим ее:


Если координата = 0, то условий нежесткости для случая нет.

Подставим , в условия ограничений:

 

Получаем


Если построенная система окажется противоречива, исследование завершается и делаем вывод, что – неоптимальное решение.

Если ли среди найденый решений на шаге 2 допустиое решение двойственной задачи (подставить решение в условия двойственной)

Задача решена.

Это так называемый анализ чувствительности

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

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



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