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

Прізвище	Барабаш
Ім'я	Світлана
По-батькові	Богданівна
Факультет	ФІС
Група	СНм-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]

Ймовірності з якими перший гравець може застосовувати свої стратегії рівні:

[math]P({{x}_{1}})=V\cdot \frac{1}{3}=\frac{3}{4}\cdot \frac{1}{3}=\frac{1}{4};\,\,\,\,\,P({{x}_{2}})=V\cdot 1=\frac{3}{4}\cdot 1=\frac{3}{4};\,\,\,\,\,P({{x}_{3}})=V\cdot 0=\frac{3}{4}\cdot 0=0;[/math]

[math]X(\frac{1}{4};\frac{3}{4};0)[/math]

Ймовірності з якими другий гравець може застосовувати свої стратегії рівні:

[math]P({{y}_{2}})=V\cdot \frac{1}{3}=\frac{3}{4}\cdot \frac{1}{3}=\frac{1}{4};\,\,\,\,\,P({{y}_{3}})=V\cdot 1=\frac{3}{4}\cdot 1=\frac{3}{4};[/math]

[math]Y(0;\frac{1}{4};\frac{3}{4};0)[/math]