Відмінності між версіями «Симплекс-метод оптимізації»
(→Алгоритм симплекс-методу) |
(→Алгоритм симплекс-методу) |
||
| Рядок 22: | Рядок 22: | ||
== Алгоритм симплекс-методу == | == Алгоритм симплекс-методу == | ||
| − | #Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне (''≤'') обмежень: | + | #Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне (''≤'') обмежень: <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>. |
| − | <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'' у вигляді аналогічному до системи обмежень, тобто: | #Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію ''F'' у вигляді аналогічному до системи обмежень, тобто: | ||
#Перевірка на оптимальність. Якщо всі коефіцієнти в рядку ''F'' є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю). | #Перевірка на оптимальність. Якщо всі коефіцієнти в рядку ''F'' є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю). | ||
#Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку ''F''. | #Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку ''F''. | ||
Версія за 20:34, 22 лютого 2012
| Прізвище | Барабаш |
| Ім'я | Світлана |
| По-батькові | Богданівна |
| Факультет | ФІС |
| Група | СНм-51 |
| Залікова книжка | № СНм-11-226 |
 |
Презентація доповіді на тему Симплекс-метод оптимізації є розміщеною в Репозиторії. |
Симплекс-метод ---- це метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку. Досить часто симплекс-метод ще називають методом покращення плану. Реальні задачі лінійного програмування містять дуже велику кількість обмежень та невідомих і виконуються на ЕОМ. Симплекс-метод ---- найбільш загальний алгоритм, що використовується для рішення таких задач.
Даний метод був розроблений американським математиком Джорджем Данцігом у 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 у вигляді аналогічному до системи обмежень, тобто:
- Перевірка на оптимальність. Якщо всі коефіцієнти в рядку F є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю).
- Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку F.
