Відмінності між версіями «Симплекс-метод оптимізації»
(→Алгоритм симплекс-методу) |
(→Приклад розв'язання матричної гри з використанням симплек-методу) |
||
Рядок 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 році.
Алгоритм симплекс-методу
- Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне (≤) обмежень:
- Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію F у вигляді аналогічному до системи обмежень, тобто:
- Перевірка на оптимальність. Якщо всі коефіцієнти в рядку 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.
Приклад розв'язання матричної гри з використанням симплек-методу
Нехай матрична гра представлена наступною матрицею:
[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]
Дана матриця не містить сідлової точки, отже запишемо для неї наступну систему рівнянь: