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

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

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

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

Неможливо розібрати вираз (невідома помилка): \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

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

Приклад

Знайти значення змінних Неможливо розібрати вираз (невідома помилка): x_1,x_2 , при яких функція Неможливо розібрати вираз (невідома помилка): Q=5x_1+6x_2

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

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} 3x_1+x_2\le75 (1)\\ x_1+4x_2\le83 (2)\\ x_2\le30 (3)\\ \end{array}} \right. Неможливо розібрати вираз (невідома помилка): x_1,x_2\ge0

Крок: 1 Позбудемося нерівностей в обмеженнях, ввівши в обмеження 1, 2, 3 невід'ємні балансові змінні Неможливо розібрати вираз (невідома помилка): s_1,s_2,s_3

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} 3x_1+x_2+s_1=75 (1)\\ x_1+4x_2+s_2=83 (2)\\ x_2+s_3=30 (3)\\ \end{array}} \right. Неможливо розібрати вираз (невідома помилка): x_1,x_2,s_1,s_2,s_3\ge0

Крок: 2 Шукаємо в системі обмежень базисні змінні. З останньої системи обмежень можна виділити базисні змінні Неможливо розібрати вираз (невідома помилка): s_1,s_2,s_3 . Тепер ми можемо сформувати початкову симплекс-таблицю.
Крок: 3 Початкова симплекс-таблиця

Iтерація 1

Iтерація 2

Досягнуто оптимальне рішення, тому що в рядку цільової функції немає позитивних коефіцієнтів. Відповідь: Оптимальне значення функції Q (x) = 193.54545454545 досягається в точці з координатами

Неможливо розібрати вираз (невідома помилка): x_1=19.727272727273 Неможливо розібрати вираз (невідома помилка): x_2=15.818181818182 Неможливо розібрати вираз (невідома помилка): s_1=0 Неможливо розібрати вираз (невідома помилка): s_2=0 Неможливо розібрати вираз (невідома помилка): s_3=14.181818181818

Література

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

http://www.math-pr.com/exampl_zlp_b.html