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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 41: Рядок 41:
  
 
<center><math>x_{j} \ge 0\,\,\,\,\,(j=1,2,...,n+m).</math></center>
 
<center><math>x_{j} \ge 0\,\,\,\,\,(j=1,2,...,n+m).</math></center>
 +
 +
 +
область допустимих розв’язків задачі розширилась.
 +
 +
Задача з даною системою обмежень називається розширеноб, або М-задачею
 +
 +
Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві
 +
 +
Для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з великими від’ємними коефіцієнтами.
 +
Нехай величина М є достатньо великим за модулем числом.
 +
Цільова функція для задачі максимізації (мінімізації):
 +
 +
<center><math>\max \,F^{\ast }=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} -Mx_{n+1}
 +
-...-Mx_{n+m} </math></center>
 +
 +
<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>

Версія за 19:45, 28 квітня 2012

Метод штучного базису застосовується в тих випадках коли система обмежень задачі лінійного програмування не містить одиничну матрицю порядку 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}
Отримано з https://wiki.cusu.edu.ua/index.php?title=Метод_штучного_базису&oldid=66372