67. Пряма та двоїста задачі лінійного програмування. Визначення Lmin для двоїстої задачі по результатам симплексної таблиці прямої задачі.
Кожній задачі лінійного програмування відповідає двоїста, що формується за допомогою певних правил безпосередньо з умови прямої задачі.
Якщо пряма задача лінійного програмування має вигляд
Загальна лінійна економіко-математична модель економічних процесів та явищ — так звана загальна задача лінійного програмування подається у вигляді:
за умов:
(2.2) (2.3)То двоїста задача записується так: →min
Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду « », а для задачі на відшукання мінімального значення — до виду « ».Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:
1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.
4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця
,що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі
утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.
Процес побудови двоїстої задачі зручно зобразити схематично:
Пари задач лінійного програмування бувають симетричні та несиметричні.
У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.
У несиметричних задачах деякі обмеження прямої задачі можуть бути рівняннями, а двоїстої — лише нерівностями. У цьому разі відповідні рівнянням змінні двоїстої задачі можуть набувати будь-яких значень, не обмежених знаком.
Всі можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач у матричній формі наведено нижче.
Пряма задача | Двоїста задача |
Cиметричні задачі | |
max F = CX AX ≤ B X ≥ 0 | min Z = BY ATY ≥ C Y ≥ 0 |
min F = CX AX ≥ B X ≥ 0 | max Z = BY ATY ≤ C Y ≥ 0 |
Якщо пряма задача лінійного програмування має оптимальний план Х*, визначений симплекс-методом, то оптимальний план двоїстої задачі Y* визначається зі співвідношення Y* = , де - вектор-рядок, що складається з коефіцієнтів цільової функції прямої задачі при змінних, які є базисними в оптимальному плані; - матриця, обернена до матриці D, складеної з базисних векторів оптимального плану , компоненти яких узято з початкового опорного плану задачі.
За допомогою зазначеного співвідношення під час визначення оптимального плану однієї з пари двоїстих задач лінійного програмування знаходять розв’язок іншої задачі.
- 1.Економіко-математична модель. Класифікація моделей
- 2. Геометрична інтерпретація роз’язку цілочислових задач лінійного програмування.
- 4. Математичний інструмент, який використовується для побудови економіко-математ. Моделей.
- 6. Формула Тейлора. Матриця Гессе, її структура, та її використання для дослідження функцій на екстремум.
- 7. Системи нерівностей. Область допустимих розв’зків системи нерівностей.
- 8. Ознаки множинних розв’язків системи нерівностей, кутові точки.
- 9. Суть ідеї методу відтинання для задач цілочислового програмування.
- 10. Додатньо та від’ємно визначена матриця Гессе. Використання цих ознак матриці для дослідження функції на екстремум.
- 11. Загальний запис лінійної оптимізаційної моделі. Цільова функція та система обмежень.
- 12. Описати алгоритм розв’язання цілочислових задач лінійного програмування за методом Гоморі.
- 13. Метод приведеного градієнта (метод Якобі).
- 14. Допустимий план розв’язку задач лінійного програмування, опорний та оптимальний плани.
- 16. Матриця Якобі, матриця управління.
- 17. Векторно-математична форма запису задачі лінійного програмування.
- 18. Геометрична інтерпретація розвязку задач лінійного програмування на площині.
- 19. Градієнт функції
- 20. Основні властивості розв’язків задач лінійного програмування.
- 21. Геометрична інтерпретація лінійних оптимізаційних моделей на площині.
- 22. Описати алгоритм методу Гоморі розвязку задач цілочислового математичного програмування.
- 23. Симплексний метод розвязування задач лінійного програмування. Ідея методу.
- 24. Розвязування дробово-лінійної оптимізаційної задачі зведенням до задачі лінійного програмування.
- 25. Градієнтний метод. Ідея методу.
- 29. Окантована матриця Гессе, та її використання при розв'язку нелінійних задач.
- 30. Структура симплексної таблиці. Базисні та вільні вектори. Оцінковий рядок симплексної таблиці.
- 31. Приведення задачі дробово-лінійного програмування до оптимізаційної задачі лінійного програмування.
- 34. Цілочислові оптимізаційні моделі. Класифікація моделей цілочислової оптимізації.
- 35. Метод множників Лагранжа. Поняття абсолютного та умовного екстремуму функції.
- 36. Симплексний метод. Вибір напрямного стовпчика і рядка при здійсненні ітерації.
- 37. Загальний запис нелінійної оптимізаційної моделі.
- 39. Метод штучного базису. Суть базису.
- 40. Окантована матриця Гессе та її побудова.
- 43. Метод множників Лагранжа
- 44.Метод штучного базису
- 47.Нелінійні моделі. Визначення стац. Точок при викор. Методу множників Лагранжа
- 48.Правила побудови двоїстих задач
- 52. .Приведення дробово-лінійної оп-ної задачі до задачі лінійного програмування.
- 53. Сиплекс табл. Для задачі лінійного програм з штучним базисом
- 54. В яких випадках викор дроб-лін цільова ф-ція при розв’язуванні екон задач
- 56.Записати загальний запис моделі та записати економічний зміст коефіцієнтів моделі.
- 57.Описати алгоритм розвязання задач лінійного програмування симплексним методом.
- 58.Загальна структура симплексної таблиці при реалізації симплексного методу для задачі цілочислового програмування.
- 59.Градієнтний метод.Основна властівість градієнта.Ідея методу.
- 60. Загальний запис лінійної оптимізаційної задачі.Приведення моделі до канонічного вигляду.Описати економічний зміст кофіцієнтів.
- 60. Загальний запис лінійної оптимізаційної моделі. Приведення моделі до канонічного вигляду.Описати економічний зміст коефіцієнтів bj,cj,aij
- 61. Графічний метод розв’язання цілочислових задач лінійного програмування.
- 62. Визначення мін(макс) для цільової функції
- 64 Записати математичну модель оцінки рентабельності виготовленої продукції
- 65. Аналіз коефіцієнтів цільової функції cj, dj.
- 67. Пряма та двоїста задачі лінійного програмування. Визначення Lmin для двоїстої задачі по результатам симплексної таблиці прямої задачі.
- 68 Базисні та вільні вектори,базисні та вільні невідомі. Як визначити число базисних векторів по заданій матриці ∆
- 69. Загальний запис математичної моделі дробово-лінійної задачі приведення її до задачі лінійного програмування.
- 71.Чому дорівнюють .
- 72.Задачу в лінійному програмуванні в загальному вигляді привести до канонічного вигляду.Базисні і вільні зміні.Економічна інтерпретація коефіцієнтів моделі а,с,b.
- 73.Математичне програмування. Обєкт матем програмування. Визначення матем моделі.
- 75.Записати економіко-матем модель в загальному вигляді.
- 76.Окантована матриця Гесе. Достатні умови для ідентифікації екстремальних точок.
- 77. Базисні та вільні вектори. Визначення базисних векторів по заданій матриці ∆.
- 78. Визначення вільних векторів через базисні.
- 79. Що описує система обмежень задачі лінійного програмування Загальний запис економіко-математичної моделі.
- 80. Симплексний метод розв’язування задач лінійного програмування. Використання методу Жордана-Гаусса для визначення елементів аij симплексної таблиці.
- 81. Структура окантованої матриці н. Визначення матриць р, Рт, q. Використання матриці н для дослідження стаціонарних точок.
- 82. Економіко-математична модель. Правила, які потрібно дотримуватись при побудові такої моделі. Поняття адекватності економіко-математичної моделі.
- 83. Симлексна таблиця для задачі лінійного прорамування. Оцінючий та оцінючий стовпчик
- Структура симплексної таблиці для розв’язку задач лінійного програмування
- 84. Метод відтинання. Метод Гоморі. Як отримати нерівність правильного відтинання
- 85. Записати загальний запис математичного програмування. Лінійні та нелінійні моделі.
- 86. Cтруктура матриць а та Ат
- 87.Дробово- лінійне програмування. Система обмежень. Яку інформацію містять
- 88. Градієнтний метод Франка-Вульфа
- 89. Метод приведеного градієнта(метод Якобі).
- 90 Загальні форми запису лінійних оптимізаційних задач
- 91. Цілочислове програмування. В яких випадках воно використовується. Геометричний розв’язок цілочислових задач на пощині.
- 92.Дати визначення допустимого плану. Область існування планів,оптимальний план
- 93. Цілочислове програмування. Визначення оптимального плану для цілочислової моделі графічним методом на площині.
- 1.Економіко-математична модель. Класифікація моделей.
- 2. Геометрична інтерпретація роз’язку цілочислових задач лінійного програмування.
- 3. Глобальний та умовний екстремуми цільової функції. Необхідна умова існування екстремуму.
- 214 Феф ми найкращі Дякую всім, хто приймав участь