Відмінності між версіями «Симплекс-метод розв’язування задач ЛП. Оптимальний розв’язок. Критерій оптимальності плану»
Tenatin (обговорення • внесок) |
|||
| Рядок 17: | Рядок 17: | ||
<center><math>\mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n (1)} </math> </center> | <center><math>\mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n (1)} </math> </center> | ||
| − | |||
<center><math>\left\{ {\begin{array}{l} | <center><math>\left\{ {\begin{array}{l} | ||
x_1+a_{1,m+1}x_{m+1} + ... + a_{1n}x_n = b_1; \\ | x_1+a_{1,m+1}x_{m+1} + ... + a_{1n}x_n = b_1; \\ | ||
Версія за 16:58, 4 травня 2012
Розглянемо задачу лінійного програмування, записану в канонічній формі:
Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:
Розглянемо задачу лінійного програмування
Допустимо, що вона має опорні плани і вони є невиродженими. Розглянемо початковий опорний план виду
Такому плану відповідає розклад за базисними векторами
та значення функціонала:
Кожен з векторів Неможливо розібрати вираз (невідома помилка): A_1,A_2,..,A_n
можна розкласти за векторами базису, причому у єдиний спосіб:
тому такому розкладу відповідатиме і єдине значення функціонала:
Позначимо через Неможливо розібрати вираз (невідома помилка): c_j
коефіцієнт функціонала, що відповідає вектору Неможливо розібрати вираз (невідома помилка): A_j , та позначимо Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j=F_j-c_j
. (їх називають оцінками відповідних векторів плану) Неможливо розібрати вираз (невідома помилка): (j=1,n)
Теорема 1Якщо для деякого вектора Неможливо розібрати вираз (невідома помилка): A_j
виконується умова Неможливо розібрати вираз (невідома помилка): F_j-c_j<0 , то план Неможливо розібрати вираз (невідома помилка): X_0 не є оптимальним і можна відшукати такий план Х, для якого виконуватиметься нерівність Неможливо розібрати вираз (невідома помилка): F(X)>F(X_0).
Якщо розглядається задача на відшукання мінімального значення цільової функції, то формулюється така теорема.
Теорема 2Якщо для деякого вектора Неможливо розібрати вираз (невідома помилка): A_j
виконується умова Неможливо розібрати вираз (невідома помилка): F_j-c_j>0 ,то план Неможливо розібрати вираз (невідома помилка): X_0 не є оптимальним і можна побудувати такий план Х, для якого виконуватиметься нерівність Неможливо розібрати вираз (невідома помилка): F(X)<F(X_0).
Наслідок:(умова оптимальності плану задачі максимізації): якщо для деякого плану Неможливо розібрати вираз (невідома помилка): X_0
розклад всіх векторів Неможливо розібрати вираз (невідома помилка): A_j(j=1,n) у даному базисі задовольняє умову:
є оптимальним розв’язком задачі лінійного програмування (1)-(3).
(умова оптимальності плану задачі мінімізації): якщо для деякого плану Неможливо розібрати вираз (невідома помилка): X_0
розклад всіх векторів Неможливо розібрати вираз (невідома помилка): A_j(j=1,n) у даному базисі задовольняє умову
то план Неможливо розібрати вираз (невідома помилка): X_0
є оптимальним розв’язком задачі лінійного програмування.
Отже, для того, щоб план задачі лінійного програмування був оптимальним, необхідно і достатньо, щоб його оцінки Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j=F_j-c_j
були невід’ємними для задачі на максимум та недодатними для задачі на мінімум.
