Доказ теореми

Анализ умов доповнюючої нежорсткості Слейтера

Якщо в оптимальних планах прямої й двоїстої задач деякі обмеження виконуються як строгі рівності, то вирази в дужках співвідношень (66-68) виконуються як строгі рівності, і відповідно обертаються в 0. Тоді відповідна двоїста змінна у_j для прямої задачі й відповідна пряма змінна х_j для двоїстої задачі можуть мати будь-які значення.

Якщо при оптимальних планах деякі обмеження обертаються в строгі нерівності, як для прямої, так і для двоїстої задач, то відповідні змінні у₁ і х_j повинні обертатися в 0.

Допустимо, що виконуються умови доповнюючої нежорсткості Слейтера. Це означає, що для деякої пари рішень х і у виконуються рівності співвідношень (64) і (65). У свою чергу основна нерівність теорії подвійності буде обертатися в рівність. А це означає, що

. Таким чином, пара рішень і буде оптимальною парою. З 2-ої теореми подвійності виходить: якщо задано пряму й складена стосовно неї двоїста задача, то для одержання пари оптимальних рішень х^* й у^* досить вирішити тільки одну з таких задач, а потім, скориставшись умовами доповнюючої нежорсткості Слейтера, можна оцінити оптимальний план іншої задачі.

Розглянемо приклади

По вихідній задачі скласти двоїсту. Вирішити її графічно, а потім по двоїстої задачі (скор. УДНС) оцінити оптимальний план прямої задачі.

1

2

Отже, таким чином, двоїста задача несумісна (система обмежень выроджена).

1) Для прямої задачі буде виконуватися альтернатива. Цільова форма такої задачі суперечлива (або система обмежень несумісна).

Задача 2

Складемо двоїсту задачу

ОДР – опуклий розімкнутий зверху багатогранник

Відповідно до першої теореми теорії подвійності мають, що пряма задача також буде мати оптимальний план. Причому значення цільової функції оптимального плану буде відповідати 46 од.

Для того, щоб оцінити оптимальний вектор необхідно скласти УДНС (Слейтера) для двоїстої задачі

Складемо УДН Слейтера для прямої задачі

Таким чином, для прямої задачі в оптимальному плані, обмеження виконуються як строгі рівності. Т. ч. при цьому мають

.

Отже, отримано оптимальний план прямої задачі без її розв’язування. Для цього була використана друга теорема теорії подвійності.