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

Страницы:
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 

'44

3; З

44

З третьої симплексної таблиці знаходимо, що Y2* =    ; —   . Отже,

оптимальний план двоїстої задачі такий:

Y* = XY? + A)Y2*,   о < А < і,

Y** = (4; о), Y2* = з j , а Fmin = /max = 4. 

5.5. Двоїстий симплексний метод. При застосуванні симплексного методу до розв'язування задачі лінійного про­грамування вимагалося, щоб компоненти вектора обмежень bi, i Є {І,... ,m} були невід'ємними. При цьому оцінки Aj, j Є {І,... ,n} могли бути довільними.

Часто зустрічаються випадки, коли є базис, що задоволь­няє ознаку оптимальності, тобто всі Aj > О, j Є {І,... ,n}, але умова допустимості не виконується, оскільки не всі bi > О, i Є {І,..., m}. Варіант симплексного методу, що застосовуєть­ся при розв'язуванні таких задач, називається двоїстим сим­плексним методом або методом уточнення оцінок.

Розглянемо задачу

/ = CX max;

AX = Ao;

X > О, (ІЗ)

276де матриця А містить одиничний базис і всі оцінки А, > 0, І є {1,... ,п}, але умова невід'ємності не накладається на ком­поненти Ьі, і є {1,..., т}, вектора А. Таку задачу називатиме­мо задачею у двоїстій базисній формі.

Симплексний метод, який застосовуємо до задачі в каноніч­ній базисній формі, приводить до еквівалентних задач із зрос­таючим значенням цільової функції і невід'ємними Ьі, і є {1,..., т}, а це означає, що кожний базисний розв'язок є до­пустимим. Двоїстий симплексний метод, при застосуванні його до задачі у двоїстій базисній формі, приводить до послідовно­сті задач зі спадним значенням цільової функції, невід'ємними оцінками А,, І є {1,..., п}, і значеннями Ьі, і є {1,..., т}, до­вільного знаку. Ітерації продовжуємо до тих пір, поки не буде встановлено, що вихідна задача не має допустимого плану або буде одержана задача з допустимим базисним розв'язком, де всі Ьі > 0, і є {1,..., т}, який є одночасно й оптимальним.

Відносно задачі (13) у двоїстій базисній формі можливі три випадки.

Випадок 1. Усі координати вектора обмежень Ао невід'ємні, Ьі > 0, і є {1,..., т}. Тоді вони визначають не тіль­ки допустимий, але й оптимальний план задачі, оскільки згідно з припущенням усі оцінки А, > 0, І є {1,..., п}.

Випадок 2. Існує рядок і, і є {1,..., т}, такий, що Ьі < 0 і &іі > 0, І є {1,... ,п}. У цьому випадку задача нерозв'язна, бо система обмежень несумісна. Справді, для довільного вектора X = (жі;...; Хп), де х, > 0, І є {1, ...,п}, при а, > 0, І є {1,... ,п}, маємо аі1х1 + аі2х2 + ... + аіпхп > 0, а тому і-те обмеження аі1х1 + аі2х2 + ... + аіпхп = Ьі, де Ьі < 0, не має змісту.

Випадок 3. Існує рядок г є {1,... ,т}, такий, що Ьг < 0 і аг, < 0 принаймні для одного І є {1,... ,п}. Нехай в є {1,... ,п} таке, що агз < 0 і

А*      .  / - а- =  ІГ1Ш '

1^1

Тоді жорданове перетворення з провідним елементом

приводить до еквівалентної задачі, в якій всі оцінки А, > 0,

277

І Є {1,..., п}, і значення цільової функції /' < /, а при Аз ф 0

Опишемо алгоритм двоїстого симплексного методу.

Розглянемо задачу (13) у двоїстій базисній формі. Двоїстий симплексний метод, застосований до цієї задачі, складаєть­ся з наступних кроків, які повторюються до тих пір, поки в ході жорданових перетворень не буде встановлено відповідність чергової еквівалентної задачі випадкам 1) або 2), які описані вище.

1. Перевіряємо знаки компонент вектора обмежень Ао. Як­що всі Ьі > 0, і Є {1,..., т}, то має місце випадок 1. Базисний розв'язок і значення цільової функції, які записані в стовпчи­ку Ао симплексної таблиці, визначають оптимальний розв'язок вихідної задачі. Якщо ж серед Ьі, і Є {1,... ,т}, є від'ємні, то переходимо до кроку 2.

2. Серед від'ємних компонент Ьі вибираємо компоненту Ьг , найбільшу за абсолютною величиною, і рядок г називаємо про­відним.

3. У провідному рядку перевіряємо знаки всіх агз, І Є {1,...,п}. Якщо всі (ігі > 0, І Є {1,...,п}, то маємо випа­док 2. Розв'язування закінчено, оскільки доведено, що задача розв'язку не має. Якщо ж принаймні один із коефіцієнтів аГ], І Є {1,..., п}, від'ємний, то маємо випадок 3, і переходимо до наступного кроку 4.

4. Серед від'ємних коефіцієнтів аГу, І Є {1,... ,п}, провід­ного рядка вибираємо елемент агз, для якого

Страницы:
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лінійна алгебра й аналітична геометрія