Симплекс-метод розв’язування задач ЛП. Оптимальний розв’язок. Критерій оптимальності плану

Симплексний метод

Цей метод уможливлює направлений перебір опорних планів, тобто перехід від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням функціонала. Отже, окремим питанням стає вибір вектора, який необхідно вводити в базис при здійсненні ітераційної процедури симплексного методу.

Розглянемо задачу лінійного програмування, записану в канонічній формі:

Неможливо розібрати вираз (невідома помилка): \mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_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\ge0(j=1,2,..,n)

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

Неможливо розібрати вираз (невідома помилка): \mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n } Неможливо розібрати вираз (невідома помилка): (1)

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} x_1+a_{1,m+1}x_{m+1} + ... + a_{1n}x_n = b_1; \\ x_2+a_{2,m+1}x_{m+1} + ... + a_{2n}x_n = b_2; \\ ........................................\\ x_m+a_{m,m+1}x_{m+1} + ... + a_{mn}x_n = b_m; \\ \end{array}} \right. Неможливо розібрати вираз (невідома помилка): (2) Неможливо розібрати вираз (невідома помилка): x_j\ge0(j=1,2,..,n) Неможливо розібрати вираз (невідома помилка): (3)

Розглянемо задачу лінійного програмування

Допустимо, що вона має опорні плани і вони є невиродженими. Розглянемо початковий опорний план виду

Неможливо розібрати вираз (невідома помилка): X_0=(x_1=b_1,x_2=b_2,x_m=b_m,x_{m+1}=0,...,x_n=0).

Такому плану відповідає розклад за базисними векторами

Неможливо розібрати вираз (невідома помилка): x_1A_1+x_2A_2+..+x_mA_m=A_0

та значення функціонала:

Неможливо розібрати вираз (невідома помилка): F=c_1x_1+c_2x_2+..+c_mx_m=F(X_0).

Кожен з векторів Неможливо розібрати вираз (невідома помилка): A_1,A_2,..,A_n

можна розкласти за векторами базису, причому у єдиний спосіб:

Неможливо розібрати вираз (невідома помилка): a_{1j}A_1+a_{2j}A_2+...+a_{mj}A_m=A_j,(j=1,n)

тому такому розкладу відповідатиме і єдине значення функціонала:

Неможливо розібрати вираз (невідома помилка): F_j=c_1a_{1j}+c_2a_{2j}+..+c_ma_{mj},(j=1,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)
у даному базисі задовольняє умову: 

Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j=F_j-c_j\ge0, то план Неможливо розібрати вираз (невідома помилка): X_0

є оптимальним розв’язком задачі лінійного програмування (1)-(3).

(умова оптимальності плану задачі мінімізації): якщо для деякого плану Неможливо розібрати вираз (невідома помилка): X_0

розклад всіх векторів Неможливо розібрати вираз (невідома помилка): A_j(j=1,n)
у даному базисі задовольняє умову 

Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j=F_j-c_j\le0,

то план Неможливо розібрати вираз (невідома помилка): X_0

є оптимальним розв’язком задачі лінійного програмування.

Отже, для того, щоб план задачі лінійного програмування був оптимальним, необхідно і достатньо, щоб його оцінки Неможливо розібрати вираз (невідома помилка): \bigtriangleup_j=F_j-c_j

були невід’ємними для задачі на максимум та недодатними для задачі на мінімум.

Література

http://fingal.com.ua/content/view/479/76/1/0/