Відмінності між версіями «Метод штучного базису»

Версія за 18:19, 4 травня 2012

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

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

Отримаємо одиничну матрицю додаванням штучних змінних

Неможливо розібрати вираз (невідома помилка): x_{n+i} \ge 0\;\,\,\,(i=\overline {1,m} )

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

Нехай штучну змінну введено у кожне рівняння:

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

Задача з даною системою обмежень називається розширеноб, або М-задачею

Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві

Для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з великими від’ємними коефіцієнтами. Нехай величина М є достатньо великим за модулем числом. Цільова функція для задачі максимізації (мінімізації):

Якого б малого значення не набувала відповідна коефіцієнту штучна змінна Неможливо розібрати вираз (невідома помилка): x_{n+i}

, значення цільової функції 

Неможливо розібрати вираз (невідома помилка): F^{\ast }

буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні 

Неможливо розібрати вираз (невідома помилка): x_{n+i} =0\;\left( {\,i=\overline {1,m} } \right)

Якщо в оптимальному плані розширеної задачі існує хоча б одне значення Неможливо розібрати вираз (невідома помилка): x_{n+i} >0 , то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна.

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.

Теорема

Якщо в оптимальному плані Неможливо розібрати вираз (невідома помилка): \mathord X _{opt} =(x_{1} ,\;x_{2} ,...,\;x_{n} ,\,0,\,...,\;0)

розширеної задачі штучні змінні Неможливо розібрати вираз (невідома помилка): x_{n+i} =0,\;\,\,(i=1,\;2,\;...,\;m)

то план Неможливо розібрати вираз (невідома помилка): X_{opt} =(x_{1}~ ,x_{2} ,...,~x_{n} )

є оптимальним планом початкової задачі.

Приклад

Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочатку запишемо систему обмежень у канонічній формі:

Зауважимо, що нерівність типу «≥» перетворюємо у рівняння введенням у ліву частину обмеження додаткової змінної зі знаком «–». Система містить лише два одиничні вектори Неможливо розібрати вираз (невідома помилка): \vec{{A}}_{5}

та Неможливо розібрати вираз (невідома помилка): \vec{{A}}_{6} 
, а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з 

коефіцієнтом +1 штучну змінну х8, якій від-повідатиме одиничний вектор Неможливо розібрати вираз (невідома помилка): \vec{{A}}_{8} = \begin{pmatrix} 0 \\ 0 \\1 \end{pmatrix}

Тепер можемо розглянути розширену задачу лінійного програмування:

На відміну від додаткових змінних штучна змінна х8 має в ці-льовій функції Z коефіцієнт +М (для задачі на min) або –М (для задачі на max), де М — досить велике додатне число. У розширеній задачі базисними змінними є х5, х6, х8, а решта змінних вільні. Початковий опорний план задачі такий

Розраховуючи оцінки першого опорного плану, дістаємо: Z0 = –9M; Z1 – с1 = –8; Z2 – с2 = –10, Z3 – с3 = –М і т. д. Отже, ми отримуємо оцінки двох видів: одні з них містять М, а інші є звичайними числами. Тому для зручності розділимо оцінковий рядок на два. У перший оцінковий рядок будемо записувати звичайні числа, а в другий — числа з коефіцієнтом М. Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Виконуємо перехід до наступного опорно-го плану задачі. Після першої ітерації з базису виведена штучна змінна х8. Дальше розв’язування продовжуємо за алгоритмом симплексного методу.

Наступні кроки розв’язування задачі наведені у загальній таблиці:

Оптимальним планом задачі є вектор:

Література

http://fingal.com.ua/content/view/479/76/1/0/