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

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

і = 3.

У другій симплексній таблиці в + 2)-му рядку є два однакових

додатних Аз = А5 = 1. За провідний візьмемо стовпчик Аз, бо йому

відповідає тіп сі . Очевидно, що провідним елементом є 1 . з

У третій симплексній таблиці умова оптимальності виконується і з базису виведено штучні вектори. Це означає, що вихідна задача

3

розв'язана: XI* =   —; 0; 1  , /тіп = —4. Оскільки в + 1)-му рядку

256цієї таблиці є чотири А3 = 0, а не три, то задача має альтернативний оптимальний план. Для того щоб знайти його, перейдемо до четвер­тої симплексної таблиці, взявши за провідний стовпчик А5, бо йому відповідає А5 = 0 і він не є базисним, а за провідний елемент 1 . Тоді з четвертої симплексної таблиці одержимо, що X2 = (2;0;0). Отже, сукупність розв'язків задачі має вигляд:

X* = А+ (1 А)^*,   де 0 < А < 1,

X** = ,      = (2;0;0),а /тіп = —4.

Приклад 5. Розв'язати задачу

/ = хі Х2 тіп;

Г       хі Х2 + хз = 1, 1  2хі 3x2 + хз + Х4 = 3;

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

Л Розглянемо розширену задачу, ввівши одну штучну змінну х5 > 0:

/ = х1 х2 + Мх5 тіп;

Г    Хі Х2 + Хз + Х5 = 1,

1  2хі 3x2 + Хз + Х4 = 3; Хз > 0Є {1,..., 5}. Запишемо розв'язування задачі у вигляді симплексних таблиць

і

Б

 

Ао

—1

— 1

0

0

м

 

 

 

 

Аі

А2

Аз

А4

А5

1

А5

м

1

1

— 1

1

0

1

2

А4

0

3

2

—3

1

1

0

т +1

 

 

0

1

1

0

0

0

т + 2

 

 

1

1

— 1

1

0

0

1

Аі

—1

1

1

— 1

1

0

 

2

А4

0

1

0

— 1

— 1

1

 

т +1

 

 

—1

0

2

— 1

0

 

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

257виберемо той, у якому стоїть тіп, тобто А\. За провідний рядок

візьмемо перший, оскільки #01 = тт 1 3 1; 2 1, і = 1, а за провід-

ний елемент |~Т~|.

Перейшовши до другої симплексної таблиці, бачимо, що в (т + 1)-му рядку в стовпчику Л 2 стоїть додатний елемент. Оскільки в цьому стовпчику всі елементи від'ємні, то задача розв'язку не має, бо цільова функція необмежена знизу на множині допустимих планів.►

Отже, алгоритм М-методу такий: 1) складаємо розширену задачу (6) - (9); 2) знаходимо опорний план розширеної зада­чі; 3) за допомогою симплексного методу виключаємо штучні вектори з базису і як результат або знаходимо опорний план вихідної задачі (2) - (5), або встановлюємо її нерозв'язність; 4) використовуючи знайдений опорний план задачі (2) - (5) або знаходимо симплексним методом її оптимальний план, або доводимо її нерозв'язність.

Вправи

1. За допомогою симплексного методу розв'язати задачу ліній­ного програмування:

1) і = 2хі +4x2-хз + Х4 тах; 2хі + Х2 + хз = 8, —хі + 2x2 + Х4 = 6; х3- > 0, і Є {1,..., 4};

І = — х1 + х2 тіп; —2хі + х2 + хз = 2, хі 2х2 + х4 = 2, хі + х2 + хб = 5; і > 0, і Є{1,..., 5};

5) і = 2хі + 2х4 тах; хі + 4хз + 6х4 = 24, х2 + 6хз + 6х4 = 30; хі > 0, і Є {1,..., 4};

і 2 + 5хб тах; і + х2 + хз + хб = 20, —хі 2 + х4 + Зхб = 24, 3хі — х2 12хб + хб = 18; хі > 0,   і є   ||.....6};

4) і

—хб хі

2хі — 3х2 + хз— + 6хб тах; х4 — 2хб = 5, х2 + 2х4 Зхб + хб = 3, хз + 2х4 5хб + 6хб = 5; хі > 0,   і Є{1,..., 6};

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