Page 13 - 4719

ПРАКТИЧНЕ ЗАНЯТТЯ 3

Тема: СИМПЛЕКС МЕТОД РОЗВ’ЯЗКУ ЗАДАЧІ
ЛІНІЙНОГО ПРОГРАМУВАННЯ

Мета заняття: навчити студентів визначати оптимальний
розв’язок задачі лінійного програмування симплекс
методом

1.Основні теоретичні положення

Симплекс - алгоритм метод – універсальний метод для
будь-якої задачі ЛП. Він передбачає в результаті ітераційного
процесу ( кожна ітерація – це перехід до нового допустимого
розв’язку) знаходження оптимального розв’язку.
Допустимим розв’язком ОЗЛП називається будь-яка
сукупність невід’ємних задач x 1, x 2,...., x е яка задовольняє
обмеження задачі.
Оптимальним називається той із допустимих розв’язків,
який обертає в мінімум ( максимум) функцію f(X).
Мета розв’язування задачі ЛП полягає в знаходженні
оптимального розв’язку, якщо такий існує.
Ідея симплекс-алгоритму полягає в тому, що
здійснюється перебір допустимих розв’язків. Спочатку
знаходиться один із таких розв’язків – координата вершини
ОДР( адже оптимальний розв’язок слід шукати серед вершин
ОДР). Такий розв’язок називають опорним або опорним
планом, а далі шляхом послідовних цілеспрямованих проб
визначається координати екстремуму z(х) або оптимальний
план (оптимальний розв’язок). Таким чином, симплекс-
алгоритм складається з двох частин: визначення опорного
плану та визначення плану оптимального.
Симплекс метод розв’язку
Умови застосування методу:
1. Значення всіх змінних додатні.
• Якщо якесь х<0, тоді вводять дві нові додатні змінні:
x=y1-y2
2. Всі обмеження записані як рівності з додатною
правою частиною.
• Для зміни знаку домножим на -1 (> мін. на <).
12