ВМП. Математичне програмування та дослідження операцій. Метод штучного базису М-метод. (Лекція 3)

Тема 7: Метод штучного базису М-метод

План

Умова застосування М-методу
Правила

Умова застосування М-методу

Під час розв’язування задачі лінійної оптимізації симплекс-методом можлива ситуація,

Ідея застосування М-методу

Ідея полягає в тому, що відсутні одиничні вектори можна

Правила введення штучних змінних

У цільовій функції задачі лінійної оптимізації штучні змінні

Алгоритм М-методу

Значення оцінок опорного плану в симплексній таблиці складаються з двох

Алгоритм М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Приклад розв′язання задачі за допомогою М-методу

Тема 8: Методика розв'язування транспортних задач

План

Постановка транспортної задачі

Постановка транспортної задачі

Транспортні задачі – спеціальний клас задач лінійної оптимізації.

Постановка транспортної задачі

Постановка транспортної задачі

Математична постановка транспортної задачі

Основні поняття транспортної задачі

Умова існування розв'язку транспортної задачі

Алгоритм розв'язання транспортної задачі

Визначення типу транспортної задачі (відкрита чи закрита).
Побудова початкового

Алгоритм розв'язання транспортної задачі (визначення типу задачі)

Методи пошуку початкового опорного плану

Метод північно-західного кута пошуку початкового опорного плану

Перевірка початкового опорного плану

Метод мінімальної вартості пошуку початкового опорного плану

Ідея методу мінімальної вартості полягає

Метод Фогеля пошуку початкового опорного плану

На кожному кроці визначають різницю між

Метод потенціалів пошуку оптимального плану

Метод потенціалів пошуку оптимального плану

Метод потенціалів пошуку оптимального плану

Метод потенціалів пошуку оптимального плану

Правила побудови циклу перерозподілу вантажу

Тема 9: Задачі цілочислового лінійного програмування

План

Постановка задачі цілочислового лінійного

Задачі цілочислового лінійного програмування

Постановка задачі цілочислового лінійного програмування

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

Ідея методів відтинань

Ідея комбінаторних методів

Ідея задачі на призначення

Математична постановка задачі на призначення

Задача на призначення

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

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

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

Приклад розв’язання задачі на призначення на мінімум

Приклад розв’язання задачі на призначення на мінімум

Приклад розв’язання задачі на призначення на максимум

Приклад розв’язання задачі на призначення на максимум

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

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

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

Геометрична інтерпретація методу Гоморі

Приклад розв’язання задачі ЦЛП методом Гоморі

Приклад розв’язання задачі ЦЛП методом Гоморі

Приклад розв’язання задачі ЦЛП методом Гоморі

Приклад розв’язання задачі ЦЛП методом Гоморі

Схема методу гілок та меж

Схема методу гілок та меж

Схема методу гілок та меж

Розгалуження методу гілок та меж

Схема методу гілок та меж

Геометрична інтерпретація розгалуження

Геометрична інтерпретація розгалуження

Алгоритм методу гілок та меж

Алгоритм методу гілок та меж

Алгоритм методу гілок та меж

Графічний метод гілок та меж

Результати застосування графічного методу гілок та меж

Приклад

Приклад

Приклад

Приклад