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

Теорема о дополняющей нежесткости

Читайте также:
  1. S-M-N-теорема, приклади її використання
  2. Б1 1.Системы линейных алгебраических уравнений (СЛУ). Теорема Кроникера-Капелли. Общее решение СЛУ.
  3. Базисный минор и ранг матрицы. Теорема о базисном миноре
  4. Билет 22Понятие евклидова пространства, неравенство Коши-Буняковского. Теорема Кронекера Капелли.
  5. Билет 5 Теорема Безу и следствия из неё. Основная теорема алгебры.
  6. Внешние эффекты (экстерналии). Теорема Коуза.
  7. Внешние эффекты трансакционные издержки. Теорема Коуза
  8. Внешние эффекты, их виды и последствия. Теорема Коуза
  9. Внешние эффекты. Теорема Коуза.
  10. Внешние эффекты. Теорема Коуза.
  11. Вопрос 1 теорема сложения вероятностей
  12. Вопрос 24 Теорема Остроградского-Гаусса для электрического поля в вакууме

Допустимые векторы х и у являются решениями задач (4.4) и (4.5) тогда и только тогда, когда они удовлетворяют условиям дополняющей нежесткости:

 

. (4.11)

 

Это утверждения вытекает из предыдущей теоремы и системы условий (4.10).

Ввиду практической важности последней теоремы для решения задач графическим способом рассмотрим условия (4.8) подробнее. Для этого представим их в скалярной форме:

(4.12)

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

Иными словами, можно сказать, что если в оптимальной точке (прямой задачи) , то , или, что то же самое, , т.е. соответствующее ограничение в оптимальной точке двойственной задачи превращается в равенство (активно). И наоборот, если в оптимальной точке двойственной задачи , т.е. некоторое ограничение не активно, то соответствующая переменная в оптимальной точке прямой задаче равна нулю: .

Аналогичные рассуждения справедливы относительно второго равенства из (4.12) с той лишь разницей, что там все сомножители неотрицательны.

Суммируя сказанное, теорему о дополняющей нежесткости можно сформулировать следующим образом:

1 0 Если в оптимальной точке прямой задачи некоторое ограничение не активно (неравенство выполняется строго), то в оптимальной точке двойственной задачи соответствующая переменная равна нулю.

2 0 Если в прямой задаче некоторая переменная не равна нулю (строго положительна), то в оптимальной точке двойственной задачи соответствующее ограничение обращается в равенство (активно).

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

 

Двойственные задачи допускают следующую экономическую интерпретацию.

Будем называть прямой задачей задачу на максимум вида (4.4), а двойственной – задачу на минимум вида (4.5).


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

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

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