Відмінності між версіями «Симплекс-метод оптимізації»

(Алгоритм симплекс-методу)
(Приклад розв'язання матричної гри з використанням симплек-методу)
Рядок 39: Рядок 39:
 
#Повернення до кроку 3.
 
#Повернення до кроку 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>
 +
Дана матриця не містить сідлової точки, отже запишемо для неї наступну систему рівнянь:

Версія за 22:12, 22 лютого 2012

Прізвище Барабаш
Ім'я Світлана
По-батькові Богданівна
Факультет ФІС
Група СНм-51
Залікова книжка № СНм-11-226


Репозиторія
Презентація доповіді на тему Симплекс-метод оптимізації
є розміщеною в Репозиторії.

Симплекс-метод ---- це метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку. Досить часто симплекс-метод ще називають методом покращення плану. Реальні задачі лінійного програмування містять дуже велику кількість обмежень та невідомих і виконуються на ЕОМ. Симплекс-метод ---- найбільш загальний алгоритм, що використовується для рішення таких задач. Даний метод був розроблений американським математиком Джорджем Данцігом у 1947 році.

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

  1. Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне () обмежень:
[math]F=\sum\limits_{i=1}^{r}{{{C}_{i}}{{x}_{i}}\to \max }[/math]
.;
[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]
..
  1. Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію F у вигляді аналогічному до системи обмежень, тобто:
[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]
.
  1. Перевірка на оптимальність. Якщо всі коефіцієнти в рядку F є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю).
  2. Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку F.
  3. Вибір ведучого рядка та ведучого елемента [math]{{a}_{rs}}[/math], щоб вибрати ведучий рядок (а отже зміну, яка залишає базис) необхідно скористатись MRT тестом (мінімальне відношення). Для цього необхідно записати у відповідному рядку відношення змінної зі стовпця "план" до змінної з ведучого стовпця і визначити мінімальне з цих відношень. Рядок з мінімальним значенням з відношення буде ведучим рядком.

Зауваження: якщо коефіцієнт у ведучому стовпці рівний 0 або від'ємний, то у стовпці MRT ставиться нескінченність, тобто не враховується при виборі ведучого рядка; відношення не визначається для рядку F. На перетині ведучого стовпця та ведучого рядка знаходиться ведучий елемент [math]{{a}_{rs}}[/math].

  1. Модифікація симплекс таблиці по відношенню до ведучого елемента [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].

Згідно наведених правил здійснюється перерахунок елементів для нової симплекс таблиці.

  1. Повернення до кроку 3.

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

Нехай матрична гра представлена наступною матрицею:

[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]

Дана матриця не містить сідлової точки, отже запишемо для неї наступну систему рівнянь: