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

Содержание

Тема 7: Метод штучного базису М-метод План Умова застосування М-методу Правила введення штучних змінних. Алгоритм М-методу. Приклад.

Слайд 1Вища та прикладна математика Модуль: Математичне програмування та дослідження операцій
доц. Лебідь О.Ю.
Дніпропетровськ
2016

Університет

митної справи та фінансів

Слайд 2Тема 7: Метод штучного базису М-метод
План
Умова застосування М-методу
Правила

введення штучних змінних.
Алгоритм М-методу.
Приклад.

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

коли при визначенні початкового опорного плану в системі обмежень немає необхідної кількості одиничних лінійно-незалежних векторів.

Для побудови початкового плану застосовують метод штучного базису.

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

дістати, увівши до відповідних обмежень деякі змінні з коефіцієнтом +1, що називаються штучними.

Слайд 5Правила введення штучних змінних
У цільовій функції задачі лінійної оптимізації штучні змінні

мають коефіцієнт

–М (для задачі на максимум),

де М – досить велике додатне число.


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

частин: одна містить М, а інша – просто число. Тому розбиваємо рядок оцінок у таблиці на два: у перший записуємо просто число, а в другий – коефіцієнт при М.

Якщо опорний план не є оптимальним, тоді при визначенні змінної, яка буде вводитись до базису, спочатку дивимось на другий рядок оцінок. Коли в ньому всі оцінки відповідають умові оптимальності, тоді переглядаємо перший рядок оцінок.

Слайд 7Алгоритм М-методу


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


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


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


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


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


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


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


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


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


Слайд 17Тема 8: Методика розв'язування транспортних задач
План
Постановка транспортної задачі

Умова існування розв'язку транспор-тної задачі
Алгоритм розв'язування транспортної задачі за загальним критерієм вартості
Методи пошуку опорного початкового плану
Метод потенціалів для розв'язування транспортної задачі

Слайд 18Постановка транспортної задачі
Транспортні задачі – спеціальний клас задач

лінійної оптимізації. Ці задачі найчастіше описують перевезення деякого товару з пункту відправлення (постачальників) до пункту призначення (споживачів).
Призначення транспортної задачі – визначення об’єму перевезень з пунктів відправлення до пунктів призначення з мінімальною вартістю перевезень. При цьому повинні враховуватися обмеження, які накладені на об’єм вантажу, який є у пунктах відправлення (пропозиція), та обмеження, які враховують необхідність вантажу в пунктах призначення (попит).

Слайд 19Постановка транспортної задачі


Слайд 20Постановка транспортної задачі


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


Слайд 22Основні поняття транспортної задачі


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


Слайд 24Алгоритм розв'язання транспортної задачі
Визначення типу транспортної задачі (відкрита чи закрита).
Побудова початкового

опорного плану транспортної задачі.
Перевірка плану транспортної задачі на оптимальність.
Якщо умова оптимальності виконується, то маємо оптимальний розв’язок транспортної задачі. Якщо ж умова оптимальності не виконується, необхідно перейти до наступного опорного плану та перейти на пункт 3.

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


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


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


Слайд 28Перевірка початкового опорного плану


Слайд 29Метод мінімальної вартості пошуку початкового опорного плану
Ідея методу мінімальної вартості полягає

в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції.
Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами.

Слайд 30Метод Фогеля пошуку початкового опорного плану
На кожному кроці визначають різницю між

двома найменшими вартостями в кожному рядку і стовпці транспортної таблиці.
Ці різниці записують у спеціально відведених місцях таблиці.
Серед усіх різниць вибирають найбільшу і у відповідному рядку чи стовпці заповнюють клітинку з найменшою вартістю.
Якщо ж однакових найбільших різниць кілька, то вибирають будь-який відповідний рядок або стовпець.
Коли залишається незаповненим лише один рядок або стовпець, то обчислення різниць припиняють, а таблицю продовжують заповнювати за методом мінімальної вартості.

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


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


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


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


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


Слайд 36Тема 9: Задачі цілочислового лінійного програмування
План
Постановка задачі цілочислового лінійного

програмування (ЦЛП)
Методи розв'язування задач ЦЛП
Задача на призначення
Алгоритм угорського методу розв'язання задачі на призначення
Метод Гоморі розв'язування задач ЦЛП
Метод гілок та меж розв'язування задач ЦЛП

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


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


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


Слайд 40Ідея методів відтинань


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


Слайд 42Ідея задачі на призначення


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


Слайд 44Задача на призначення


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Слайд 72Приклад


Слайд 73Приклад


Слайд 74Приклад


Слайд 75Приклад


Слайд 76Список літератури
Основна:
Зайченко Ю. П. Дослідження операцій : підручник / Ю. П. Зайченко. –

К. : ВІПОЛ, 2000.
Таха Х. Введение в исследование операций / Х. Таха. – М. : Вильямс, 2001.
Ульянченко О. В. Дослідження операцій в економіці / О. В. Ульянченко. – Х. : Гриф, 2003.
Додаткова:
Вітлінський В. В. Математичне програмування / В. В. Вітлінський, С. І. Наконечний, Т. О. Терещенко. – К., 2001.
Кузнецов А. В. Математическое программирование / А. В. Кузнецов и др. – М.: Высшая школа, 1994.

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика