В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 90

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

При цьому уі > 0, оскільки перше обмеження прямої задачі має знак " < уз < 0, бо третє обмеження прямої задачі має знак " > а

267обмеження на знак у2 не накладається через те, що друге обмеження у прямій задачі має знак " = ". ►

5.3. Основні теореми двоїстості. Зв'язок між розв'язками прямої та двоїстої задач встановлюють теореми двоїстості. Розглянемо задачі (1) - (3) і (5) - (7) з економічною інтерпретацією, наведеною в пункті 5.1.

Теорема 1. Для довільних допустимих розв'язків X і У відповідно прямої та двоїстої задач правильна нерівність

/ (X) < Я (У). (11)

Л Оскільки X є допустимим планом задачі (4), то АХ < Ао і X > 0. З того, що У допустимий план задачі (8), випливають нерівності У А > С, У > 0. Тому У AX < УА0, УAX > CX, а отже, CX < УAX < УАо, тобто / (X) < Я ).

Нерівність (11) називається основною нєрівністю теорії двоїстості. Економічний зміст її полягає в тому, що при до­вільному допустимому плані виробництва X загальна вартість всієї продукції не перевищує оцінки всіх ресурсів, яка відпові­дає довільному допустимому плану оцінок У.

Теорема 2. Нехай X * і У * допустимі плани прямої (4) і двоїстої (8) .задач такі, що

/ (X *) = Я *). (12)

Тоді план X* є оптимальним планом прямої задачі, а план У * - оптимальним планом двоїстої задачі.

Л Поряд з планом X* розглянемо довільний допустимий план X прямої задачі (4). Згідно з теоремою 1 і рівністю (12) маємо / (X) < Я (У *) = / (X *), а це означає, що X * - оптималь­ний план прямої задачі.

Аналогічно, якщо розглянути поряд з У * довільний до­пустимий план У двоїстої задачі (8), то матимемо Я (У) > / (X *) = Я (У *), тобто У * є оптимальним планом задачі (7).

З цієї теореми випливає, що коли серед допустимих розв'язків задач (4) і (8) знайдуться вектори X* і У*, які задовольняють умову(12), то вони будуть оптимальними розв'язками відповідних задач. З економічної точки зору це

268означає, що плани виробництва і оцінки ресурсів є оптималь­ними, коли ціна всієї продукції і сумарна оцінка ресурсів одна­кові.

Теорема 3 (перша теорема двoїстостi). Якщо одна з пари взаємно двоїстих задач має оптимальний розв'язок, то має оптимальний план й друга задача, причому для опти­мальних розв'язків значення цільових функцій обох задач збі-

Якщо цільова функція однієї з пари двоїстих задач необме-жжена (для прямої задачі - зверху, а для двоїстої - знизу), то друга задача не має допустимих планів.

Приклад 3. Для задачі

гаються.

f = —2хі 3х2 тіп;

-Ах* + 2х2 > 4, хі + Х2 > 6;

хі > 0, х2 > 0

записати двоїсту й розв'язати обидві задачі. < Двоїста задача до заданої має вигляд

і + 6у2 тах;

—4уі + у2 < —2, і + У2 < —3;

Уі > 0, У2 > 0.

Розв'яжемо обидві задачі графічно.

х2 І

(1)

269

З рис.  І випливає, що пряма задача пє має оптимальпого

розв'язку, бо цільова фупкщя / пеобмежепа зпизу па мпожиш допу­стимих плапів Q.

Двоїста задача пє має допустимих плашв, як видпо з рис. 2, бо мпогокутпик розв'язків є порожпьою мпожипою. ►

Зауваження. Твердження, обернене до другої частини теореми 3, взагалі кажучи, неправильне, тобто з того, що умови вихідної задачі суперечливі, не випливає, що цільова функція двоїстої задачі необмежена. Двоїста задача може так само не мати допустимих планів.

З'ясуємо економічний зміст першої теореми двої­стості. Максимальний прибуток /max підприємство отримує, коли випуск продукції організовано за оптимальним планом X * = (x**; x**;...; x*n). Таку саму сума Fmin = /max воно мо­же мати, реалізувавши ресурси за оптимальними цінами Y* = (y1; у**;...; ). Якщо ж використовуються інші допустимі пла­ни X = X* і Y = Y*, то згідно з основною нерівністю тео­рії двоїстості можна стверджувати, що прибутки від реалізації продукції менші, ніж витрати на її виробництво.

Теорема 4 (друга теорема двоїстості). Допустимл розв язки X* i Y* прямої та двоїстої задач є оптимальними планами вiдповiдних задач тодi й тлльки тодi, коли викону­ються спiввiдношення:

1) (Y*A - C)X* = 0,       2) Y*(A0 - AX*) = 0

Умови   1)   i   2)   називають   умовами доповнюючої

нежорсткості.

З цієї теореми випливає властивість ортогональності розв'язків пари взаємно двоїстих задач лінійного програмуван­ня: якщо ]-та компонента оптимального вектора X* додат­на, то і-те обмеження двоїстої задачі повинно виконуватись як рівність. Аналогічно, якщо додатною є і-та компонента

оптимального вектора Y*, то повинно виконуватись як рлв-

або

1)

2)

0.

тсть i-те обмеження прямої задачi.

270

Приклад 4. Знайти розв'язок прямої задачі

/ = 15жі + 6ж2 + 4ж3 тах;

Г   3жі + 2ж2 жз =9, 1  5жі 2 + 4жз = 25;

ж3 > 0,    З Є{1, 2, 3},

розв'язавши графічно двоїсту до неї.

< Двоїста задача до заданої має вигляд:

Я = 9уі + 25у2 тіп;

і + 5у2 > 15, 2уі 2 > 6, —Уі + 4у2 > 4.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


Похожие статьи

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія