- •Аналіз коефіцієнтів цільової функції задач лінійного програмування.
- •Аналіз розв’язків лінійних економіко-математичних моделей. Оцінка рентабельності продукції. Доцільність введення нової продукції.
- •12.Етапи математичного моделювання.
- •Аналіз обмежень дефіцитних і недефіцитних ресурсів.
- •Властивості розв’язків задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування.
- •Геометрична інтерпретація задачі цілочислового програмування.
- •Градієнтні методи розв’язання задач нелінійного програмування та їх класифікація.
- •Графічний метод розв’язування задач нелінійного програмування.
- •Гра в чистих стратегіях. Поняття сідлової точки і її знаходження.
- •Гра 2х2 в змішаних стратегіях. Алгоритм розв’язування задачі.
- •13.Загальна постановка задачі лінійного програмування. Приклади економічних задач лінійного програмування.
- •14.Застосування теорем двоїстості в розв’язуванні задач лінійного програмування.
- •15.Зведення гри двох осіб до задачі лінійного програмування.
- •16.Знаходження розв’язку задачі лінійного програмування. Алгоритм симплексного методу.
- •17.Квадратична функція та її властивості.
- •18.Математична постановка задачі динамічного програмування, її економічний зміст. Принцип оптимальності Беллмана.
- •19.Метод Гоморі.
- •21.Методи розв’язування задач динамічного програмування. Основні кроки алгоритму розв’язування задачі динамічного програмування.
- •22.Метод Франка-Вульфа. Алгоритм розв’язування задачі нелінійного програмування.
- •23.Модель задачі лінійного програмування в розгорнутому і скороченому вигляді, а також в матричній і векторній формах.
- •24.Необхідність використання математичного моделювання економічних процесів.
- •25.Означення планів задачі лінійного програмування (допустимий, опорний, оптимальний).
- •26.Основні поняття теорії ігор. Гра двох гравців з нульовою сумою, правила гри, ціна гри, пара оптимальних стратегій для двох осіб.
- •27.Основні рекурентні співвідношення розв’язування задач динамічного програмування.
- •28.Платіжна матриця. Основна теорема теорії ігор. Принцип мінімаксу.
- •Нехай маємо скінченну матричну гру з платіжною матрицею
- •29.Побудова опорного плану задачі лінійного програмування, перехід до іншого опорного плану.
- •30. Поняття адаптації та адаптивних систем.
- •31.Поняття про опуклі функції. Геометрична інтерпретація задачі опуклого програмування на площині.
- •32.Постановка задачі нелінійного програмування, математична модель. Геометрична інтерпретація.
- •33.Постановка задачі квадратичного програмування та її математична модель.
- •34.Принципи моделювання соціально-економічних систем і процесів.
- •35. Проблеми оцінювання адекватності моделі
- •36. Симплексний метод із штучним базисом. Ознака оптимальності плану із штучним базисом.
- •37.Сідлова точка та необхідні і достатні умови її існування. Теорема Куна-Таккера.
- •39. Сутність адекватності економіко-математичних моделей
- •40.Сутність економіко-математичної моделі.
- •41.Сутність оптимізаційних моделей. Приклади економічних задач математичного програмування.
- •42.Теореми двоїстості, їх економічна інтерпретація.
- •43.Теорема про оптимальність розв’язку задачі лінійного програмування симплекс-методом.
- •44.Цілочислове програмування. Область застосування цілочислових задач в плануванні й управлінні виробництвом.
- •1.Аналіз коефіцієнтів цільової функції задач лінійного програмування.
- •2.Аналіз розв’язків лінійних економіко-математичних моделей. Оцінка рентабельності продукції. Доцільність введення нової продукції.
Гра 2х2 в змішаних стратегіях. Алгоритм розв’язування задачі.
Найпростішим випадком скінченної гри є парна гра, коли у кожного учасника є дві стратегії.
Вj Ai |
B1 |
B2 |
A1 |
a11 |
a12 |
A2 |
a21 |
a22 |
Розглянемо випадок, коли гра не має сідлової точки. Отже, . Необхідно знайти змішані стратегії та ціну гри. Позначимо шукані значення ймовірноcтей застосування «чистих» стратегій гравця А через , а для гравця В — через .
Згідно з основною теоремою теорії ігор, якщо гравець А притримується своєї оптимальної стратегії, то виграш буде дорівнювати ціні гри. Отже, якщо гравець А притримуватиметься своєї оптимальної стратегії , то:
(11.3)
Оскільки , то . Підставивши цей вираз у систему рівнянь (11.3), отримаємо:
.
Розв’язавши дане рівняння відносно невідомого , маємо:
, (11.4)
тоді: = . (11.5)
Провівши аналогічні міркування стосовно гравця В, маємо:
(11.6)
Оскільки , то .
.
Розв’язавши це рівняння відносно невідомого , маємо:
, (11.7)
тоді: . (11.8)
Ціну гри знаходять, підставлючи значення (або ) в будь-яке з рівнянь (11.3) або (11.6):
.
13.Загальна постановка задачі лінійного програмування. Приклади економічних задач лінійного програмування.
Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(1) при обмеженнях (2) 3 (4) де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні.
14.Застосування теорем двоїстості в розв’язуванні задач лінійного програмування.
І т-ма: Якщо одна із спряжених задач має розв’язок то друга задача теж має розв’язок і знач-я цієї ф-ції співпадатимуть. Х*=(x*1,x*2,x*3…x*n);Y*=(y*1,y*2,y*3…y*n); Fmax=F(x*)=>Zmin=Z(y*);Fmax=Zmin; Max прибуток F підпр-во має від реалізації оптим плану х*, однак ту ж суму він отримає від продажу ресурсів за оптим. Цінами у*. ІІ т-ма: При підстановці оптим плану х* в і-те обмеж-я прямої задачі можна отримати 2 варіанти оцінки ресурсів, якщо маємо знак (=), то ресурс викор-ся повністю, він є дефіцитним тобто цінним, його треба поповнювати, його двоїста оцінка є додатнім числом. ІІІ т-ма: Компоненти оптим плану Y*i дають оцінку дефіцитних і недефіц-их ресурсів, а кожне додатнє знач-я двоїстої оцінки характер-є приріст цільової ф-ції F, зумовлю-ий малими змінами на одиницю відповідного запасу дефіцитних ресурсів. В симплекс таблиці знач-я двоїстих оцінок знаходь в останньому перевірочному рядку навпроти баз. змінних прямої задачі.
15.Зведення гри двох осіб до задачі лінійного програмування.
Для розв’язування гри m × n використовують прийом зведення її до задачі лінійного програмування.
Нехай розглядається парна гра зі стратегіями для гравця А та стратегіями для гравця В і платіжною матрицею . Необхідно знайти оптимальні змішані стратегії та , де , .
Знайдемо спочатку оптимальну стратегію гравця А. За основною теоремою теорії ігор така стратегія має забезпечити гравцеві виграш, не менший за ціну гри (поки що невідому величину) , за будь-якої поведінки гравця В.
Допустимо, що гравець А застосовує свою оптимальну стратегію, а гравець В — свою «чисту» j-ту стратегію Bj, тоді середній виграш гравця А дорівнюватиме:
. (11.10)
За цих обставин виграш має бути не меншим, ніж ціна гри. Отже, для будь-якого значення j величина виду (11.10) має бути не меншою, ніж :
Розділивши всі обмеження на , отримаємо:
Позначивши маємо:
.
Враховуючи умову, що , отримуємо .
Необхідно зробити виграш максимальним. Цього можна досягти, коли вираз набуватиме мінімального значення. Отже, врешті маємо звичайну задачу лінійного програмування.
Цільова функція:
(11.11)
за умов:
(11.12)
.