су. Поряд з вихідною завданням, розглядається розширена задача, складена на основі вихідної, шляхом введення невід'ємних штучних змінних, а з цільової функції віднімемо суму штучних змінних, помножену на як завгодно велике позитивне число М. У результаті отримаємо так звану М-задачу.
F = cj xj - x n + i {max} (7)
a ij + x n + i = a i0 (i = 1, ..., m) (8) j> = 0 (j = 1, ..., n + m) (9)
В системі (8) змінні x n + i (i = 1, ..., m) утворюють базис, званий штучним. При x 1 = ... = xn = 0 з (8) отримуємо початковий опорний план М-задачі: (0; ...; 0; a 10; ...; a m0). p> Отримання оптимального плану вихідної завдання із залученням М-завдання грунтується на наступних твердженнях:
1. Якщо в оптимальному плані М-задачі всі штучні змінні дорівнюють нулю (х 1; ...; х n, 0, ..., 0), то план (х 1; ...; хn) є оптимальним для вихідної завдання.
2. Якщо в оптимальному плані М-задачі принаймні одна з штучних змінних позитивна при будь-якому великому М, то вихідна задача не має жодного плану.
. Якщо М-задача нерозв'язна, то й вихідна завдання нерозв'язна.
При вирішенні ЗЛП методом штучного базису штучні змінні слід вводити лише в ті рівняння, які не дозволені щодо В«природнихВ» базисних змінних.
Як видно з (7), цільова функція тепер містить два доданки
cj xj і x n + i
тому в симплекс-таблицях для f відводять два рядки (табл.1.3.) і ознака оптимальності перевіряється спочатку по другому рядку, що відповідає сумі
x n + i
Лише після того, як всі елементи цього рядка стануть рівними нулю, ознака оптимальності перевіряють по першій рядку, що відповідає сумі
cj xj
У міру виключення з базису штучних змінних відповідні їм стовпці опускають (не враховують), так як штучні змінні назад в базис не вводяться.
Таблиця 2
БПСП1-x m +1 ................. - X m + s ............. -X nx 1 = x k = x m = b 11 ...................... b 1s ................ b 1, nm b k1 ..................... b ks ................ b k, n-m b m1 ...................... b ms ............... bm, n-mb 10 b k0 b m0Fb 01 ...................... b0s ................. b 0, n-mb 00Мb 01 (M) ................... b0s (M) ............... b 0, n-m (M) b 00 (M)
Глава 2. Практична частина
Задача
Знайти значення змінних ..., при яких функція:
В
лінійний мінлива функція симплекс штучний
приймає максимальне значення, за умови наступних обмежень:
В В В В В
Шукаємо в системі обмежень базисні змінні.
Базисні змінні у вихідній задачі відсутні, це означає, що вихідна задача не містить в собі допустимого базисного р...
