ВПМ. Математичне програмування та дослідження операцій. Основні аналітичні властивості задач ЛП. Канонічна форма. (Лекція 2)

Содержание

Слайд 2

Тема 4: Основні аналітичні властивості задач ЛП. Канонічна форма План Загальна

Тема 4: Основні аналітичні властивості задач ЛП. Канонічна форма

План

Загальна постановка

задачі ЛП.
Форми запису задач лінійного програмування (ЛП).
Основні аналітичні властивості розв’язків задач ЛП.
Канонічна форма загальної задачі ЛП.
Правила переходу від загальної задачі ЛП до канонічної.
Приклад зведення задачі ЛП до канонічної форми.
Властивості розв'язків задач ЛП.
Слайд 3

Загальна постановка задачі лінійного програмування

Загальна постановка задачі лінійного програмування

Слайд 4

Форми запису задач лінійного програмування За допомогою знака суми Σ. 2. Векторно-матрична форма. 3. Векторна форма.

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

За допомогою знака суми Σ.
2. Векторно-матрична форма.
3.

Векторна форма.
Слайд 5

Форми запису задач лінійного програмування За допомогою знака суми Σ.

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

За допомогою знака суми Σ.

Слайд 6

Форми запису задач лінійного програмування Векторно-матрична форма.

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

Векторно-матрична форма.

Слайд 7

Форми запису задач лінійного програмування Векторна форма.

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

Векторна форма.

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

Канонічна форма загальної задачі лінійного програмування

Канонічна форма загальної задачі лінійного програмування

Слайд 12

Правила переходу від загальної задачі лінійного програмування до канонічної Цільову функцію

Правила переходу від загальної задачі лінійного програмування до канонічної

Цільову функцію необхідно

максимізувати.
В системі обмежень всі праві частини невід’ємні.
Всі обмеження в системі є рівностями (явні).
Всі змінні мають невід’ємний характер.
Слайд 13

Правила переходу від загальної задачі лінійного програмування до канонічної Залишкова змінна.

Правила переходу від загальної задачі лінійного програмування до канонічної

Залишкова змінна. Нерівності

типу “≤” зазвичай можна інтерпретувати як обмеження на використання деяких ресурсів. В нерівність вона входить зі знаком “+”.
Надлишкова змінна. Нерівність типу “≥” показує на те, що “щось” повинно бути не менш за деяку величину. В нерівність вона входить зі знаком “–”.
Слайд 14

Правила переходу від загальної задачі лінійного програмування до канонічної

Правила переходу від загальної задачі лінійного програмування до канонічної

Слайд 15

Приклад зведення задачі ЛП до канонічної форми

Приклад зведення задачі ЛП до канонічної форми

Слайд 16

Приклад зведення задачі ЛП до канонічної форми Канонічна форма задачі (4)-(6):

Приклад зведення задачі ЛП до канонічної форми

Канонічна форма задачі (4)-(6):

Слайд 17

Основні властивості розв’язків задач лінійного програмування Теорема 1. Множина всіх планів

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

Теорема 1. Множина всіх планів

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

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

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

Слайд 19

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

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

Слайд 20

Тема 5: Лінійне програмування. Симплекс-метод План Симплекс-метод розв'язання задач ЛП. Алгоритм

Тема 5: Лінійне програмування. Симплекс-метод

План

Симплекс-метод розв'язання задач ЛП.
Алгоритм симплекс-методу розв'язання задач

ЛП.
Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса.
Правило прямокутника перебудови симплексної таблиці.
Варіанти розв'язку задачі ЛП симплекс-методом.
Приклад розв'язання задачі ЛП симплекс-методом.
Слайд 21

Симплекс-метод розв'язання задач лінійного програмування Симплекс-метод – це поетапна обчислювальна процедура,

Симплекс-метод розв'язання задач лінійного програмування

Симплекс-метод – це поетапна обчислювальна процедура,

в основу якої покладено принцип послідовного покращення значень цільової функції переходом від одного опорного плану задачі лінійного програмування до іншого.
Алгоритм симплекс-методу завжди починається з деякого опорного розв’язку (плану) і потім намагається знайти інший опорний план, який покращує значення цільової функції.
Слайд 22

Алгоритм симплекс-методу розв'язання задач ЛП Визначення початкового опорного плану задачі ЛП.

Алгоритм симплекс-методу розв'язання задач ЛП

Визначення початкового опорного плану задачі ЛП.
Побудова

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

Алгоритм симплекс-методу розв'язання задач ЛП На етапі визначення початкового опорного плану

Алгоритм симплекс-методу розв'язання задач ЛП

На етапі визначення початкового опорного плану

задачі ЛП, після її зведення до канонічної форми, шукаємо m одиничних лінійно незалежних векторів, які становлять базис m-вимірного простору. Можливі такі випадки:
є необхідна кількість одиничних векторів, тоді початковий опорний план визначається безпосередньо без додаткових дій;
у системі обмежень немає необхідної кількості одиничних незалежних векторів. Тоді для побудови першого опорного плану застосовують метод штучного базису.
Слайд 24

Алгоритм симплекс-методу розв'язання задач ЛП Визначені одиничні лінійно незалежні вектори утворюють

Алгоритм симплекс-методу розв'язання задач ЛП

Визначені одиничні лінійно незалежні вектори утворюють

базис, і змінні задачі, що відповідають їм, називають базисними, а всі інші змінні – вільними.
Слайд 25

Алгоритм симплекс-методу розв'язання задач ЛП

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 26

Алгоритм симплекс-методу розв'язання задач ЛП

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 27

Алгоритм симплекс-методу розв'язання задач ЛП

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 28

Алгоритм симплекс-методу розв'язання задач ЛП

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 29

Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса 1. Розв’язувальний (напрямний) рядок необхідно

Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса

1. Розв’язувальний (напрямний) рядок необхідно

поділити на розв’язувальний елемент і здобуті числа записати у відповідний рядок симплексної таблиці.
2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
5. Усі інші елементи наступної симплекс-таблиці розраховують за правилом прямокутника.
Слайд 30

Правило прямокутника перебудови симплекс-таблиці

Правило прямокутника перебудови симплекс-таблиці

Слайд 31

Варіанти розв'язку задачі ЛП симплекс-методом

Варіанти розв'язку задачі ЛП симплекс-методом

Слайд 32

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 33

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 34

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 35

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 36

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 37

Приклад розв'язання задачі ЛП симплекс-методом

Приклад розв'язання задачі ЛП симплекс-методом

Слайд 38

Тема 6: Двоїстість у задачах лінійного програмування План Правила побудови двоїстої

Тема 6: Двоїстість у задачах лінійного програмування

План

Правила побудови двоїстої

задачі лінійного програмування.
Приклад побудови двоїстої задачі лінійного програмування.
Основні теореми двоїстості.
Економічний зміст основних теорем двоїстості.
Аналіз задачі на чутливість.
Слайд 39

Постановка задачі лінійного програмування (пряма задача) Кожній задачі ЛП відповідає двоїста,

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

Кожній задачі ЛП відповідає двоїста, що

формується за допомогою певних правил безпосередньо з умови прямої задачі.
Слайд 40

Економічний зміст прямої задачі

Економічний зміст прямої задачі

Слайд 41

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

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

Слайд 42

Економічний зміст двоїстої задачі

Економічний зміст двоїстої задачі

Слайд 43

Постановка пари двоїстих задач у матрично-векторній формі

Постановка пари двоїстих задач у матрично-векторній формі

Слайд 44

Правила побудови двоїстої задачі лінійного програмування 1. Кожному обмеженню прямої задачі

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

1. Кожному обмеженню прямої задачі

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

Правила побудови двоїстої задачі лінійного програмування 4. Коефіцієнтами при змінних у

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

4. Коефіцієнтами при змінних у

цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця, що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпцями, а стовпців – рядками.
Слайд 46

Правила побудови двоїстої задачі лінійного програмування 7. Якщо змінній двоїстої задачі

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

7. Якщо змінній двоїстої задачі

відповідає обмеження прямої задачі у формі рівняння, то така змінна вільна за знаком. Якщо відповідає нерівність, тоді змінна двоїстої задачі невід’ємна.
8. Якщо змінна прямої задачі вільна за знаком, то відповідне обмеження двоїстої задачі має форму рівняння. Якщо змінна невід’ємна, то відповідне обмеження двоїстої задачі має форму нерівності.
Слайд 47

Схема побудови двоїстої задачі лінійного програмування

Схема побудови двоїстої задачі лінійного програмування

Слайд 48

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

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

Слайд 49

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

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

Слайд 50

Основні теореми двоїстості

Основні теореми двоїстості

Слайд 51

Основні теореми двоїстості (І теорема двоїстості)

Основні теореми двоїстості (І теорема двоїстості)

Слайд 52

Економічний зміст І теореми двоїстості

Економічний зміст І теореми двоїстості

Слайд 53

Економічний зміст І теореми двоїстості

Економічний зміст І теореми двоїстості

Слайд 54

Економічний зміст І теореми двоїстості

Економічний зміст І теореми двоїстості

Слайд 55

Основні теореми двоїстості (наслідок з І теореми двоїстості)

Основні теореми двоїстості (наслідок з І теореми двоїстості)

Слайд 56

Приклад (застосування наслідку з І теореми двоїстості) Ціна одиниці продукції видів

Приклад (застосування наслідку з І теореми двоїстості)

Ціна одиниці продукції видів А,

В і С дорівнює 90 дол., 110 дол. та 150 дол. відповідно.
Слайд 57

Приклад (застосування наслідку з І теореми двоїстості)

Приклад (застосування наслідку з І теореми двоїстості)

Слайд 58

Приклад (застосування наслідку з І теореми двоїстості)

Приклад (застосування наслідку з І теореми двоїстості)

Слайд 59

Приклад (застосування наслідку з І теореми двоїстості)

Приклад (застосування наслідку з І теореми двоїстості)

Слайд 60

Аналіз двоїстих оцінок

Аналіз двоїстих оцінок

Слайд 61

Основні теореми двоїстості (ІІ теорема двоїстості)

Основні теореми двоїстості (ІІ теорема двоїстості)

Слайд 62

Економічний зміст ІІ теореми двоїстості

Економічний зміст ІІ теореми двоїстості

Слайд 63

Економічний зміст ІІ теореми двоїстості

Економічний зміст ІІ теореми двоїстості

Слайд 64

Наслідок ІІ теореми двоїстості

Наслідок ІІ теореми двоїстості

Слайд 65

Приклад (застосування наслідку з ІІ теореми двоїстості)

Приклад (застосування наслідку з ІІ теореми двоїстості)

Слайд 66

Основні теореми двоїстості (ІІІ теорема двоїстості)

Основні теореми двоїстості (ІІІ теорема двоїстості)

Слайд 67

Економічний зміст ІІІ теореми двоїстості

Економічний зміст ІІІ теореми двоїстості

Слайд 68

Аналіз задачі на чутливість

Аналіз задачі на чутливість

Слайд 69

Аналіз задачі на чутливість. Алгоритм 1. Формулюємо математичну модель задачі лінійного

Аналіз задачі на чутливість. Алгоритм

1. Формулюємо математичну модель задачі лінійного програмування

та двоїсту до неї.
2. Записуємо оптимальні плани прямої та двоїстої задач і робимо їх економічний аналіз.
3. Визначаємо статус ресурсів прямої задачі та інтер-вали стійкості двоїстих оцінок відносно запасів дефіцитних ресурсів.
4. Визначаємо план виробництва продукції та зміну загального доходу підприємства, якщо збільшувати запас кожного ресурсу.
5. Визначаємо рентабельність кожного виду продукції, що виготовляється на підприємстві.
6. Розраховуємо інтервали можливої зміни ціни оди-ниці кожного виду продукції.
- Предыдущая
ВПМ. Математичне програмування та дослідження операцій. Предмет та основні завдання математичного програмування та ДО. (Лекція1)
Следующая -
ВМП. Математичне програмування та дослідження операцій. Метод штучного базису М-метод. (Лекція 3)

Похожие презентации

Тема 6
Разработка техпроцесса восстановления зубчатого колеса ткацкого станка
Постреляционные, объектные модели данных
Конгресс Соединенных Штатов Америки
Экология
Электротехника и электроника. Основные определения
Іменник
Физиология эндокринной системы
Осанка. Дефекты осанки. Упражнения для формирования правильной осанки
ПСОРИАТИЧЕСКИЙ АРТРИТ Врач-дерматовенеролог Махмуд Асиф
Tema_4
Җәя кую очраклары
Консерватизм как политическая идеология
Мир развлечений
Средние величины и показатели вариации
Презентация "Сбереженная капля море спасет" - скачать презентации по Экономике
Профессиограмма ЮРИСТА
Особенности распространения возбуждения в ЦНС
Александр Трифонович Твардовский. Русский советский писатель и поэт, журналист, военный корреспондент
Развитие науки и образования в России в начале 18 века
3D-сканеры и 3D-принтеры
Демократия. Местное самоуправление в РФ
Столицы стран мира
Проект организации и планирования выполнения тахеометрической съемки для последующего строительства водоограждающей дамбы
Улс төрийн нам Улс төрийн нам
Физиотерапия Область клинической медицины, изучающая лечебные свойства физических факторов и разрабатывающая методы их п
НОЦИЦЕПЦИЯ Рецепция боли
Анализ рядов динамики
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть