- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ВПМ. Математичне програмування та дослідження операцій. Основні аналітичні властивості задач ЛП. Канонічна форма. (Лекція 2) презентация
Содержание
- 1. ВПМ. Математичне програмування та дослідження операцій. Основні аналітичні властивості задач ЛП. Канонічна форма. (Лекція 2)
- 2. Тема 4: Основні аналітичні властивості задач ЛП.
- 3. Загальна постановка задачі лінійного програмування
- 4. Форми запису задач лінійного програмування За допомогою
- 5. Форми запису задач лінійного програмування За допомогою знака суми Σ.
- 6. Форми запису задач лінійного програмування Векторно-матрична форма.
- 7. Форми запису задач лінійного програмування Векторна форма.
- 8. Основні аналітичні властивості розв’язків задач лінійного програмування
- 9. Основні аналітичні властивості розв’язків задач лінійного програмування
- 10. Основні аналітичні властивості розв’язків задач лінійного програмування
- 11. Канонічна форма загальної задачі лінійного програмування
- 12. Правила переходу від загальної задачі лінійного програмування
- 13. Правила переходу від загальної задачі лінійного програмування
- 14. Правила переходу від загальної задачі лінійного програмування до канонічної
- 15. Приклад зведення задачі ЛП до канонічної форми
- 16. Приклад зведення задачі ЛП до канонічної форми Канонічна форма задачі (4)-(6):
- 17. Основні властивості розв’язків задач лінійного програмування
- 18. Основні властивості розв’язків задач лінійного програмування
- 19. Основні властивості розв’язків задач лінійного програмування
- 20. Тема 5: Лінійне програмування. Симплекс-метод План Симплекс-метод
- 21. Симплекс-метод розв'язання задач лінійного програмування Симплекс-метод
- 22. Алгоритм симплекс-методу розв'язання задач ЛП Визначення
- 23. Алгоритм симплекс-методу розв'язання задач ЛП На
- 24. Алгоритм симплекс-методу розв'язання задач ЛП Визначені
- 25. Алгоритм симплекс-методу розв'язання задач ЛП
- 26. Алгоритм симплекс-методу розв'язання задач ЛП
- 27. Алгоритм симплекс-методу розв'язання задач ЛП
- 28. Алгоритм симплекс-методу розв'язання задач ЛП
- 29. Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса
- 30. Правило прямокутника перебудови симплекс-таблиці
- 31. Варіанти розв'язку задачі ЛП симплекс-методом
- 32. Приклад розв'язання задачі ЛП симплекс-методом
- 33. Приклад розв'язання задачі ЛП симплекс-методом
- 34. Приклад розв'язання задачі ЛП симплекс-методом
- 35. Приклад розв'язання задачі ЛП симплекс-методом
- 36. Приклад розв'язання задачі ЛП симплекс-методом
- 37. Приклад розв'язання задачі ЛП симплекс-методом
- 38. Тема 6: Двоїстість у задачах лінійного програмування
- 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. Аналіз задачі на чутливість. Алгоритм 1. Формулюємо
- 70. Список літератури Основна: Зайченко Ю. П. Дослідження
Тема 4: Основні аналітичні властивості задач ЛП. Канонічна форма План Загальна постановка задачі ЛП. Форми запису задач лінійного програмування (ЛП). Основні аналітичні властивості розв’язків задач ЛП. Канонічна форма загальної задачі
Слайд 1Вища та прикладна математика
Модуль: Математичне програмування та дослідження операцій
доц. Лебідь О.Ю.
Дніпропетровськ
2016
Університет митної справи та фінансів
Слайд 2Тема 4: Основні аналітичні властивості задач ЛП. Канонічна форма
План
Загальна постановка
задачі ЛП.
Форми запису задач лінійного програмування (ЛП).
Основні аналітичні властивості розв’язків задач ЛП.
Канонічна форма загальної задачі ЛП.
Правила переходу від загальної задачі ЛП до канонічної.
Приклад зведення задачі ЛП до канонічної форми.
Властивості розв'язків задач ЛП.
Форми запису задач лінійного програмування (ЛП).
Основні аналітичні властивості розв’язків задач ЛП.
Канонічна форма загальної задачі ЛП.
Правила переходу від загальної задачі ЛП до канонічної.
Приклад зведення задачі ЛП до канонічної форми.
Властивості розв'язків задач ЛП.
Слайд 4Форми запису задач лінійного програмування
За допомогою знака суми Σ.
2. Векторно-матрична форма.
3.
Векторна форма.
Слайд 12Правила переходу від загальної задачі лінійного програмування до канонічної
Цільову функцію необхідно
максимізувати.
В системі обмежень всі праві частини невід’ємні.
Всі обмеження в системі є рівностями (явні).
Всі змінні мають невід’ємний характер.
В системі обмежень всі праві частини невід’ємні.
Всі обмеження в системі є рівностями (явні).
Всі змінні мають невід’ємний характер.
Слайд 13Правила переходу від загальної задачі лінійного програмування до канонічної
Залишкова змінна. Нерівності
типу “≤” зазвичай можна інтерпретувати як обмеження на використання деяких ресурсів. В нерівність вона входить зі знаком “+”.
Надлишкова змінна. Нерівність типу “≥” показує на те, що “щось” повинно бути не менш за деяку величину. В нерівність вона входить зі знаком “–”.
Надлишкова змінна. Нерівність типу “≥” показує на те, що “щось” повинно бути не менш за деяку величину. В нерівність вона входить зі знаком “–”.
Слайд 17Основні властивості розв’язків задач лінійного програмування
Теорема 1. Множина всіх планів
задачі лінійного програмування опукла.
Теорема 2. Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’язків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.
Теорема 2. Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’язків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.
Слайд 20Тема 5: Лінійне програмування. Симплекс-метод
План
Симплекс-метод розв'язання задач ЛП.
Алгоритм симплекс-методу розв'язання задач
ЛП.
Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса.
Правило прямокутника перебудови симплексної таблиці.
Варіанти розв'язку задачі ЛП симплекс-методом.
Приклад розв'язання задачі ЛП симплекс-методом.
Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса.
Правило прямокутника перебудови симплексної таблиці.
Варіанти розв'язку задачі ЛП симплекс-методом.
Приклад розв'язання задачі ЛП симплекс-методом.
Слайд 21Симплекс-метод розв'язання задач лінійного програмування
Симплекс-метод – це поетапна обчислювальна процедура,
в основу якої покладено принцип послідовного покращення значень цільової функції переходом від одного опорного плану задачі лінійного програмування до іншого.
Алгоритм симплекс-методу завжди починається з деякого опорного розв’язку (плану) і потім намагається знайти інший опорний план, який покращує значення цільової функції.
Алгоритм симплекс-методу завжди починається з деякого опорного розв’язку (плану) і потім намагається знайти інший опорний план, який покращує значення цільової функції.
Слайд 22Алгоритм симплекс-методу розв'язання задач ЛП
Визначення початкового опорного плану задачі ЛП.
Побудова
симплексної таблиці.
Перевірка опорного плану на оптимальність за допомогою оцінок. Якщо план не оптимальний, то переходять до нового опорного плану або встановлюють, що оптимального плану не існує.
Перехід до нового опорного плану задачі, тобто розрахунок нової симплексної таблиці.
Повторення дій, починаючи з п. 3.
Перевірка опорного плану на оптимальність за допомогою оцінок. Якщо план не оптимальний, то переходять до нового опорного плану або встановлюють, що оптимального плану не існує.
Перехід до нового опорного плану задачі, тобто розрахунок нової симплексної таблиці.
Повторення дій, починаючи з п. 3.
Слайд 23Алгоритм симплекс-методу розв'язання задач ЛП
На етапі визначення початкового опорного плану
задачі ЛП, після її зведення до канонічної форми, шукаємо m одиничних лінійно незалежних векторів, які становлять базис m-вимірного простору. Можливі такі випадки:
є необхідна кількість одиничних векторів, тоді початковий опорний план визначається безпосередньо без додаткових дій;
у системі обмежень немає необхідної кількості одиничних незалежних векторів. Тоді для побудови першого опорного плану застосовують метод штучного базису.
є необхідна кількість одиничних векторів, тоді початковий опорний план визначається безпосередньо без додаткових дій;
у системі обмежень немає необхідної кількості одиничних незалежних векторів. Тоді для побудови першого опорного плану застосовують метод штучного базису.
Слайд 24Алгоритм симплекс-методу розв'язання задач ЛП
Визначені одиничні лінійно незалежні вектори утворюють
базис, і змінні задачі, що відповідають їм, називають базисними, а всі інші змінні – вільними.
Слайд 29Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса
1. Розв’язувальний (напрямний) рядок необхідно
поділити на розв’язувальний елемент і здобуті числа записати у відповідний рядок симплексної таблиці.
2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
5. Усі інші елементи наступної симплекс-таблиці розраховують за правилом прямокутника.
2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
5. Усі інші елементи наступної симплекс-таблиці розраховують за правилом прямокутника.
Слайд 38Тема 6: Двоїстість у задачах лінійного програмування
План
Правила побудови двоїстої
задачі лінійного програмування.
Приклад побудови двоїстої задачі лінійного програмування.
Основні теореми двоїстості.
Економічний зміст основних теорем двоїстості.
Аналіз задачі на чутливість.
Приклад побудови двоїстої задачі лінійного програмування.
Основні теореми двоїстості.
Економічний зміст основних теорем двоїстості.
Аналіз задачі на чутливість.
Слайд 39Постановка задачі лінійного програмування (пряма задача)
Кожній задачі ЛП відповідає двоїста, що
формується за допомогою певних правил безпосередньо з умови прямої задачі.
Слайд 44Правила побудови двоїстої задачі лінійного програмування
1. Кожному обмеженню прямої
задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обме-ження двоїстої задачі, причому кількість обмежень дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення, то цільова фун-кція двоїстої задачі – на визначення найменшого значення, і навпаки.
2. Кожній змінній прямої задачі відповідає обме-ження двоїстої задачі, причому кількість обмежень дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення, то цільова фун-кція двоїстої задачі – на визначення найменшого значення, і навпаки.
Слайд 45Правила побудови двоїстої задачі лінійного програмування
4. Коефіцієнтами при
змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця, що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпцями, а стовпців – рядками.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця, що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпцями, а стовпців – рядками.
Слайд 46Правила побудови двоїстої задачі лінійного програмування
7. Якщо змінній
двоїстої задачі відповідає обмеження прямої задачі у формі рівняння, то така змінна вільна за знаком. Якщо відповідає нерівність, тоді змінна двоїстої задачі невід’ємна.
8. Якщо змінна прямої задачі вільна за знаком, то відповідне обмеження двоїстої задачі має форму рівняння. Якщо змінна невід’ємна, то відповідне обмеження двоїстої задачі має форму нерівності.
8. Якщо змінна прямої задачі вільна за знаком, то відповідне обмеження двоїстої задачі має форму рівняння. Якщо змінна невід’ємна, то відповідне обмеження двоїстої задачі має форму нерівності.
Слайд 56Приклад (застосування наслідку
з І теореми двоїстості)
Ціна одиниці
продукції видів А, В і С дорівнює 90 дол., 110 дол. та 150 дол. відповідно.
Слайд 69Аналіз задачі на чутливість. Алгоритм
1. Формулюємо математичну модель задачі лінійного програмування
та двоїсту до неї.
2. Записуємо оптимальні плани прямої та двоїстої задач і робимо їх економічний аналіз.
3. Визначаємо статус ресурсів прямої задачі та інтер-вали стійкості двоїстих оцінок відносно запасів дефіцитних ресурсів.
4. Визначаємо план виробництва продукції та зміну загального доходу підприємства, якщо збільшувати запас кожного ресурсу.
5. Визначаємо рентабельність кожного виду продукції, що виготовляється на підприємстві.
6. Розраховуємо інтервали можливої зміни ціни оди-ниці кожного виду продукції.
2. Записуємо оптимальні плани прямої та двоїстої задач і робимо їх економічний аналіз.
3. Визначаємо статус ресурсів прямої задачі та інтер-вали стійкості двоїстих оцінок відносно запасів дефіцитних ресурсів.
4. Визначаємо план виробництва продукції та зміну загального доходу підприємства, якщо збільшувати запас кожного ресурсу.
5. Визначаємо рентабельність кожного виду продукції, що виготовляється на підприємстві.
6. Розраховуємо інтервали можливої зміни ціни оди-ниці кожного виду продукції.
Слайд 70Список літератури
Основна:
Зайченко Ю. П. Дослідження операцій : підручник / Ю. П. Зайченко. –
К. : ВІПОЛ, 2000.
Исследование операций в экономике :учеб. пособие / под. ред. Н. Ш. Кремера. – М. : Банки и биржи; ЮНИТИ, 1999.
Таха Х. Введение в исследование операций / Х. Таха. – М. : Вильямс, 2001.
Ульянченко О. В. Досліждення операцій в економіці / О. В. Ульянченко. – Х. : Гриф, 2003.
Додаткова:
Вітлінський В. В. Математичне програмування / В. В. Вітлінський, С. І. Наконечний, Т. О. Терещенко. – К., 2001.
Кузнецов А. В. Математическое программирование / А. В. Кузнецов и др. – М.: Высшая школа, 1994.
Исследование операций в экономике. Учеб. пособие для вузов/ Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридмак; Под. ред. проф. Н. Ш. Кремера. – М. : ЮНИТИ, 2004. – 407с.
Бережная Е. В. Математические методы моделирования экономических систем / Е. В. Бережная, В. И. Бережной. – М., 2002.
Экономико-математические методы и прикладные модели / В. В. Федосеев, А. Н. Гармаш, Д. М. Дайнбегов и др. – М., 1999.
Исследование операций в экономике :учеб. пособие / под. ред. Н. Ш. Кремера. – М. : Банки и биржи; ЮНИТИ, 1999.
Таха Х. Введение в исследование операций / Х. Таха. – М. : Вильямс, 2001.
Ульянченко О. В. Досліждення операцій в економіці / О. В. Ульянченко. – Х. : Гриф, 2003.
Додаткова:
Вітлінський В. В. Математичне програмування / В. В. Вітлінський, С. І. Наконечний, Т. О. Терещенко. – К., 2001.
Кузнецов А. В. Математическое программирование / А. В. Кузнецов и др. – М.: Высшая школа, 1994.
Исследование операций в экономике. Учеб. пособие для вузов/ Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридмак; Под. ред. проф. Н. Ш. Кремера. – М. : ЮНИТИ, 2004. – 407с.
Бережная Е. В. Математические методы моделирования экономических систем / Е. В. Бережная, В. И. Бережной. – М., 2002.
Экономико-математические методы и прикладные модели / В. В. Федосеев, А. Н. Гармаш, Д. М. Дайнбегов и др. – М., 1999.
