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

Страницы:
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,   І Є[1,...,и};

Ьі > 0,   і є[1,...,ш}. (1)

Умови такої задачі зручно записувати у вигляді симплекс­ної таблиці

245


і

Б

Сб

Ао

Сі

С2

 

Ст

Ст

 

Сз

 

Сп

 

 

 

 

Аі

А2

 

А

Ат

 

Аз

 

Ап

1

Аг

Сі

Ьі

1

0

 

0

аіт

 

аіз

 

аіп

2

А2

С2

 

0

1

 

0

а2т

 

а2з

 

а2п

 

 

 

 

 

 

 

 

 

 

 

 

 

г

 

Сг

Ьг

0

0

 

0

 

 

аГ8

 

СІГп

 

 

 

 

 

 

 

 

 

 

 

 

 

т

А

Ст

 

0

0

 

1

атт

 

 

 

атп

т + 1

 

 

Аі

А2

 

 

Ат

 

Аз

 

Ап

Над позначеннями векторів Аі, ..., Ап записуються коефі­цієнти цільової функції. У стовпчику Б (базис) записуємо оди­ничні базисні вектори; у стовпчику Сб - коефіцієнти цільової функції, які відповідають векторам базису; у стовпчику Ао -значення базисних змінних; у стовпчиках Аі, ..Ап - коефі­цієнти      матриці умов.

При заповненні + 1)-го рядка користуємося тим, що

= СбАо = СіЬі + С2Ь2 + ... + СтЬт, = СбАу = СіСЦу + С2СІ2І + ... + Стйті,

Аі = /і Сі,   З є{1,...,п}.

Очевидно, що коли цільова функція містить лише вільні змінні, то елементи + 1)-го рядка визначається так: = 0, Аі = 0 для базисних змінних хі, ..хт і Аі = —с3 для вільних змінних Хі+і, ..хп.

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

1. Переглядаємо знаки всіх коефіцієнтів Аі оціночного + 1)-го рядка. Якщо всі Аі > 0, то задача розв'язана: допу­стимий базисний розв'язок Хо = і,..., Ьт, 0,..., 0) оптималь­ний, /тах = /о. Якщо не всі Аі > 0, то переходимо до кроку

2.

2. Серед значень Аі < 0 вибираємо найбільше за абсо­лютною величиною, і стовпчик, який йому відповідає, беремо за провідний. Нехай це буде стовпчик Аз. Якщо в провідно­му стовпчику всі елементи сііз < 0, і Є {1,... ,т}, то задача

246

(І) розв'язку не має, бо цільова функція необмежена, тобто /max = +оо. Якщо ж серед ais, i Є {1,...,m} є додатні, то переходимо до кроку 3.

3. Для кожного елемента ais > 0 провідного стовпчика зна­ходимо відношення —, вибираємо серед них найменше, тобто

знаходимо симплексне відношення Uos = min < — >, і нази-

<iiS>o I ais І

ваємо рядок де воно досягається провідним. Нехай це буде рядок з номером r. Елемент ars який знаходиться на перетині провідного стовпчика і провідного рядка беремо за провідний (розв'язувальний).

4. Заповнюємо наступну симплексну таблицю. Для цього переписуємо провідний рядок поділивши його на провідний елемент у стовпчику Б (базис) замінюємо вектор Ar на As а в стовпчику Сб - cr на cs. Решту коефіцієнтів таблиці знаходи­мо за методом Жордана-Гаусса (за правилом прямокутника). Одержаний новий опорний план перевіряємо на оптимальність тобто переходимо до кроку І.

Зауваження І. Якщо на кроці 2 є декілька найбільших

за абсолютною величиною оцінок Aj  то в базис включають

той вектор, якому відповідає max Cj. Точнішим є таке пра-

j

вило: якщо не виконується умова оптимальності Aj > 0,

j Є {1,... ,n}, то в базис включають той вектор, якому від-

noвiдaє min 9ojAj, де мінімум береться по тих j, для яких j

Aj < 0; якщо ж мінімальних оцінок декілька, то в базис вклю­чають вектор, якому відповідає max Cj.

j

Зауваження 2. Якщо в задачі (І) / min, то умовою

оптимальності плану є Aj < 0, j Є {1,... ,n}. Якщо ж умова

оптимальності не виконується, то в базис включають вектор,

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

є декілька, то включають той вектор, якому відповідає min Cj.

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