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

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


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

<center><math>\mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n}</math></center>


<center><math>\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.</math></center>

<center><math>x_j\ge0(j=1,2,..,n)</math></center>

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

<center><math>\mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n } </math>  </center>
<center><math> (1) </math>  </center>


<center><math>\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.</math></center>
<center><math>  (2)  </math></center>

<center><math>x_j\ge0(j=1,2,..,n)</math></center>
<center><math>  (3)  </math></center>

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

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

<center><math>X_0=(x_1=b_1,x_2=b_2,x_m=b_m,x_{m+1}=0,...,x_n=0).</math></center>

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

<center><math>x_1A_1+x_2A_2+..+x_mA_m=A_0</math></center>

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

<center><math>F=c_1x_1+c_2x_2+..+c_mx_m=F(X_0).</math></center>

Кожен з векторів <math>A_1,A_2,..,A_n</math> можна розкласти за векторами базису, причому у єдиний спосіб:

<center><math>a_{1j}A_1+a_{2j}A_2+...+a_{mj}A_m=A_j,(j=1,n)</math></center>

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

<center><math>F_j=c_1a_{1j}+c_2a_{2j}+..+c_ma_{mj},(j=1,n)</math></center>

Позначимо через <math>c_j</math> коефіцієнт функціонала, що відповідає вектору <math>A_j</math> , та позначимо <math>\bigtriangleup_j=F_j-c_j</math>.
(їх називають оцінками відповідних векторів плану)  <math>(j=1,n)</math>

== '''Теорема 1''' ==
Якщо для деякого вектора <math>A_j</math> виконується умова  <math>F_j-c_j<0</math> , то план <math>X_0</math> не є оптимальним і можна відшукати такий план Х, для якого виконуватиметься нерівність <math> F(X)>F(X_0).</math> 

Якщо розглядається задача на відшукання мінімального значення цільової функції, то формулюється така теорема.

== '''Теорема 2''' ==
Якщо для деякого вектора <math>A_j</math> виконується умова <math>F_j-c_j>0</math> ,то план <math>X_0</math> не є оптимальним і можна побудувати такий план Х, для якого виконуватиметься нерівність <math> F(X)<F(X_0).</math> 

== '''Наслідок:''' ==
''(умова оптимальності плану задачі максимізації)'': якщо для деякого плану <math>X_0</math> розклад всіх векторів <math>A_j(j=1,n)</math> у даному базисі задовольняє умову: 

<center><math>\bigtriangleup_j=F_j-c_j\ge0,</math></center> то план <math>X_0</math> є оптимальним розв’язком задачі лінійного програмування (1)-(3).

''(умова оптимальності плану задачі мінімізації)'': якщо для деякого плану <math>X_0</math> розклад всіх векторів <math>A_j(j=1,n)</math> у даному базисі задовольняє умову 

<center><math>\bigtriangleup_j=F_j-c_j\le0,</math></center>
то план <math>X_0</math> є оптимальним розв’язком задачі лінійного програмування.

Отже, для того, щоб план задачі лінійного програмування був оптимальним, необхідно і достатньо, щоб його оцінки <math>\bigtriangleup_j=F_j-c_j</math> були невід’ємними для задачі на максимум та недодатними для задачі на мінімум.

== Приклад ==
Знайти значення змінних <math>x_1,x_2</math>, при яких функція <math>Q=5x_1+6x_2</math> приймає максимальне значення, за умови наступних обмежень:
<center><math>\left\{ {\begin{array}{l}
3x_1+x_2\le75 (1)\\
x_1+4x_2\le83 (2)\\
x_2\le30 (3)\\
\end{array}} \right.</math></center>
<center><math>x_1,x_2\ge0</math></center>
<br>
Крок: 1
Позбудемося нерівностей в обмеженнях, ввівши в обмеження 1, 2, 3 невід'ємні балансові змінні <math>s_1,s_2,s_3</math>
<center><math>\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.</math></center>
<center><math>x_1,x_2,s_1,s_2,s_3\ge0</math></center>
<br>
Крок: 2
Шукаємо в системі обмежень базисні змінні.
З останньої системи обмежень можна виділити базисні змінні <math>s_1,s_2,s_3</math>.
Тепер ми можемо сформувати початкову симплекс-таблицю.
<br>
<br>Крок: 3
<br>Початкова симплекс-таблиця
[[Файл:1табл.jpg]]
<br>Iтерація 1
[[Файл:2табл.jpg]]
<br>Iтерація 2
[[Файл:3табл.jpg]]
<br>Досягнуто оптимальне рішення, тому що в рядку цільової функції немає позитивних коефіцієнтів.
<br>
<br>Відповідь: Оптимальне значення функції Q (x) = 193.54545454545  досягається в точці з координатами
<center><math>x_1=19.727272727273</math></center>
<center><math>x_2=15.818181818182</math></center>
<center><math>s_1=0</math></center>
<center><math>s_2=0</math></center>
<center><math>s_3=14.181818181818</math></center>


== Література ==
http://fingal.com.ua/content/view/479/76/1/0/,

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