© проф. Триус Ю.В.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Задача лінійного програмування та деякі методи їх розв’язування презентация
Содержание
- 1. Задача лінійного програмування та деякі методи їх розв’язування
- 2. Питання: Загальна задача лiнiйного програмування та її
- 3. 1. Загальна задача лiнiйного програмування та її
- 4. Загальна задача лінійного програмування
- 5. Класифікація задач лінійного програмування
- 6. Основна задача лінійного програмування
- 7. Перша стандартна задача лінійного
- 8. Друга стандартна задача лінійного
- 9. Канонічна задача лінійного програмування
- 10. Економічна постановка задачі Підприємство може здійснювати
- 11. Таблиця вхідних даних Приклад 1. Завдання:
- 12. Математична модель задачі з прикладу 1
- 13. Канонічна форма математичної моделі задачі з прикладу 1
- 14. Розв’язок задачі за допомогою пакету MathCad
- 15. Висновок: Оптимальний план використання
- 16. 2. Поняття плану, опорного плану, невиродженого опорного
- 17. Введемо позначення: 2. Поняття плану, опорного плану,
- 18. 2. Поняття плану, опорного плану, невиродженого опорного
- 19. 2. Поняття плану, опорного плану, невиродженого опорного
- 20. 2. Поняття плану, опорного плану, невиродженого
- 21. 3. Властивості розв’язків задачі лінійного програмування
- 22. 3. Властивості розв’язків задачі лінійного програмування Теорема 1.
- 23. 3. Властивості розв’язків задачі лінійного програмування Нехай лінійна
- 24. 3. Властивості розв’язків задачі лінійного програмування Теорема 3
- 25. 4. Геометричний метод розв’язування задачі лінійного програмування
- 26. 4. Геометричний метод розв’язування задачі лінійного програмування α
- 27. 4. Геометричний метод розв’язування задачі лінійного програмування
- 28. 4. Геометричний метод розв’язування задачі лінійного програмування
- 29. 4. Геометричний метод розв’язування задачі лінійного програмування
- 30. 4. Геометричний метод розв’язування задачі лінійного програмування
- 31. 4. Геометричний метод розв’язування задачі лінійного програмування
- 32. 4. Геометричний метод розв’язування задачі лінійного програмування
- 33. 4. Геометричний метод розв’язування задачі лінійного програмування
- 34. 4. Геометричний метод розв’язування задачі лінійного програмування
- 35. 4. Геометричний метод розв’язування задачі лінійного програмування
- 36. 4. Геометричний метод розв’язування задачі лінійного
- 37. 4. Геометричний метод розв’язування задачі
- 42. 4. Геометричний метод розв’язування задачі лінійного
- 43. 4. Геометричний метод розв’язування задачі лінійного
- 44. Ваші запитання 8(0472) 730271 herasymenkoinna@gmail.com Дякую за увагу!
Питання: Загальна задача лiнiйного програмування та її подання в канонічній формі. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі лінійного програмування. Властивості розв’язків задачі лінійного програмування. Геометричний метод розв’язування
Слайд 1Черкаський державний технологічний університет
Дисципліна
“Інформаційні технології аналізу систем”
Лекція 8-9
Викладач: Герасименко І. В.
ТЕМА:
“Задача лінійного програмування та деякі методи їх розв’язування"
Слайд 2Питання:
Загальна задача лiнiйного програмування та її подання в канонічній формі.
Поняття плану,
опорного плану, невиродженого опорного плану, оптимального плану задачі лінійного програмування.
Властивості розв’язків задачі лінійного програмування.
Геометричний метод розв’язування задачі лінійного програмування.
Властивості розв’язків задачі лінійного програмування.
Геометричний метод розв’язування задачі лінійного програмування.
Слайд 31. Загальна задача лiнiйного програмування та її подання в канонічній формі
Задача
однокритеріальної оптимізації
в якій цільова функція лiнiйна i множина X визначається системою лiнiйних рiвнянь i(або) нерiвностей називається задачею лiнiйного програмування.
Слайд 4
Загальна задача лінійного програмування
де
- задані дійсні числа.
(1)
1. Загальна задача
лiнiйного програмування та її подання в канонічній формі
Слайд 6
Основна задача лінійного програмування
де
- задані дійсні числа.
(2)
1. Загальна задача
лiнiйного програмування та її подання в канонічній формі
Слайд 7
Перша стандартна задача лінійного програмування
де
- задані дійсні числа.
(3)
1. Загальна
задача лiнiйного програмування та її подання в канонічній формі
Слайд 8
Друга стандартна задача лінійного програмування
де
- задані дійсні числа.
(3’)
1. Загальна
задача лiнiйного програмування та її подання в канонічній формі
Слайд 9
Канонічна задача лінійного програмування
де
- задані дійсні числа.
(4)
1. Загальна задача
лiнiйного програмування та її подання в канонічній формі
Слайд 10Економічна постановка задачі
Підприємство може здійснювати випуск продукції за трьома технологіями Т1,
Т2 ,Т3. Види і норми витрат ресурсiв на один виріб продукції, продуктивність кожної технології та загальна кiлькiсть наявних ресурсiв наведено в таблицi.
Визначити скiльки часу необхiдно працювати за кожною з технологій, щоб обсяг виробництва підприємством продукції за наявних умов був найбільшим.
Визначити скiльки часу необхiдно працювати за кожною з технологій, щоб обсяг виробництва підприємством продукції за наявних умов був найбільшим.
Приклад 1.
Слайд 11Таблиця вхідних даних
Приклад 1.
Завдання: побудувати математичну модель поставленої задачі, визначити
до якого класу задач математичного програмування вона належить, записати математичну модель у канонічному вигляді, розв”язати задачу за допомогою пакету MathCad.
20000
5000
20000
Слайд 12Математична модель задачі з прикладу 1
де
– кількість годин роботи
за Тi-ою технологією (i=1,2,3).
Слайд 15Висновок:
Оптимальний план використання підприємством технологій для випуску продукції:
за
технологією Т1 – 0 годин,
за технологією Т2 – 0 годин,
за технологією Т3 – 47,6 години.
При цьому максимальний обсяг випуску продукції підприємством становить
1666 виробів.
за технологією Т2 – 0 годин,
за технологією Т3 – 47,6 години.
При цьому максимальний обсяг випуску продукції підприємством становить
1666 виробів.
Слайд 162. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі
лінійного програмування
Розглянемо задачу лінійного програмування, записану в канонічній формі:
,
,
,
,
(5)
(6)
(7)
Слайд 17Введемо позначення:
2. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану
задачі лінійного програмування
Слайд 182. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі
лінійного програмування
Означення 1. Планом задачі лінійного програмування (5)-(7) називається вектор
компоненти якого задовольняють умови (6), (7).
називається опорним, якщо вектори , які відповідають
додатним компонентам плану Х, утворюють
лінійно-незалежну систему.
Зауваження. Оскільки вектори є m-вимірними, то максимальне
число таких векторів, що утворюють лінійно-незалежну систему, не перевершує m. Звідси випливає, що кожний опорний план містить не більше ніж m додатних компонент.
,
Означення 2. План
задачі (5)-(7)
Слайд 192. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі
лінійного програмування
Означення 3. Опорний план називається невиродженим, якщо він містить рівно m додатних компонент. Якщо опорний план містить менше за m додатних компонент, то такий опорний план називається виродженим.
Означення 4. Оптимальним планом або розв`язком задачі лінійного програмування (5)-(7), називається план цієї задачі, який мінімізує (максимізує) лінійну функцію (5), іншими словами, Х* – оптимальний план задачі лінійного програмування, якщо для будь-якого плану Х задачі (5)-(7) виконується умова
Слайд 20
2. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі
лінійного програмування
Приклад 2. Нехай задача лінійного програмування має вигляд
xj≥0, j=1, 2, 3, 4.
f(x)=2x1–х2+2x3–3x4→min;
З”ясувати, які з векторів є планами, опорними планами:
Х1=(1,0,1,0)
Х2=(0,1,0,1)
Х3=(0,1,0,0)
Х4=(0,0,3,1)
Слайд 213. Властивості розв’язків задачі лінійного програмування
Запишемо задачу (5) – (7)
у матричному вигляді:
(8)
(9)
(10)
(8)
(9)
(10)
Слайд 223. Властивості розв’язків задачі лінійного програмування
Теорема 1. Множина всіх планів задачі (8)–(10)
– опукла.
Опуклу множину планів задачі лінійного програмування позначимо через М.
Зауважимо, що М може бути порожньою множиною, опуклим многогранником або необмеженою опуклою многогранною областю.
Опуклу множину планів задачі лінійного програмування позначимо через М.
Зауважимо, що М може бути порожньою множиною, опуклим многогранником або необмеженою опуклою многогранною областю.
Слайд 233. Властивості розв’язків задачі лінійного програмування
Нехай лінійна функція задачі лінійного програмування обмежена
знизу і зверху на множині планів.
Теорема 2. Лінійна функція задачі лінійного програмування (8) – (10) досягає мінімального (максимального) значення у крайній точці опуклої множини М планів задачі. Якщо лінійна функція набуває мінімального (максимального) значення більш ніж в одній крайній точці, то вона набуває цього ж значення в будь-якій точці, яка є опуклою комбінацією цих точок.
Теорема 2. Лінійна функція задачі лінійного програмування (8) – (10) досягає мінімального (максимального) значення у крайній точці опуклої множини М планів задачі. Якщо лінійна функція набуває мінімального (максимального) значення більш ніж в одній крайній точці, то вона набуває цього ж значення в будь-якій точці, яка є опуклою комбінацією цих точок.
Слайд 243. Властивості розв’язків задачі лінійного програмування
Теорема 3 (критерій крайності точки опуклої множини
планів). Для того щоб точка Х, яка містить m додатніх координат, була крайньою точкою множини планів М задачі лінійного програмування (8)-(10), необхідно і досить, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему.
Слайд 254. Геометричний метод розв’язування задачі лінійного програмування
Розглянемо двовимiрну задачу мiнiмiзацiї:
(11)
Лiнiєю
(поверхнею) рiвня функцiї
є множина точок
є множина точок
Слайд 284. Геометричний метод розв’язування задачі лінійного програмування
Особливість геометричної інтерпретації двовимірної задачі
лінійного програмування
полягає в тому, що:
- допустима множина X являє собою опуклу многокутну область (обмежену) або необмежену;
полягає в тому, що:
- допустима множина X являє собою опуклу многокутну область (обмежену) або необмежену;
Слайд 294. Геометричний метод розв’язування задачі лінійного програмування
лінія рівня цільової функції
є пряма, при цьому градієнт функції - вектор
перпендикулярний цій прямій і є напрямом найшвидшого зростання цільової функції в кожній точці допустимої множини X, а антиградієнт (вектор ) є напрямом її найшвидшого спадання;
якщо задача має розв’язок, то він досягається обов’язково на межі допустимої множини X, а сам розв’язок задачі є або деяка вершина многокутника або множина точок деякої його сторони.
перпендикулярний цій прямій і є напрямом найшвидшого зростання цільової функції в кожній точці допустимої множини X, а антиградієнт (вектор ) є напрямом її найшвидшого спадання;
якщо задача має розв’язок, то він досягається обов’язково на межі допустимої множини X, а сам розв’язок задачі є або деяка вершина многокутника або множина точок деякої його сторони.
Слайд 324. Геометричний метод розв’язування задачі лінійного програмування
Розглянемо більш детально алгоритм розв'язування
двовимірної задачi лiнiйного програмування виду:
(12)
(13)
(12)
(13)
Слайд 334. Геометричний метод розв’язування задачі лінійного програмування
1. Побудувати прямi, рiвняння яких одержуються
внаслiдок замiни в обмеженнях (13) знакiв нерiвностей на знаки рiвностей.
2. Знайти пiвплощини, якi визначаються кожним з обмежень-нерівностей задачi.
3. Знайти множину допустимих розв”язкiв задачі M, як перетин знайдених півплощин.
2. Знайти пiвплощини, якi визначаються кожним з обмежень-нерівностей задачi.
3. Знайти множину допустимих розв”язкiв задачі M, як перетин знайдених півплощин.
Слайд 344. Геометричний метод розв’язування задачі лінійного програмування
4. Побудувати пряму
(лінію рівня цільової функції), при цьому величина h підбирається так, щоб лінія рівня проходила через множину допустимих розв”язкiв М. Побудувати вектор .
5. Рухаючи пряму в напрямі вектора с при розв”язуванні задачі максимізації (або в зворотньому напрямі при розв”язанні задачі мінімізації), знайти точку (множину точок), де цiльова функцiя приймає максимальне (мiнiмальне) значення, або встановити необмеженiсть зверху (знизу) функцiї на допустимій множинi.
5. Рухаючи пряму в напрямі вектора с при розв”язуванні задачі максимізації (або в зворотньому напрямі при розв”язанні задачі мінімізації), знайти точку (множину точок), де цiльова функцiя приймає максимальне (мiнiмальне) значення, або встановити необмеженiсть зверху (знизу) функцiї на допустимій множинi.
Слайд 354. Геометричний метод розв’язування задачі лінійного програмування
6. Якщо існує єдиний розв’язок задачі,
визначити координати знайденої точки як розв’язок системи двох відповідних рівнянь з двома невідомими, i обчислити значення цiльової функцiї в цiй точцi. Якщо існує безліч розв’язків, то визначити координати принаймні однієї екстремальної точки i обчислити значення цiльової функцiї в цiй точцi.
Слайд 36
4. Геометричний метод розв’язування задачі лінійного програмування
Приклад 2.
На виготовлення двох видів продукції П1 і П2 витрачаються три види ресурсів А1, А2 і А3. Запаси ресурсів, норми їх витрат і прибуток від реалізації одиниці продукції (у.о.) задані у таблиці. Знайти такий план виробництва, який би забезпечував найбільший прибуток.
Побудувати математичну модель поставленої задачі і розв’язати її геометричним методом.
Побудувати математичну модель поставленої задачі і розв’язати її геометричним методом.
Слайд 37
4. Геометричний метод розв’язування задачі лінійного програмування
Розв”язування. Математична модель задачі має
такий вигляд:
де x1 – обсяг випуску продукції виду П1,
x2 – обсяг випуску продукції виду П2.
Слайд 43
4. Геометричний метод розв’язування задачі лінійного програмування
Відповідь:
Обидва види продукції є
рентабельними, при цьому оптимальний план дорівнює X1*=16, X2*=9, а оптимальний прибуток від реалізації продукції дорівнює 348 у.о.
