ивають базисними (б.п.), інші n - m змінних називають вільними.
Щоб отримати найпростіше приватне рішення системи необхідно вільні змінні прирівняти нулю, враховуючи при цьому неотрицательность всіх змінних.
Припустимим базисним рішенням (ДБР) є таке, при якому всі змінні невід'ємні. В іншому випадку базисне рішення неприпустимо.
Приватна допустиме базисне рішення, з якого починають рішення, називають початковим допустимим базисним рішенням (НДБР).
Щоб знайти НДБР, зручно ЗЛП записати в канонічному вигляді.
Канонічний вигляд ЗЛП - це такий стандартний вид, в якому в кожному i-му рівнянні знайдеться така змінна х I , що коефіцієнт перед нею в даному рівнянні дорівнює +1, а в інших рівняннях і у виразі цільової функції ці коефіцієнти дорівнюють нулю. Якщо при цьому всі b, то говорять про допустимому канонічному вигляді, в іншому випадку - про неприпустимий. p> Наприклад.
Випадок. Вихідна завдання ЗЛП містить всі обмеження зі знаком. br/>
,,, (x) =.
Стандартна форма ЗЛП є одночасно і канонічним припустимим видом.
,,,
, - додаткові, що врівноважують змінні
(x) = -.
При цьому хj = 0, - вільні змінні, хn + I = bi, - базисні змінні - НДБР.
Випадок. Обмеження вихідної ЗЛП містять нерівності різних знаків і рівняння. br/>
,,,
,
,,, (x) =.
Стандартна форма ЗЛП не співпадає з канонічним виглядом.
,,
,,
,,
, - додаткові, що врівноважують змінні. (x) = -.
Щоб побудувати канонічний вигляд і отримати НДБР використовують метод штучного базису. У кожне рівняння, що не містить змінну, що створює канонічний вигляд, вводять штучну неотрицательную змінну. br/>
,,
,,,
,,, (x) = -.
Нові штучні змінні створюють канонічний вигляд. Однак, вводячи в обмеження-рівності штучну змінну, змінюють вихідні умови. p> Щоб перетворена завдання відповідала вихідної, необхідно, щоб в остаточному рішенні штучні змінні дорівнювали нулю. Цього можна досягти, якщо допоміжна цільова функція, що дорівнює сумі штучних змінних, буде дорівнює нулю, то естьb
G (x) = або G (x) =.
Оптимальне рішення допоміжної задачі відповідає НДБР вихідної задачі.
3. Симплекс-метод
При вирішенні ЗЛП симплекс-методом зручно представити задачу в табличному вигляді.
ОЗНАКА ОПТИМАЛЬНОСТИ. План х * = (х1, х2, ..., хn) вважається оптимальним, якщо всі коефіцієнти цільової функції невід'ємні, Сj Ві 0,. Тоді значення Fmax дорівнює значенню, який стоїть у правому нижньому куті таблиці. p> Якщо є хоча б один негативний коефіцієнт цільової функції, слід перейти до нового базисного рішенням, значення цільової функції при якому буде менше. Для цього використовують такі правила:
Серед негативних коефіцієнтів цільової функції вибирають максимальний по модулю. Стовпець, що в якому стоїть цей коефіцієнт, називають вирішальним і позначають *.
Знаходять відносини, тобто відносини вільних членів обмежень до елементів матриці коефіцієнтів обмежень, що стоять в вирішуючому стовпці і мають позитивні значення. Серед цих відносин вибирають мінімальне. Рядок, в якій коштує це мінімальне відношення, називається дозволяючий і позначається *. Якщо серед елементів дозволяє стовпця не буде жодного позитивного, то задача оптимізації не має рішення. ol>
Елемент, що стоїть на перетині дозвільних рядка і стовпчика, називається що дозволяє і відзначається ? .
Проводиться заміна базисного допустимого рішення на інше, при цьому таблиця буде мати такий зміст:
а) вільна змінна х j * , що стоїть в вирішуючому стовпці, стає базисної, а
базисна змінна х ai * , що стоїть у роздільній рядку, - вільної;
б) всі елементи роздільної рядка в новій таблиці мають значення
В
(штрихом відзначені нові значення);
в) всі інші елементи таблиці визначаються за формулами:
(i В№ i *), (i В№ i *),
(i В№ i *),.
Кожна нова таблиця перевіряється на оптимальність. Операції 1) -4) здійснюються до тих пір, поки не буде отримано оптимальне значення цільової функції. br/>
Лекція 4, 5
Стійкість рішень ЗЛП при невеликих змінах умов. Двоїстий симплекс-метод
Запитання:
. Звернений базис, симплекс - множники. p>. Зміна значень правих частин обмежень. p>. Зміна значень коефіцієнтів цільо...
