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

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

Аз

—4

3

0

 

— 1/2

1

1/4

0

т + 1

 

 

— 12

0

0

0

— 1

—2

1

 

2

4

2/5

 

1

 

0

1/10

4/5

2

Аз

—4

5

1/5

 

0

 

1

3/10

2/5

т + 1

 

 

— 12

0

0

0

—1

—2

У першій симплексній таблиці умова оптимальності не вико­нується, бо Дз =4 > 0. Стовпчик Аз беремо за провідний. Оче­видно, що провідним елементом є 4 . Складемо другу симплексну таблицю, замінивши в базисі вектор А4 на вектор А , і зробивши пе­рерахунок елементів таблиці за методом Жордана-Гаусса. У другій симплексній таблиці умова оптимальності виконується, бо всі Ду < 0, І Є {1,..., 5}. Це означає, що задача розв'язана і XI* = (10; 0; 3; 0; 0), Ітіп = —12. Оскільки нульових більше ніж обмежень задачі, то задача має безліч розв'язків. Для того щоб знайти другий оптималь­ний план, перейдемо до третьої симплексної таблиці, взявши за про­відний стовпчик А2, бо йому відповідає Д2 = 0, але він не є базис-

250ним. Провідний елемент І 5/2 І виберемо за допомогою симплексного відношення. Тоді одержимо, що X* = (0;4;5;0;0). Тому сукупність розв'язків задачі має вигляд:

X* = XXi + (1 - А)Х**,   де 0 < X < 1,

а /шіп = 12.^

4.2. Метод штучного базису (М-метод). У поперед­ньому пункті описано алгоритм розв'язування задачі лінійно­го програмування симплекс-методом. При цьому обов'язковою умовою є наявність в системі обмежень одиничного базису. В багатьох задачах ця умова виконується, а в загальному випад­ку такий базис треба шукати. Нижче ми розглянемо один із методів знаходження одиничного базису, який називають ме­тодом штучного базису або М-методом.

Нехай задано канонічну задачу лінійного програмування:

/ = С\Х\ + С2 Х2 + ... + Сп Хп тах; (2)

(3)

aiixi + ai2X2 + .+ ainXn = bi,

a2lXi + a22X2 + . . . + a2nXn = b2,

ami Xi + am2 X2 + . . . + amnXn = bm;

Xj > 0, j Є {1,...,n}, (4)

bi > 0, i Є {1,...,m}, (5)

де система обмежень не містить одиничного базису.

Для одержання одиничного базису додамо до лівої частини кожної з рівностей в системі обмежень (3) по одній змінній xn+i > 0, i Є {1,..., m}, які назвемо штучними і розглянемо розширену задачу (М-задачу):

/ = cixi + C2X2 +... + CnXn - Mxn+i -... - Mxn+m     max; (б)

(7)

aiixi + ai2X2 +   . + ainXn + Xn+i = bi,

a2lXi + a22X2 +     . + Cl2nXn + Xn+2 = b2,

ami Xi + am2X2 + . . . + amnXn + Xn+m = bm;

251

Х] > 0, і є {1,... + п}, Ьі > 0, і є {1,..., т}.

(8) (9)

При цьому вважаємо, що М - як завгодно велике додатне число.

У задачі (6) - (9) одиничні вектори-стовпчики Ап+і, Ап+2, ..Ап+т утворюють штучний одиничний ба­зис. Йому відповідають початковий опорний план Хо = (0, 0,..., 0; Ьі, ..., Ьт), де нульовими є перші п координат, і зна­чення цільової функції = —МЬі МЬ2 ... МЬт.

Наявність у цільовій функції / коефіцієнтів —М при штуч­них змінних хп+і, і Є {1,..., т}, еквівалентна штрафу за вклю­чення їх в опорний план. Вважають, что число —М за абсолют-

ною величиною значно перевищує решту коефіцієнтів цільової

функції, що дозволяє виводити з базису штучні вектори і вво­дити в базис вектори вихідної задачі (2) - (5).

Оскільки задача (6) - (9) має початковий опорний план, то для її розв'язування можна застосувати симплексний метод.

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