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

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

Між розв'язками задачі (2) - (5) і (6) - (9) існує певний

Теорема. Якщо в оптимальному плані X* = (х\, ... П; 0,..., 0) М-задачі всі штучні змінні дорівнюють нулю, тобто Х*п+І = 0, і Є {1,..., т}), то план X* = (х*, ..., Х*п) є опти­мальним планом вихідної задачі.

Л Очевидно, що плани X* і X* відрізняються т останні­ми координатами, які дорівнюють нулю. Отже, якщо вектор X* задовольняє обмеження (7) - (9), то вектор X* задоволь­няє обмеження (3) - (5), тобто є планом вихідної задачі. При цьому, оскільки відмінні від нуля координати планів X* і X* збігаються, значення цільових функцій /(X*) і /(X*) також збігаються.

Доведемо, що X* - оптимальний план задачі (2) - (5). Нехай це не так. Тоді існує план Xо = (хіо, Х20,..., хпо) вихідної за­дачі такий, що / > /(X*). Тоді для плану розширеної за­дачі Xо = іо2о,... 1Хпо;0,.0), маємо / X) = / —о) > /(X*) = /(X*), тобто / —о) > /(X*). Останнє суперечить то­му, що X* оптимальний план М-задачі.

зв'язок.

252

Отже, якщо, розв'язавши М-задачу, одержимо її оптималь­ний план, у якого всі штучні змінні хП+і = 0, і Є {1,..., т}, то його перші п координат дають оптимальний план задачі (2) -

(5).

Можна довести, що коли:

1) в оптимальному плані М-задачі принаймні одна з штуч­них змінних не дорівнює нулю, то вихідна задача не має до­пустимих планів, тобто її умови-обмеження несумісні;

2) М-задача не має розв'язків, то й вихідна задача неро­зв'язна.

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

Перерахунок симплексних таблиць при переході від одного опорного плану до другого проводять за загальними правила­ми симплексного методу.

Ітераційний процес по (т + 2)-му рядку проводимо до тих пір, поки або: 1) всі штучні вектори виведені з базису; 2) не всі штучні вектори виведені з базису, але + 2)-й рядок не містить більше від'ємних елементів у стовпчиках А , . . .,

Ап+т.

У першому випадку базис відповідає деякому опорному

253плану вихідної задачі (2) - (5) й знаходження її оптимального плану продовжують за (m + 1)-им рядком.

У другому випадку, якщо елемент, який стоїть в (m + 2)-му рядку в стовпчику Aq від'ємний, то вихідна задача розв'язку не має, а якщо він дорівнює нулю, то знайдений опорний план вихідної задачі є виродженим, бо базис містить принаймні один вектор штучного базису.

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

/ = -xi + X2 + xз - X4 max;

j - xi - 6x2 + xз - X4 = 5, 1   3xi - 2x2 + xз - X4 = 1;

Xj > 0, j Є {1,..., 4}.

Оскільки відсутній одиничний базис, то введемо штучні базис­ні змінні X5 > 0 і X6 > 0. Тоді одержимо таку розширену задачу:

/ = - xi + X2 + xз - X4 - MX5 - Mxe max;

j - xi - 6x2 + xз - X4 + X5 = 5, 1   3xi - 2x2 + - X4 + X6 = 1;

Xj > 0,     j Є    |l.....б}.

Розв'язування цієї розширеної задачі, проведемо за допомогою симплексних таблиць

i

Б

сб

Ao

-1

І

І

-1

-M

-M

 

 

 

 

Ai

A2

Aз

A4

A5

Ae

І 2

A5 Ae

-M -M

5 І

-1 3

-б -2

І

ш

-1 -1

І

О

О І

m + 1

 

 

О

І

-1

-1

І

О

О

m + 2

 

 

-2

В

-2

2

О

О

І 2

A5 Aз

-M І

І І

-4 3

-4 -2

О І

О

-1

І 0

-1

І

m + 1

 

 

І

4

-3

О

0

О

І

m + 2

 

 

-4

4

4

О

О

О

2

У першій симплексній таблиці умова оптимальності не вико­нується, бо Аі = —2 < 0 і A3 = —2 < 0. За провідний беремо стовпчик

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