Відмінності між версіями «Метод штучного базису»
| Рядок 68: | Рядок 68: | ||
Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою. | Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою. | ||
| + | |||
| + | Теорема | ||
| + | |||
| + | Якщо в оптимальному плані <math>\mathord X | ||
| + | _{opt} =(x_{1} ,\;x_{2} ,...,\;x_{n} ,\,0,\,...,\;0) | ||
| + | </math> розширеної задачі штучні змінні <math>x_{n+i} =0,\;\,\,(i=1,\;2,\;...,\;m)</math> | ||
| + | то план <math>X_{opt} =(x_{1}~ ,x_{2} ,...,~x_{n} )</math> є оптимальним планом початкової задачі. | ||
Версія за 20:10, 28 квітня 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} )
є оптимальним планом початкової задачі.
