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

Дана стаття являється неперевіреним навчальним завданням. Студент: Барабаш С. Б. Викладач: Назаревич О. Б. Термін до: 18 березня 2012 До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону.

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

Презентація доповіді на тему http://elartu.tntu.edu.ua/handle/123456789/1584 Симплекс-метод оптимізації є розміщеною в Репозиторії.

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

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

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

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

• Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію 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]

• Перевірка на оптимальність. Якщо всі коефіцієнти в рядку 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]

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

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

Основна ідея симплек методу

Основна ідея симплекс-метода полягає в тому, що екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод, званий також методом послідовного поліпшення плану, реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна. Перш за все, знаходиться яке-небудь допустиме початкове (опорне) рішення, тобто яка-небудь кутова точка області допустимих рішень. Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення. Якщо деяка кутова крапка має декілька суміжних, то обчислювальна процедура методу забезпечує перехід до тієї з них, для якої поліпшення цільової функції буде найбільшим. Процес перебору кутових точок області допустимих рішень повторюється, поки не буде знайдена крапка, якою відповідає екстремум цільової функції Е.

Список літературних джерел

• Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.
• Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций. -- 7-е изд. -- М.: "Вильямс", 2007.

Посилання

[1]

[2]