Метод штучного базису застосовується в тих випадках коли система обмежень задачі лінійного програмування не містить одиничну матрицю порядку m.
Розглянемо задачу лінійного програмування:
Неможливо розібрати вираз (невідома помилка): \max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n}
Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11} x_{1} +a_{12} x_{2} +...+a_{1n} x_{n} =b_{1} ; \\ a_{21} x_{1} +a_{22} x_{2} +...+a_{2n} x_{n} =b_{2} ; \\ ......................................... \\ a_{m1} x_{1} +a_{m2} x_{2} +...+a_{mn} x_{n} =b_{m} . \\ \end{array}} \right.
Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0\,\,\,\,\,\,(j=1,2,...,n).
Отримаємо одиничну матрицю додаванням штучних змінних
Неможливо розібрати вираз (невідома помилка): x_{n+i} \ge 0\;\,\,\,(i=\overline {1,m} )
лише в ті рівняння, які не розв’язані відносно базисних змінних.
Нехай штучну змінну введено у кожне рівняння:
Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} a_{11} x_{1} +a_{12} x_{2} +...+a_{1n} x_{n} +x_{n+1} \,=b_{1} , \\ a_{21} x_{1} +a_{22} x_{2} +...+a_{2n} x_{n} +x_{n+2} \,=b_{2} , \\ ......................................... \\ a_{m1} x_{1} +a_{m2} x_{2} +...+a_{mn} x_{n} +x_{n+m} =b_{m} . \\ \end{array}} \right.
Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0\,\,\,\,\,(j=1,2,...,n+m).
область допустимих розв’язків задачі розширилась.
Задача з даною системою обмежень називається розширеноб, або М-задачею
Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві
Для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з великими від’ємними коефіцієнтами.
Нехай величина М є достатньо великим за модулем числом.
Цільова функція для задачі максимізації (мінімізації):
Неможливо розібрати вираз (невідома помилка): \max \,F^{\ast }=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} -Mx_{n+1} -...-Mx_{n+m}
Неможливо розібрати вираз (невідома помилка): \min \,F^{\ast }=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} +Mx_{n+1} +...+Mx_{n+m}
