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

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

A3, оскільки йому відповідає max Cj. Провідний рядок, а отже, й про­з

254відний елемент вибираємо за допомогою симплексного відношення: в02 = пііп т} = 1' і = 2' Перейдемо до другої симплексної таб­лиці, взявши за провідний елемент [Т]. У другій симплексній таблиці в + 2)-му рядку всі > 0, і Є {1,..., 6}, а це означає, що умова оптимальності для М-задачі виконується. Оскільки в оптимально­му розв'язку X* = (0;0; 1;0;4;0) цієї задачі х* =4 > 0, то вихідна задача розв'язку не має, бо відсутні допустимі плани.

Зауваження. Якщо в задачі (2) - (5) / тіп, то в розши­реній задачі (6) - (9) цільова функція / = СіХі +Спхп+Мхп + .. . + Мхп+т тіп. При цьому як і раніше М достатньо велике додатне число. Симплексні таблиці з + 2)- рядками перетво­рюємо за тими самими правилами, що й звичайні симплексні таблиці. Однак вектор, що вводиться в базис, відповідає тепер найбільшому додатному елементу А] + 2)-го рядка.

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

/ = —2хі + Х2 хз тіп;

2хі + Х2 + хз = 4, хі 2хз < 5, 2хі + 2х2 > 3;

х0- > 0, і Є {1, 2, 3}.

Л Запишемо спочатку задачу в канонічній формі, ввівши додат­кові (балансуючі) змінні Х4 > 0 і Х5 > 0. Одержимо задачу

/ = —2хі + Х2 — хз тіп;

2хі + Х2 + хз = 4, хі 2хз + Х4 = 5, 2хі + 2x2 — Х5 =3;

хз > 0,і Є {1,..., 5}.

Ця задача еквівалентна даній, але відсутній початковий опорний план. Оскільки в другому обмеженні є базисна змінна Х4, то її можна ввести в шуканий базис. У перше і третє рівняння-обмеження вве­демо штучні змінні Х6 > 0 і Х7 > 0. Тоді одержимо розширену або М-задачу:

/ = 2хі + х2 х3 + Мхб + Мх7 тіп;

255

2хі + Х2 + хз + хе =4,

хі 2хз + Х4 = 5, 2хі + 2x2 Х5 + Х7 = 3;

хі > 0Є {1,..., 7},

і

Б

сб

Ао

—2

1

— 1

0

0

м

м

 

 

 

 

Аі

А2

Аз

А4

А5

Ае

А7

1

Ае

М

4

2

1

1

0

0

1

0

2

 

0

5

1

0

—2

1

0

0

0

3

 

м

3

2

2

0

0

—1

0

1

т +1

 

 

0

2

— 1

1

0

0

0

0

т + 2

 

 

7

4

3

1

0

—1

0

0

1

Ае

м

1

0

— 1

1

0

1

1

 

2

 

0

7/2

0

— 1

—2

1

1/2

0

 

3

Аі

—2

3/2

1

1

0

0

— 1/2

0

 

т +1

 

 

—3

0

—3

1

0

1

0

 

т + 2

 

 

1

0

— 1

1

0

1

0

 

1

Аз

— 1

1

0

— 1

1

0

1

 

 

2

 

0

11/2

0

—3

0

1

5/2

 

 

3

Аі

—2

3/2

1

1

0

0

— 1/2

 

 

т +1

 

 

—4

0

—2

0

0

0

 

 

1

 

0

1

0

— 1

1

0

1

 

 

2

 

0

3

0

— 1/2

—5/2

1

0

 

 

3

Аі

—2

2

1

1/2

1/2

0

0

 

 

т +1

 

 

—4

0

—2

0

0

0

 

 

У першій симплексній таблиці в + 2)-му рядку є декілька додатних Аі, а це означає, що умова оптимальності не виконується. За провідний стовпчик беремо Аі, бо йому відповідає найбільше А3.

Г 4 5 3 1 3

За провідний елемент беремо 2 , оскільки воі = тіп < 2; 1; 2 Г = 2,

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