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