93. Цілочислове програмування. Визначення оптимального плану для цілочислової моделі графічним методом на площині.
Існує доволі широке коло задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних мають набувати цілих значень. До них належать задачі, у яких змінні означають кількість одиниць неділимої продукції. Наприклад, коли йдеться про кількість верстатів у цеху, тварин у сільському господарських підприємствах тощо.Наведені задачі називаються задачами цілочислового програмування. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень – 0 або 1.
З адача цілочислового програмування формується так само, як і задача лінійного програмування, але включає додаткову вимогу, яка полягає в такому: змінні, які становлять оптимальний розв’язок, мають бути цілими невід’ємними числами.
→min(max) при обмеженнях: хj – цілі числа ( ) Параметри , , ( ) вважаються цілими числами.
Для знаходження оптимального розв’язку цілочислових задач застосовують спеціальні методи. Найпростішим з них є знаходження оптимального розв’язку задачі як такої, що має лише неперервні змінні, з дальшим їх округленням. Такий підхід є виправданим тоді, коли змінні в оптимальному плані набувають досить великих значень у зіставленні їх з одиницями вимірювання. Проте за деяких умов такі спрощення призводять до істотних неточностей. Скажімо, множина допустимих розв’язків деякої нецільової задачі лінійного програмування має такий вигляд:
Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв’язків відповідної не цілочислової задачі. Отже для розглянутого на рисунку випадку множина допустимих планів складається з 9 точок, які утворені перетинами сім’ї прямих, що паралельні осям Ох1 та Ох2 і проходять через точки з цілими координатами 0, 1, 2. Для знаходження цілочислового оптимального розв’язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі до перетину з кутовою точкою утвореної цільової сітки. Координати цієї точки і є оптимальним цілочисловим роз’язком задачі. Отже, точка М(2;2) – цілочисловий розв’язок данної задачі.
Очевидно, особливість геометричної інтерпретації цілочислової задачі у зіставленні зі звичайною задачею лінійного програмування полягає лише у визначенні множини допустимих розв’язків. Областю допустимих розв’язків загальної задачі лінійного програмування є опуклий багатокутник, а вимога цілочисловості розв’язку призводить до такої множини допустимих розв’язків, яка є дискретною і утворюється тільки з окремих точок. Якщо у разі 2 змінних розв’язок задачі можна відшукати графічним методом, тобто, використовуючи цілочислову сітку, можна досить просто знайти оптимальний план, то в іншому разі необхідно застосовувати спеціальні методи.
- 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 Феф ми найкращі Дякую всім, хто приймав участь