Перегляд вихідного коду сторінки Симплекс-метод оптимізації

{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px"

|-
| '''Прізвище''' || Барабаш
|-
| '''Ім'я''' || Світлана
|-
| '''По-батькові''' || Богданівна
|-
| '''Факультет''' || ФІС
|-
| '''Група''' || СНм-51
|-
| '''Залікова книжка''' || № СНм-11-226
|}
<br>
{{Презентація доповіді |title= Симплекс-метод оптимізації}}
'''Симплекс-метод''' ---- це метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку. Досить часто симплекс-метод ще називають методом покращення плану. Реальні задачі лінійного програмування містять дуже велику кількість обмежень та невідомих і виконуються на ЕОМ. Симплекс-метод ---- найбільш загальний алгоритм, що використовується для рішення таких задач.
Даний метод був розроблений американським математиком Джорджем Данцігом у 1947 році.
<br>

== Алгоритм симплекс-методу ==

#Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне (''&le;'') обмежень: 
<center><math>F=\sum\limits_{i=1}^{r}{{{C}_{i}}{{x}_{i}}\to \max }</math></center> 
<center><math>\sum\limits_{i=1}^{n}{{{a}_{ji}}{{x}_{i}}+{{x}_{n+j}}={{b}_{j}}};\,\,\,j=\overline{1,m};\,\,\,{{x}_{i}}\ge 0;\,\,\,i=\overline{1,n}</math></center>
#Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію ''F'' у вигляді аналогічному до системи обмежень, тобто:
<center><math>F=\sum\limits_{i=1}^{r}{{{C}_{i}}{{x}_{i}}\to \max ;\,\,\,F-\sum\limits_{i=1}^{r}{{{C}_{i}}{{x}_{i}}=0}}</math></center>

{| border=1
!Базис !! План !! <math>{{x}_{1}}</math> !! <math>{{x}_{2}}</math> !! ... !! <math>{{x}_{s}}</math> !! ... !! <math>{{x}_{n}}</math> !! <math>{{x}_{n+1}}</math> !! ... !! <math>{{x}_{n+m}}</math> !! MRT 
|-
| F || 0 || <math>{{-c}_{1}}</math> || <math>{{-c}_{2}}</math> || ... || <math>{{-c}_{s}}</math> || ... || <math>{{-c}_{n}}</math> || 0 || ... || 0 ||   
|-
| <math>{{x}_{n+1}}</math> || <math>{{b}_{1}}</math> || <math>{{a}_{11}}</math> || <math>{{a}_{12}}</math> || ... || <math>{{a}_{s}}</math> || ... || <math>{{a}_{1n}}</math> || 1 || ... || 0 || <math>\frac{{{b}_{1}}}{{{a}_{1s}}}</math>
|-
|| ...
|-
| <math>{{x}_{n+r}}</math> || <math>{{b}_{r}}</math> || <math>{{a}_{r1}}</math> || <math>{{a}_{r2}}</math> || ... || <math>{{a}_{rs}}</math> || ... || <math>{{a}_{rn}}</math> || 0 || ... || 0 || <math>\frac{{{b}_{r}}}{{{a}_{rs}}}</math>
|-
| <math>{{x}_{n+m}}</math> || <math>{{b}_{m}}</math> || <math>{{a}_{m1}}</math> || <math>{{a}_{m2}}</math> || ... || <math>{{a}_{ms}}</math> || ... || <math>{{a}_{mn}}</math> || 0 || ... || 1 || <math>\frac{{{b}_{m}}}{{{a}_{ms}}}</math>
|}

#Перевірка на оптимальність. Якщо всі коефіцієнти в рядку ''F'' є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю).
#Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку ''F''.
#Вибір ведучого рядка та ведучого елемента <math>{{a}_{rs}}</math>, щоб вибрати ведучий рядок (а отже зміну, яка залишає базис) необхідно скористатись MRT тестом (мінімальне відношення). Для цього необхідно записати у відповідному рядку відношення змінної зі стовпця "план" до змінної з ведучого стовпця і визначити мінімальне з цих відношень. Рядок з мінімальним значенням з відношення буде ведучим рядком.
''Зауваження'': якщо коефіцієнт у ведучому стовпці рівний ''0'' або від'ємний, то у стовпці MRT ставиться нескінченність, тобто не враховується при виборі ведучого рядка; відношення не визначається для рядку ''F''.
На перетині ведучого стовпця та ведучого рядка знаходиться ведучий елемент <math>{{a}_{rs}}</math>.
#Модифікація симплекс таблиці по відношенню до ведучого елемента <math>{{a}_{rs}}</math>.
#*для ведучого рядка ---- <math>{{\widehat{a}}_{rj}}=\frac{{{a}_{rj}}}{a_{rs}^{*}}</math>;
#*для ведучого стовпця ---- <math>{{\widehat{a}}_{rs}}=1;\,\,\,{{\widehat{a}}_{is}}=0;\,\,\,j=\overline{1,m};\,\,\,i\ne r</math>;
#*для решти елементів ---- <math>{{\widehat{a}}_{ij}}=\frac{{{a}_{ij}}\cdot a_{rs}^{*}-{{a}_{rj}}\cdot {{a}_{is}}}{a_{rs}^{*}}</math>.
Згідно наведених правил здійснюється перерахунок елементів для нової симплекс таблиці.
#Повернення до кроку 3.

== Приклад розв'язання матричної гри з використанням симплек-методу ==

Нехай матрична гра представлена наступною матрицею:
<center>
<math>\begin{matrix}
   \left. \left( \begin{matrix}
   1 & 3 & \begin{matrix}
   0 & 1  \\
\end{matrix}  \\
   2 & 0 & \begin{matrix}
   1 & 2  \\
\end{matrix}  \\
   1 & 2 & \begin{matrix}
   3 & 4  \\
\end{matrix}  \\
\end{matrix} \right. \right) & \begin{matrix}
   0  \\
   0  \\
   1  \\
\end{matrix}  \\
   \begin{matrix}
   2 & 3 & \begin{matrix}
   3 & 4  \\
\end{matrix}  \\
\end{matrix} & 2\backslash 1  \\
\end{matrix}</math>
</center>
Дана матриця не містить сідлової точки, отже для неї можна записати наступну систему рівнянь:
<center>
<math>\left\{ \begin{align}
  & {{x}_{1}}+3{{x}_{2}}+{{x}_{4}}\le 1 \\ 
 & 2{{x}_{1}}+{{x}_{3}}+2{{x}_{4}}\le 1 \\ 
 & {{x}_{1}}+2{{x}_{2}}+3{{x}_{3}}+4{{x}_{4}}\le 1 \\ 
\end{align} \right.</math>
</center>
Дальше потрібно представити стандартну форму форму задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності обмежень:
<center>
<math>\left\{ \begin{align}
  & {{x}_{1}}+3{{x}_{2}}+{{x}_{4}}=1 \\ 
 & 2{{x}_{1}}+{{x}_{3}}+2{{x}_{4}}=1 \\ 
 & {{x}_{1}}+2{{x}_{2}}+3{{x}_{3}}+4{{x}_{4}}=1 \\ 
\end{align} \right.</math>
</center>
Цільова функція має наступний вигляд:
<center>
<math>F={{x}_{1}}+{{x}_{2}}+{{x}_{3}}+{{x}_{4}}\to \max </math>
</center>
Дану цільову функцію ''F'' потрібно теж переписати в аналогічному вигляді до систем обмежень:
<center>
<math>F-{{x}_{1}}-{{x}_{2}}-{{x}_{3}}-{{x}_{4}}=0</math>
</center>
Дальше будується початкова сиплекс таблиця:
{| border=1
!Базис !! План !! <math>{{x}_{1}}</math> !! <math>\downarrow {{x}_{2}}</math> !! <math>{{x}_{3}}</math> !! <math>{{x}_{4}}</math> !! <math>{{x}_{5}}</math> !! <math>{{x}_{6}}</math> !! <math>{{x}_{7}}</math> !! MRT 
|-
| F || 0 || -1 || -1 || -1 || -1 || 0 || 0 || 0 ||  
|-
| <math>\overset{\to }{{{x}_{5}}}\,</math> || 1 || 1 || '''<math>\left( 3 \right)</math>''' || 0 || 1 || 1 || 0 || 0 || 1/3 
|-
| <math>{{x}_{6}}</math> || 1 || 2 || 0 || 1 || 2 || 0 || 1 || 0 || &infin;
|-
| <math>{{x}_{7}}</math> || 1 || 1 || 2 || 3 || 4 || 0 || 0 || 1 || 1/2
|}