Симплекс-метод оптимізації

Версія від 11:04, 23 лютого 2012, створена Svetik B7 (обговореннявнесок) (Приклад розв'язання матричної гри з використанням симплек-методу)
Прізвище Барабаш
Ім'я Світлана
По-батькові Богданівна
Факультет ФІС
Група СНм-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]


Базис План [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]


  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]

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

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

Дальше потрібно представити стандартну форму форму задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності обмежень:

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

Цільова функція має наступний вигляд:

[math]F={{x}_{1}}+{{x}_{2}}+{{x}_{3}}+{{x}_{4}}\to \max[/math]

Дану цільову функцію F потрібно теж переписати в аналогічному вигляді до систем обмежень:

[math]F-{{x}_{1}}-{{x}_{2}}-{{x}_{3}}-{{x}_{4}}=0[/math]

Дальше будується та заповнюється початкова сиплекс таблиця:

Базис План [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
[math]{{x}_{7}}[/math] 1 1 2 3 4 0 0 1 1/2

Оскільки чотири коефіцієнти в рядку F є від'ємними, то потрібно дальше продовжити симплекс-ітерацію, отже будується та заповнюється наступна симплекс таблиця.

Базис План [math]{{x}_{1}}[/math] [math]{{x}_{2}}[/math] [math]\downarrow {{x}_{3}}[/math] [math]{{x}_{4}}[/math] [math]{{x}_{5}}[/math] [math]{{x}_{6}}[/math] [math]{{x}_{7}}[/math] MRT
F 1/3 -2/3 0 -1 -2/3 1/3 0 0
[math]{{x}_{2}}[/math] 1/3 1/3 1 0 1/3 1/3 0 0
[math]\overset{\to }{{{x}_{6}}}\,[/math] 1 2 0 [math]\left( 1 \right)[/math] 3 0 1 0 1
[math]{{x}_{7}}[/math] 1/3 1/3 0 3 10/3 -2/3 0 1 1

Оскільки три коефіцієнти в рядку F є від'ємними, то потрібно знову ж таки проводити симплекс-ітерацію, а отже будувати та заповнювати ще одну симплекс таблицю.

Базис План [math]{{x}_{1}}[/math] [math]{{x}_{2}}[/math] [math]{{x}_{3}}[/math] [math]{{x}_{4}}[/math] [math]{{x}_{5}}[/math] [math]{{x}_{6}}[/math] [math]{{x}_{7}}[/math]
F 4/3 4/3 0 0 7/3 1/3 1 0
[math]{{x}_{2}}[/math] 1/3 1/3 1 0 1/3 1/3 0 0
[math]{{x}_{3}}[/math] 1 2 0 1 3 0 1 0
[math]{{x}_{7}}[/math] -8/3 -23/3 0 0 -17/3 2/3 -3 1

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

[math]V=\frac{1}{{{F}_{}}}=\frac{1}{\frac{4}{3}}=\frac{3}{4}[/math]