Симплекс-метод розв’язання задачі лінійного програмування.
Симплекс-метод розв’язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином,що кожного разу значення цільової функції зростає (за умов, що задача
має оптимальний план та кожний з опорних планів не є надмірним).Під опорним планом розуміють невід’ємний базисний розв’язок задачілінійного програмування. Нагадаємо: базисний план (розв’язок) – рішення системи обмежень, у якому всі вільні змінні дорівнюють нулю,тобто геометрично базисний план відповідає одній з вершин або граней багатокутника розв’язків.
Стереометрично ідея методу полягає у тому, що:
знаходять будь-яку вершину багатогранника розв’язків;
рухаються вздовж того з ребер, по якому функція зменшується(збільшується) до іншої вершини багатогранника розв’язків;
мінімум (максимум) функції знаходять при потраплянні у вершину, з якої у всі боки функція зростає (спадає).
Нагадаємо ще раз:
вектор розв’язків, що задовольняє всім обмеженням, називається планом;
план, що відповідає вершині багатогранника розв’язків (всівільні змінні дорівнюють нулю), називається опорним планом;
опорний план, що відповідає екстремальному значенню цільової функції, називається оптимальним планом.
- Теоретичні питання
- Загальна задача лінійного програмування (злп).
- Постановка задачі. Побудова математичної моделі. Форми представлення злп.
- Графічний метод розв’язання задачі лінійного програмування.
- Симплекс-метод розв’язання задачі лінійного програмування.
- Алгоритм симплекс-метода.
- Теорія двоїстості. Двоїста задачі лінійного програмування.
- Співвідношення між прямою та двоїстою злп.
- Транспортні моделі. Визначення транспортної моделі. Методи розв’язання транспортної задачі.
- Визначення початкового рішення транспортної задачі.
- Метод північно-західного кута.
- Метод мінімального елементу.
- Транспортні моделі. Визначення оптимального рішення.
- Сітьові моделі.
- Цілочислове програмування.