Відмінності між версіями «Метод штучного базису»
| Рядок 58: | Рядок 58: | ||
<center><math>\min \,F^{\ast }=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} +Mx_{n+1} | <center><math>\min \,F^{\ast }=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} +Mx_{n+1} | ||
+...+Mx_{n+m} </math></center> | +...+Mx_{n+m} </math></center> | ||
| + | |||
| + | Якого б малого значення не набувала відповідна коефіцієнту штучна змінна <math>x_{n+i}</math> , значення цільової функції | ||
| + | <math>F^{\ast }</math> буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні | ||
| + | <math>x_{n+i} =0\;\left( {\,i=\overline {1,m} } \right)</math> | ||
| + | |||
| + | Якщо в оптимальному плані розширеної задачі існує хоча б одне значення <math>x_{n+i} >0</math>, то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна. | ||
| + | |||
| + | Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком. | ||
| + | |||
| + | Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою. | ||
Версія за 19:54, 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)-им рядком.
Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.
