My_horosho_postaralis_2003_WORD
88. Градієнтний метод Франка-Вульфа
.Розглянемо метод Франка — Вульфа, процедура якого передбачає визначення оптимального плану задачі шляхом перебору розв’язків, які є допустимими планами задачі.
Нехай необхідно відшукати
за лінійних обмежень: ;
Допустимо, що Х0 — початкова точка, що належить множині допустимих планів даної задачі. В деякому околі цієї точки нелінійну цільову функцію замінюють лінійною і потім розв’язують задачу лінійного програмування. Нехай розв’язок лінійної задачі дав значення цільової функції F0, тоді з точки Х0 в напрямку F0 необхідно рухатись доти, поки не припиниться зростання цільової функції. Тобто у зазначеному напрямку вибирають наступну точку Х1, цільова функція знову замінюється на лінійну, і знову розв’язується задача лінійного програмування.
Розглянемо детальніше перехід від k-ої ітерації методу до (k + 1)-ої ітерації.
Припустимо, що відома точка Xk, яка належить області допустимих розв’язків. У даній точці обчислюємо градієнт цільової функції:
.Значення градієнта функції задає в даній точці напрям найшвидшого її зростання.
Замінюємо цільову функцію задачі лінійною функцією виду:
.Потім розв’язуємо задачу лінійного програмування з обмеженнями початкової задачі і новою цільовою функцією:
за умов: ; .
Нехай розв’язком такої задачі є точка .З початкової точки в напрямку рухаємося з деяким довільним кроком , визначаючи координати нової точки у такий спосіб:
Содержание
- 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 Феф ми найкращі Дякую всім, хто приймав участь