Двоетапний метод штучного базису.

Нехай маємо КЗЛП:

, , де . (1.5.1)

 

Розглянемо допоміжну КЗЛП:

 

, , , … , . (1.5.2)

 

або у матричному вигляді

,

,

,

де — одинична матриця розміру .

Цільову функцію цієї задачі можна розглядати як міру недопустимості при перевірці виконання обмежень задачі. Коли , тоді . Тому оптимальний базисний розв’язок цієї задачі буде допустимим для задачі (1.5.1).

Нехай, як і раніше, — допустима множина початкової КЗЛП (1.5.1), а — допустима множина допоміжної КЗЛП (1.5.2) і нехай .

Розв’язуємо задачу (1.5.2) симплекс-методом з початковим базисним розв’язком та з одиничним базисом (за умовою всі ).

Оскільки , то можливі два випадки:

а) . Це можливо тоді і тільки тоді, якщо всі .

Отже, оптимальний базисний розв’язок допоміжної КЗЛП має вигляд:

.

Оскільки — базисний розв’язок, то серед , не більше відмінних від нуля.

Отже, вектор і буде допустимим базисним розв’язком задачі (1.5.1).

б) . Це можливо лише у тому випадку, коли хоча б одна з компонент оптимального базисного розв’язку додатна (відмінна від нуля).

Доведемо, що у цьому випадку початкова задача (1.5.1) не має жодного розв’язку (допустима множина порожня).

Доведемо це від супротивного. Нехай допустимий (не обов’язково базисний) розв’язок початкової КЗЛП (1.5.1), .

Тоді — допустимий розв’язок допоміжної КЗЛП (1.5.2) ( ).

Але при цьому , що суперечить тому, що .

Приклад 1.12. Розв’язати ЗЛП:

, , , . (1.5.3)

 

Побудуємо допоміжну ЗЛП:

, , , . (1.5.4)

 

Приймемо за початковий базисний розв’язок з базисом . Розв’яжемо задачу (1.5.4) (табл. 1.15):

Таблиця 1.15.

                 
  Базис – 1 – 1
– 1     – 1        
      – ½   3/2   ½  
  – 1 – 1
      – 28 – 3 – 1 – 2
  – 1/2 3/2 1/2
– 1     5/2   –5/2   -1    
        -1   –2/5   2/5
      – 10 – 5/2 5/2
  3/10 1/2
  -1 –2/5 2/5
     
                                 

 

Отже, оптимальний розв’язок задачі (1.5.4) є . Серед базисних векторів немає штучних. Таким чином, вектор є початковим базисним розв’язком задачі (1.5.3). Його базис складають вектори .

Для побудови початкової симплекс-таблиці задачі (1.5.3) скористаємося останньою частиною таблиці (1.15), але замінимо елементи стовпчика та числа над стовпчиками відповідно до даних цільової функції задачі (1.5.3) (табл. 1.16).

Таблиця 1.16.

Базис – 2
– 2 –1
   

 

Оскільки всі оцінки невід’ємні, то початковий базисний розв’язок виявляється і оптимальним для ЗЛП (1.5.3):



.

Цей метод носить назву двоетапного методу штучного базису. Він дозволяє знайти оптимальний розв’язок початкової задачі у два етапи. На першому етапі розв’язується допоміжна КЗЛП (1.5.2) з одиничним базисом. Якщо до базису, який відповідає оптимальному розв’язку допоміжної задачі, не входять штучні вектори, тоді цей базисний розв’язок приймається за початковий для задачі (1.5.1). На другому етапі розв’язуємо симплекс-методом задачу (1.5.1). Якщо до оптимального базису задачі (1.5.2) входять штучні вектори, тоді задача (1.5.1) буде нерозв’язуваною.

Існує інший метод, який дозволяє одночасно з пошуком початкового базисного розв’язку знайти її оптимум. Це – М-метод.

2. М-методрозв’язування КЗЛП.

Нехай маємо КЗЛП (1.5.1) з .

Як і у двоетапному методі штучного базису, який розглядався вище, в систему обмежень вводимо штучні змінні для отримання повного одиничного базису. Але при цьому цільова функція будується інакше. Допоміжна М-задача має вигляд:

, , , (1.5.5)

де — достатньо велике число.

За використання штучних змінних в обмеженнях задачі вводиться великий штраф у вигляді коефіцієнту у цільовій функції при штучних змінних.

М-задача розв’язується симплекс-методом з однією особливістю, яка пов’язана з коефіцієнтами у цільовій функції. Оцінки записуються у вигляді:

.

У симплекс-таблиці вводяться два рядка для запису та . Розв’язування М-задачі ведеться по рядку оцінок до тих пір, поки існують , а потім по рядку згідно з правилами симплекс-методу.

Розв’язуючи КЗЛП (1.5.5), можна отримати три варіанта відповіді:

а) у оптимальному розв’язку М-задачі всі .

В цьому випадку оптимальним розв’язком початкової задачі (1.5.1) є вектор .

Дійсно, нехай — довільний допустимий розв’язок задачі (1.5.1). Тоді — допустимий розв’язок задачі (1.5.5).

Оскільки — оптимальний розв’язок задачі (1.5.5), то маємо

де .

Нерівність і доводить оптимальність .

б) у оптимальному розв’язку М-задачі хоча б одна із штучних координат .

В цьому випадку можна довести, що початкова задача не має жодного допустимого розв’язку ( ).

в) при достатньо великих цільова функція задачі (1.5.5) необмежена на допустимій множині: . Тоді і початкова задача нерозв’язувана, тобто .

Зауважимо, що у М-методі, константі не обов’язково придавати якесь конкретне значення. Достатньо вимагати, щоб у процесі розв’язування при порівнянні з будь-яким конкретним числом, було більше.

Для розв’язування М-задачі з використанням ЕОМ можна брати за будь-яке число таке, що .

Приклад 1.13.

,

,

,

.

Побудуємо М-задачу:

,

,

,

.

.

Початковий базис М-задачі складається з штучних одиничних векторів (при штучній змінній ) та (при штучній змінній ). Початковий базисний розв’язок .

Розв’язування М-задачі наведено у таблиці 1.17.

Таблиця 1.17

Базис
-1 -3
    -1 -2 -1
    -15 -3

Зручно записувати оцінку у такому вигляді .

Оцінка . Значить , а .

, , .

, , .

, , .

, , .

, , .

Оцінки записуємо у рядок з номером „3” симплекс-таблиці, а - у рядок з номером „4”. Так як у рядку з оцінками існує одна від’ємна оцінка , тоді вводимо до базису вектор , а виведемо з базису вектор та переходимо до наступного базисного розв’язку (табл. 1.18).

 

Таблиця 1.18.

Базис
   
   

 

Вибираємо , змінюємо базис і переходимо до нового базисного розв’язку (табл.1.19).

Таблиця 1.19.

Базис
    -1
   

 

Оскільки всі , тоді переходимо до оцінок у рядку з номером „3”. Вводимо до базису вектор , виводимо та знаходимо новий базисний розв’язок (табл. 1.20).

Таблиця 1.20.

Базис
   

 

Оцінка буде невід’ємною при достатньо великих . Отже, оптимальний розв’язок М-задачі , . Оскільки всі штучні змінні та дорівнюють нулеві, тому оптимальний розв’язок початкової задачі , .

Зауваження. Якщо в КЗЛП є одиничні вектори, але їх не вистачає для формування базису, тоді в задачу вводиться стільки штучних змінних, скільки не вистачає одиничних векторів. Причому вибір обмежень, в які вводяться штучні змінні, визначається структурою одиничних векторів, яких не вистачає. (В усіх базисних одиничних векторах одиниці мають стояти на різних місцях.)

 









Последнее изменение этой страницы: 2016-04-06; Нарушение авторского права страницы

infopedia.su не принадлежат авторские права, размещенных материалов. Все права принадлежать их авторам. Обратная связь