1. Загальна економіко-математична модель задачі лінійного програмування. Допустимий та оптимальний план задачі лінійного програмування. Загальна лінійна економіко-математична модель економічних процесів та явищ — так звана загальна задача лінійного програмування подається у вигляді: (2.1) за умов: (2.2) (2.3) Отже, потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (2.2) і (2.3), і цільова функція (2.1) набуває екстремального (максимального чи мінімального) значення. Для загальної задачі лінійного програмування використовуються такі поняття. Вектор Х = (х1, х2, …, хn), координати якого задовольняють систему обмежень (2.2) та умови невід’ємності змінних (2.3), називається допустимим розв’язком (планом) задачі лінійного програмування. Допустимий план Х = (х1, х2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (2.2) у вигляді рівностей, а також обмеження (2.3) щодо невід’ємності змінних. Опорний план Х = (х1, х2, …, хn), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений. Опорний план , за якого цільова функція (2.1) досягає масимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування. 2. Завдання економетричного дослідження. Роль економетричного дослідження визначається тими задачами, які може розв’язувати економетрія. Найважливішою задачею є оцінювання параметрів і перевірка значущості економетричної моделі. Першим етапом цього процесу є специфікація моделі в математичній формі. Другий етап — збір і підготовка економічної інформації. На третьому етапі оцінюються параметри моделі. Четвертий етап — це перевірка моделі на вірогідність. Дуже важливими на цьому етапі є оцінки дисперсії залишків моделі. Ці оцінки відіграють вирішальну роль при з’ясуванні якості економетричних моделей, вони необхідні для визначення надійності обчислених параметрів і для застосування розроблених моделей у прогнозуванні. 3. Двоїстість у лінійному програмуванні. Економічний зміст двоїстих оцінок. Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду «?», а для задачі на відшукання мінімального значення — до виду «(». Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами: 1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі. 2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі. 3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки. 4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі. 5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі. 6. Матриця , що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі
утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками. Кожну з двох спряжених задач можна розв’язати окремо, проте встановлені теоремами двоїстості залежності між оптимальними планами прямої та двоїстої задач уможливлюють знаходження розв’язку двоїстої задачі за наявності оптимального плану прямої, і навпаки. 4. Правила побудови двоїстих задач. Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею. Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду «?», а для задачі на відшукання мінімального значення — до виду «(». Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами: 1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі. 2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі. 3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки. 4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі. 5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі. 6. Матриця , що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі
утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками. Процес побудови двоїстої задачі зручно зобразити схематично: Рис. 3.1. Схема побудови двоїстої задачі до прямої Пари задач лінійного програмування бувають симетричні та несиметричні. У симетричних задачах обмеження прямої та двоїстої задач є лише нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень. У несиметричних задачах деякі обмеження прямої задачі можуть бути рівняннями, а двоїстої — лише нерівностями. У цьому разі відповідні рівнянням змінні двоїстої задачі можуть набувати будь-яких значень, не обмежених знаком. Всі можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач у матричній формі наведено нижче. Симетричні задачі Пряма задача Двоїста задача max F = CX min Z = BY AX ? B ATY ( C X ( 0 Y ( 0
min F = CX max Z = BY AX ( B ATY ? C X ( 0 Y ( 0
Ст 107 5. Геометрична інтерпретація задачі лінійного програмування. Розглянемо на площині х1Оx2 сумісну систему лінійних нерівностей: (2.9)
Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою ai1x1 + ai2x2 = bi (i = 1, 2, ...,т). Умови невід’ємності змінних визначають півплощини з граничними прямими х1 = 0 та х2 = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи. Сукупність цих точок (розв’язків) називають багатокутником розв’язків, або областю допустимих планів (розв’язків) задачі лінйного програмування. Це може бути точка (єдиний розв’язок), відрізок, промінь, багатокутник, необмежена багатокутна область. Якщо в системі обмежень (2.9) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть ai1x1 + ai2x2 + ai3x3 = bi (i = 1, 2, ...,т), а умови невід’ємності — півпростори з граничними площинами хj = 0 (j = 1, 2, 3), де і — номер обмеження, а j — номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю. Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: х1, х2,… хn; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною аi1x1 + ai2x2 + ai3x3 + … +ainxn = bi (i = 1, 2, ...,т). Кожному обмеженню виду (2.9) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпростори з граничними гіперплощинами хj = 0 (j = 1, 2, 3, ..., n). Якщо система обмежень сумісна, то за аналогією з тривимірним простором вона утворює спільну частину в n-вимірному просторі — опуклий багатогранник допустимих розв’язків. Отже, геометрично задача лінійного програмування являє собою відшукання координат такої точки багатогранника розв’язків, при підстановці яких у цільову лінійну функцію остання набирає максимального (мінімального) значення, причому допустимими розв’язками є усі точки багатогранника розв’язків. Цільову функцію
в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім’ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.Критерієм оптимальності є максимізація прибутку. Ст 40 6. Означення економетричної моделі. Серед багаточисленних зв’язків між економічними показниками завжди можна виділити такий показник, вплив якого на результативну ознаку є основним, найбільш важливим. Щоб виміряти цей зв’язок кількісно, необхідно побудувати економетричну модель з двома змінними (просту модель). Загальний вигляд такої моделі: Y = f (X, u), де Y — залежна змінна (результативна ознака); X — незалежна змінна (фактор); u — стохастична складова. Аналітична форма цієї моделі може бути різною залежно від економічної сутності зв’язків. Найбільш поширені форми залежностей: ; ; ; , де а0, а1 — невідомі параметри моделі. Неважко переконатись, що наведені нелінійні форми залежностей за допомогою елементарних перетворень приводяться до лінійних. Якщо припустити, що економетрична модель з двома змінними є лінійною: , в якій стохастична складова (залишки) має нульове математичне сподівання та постійну дисперсію, то параметри моделі можна оцінити на основі звичайного методу найменших квадратів (1МНК). В основі методу 1МНК лежить принцип мінімізації суми квадратів залишків моделі. Реалізація цього принципу дає можливість отримати систему нормальних рівнянь:
В даній системі n — кількість спостережень, ,,, — величини, які можна розрахувати на основі вихідних спостережень над змінними і . Розв’язавши систему нормальних рівнянь, одержимо оцінки невідомих параметрів моделі і : . Достовірність побудованої економетричної моделі можна перевірити, користуючись елементами дисперсійного аналізу. Перш за все слід розрахувати залишки моделі
та знайти їх дисперсію: , де — кількість змінних моделі (). необхідно визначити стандартну помилку кожного параметра моделі. в цій формулі характеризує відповідний діагональний елемент матриці помилок (матриці, оберненої до матриці системи нормальних рівнянь). На основі коефіцієнта детермінації
можна зробити висновок про ступінь значущості вимірюваного зв’язку на основі економетричної моделі . Оскільки коефіцієнт детермінації R2 характеризує, якою мірою варіація залежної змінної визначається варіацією незалежної змінної, то чим ближче R2 до одиниці, тим суттєвішим є зв’язок між цими змінними. Коефіцієнт кореляції R = характеризує тісноту зв’язку між змінними моделі. Він може знаходитись на множині . Чим ближче R до одиниці по модулю, тим тіснішим є зв’язок. Від’ємний знак свідчить про обернений зв’язок, додатній — про прямий. Якщо прийняти відповідну гіпотезу про закон розподілу залишків економетричної моделі, то параметри її можна оцінити на основі метода максимальної правдоподібності. Нехай залишки моделі розподіляються за нормальним законом, тоді функція правдоподібності запишеться так:
Продифереціюємо цю функцію за невідомими параметрами , і і, прирівнявши похідні до нуля, отримаємо систему рівнянь:
Підставимо в цю систему величини ,,,, які розраховуються на основі вихідних даних, і розв’яжемо її відносно параметрів , і . В результаті отримаємо оцінки параметрів моделі і , а також оцінку дисперсії залишків. Ст 14 методичка 7. Метод множників Лагранжа розв'язування нелінійних задач оптимізації. Ідея методу множників Лагранжа полягає в заміні початкової задачі простішою. Для цього цільову функцію замінюють іншою, з більшою кількістю змінних, тобто такою, яка включає в себе умови, що подані як обмеження. Після такого перетворення дальше розв’язування задачі полягає в знаходженні екстремуму нової функції, на змінні якої не накладено ніяких обмежень. Тобто від початкової задачі пошуку умовного екстремуму переходимо до задачі відшукання безумовного екстремального значення іншої функції. Отже, завдяки такому перетворенню можливе застосування методів класичного знаходження екстремуму функції кількох змінних. Узагальнення необхідної умови існування локального екстремуму функції n змінних має аналогічний вигляд. Отже, для розв’язування задачі необхідно знайти вирази частинних похідних нової цільової функції за кожною змінною і прирівняти їх до нуля. В результаті отримаємо систему рівнянь. Її розв’язок визначає так звані стаціонарні точки, серед яких є і шукані екстремальні значення функції. Розглянемо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд: (8.6) за умов: ,(8.7) де функції і мають бути диференційовними. Задача (8.6), (8.7) полягає в знаходженні екстремуму функції за умов виконання обмежень . Переходимо до задачі пошуку безумовного екстремуму. Замінюємо цільову функцію (8.6) на складнішу. Ця функція називається функцією Лагранжа і має такий вигляд (8.8) де — деякі невідомі величини, що називаються множниками Лагранжа. Знайдемо частинні похідні і прирівняємо їх до нуля:
(8.9) Друга група рівнянь системи (8.9) забезпечує виконання умов (8.7) початкової задачі нелінійного програмування. Система (8.9), як правило, нелінійна. Розв’язками її є і — стаціонарні точки. Оскільки, ці розв’язки отримані з необхідної умови екстремуму, то вони визначають максимум, мінімум задачі (8.6), (8.7) або можуть бути точками перегину (сідловими точками). Для діагностування стаціонарних точок і визначення типу екстремуму необхідно перевірити виконання достатніх умов екстремуму, тобто дослідити в околі стаціонарних точок диференціали другого порядку (якщо для функцій існують другі частинні похідні і вони неперервні). Узагальнення достатньої умови існування локального екстремуму для функції n змінних приводить до такого правила: за функцією Лагранжа виду (8.8) будується матриця Гессе, що має блочну структуру розмірністю :
де О — матриця розмірністю , що складається з нульових елементів, Р — матриця розмірністю , елементи якої визначаються так: , — транспонована матриця до Р розмірністю , Q — матриця розмірністю виду: , де . Розглянемо ознаки виду екстремуму розв’язку системи (8.9). Нехай стаціонарна точка має координати і . 1. Точка є точкою максимуму, якщо, починаючи з головного мінору порядку (m + 1), наступні (n – m) головних мінорів матриці Н утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником . 2. Точка є точкою мінімуму, якщо, починаючи з головного мінору порядку (m + 1), знак наступних (n – m) головних мінорів матриці Н визначається множником . Ст 320 8. Симплексний метод зі штучним базисом. Ознака оптимальності плану зі штучним базисом. Якщо канонічна форма ЗЛП не містить одиничних базисних векторів, або їх недостатня кількість, то в такому випадку застосовують метод штучного базису. Ідея МШБ: У відповідні обмеження канонічної форми ЗЛП вводяться штучні змінні, які дають необхідну кількість одиничних базисних векторів. Штучні змінні вводяться функцією мети з коефіцієнтами +М (для задач на мин.), -М(для задач на макс.), де М – дуже велике число. Визначені одиничні лінійно незалежні вектори утворюють базис, і змінні задачі, що відповідають їм, називаються базисними, а всі інші змінні – вільними. Їх прирівнюють до нуля та з кожного обмеження задачі визначають значення базисних змінних. У такий спосіб отримують початковий опорний план ЗЛП. В результаті одержуємо задачу, яка називається ЗЛП зі штучним базисом, до якої застосовується симплекс-метод. Зв'язок між оптимальнім розв’язком ЗЛП і ЗЛП зі штучним базисом: 1. Якщо задача зі штучним базисом не має розв’язків, то по початкова ЗЛП не має оптимального розвязку. 2. Якщо задача зі штучним базисом має оптимальний розвязок і всі штучні змінні =0, то цей оптимальний розвязок буде оптимальним розв’язком початкової ЗЛП. 3. Якщо задача зі штучним базисом має оптимальний розвязок і хоча б одна штучна змінна>0, то початкова задача має оптимальний розвязок. 9. Етапи побудови економетричної моделі. Економетрична модель – це функція чи система функцій, що кількісно описує залежність між соціально-економічними показниками, один чи кілька з яких є залежною змінною, інші – незалежними. У загальному вигляді економетрична модель записується так: Y=f(X1, X2, X3,…Xm-1, u), Де Y – залежна змінна Xj – незалежні змінні u – стохастична складова. Етапи по побудови економетричної моделі: 1. Знайомство з економ.теорією, висунення гіпотези взаємозв’язку. Чітка постановка задачі. 2. Специфікація моделі. Використовуючи всі види функцій, які можуть бути застосовані для вивчення взаємозв’язків, необхідно сформулювати теоретичні уявлення і прийняті гіпотези у вигляді математичних рівнянь. Ці рівняння встановлюють зв’язки між основними визначальними змінними, припускаючи, що решта змінних є випадковими. 3. Формування масивів вхідної інформації згідно з метою та завданнями дослідження. 4. Оцінка параметрів економетричної моделі методом найменших квадратів. Аналіз залишків дає змогу відповісти на запитання: чи не суперечить специфікація моделі застосуванню 1 МНК. 5. Якщо деякі передумови застосування 1 МНК не виконуються, то для подальшого аналізу треба замінювати специфікацію або застосовувати інші методи оцінювання параметрів. 6. Верифікація моделі та її оцінок параметрів. 7. Прогноз на основі моделі. 10. Довірчі інтервали значень парної лінійної функції регресії із заданою надійністю (. Моделі лінійної регресії знайшли найбільш широке використання в економічних дослідженнях, хоча це і є спрощений засіб в моделюванні реальних економічних процесів. Але ґрунтовне вивчення і застосування методики побудови лінійних моделей, надає необхідну теоретичну базу для створення більш складних, нелінійних моделей, що будуть значно більше відповідати реальним економічним процесам. Крім цього, з практики побудови і досліджені парної лінійної моделі створюються необхідні передумови для економетричного аналізу. Якщо в рівняння включено лише одну пояснюючу змінну, то одержуємо теоретичну модель, яка дістала назву парної лінійної регресії: yі = ?0 + ?1xi + i . У загальному випадку парна лінійна регресія є лінійною функцією між залежною змінною Y і однією пояснюючою змінною X: Y = a0 + a1 X. Співвідношення (2.1) називається теоретичною лінійною регресійною моделлю; а0 і а1 – теоретичні параметри (теоретичні коефіцієнти) регресії. - надійність попадання в інтервал. - це табличне значення розподілу Стьюдента, з надійність і степенем вільності k=n-2. - параметри лінійної функції. 11 .Довірчі інтервали параметрів парної лінійної функції регресії із заданою надійністю (. Моделі лінійної регресії знайшли найбільш широке використання в економічних дослідженнях, хоча це і є спрощений засіб в моделюванні реальних економічних процесів. Але ґрунтовне вивчення і застосування методики побудови лінійних моделей, надає необхідну теоретичну базу для створення більш складних, нелінійних моделей, що будуть значно більше відповідати реальним економічним процесам. Крім цього, з практики побудови і досліджені парної лінійної моделі створюються необхідні передумови для економетричного аналізу. Якщо в рівняння включено лише одну пояснюючу змінну, то одержуємо теоретичну модель, яка дістала назву парної лінійної регресії: yі = ?0 + ?1xi + i . У загальному випадку парна лінійна регресія є лінійною функцією між залежною змінною Y і однією пояснюючою змінною X: Y = a0 + a1 X. Співвідношення (2.1) називається теоретичною лінійною регресійною моделлю; а0 і а1 – теоретичні параметри (теоретичні коефіцієнти) регресії. Довірчі інтервали для оцінок параметрів економетричної моделі Довірчі інтервали обчислюється за формулами: для :
для :
де табличне значення розподілу Стьюдента з надійністю ( і ступенем вільності , а та визначається за формулою: = , = , де = . 12. Довірчі інтервали прогнозного значення парної лінійної функції регресії із заданою надійністю (. Моделі лінійної регресії знайшли найбільш широке використання в економічних дослідженнях, хоча це і є спрощений засіб в моделюванні реальних економічних процесів. Але ґрунтовне вивчення і застосування методики побудови лінійних моделей, надає необхідну теоретичну базу для створення більш складних, нелінійних моделей, що будуть значно більше відповідати реальним економічним процесам. Крім цього, з практики побудови і досліджені парної лінійної моделі створюються необхідні передумови для економетричного аналізу. Якщо в рівняння включено лише одну пояснюючу змінну, то одержуємо теоретичну модель, яка дістала назву парної лінійної регресії: yі = ?0 + ?1xi + i . У загальному випадку парна лінійна регресія є лінійною функцією між залежною змінною Y і однією пояснюючою змінною X: Y = a0 + a1 X. Співвідношення (2.1) називається теоретичною лінійною регресійною моделлю; а0 і а1 – теоретичні параметри (теоретичні коефіцієнти) регресії. Прогнозування середнього значення залежної змінної. Довірчий інтервал для теоретичної функції регресії знаходимо за формулою: де табличне значення розподілу Стьюдента з надійністю ( і ступенем вільності , а визначається за формулою: =. 13. Алгоритм графічного методу розв'язування задач лінійного програмування. Для розв’язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв’язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе. Розглянемо задачу. Знайти (2.17) за умов: (2.18) .(2.19) Розв’язати задачу лінійного програмування графічно означає знайти таку вершину багатокутника розв’язків, у результаті підстановки координат якої в (2.17) лінійна цільова функція набуває найбільшого (найменшого) значення. Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків: 1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей. 2. Визначаємо півплощини, що відповідають кожному обмеженню задачі. 3. Знаходимо багатокутник розв’язків задачі лінійного програмування. 4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі. 5. Будуємо пряму с1х1 + с2х2 = const, перпендикулярну до вектора . 6. Рухаючи пряму с1х1 + с2х2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального значення. 7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці. 14. Перша основна теорема двоїстості. Теорема (перша теорема двоїстості). Якщо пряма задача має оптимальній розв’язок, то і двоїста задача має оптимальний розв’язок і навпаки. Якщо пряма задача не має оптимального розв’язку, то і двоїста задача не має оптимального розв’язку. Якщо X0 – оптимальній розв’язок прямої задачі, а Y0 – оптимальний розв’язок двоїстої задачі, то справедлива слідуюча рівність: . Економічний зміст першої теореми двоїстості. Максимальний прибуток () підприємство отримує при виробництві продукції за оптимальним планом , однак ту саму суму коштів () воно може отримати реалізуючи ресурси за оптимальними цінами . За умов використання інших планів , виходячи з основної нерівності теорії двоїстості, доходи від реалізації продукції завжди менші ніж витрати на її виробництво. ЯКщо пряма задача має оптимальній розвязок і він знайдений за допомогою симплекс методу, то оптимальний розвязок двоїстої задачі можна знайти не розвязуючи її використавши слідуючу формулу: , де – це значення стовпчика в останній симплекс таблиці. – це матриця, яка знаходиться в останній симплекс таблиці під одиничною матрицею першої симплекс таблиці. 15. Друга основна теорема двоїстості. Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани X* та Y* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:
Наслідок. Якщо в результаті підстановки оптимального плану однієї із задач (прямої чи двоїстої) в систему обмежень цієї задачі і-те обмеження виконується як строга нерівність, то відповідна і-та компонента оптимального плану спряженої задачі дорівнює нулю. Якщо і-та компонента оптимального плану однієї із задач додатна, то відповідне і-те обмеження спряженої задачі виконується для оптимального плану як рівність. Економічний зміст другої теореми двоїстості стосовно оптимального плану Х* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг , то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним». Якщо ж витрати ресурсу дорівнюють його наявному обсягові , тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка буде строго більшою від нуля. Економічне тлумачення другої теореми двоїстості щодо оптимального плану Y* двоїстої задачі: у разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю. Якщо витрати на виробництво j-го виду продукції дорівнюють ціні одиниці продукції , то її необхідно виготовляти в обсязі, який визначає оптимальний план прямої задачі . 16. Третя основна теорема двоїстості. Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі дорівнюють значенням частинних похідних від цільової функції за відповідними аргументами , або (1) Економічний зміст третьої теореми двоїстості. Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, м2, люд./год, га тощо). Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу . 17. Довірчі інтервали для прогнозного значення Yp загальної лінійної економетричної моделі із заданою надійністю (. 18. Оператор оцінювання 1МНК. Скористаємося моделлю для якої виконуються умови , щоб оцінити параметри методом 1МНК. Рівняння подамо у вигляді: . Тоді суму квадратів залишків u можна записати так:
Продиференціюємо цю умову за А і прирівняємо похідні до нуля:
або (1) Тут — матриця, транспонована до матриці незалежних змінних X. Звідси (2) Рівняння (1) дає матричну форму запису системи нормальних рівнянь, а формула (2) показує, що значення вектора А є розв’язком системи таких рівнянь. Формули (1) і (2) можна дістати й інакше. Так, помноживши рівняння зліва спочатку на , а потім на матрицю , дістанемо:
Оскільки то справджується рівність . Згідно з , коли , , отже, (2) Неважко показати, що оцінки (, обчислені за (2), мінімізують суму квадратів залишків u. При цьому значення вектору ( є розв’язком так званої системи нормальних рівнянь . Якщо незалежні змінні в матриці X взяті як відхилення кожного значення від свого середнього, то матрицю називають матрицею моментів. Числа, що розміщені на її головній діагоналі, характеризують величину дисперсій незалежних змінних, інші елементи відповідають взаємним коваріаціям. Отже, структура матриці моментів відбиває зв’язки між незалежними змінними. Чим ближчі показники коваріацій до величини дисперсій, тим ближчий визначник матриці до нуля і тим гірші оцінки параметрів . Далі буде показано, що стандартні помилки параметрів прямо пропорційні до значень, розміщених на головній діагоналі матриці . 19. Економічна та математична постановка задачі дрібно-лінійного програмування. Розв’язуючи економічні задачі, часто як критерії оптимальності беруть рівень рентабельності, продуктивність праці тощо. Ці показники математично виражаються дробово-лінійними функціями. Деяке виробництво планує виробляти N-видів продукція. При цьому використовує «m» видів ресурсів, обсяги яких = bi, i=1,m. Технологічна матриця aij, i=1,n та j=1,m. Відомі ціни Cj – одиниці j-го виду продукції. Відомі витрати dj – j-го виду продукції. С1х1 + С2х2 +…+ сnxn – прибуток виробництва d1x1 + d2x2 +…+dnxn - витрати виробництва Тоді, z = прибуток / витрати – це рентабельність виробництва (1) Обмеження, які описуються виробничий процес: a11x1 + a12x2 +…+ a1nxn <= b1 (2) a21x1 + a22x2 +…+a2nxn <= b2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ am1x1 + am2x2 +…+ amnxn <= bm X > = 0, j = 1,n Знайти: такий оптимальний план випуску продукції, щоб рентабельність від виробництва була Мах. Математична постановка задачі (1-2). Задача (1-2) – є задачею дрябно-лінійного програмування. Загальна постановак задачі. Знайти Мах. і Min. значення функції при обмеженнях:
.(3) Передбачається, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю. Очевидно, що задача (1-3) відрізняється від звичайної задачі лінійного програмування лише цільовою функцією, що дає змогу застосовувати для її розв’язування за певного модифікування вже відомі методи розв’язання задач лінійного програмування. 20. Графічний метод розв'язування задач дрібно лінійного програмування. Якщо задачы: Z = ? Сj*xj / ? dj * xj ( max ( min) (3) ? aj*xj (<>=) bj, i = 1,m (4) можна представити графічно, то її можна розв’язати графічним методом, тобто якщо задача (3-4) задана на площині або в двовимірному просторі, то для її розв’язання можна застосувати графічний метод! Знайти Мах. (Мін.) значення функції при обмеженнях: (5) (6) ,(7) (6) – допустима область нашої задачі, так як вона складається з лінійних нерівностей, то геометрично це є випуклий багатокутник. Дослідимо функцію мети: Z = c1x1 + c2x2 / d1x1 + d2x2 ( max ( min) c1x1 + c2x2 = dzx1 + dzx2 (c1 – d1z) x1 + (c2 – d2z) x2 =0 x2= - (c1 – d1z) / (c2 – d2z) x1 (7) (7) – представляє собою лінійну функцію з кутовим коефіцієнтом, який К(z) = - (c1 – d1z) / (c2 – d2z) (8) і проходить через початок координат. (8) – кутовий коефіцієнт є функція від z. Дослідимо спадання і зростання цієї функції: для цього нам потрібно знайти першу похідну: К’(z) = (d1c2-c1d2) / (c2 – d2z)^2 Маємо слідуючі випадки: а) К’(z)>0, тому (d1c2-c1d2) >0 К(z) – є зростаючою, при збільшенні (z) – (К) збільшується, і навпаки. Виходячі із вище сказаного можна запропонувати наступний спосіб знаходження екстремального значення функції мети, а саме: через допустиму область і початок координат проводимо пряму. Для задачі на Мах. Повертаємо її проти часової стрілки до тих пір, поки вона останній раз не перетне допустиму область. А для задачі на Міn. Повертаємо за часовою стрілкою, до тих пір поки вона не перетне допустиму область останній раз. Візуально визначаємо оптимальний розв’язок. Для знаходження точного розв’язку складаємо відповідну систему і розв’язуємо її. б) К’(z) <0 (d1c2-c1d2) <0 К(z) – є спадною функцією, при збільшенні (z) – (К) зменшується, і навпаки. В зв’язку з вище сказаним, пропонується наступний спосіб знаходження оптимального розв’язку: через допустиму область і початок координат проводимо пряму. На Мах. – за часовою стрілкою, до тих пір доки останній раз не перетне область. На Min. – проти часової стрілки до останнього перетину з областю. Візуально визначаємо оптимальний розв’язок. При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки: - багатокутник розв’язків задачі обмежений і максимальне та мінімальне значення досягаються у його кутових точках; - багатокутник розв’язків задачі необмежений, однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції; - багатокутник розв’язків задачі необмежений і досягається лише один із екстремумів; - багатокутник розв’язків задачі необмежений, точки екстремумів визначити неможливо. Для знаходження точного розв’язку складаємо відповідну систему і розв’язуємо її. (d1c2 – d2c1) >0
(d1c2 – d2c1) <0
21 .Алгоритм симплексного методу для задач лінійного програмування. Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів A1, A2,….,An! Отже, загальна кількість опорних планів визначається кількістю комбінацій:
Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж. Данцігом — так званий симплексний метод, або симплекс-метод. Ідея цього методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за попередній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум). Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує. Отже, симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування. Отже в загальному випадку алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів: 1. Визначення початкового опорного плану задачі лінійного програмування. 2. Побудова симплексної таблиці. 3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує. 4. Перехід до нового опорного плану задачі виконується визначенням розв’язувального елемента та розрахунком нової симплексної таблиці. 5. Повторення дій починаючи з пункта 3. 22. Метод розв'язування задачі дрібно лінійного програмування у загальному вигляді. Економічна і математична постановка задачі Розв'язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:
за умов
Припускають, що знаменник цільової функції в області допустимих розв'язків системи обмежень не дорівнює нулю. Алгоритм розв'язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо
зробимо заміну змінних
і запишемо економіко-математичну модель:
за умов
Дістали задачу лінійного програмування, яку можна розв'язати симплексним методом. Нехай оптимальний план Оптимальні значення х0j знайдемо за формулою
Графічний метод У разі, коли задача дробово-лінійного програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом. Нехай маємо таку задачу: (7.4) за умов: (7.5) , (7.6) Спочатку, як і для звичайної задачі лінійного програмування будуємо геометричне місце точок системи нерівностей (7.5), що визначає деякий багатокутник допустимих розв’язків. Допустимо, що , і цільова функція набуває деякого значення: . Після елементарних перетворень дістанемо:
або (7.7) Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х1 та х2. Розглянемо кутовий коефіцієнт нахилу прямої (7.7), що виражає цільову функцію: (7.8) Отже, кутовий коефіцієнт являє собою функцію від Z. Для визначення умов зростання (спадання) функції (7.8) дослідимо зміну знака її похідної: (7.9) Використовуючи формулу (7.9), можна встановити правила пошуку максимального (мінімального) значення цільової функції: 1.) якщо , то функція (7.8) є зростаючою, і за збільшення значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (7.7) також збільшується. Тобто у разі, якщо , для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку проти годинникової стрілки; 2.)якщо , то функція (7.8) є спадною і за збільшення значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (7.7) буде зменшуватись. Тому у разі, якщо , для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку за годинниковою стрілкою. При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки: -багатокутник розв’язків задачі обмежений і максимальне та мінімальне значення досягаються у його кутових точках; -багатокутник розв’язків задачі необмежений, однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції; -багатокутник розв’язків задачі необмежений і досягається лише один із екстремумів; -багатокутник розв’язків задачі необмежений, точки екстремумів визначити неможливо. Розв’язування зведенням до задачі лінійного програмування Нехай потрібно розв’язати задачу (7.1)—(7.3). Позначимо і введемо заміну змінних . Тоді цільова функція (7.1) матиме вигляд: Отримали цільову функцію, що виражена лінійною залежністю. Оскільки , то звідси маємо: . Підставимо виражені через нові змінні значення в систему обмежень (7.2):
Крім того, з початкової умови Умова (7.3) стосовно невід’ємності змінних набуває вигляду: . Виконані перетворення приводять до такої моделі задачі:
Отримали звичайну задачу лінійного програмування, яку можна розв’язувати симплексним методом. Допустимо, що оптимальний розв’язок останньої задачі існує і позначається: . Оптимальні значення початкової задачі (7.1)—(7.3) визначають за формулою: . 23. Довірчі інтервали значень множинної лінійної функції регресії із заданою надійністю (. 24. Довірчі інтервали параметрів множинної лінійної функції регресії із заданою надійністю (. 25. Форми запису лінійної задачі оптимізації: в скороченому вигляді, в матричній і векторній формах. 1. матричний Z=cx ( max(min) AX=B, x(0, де C=(C1 C2…Cn)
3. Через знак ? (1) , i=1,m (2) Xj ( 0, j=1,n (3) Вектор Х=(х1,х2…хn) називається допустимим розв’язком задачі (1)-(2), якщо задовольняє обмеження (3). 26. Метод найменших квадратів (1МНК). (Система нормальних рівнянь). Якщо припустити, що економетрична модель з двома змінними є лінійною: , в якій стохастична складова (залишки) має нульове математичне сподівання та постійну дисперсію, то параметри моделі можна оцінити на основі звичайного методу найменших квадратів (1МНК). В основі методу 1МНК лежить принцип мінімізації суми квадратів залишків моделі. Реалізація цього принципу дає можливість отримати систему нормальних рівнянь:
В даній системі n — кількість спостережень, , ,, — величини, які можна розрахувати на основі вихідних спостережень над змінними Y і X. Щоб оцінити параметри моделі на основі методу 1МНК, необхідно дотримуватися таких передумов (гіпотез): 1) математичне сподівання залишків має дорівнювати нулю, тобто M(u) = 0; 2) значення вектора залишків u незалежні між собою і мають постійну дисперсію:
незалежні змінні моделі не зв’язані із залишками, тобто ; 4) незалежні змінні моделі створюють лінійно-незалежну систему векторів, тобто
Оператор оцінювання параметрів моделі на основі 1МНК: Неважко довести, що оцінки , які можна отримати на основі оператора оцінювання 1МНК, мінімізують суму квадратів залишків u. При цьому значення вектора є розв’язком нормальної системи рівнянь:
Якщо незалежні змінні в матриці X взяті як відхилення кожного значення від своєї середньої, то матрицю називають матрицею моментів. Числа, що стоять на її головній діагоналі, характеризують величину дисперсій незалежних змінних, інші елементи відповідають взаємним коваріаціям. 27. Постановка транспортної задачі. Представляє собою ЗЛП. Це означає, що її можна досліджувати і розв’язувати, використовуючи теорію ЛП. Використовуючи специфіку ТЗ, для неї існують свої методи розв’язання, які є більш прості, ніж загальні. Економічна постановка. Деякий однорідний продукт перевозиться з m пунктів постачання з обсягами ai, і=1, m в n пунктів споживання з потребами bij, j=1,n. Із всіх пунктів постачання у всі пункти споживання представлені у вигляді матриці перевезення.
Необхідно знайти такий оптимальний план перевезень, щоб загальна вартість всіх перевезень була мінімальною. Математична постановка. Позначимо через xij – кількість однорідної продукції, яка перевозиться із і-го пункту постачання в bj - пункт споживання. Умову ТЗ зручно задавати у вигляді симплекс-таблиці для ТЗ. Bj Ai B1 B2 … Bn
b1 b2 … bn
A1 a1 c11 X11 c12 X12 … c1n X1n
A2 a2 c21 X21 c22 X22 … c2n X2n
… … … … … …
Am am cm1 Xm1 cm2 Xm2 … cmn Xmn
Функція мети, яка економічно означає, що сумарна вартість перевезень повинна бути мінімальною, математично можна записати наступним чином: Z = c11x11 + c12x12 + … + c1nx1n + + c21x21 + c22x22 + … + c2nx2n + (1) + cm1xm1 + cm2xm2 … + cmnxmn ( min Так, як вся продукція повинна бути вивезена із пункту постачання, то математично це можна записати наступним чином: x11 + x12 + … + x1n = a1 x21 + x22 + … + x2n = a2 (2) xm1+ xm2 + … + xmn = am Всі потреби пунктів споживання повинні бути виконані, то це можна записати наступним чином: x11 + x12 + … + x1n = b1 x21 + x22 + … + x2n = b2 (3) xm1+ xm2 + … + xmn = bm (1)-(4) – математична постановка ТЗ. Транспортна задача — це специфічна задача лінійного програмування, застосовувана для визначення найекономічнішого плану перевезення однорідної продукції від постачальників до споживачів. Математична модель транспортної задачі має такий вигляд:
за обмежень
де xij – кількість продукції, що перевозиться від і-го постачальника до j-го споживача; cij – вартість перевезення одиниці продукції від і-го постачальника до j-го споживача; ai – запаси продукції i-го постачальника; bj – попит на продукцію j-го споживача. Якщо в транспортній задачі загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, то таку транспорту задачу називають збалансованою, або закритою. Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою. Планом транспортної задачі називають будь-який розв'язок системи обмежень, що вказані вище ТЗ, який позначають матрицею 28. Методи розв'язання транспортної задачі. Один із способів розв’язування транспортної задачі ґрунтується на розгляді двоїстої задачі. Розглянемо транспортну задачу. (5.1) за обмежень: ;(5.2) ;(5.3) .(5.4) Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються. Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої: (5.20) (5.21) . Згідно з загальними правилами побудови двоїстих задач маємо: (5.22) за умов: ,(5.23) . Метод потенціалів розв’язування транспортної задачі. Алгоритм методу потенціалів складається з таких етапів: 1.Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу. 2.Побудова першого опорного плану транспортної задачі одним з відомих методів. 3.Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання. 4.Перевірка плану транспортної задачі на оптимальність. 4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих — . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. 4.2. Перевірка виконання умови оптимальності для пустих клітин. 4.3. Вибір змінної для введення в базис на наступному кроці. 4.4. Побудова циклу і перехід до наступного опорного плану. 5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується — маємо оптимальний план транспортної задачі Угорський метод розв’язування транспортної задачі. (5.27) (5.28) (5.29) Починаючи з деякого початкового плану задачі, подвійної до транспортної , можна знайти послідовність оптимальних планів ряду допоміжних задач на мінімізацію (5.29) за обмежень (5.27) і (5.28), кожний наступний план якої надає нев’язці (5.29) меншого значення у зіставленні з попереднім, а останній план цієї послідовності надає нев’язці нульового значення, збігаючись у такий спосіб з оптимальним планом транспортної задачі. Отже, кожна ітерація методу означатиме розв’язування допоміжної задачі (5.27)—(5.28) і зменшення при цьому значення цільової функції (5.29) порівняно з попереднім розв’язком цієї задачі. Ідея методу полягає у здійсненні послідовного переходу від деякого недопустимого плану (не всі потреби задоволені і не вся продукція вивезена) до допустимого, що є розв’язком задачі. Цей перехід здійснюється за скінченну кількість ітерацій (але невідому до кінця обчислень), що пов’язані з перетвореннями матриці вартостей і поточного плану . Виходячи з наведених теоретичних засад, розглянемо алгоритм угорського методу: 1. Побудова допоміжної задачі з цільовою функцією (5.32) та умовами (5.27), (5.28). 2. Побудова початкового опорного плану допоміжної задачі, що отримана на попередньому кроці алгоритму, одним з відомих методів. 3. Відшукання оптимального плану допоміжної задачі. 3.1.Збільшення значення. Визначають рядки, де сума перевезень по рядку менша від запасів, а за допомогою них — стовпці, які мають у вибраному рядку не заборонені для перевезень клітини. Вибрані рядки і стовпці позначають так: , ,(5.33) та .(5.34) Потім , .(5.35) 3.2. Визначення клітин, значення перевезень в яких необхідно змінити. Послідовність цих клітин повинна утворювати деякий ланцюг, елементи якого є в позначених рядках та колонках і за яким можна перенести лишок запасу деякого -го рядка, що був позначений першим, у -ту колонку, позначену останньою. У загальному випадку послідовність має вигляд:
4. Перехід до наступної допоміжної задачі, оптимальний план якої буде ближчим до оптимального плану початкової транспортної задачі. 5. Повторення кроків 2—4 до відшукання оптимального плану початкової транспортної задачі. Двохетапна транспортна задача Метод розв’язування двохетапної транспортної задачі, розроблений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять нульові величини затрат. Решту клітин таблиці блокують, тобто вартості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам двохетапної транспортної задачі. За деяких умов, наприклад, при перевезенні продукції, що швидко псується; матеріалів для аварійних та рятівних робіт тощо вартість перевезень має другорядне значення, а на перше місце виходить завдання мінімізації того часу, протягом якого здійснюються всі перевезення. Так виникає транспортна задача за критерієм часу. Розглянемо алгоритм розв’язання сформульованої задачі, що ґрунтується на послідовному розв’язуванні ряду допоміжних задач, розглянутих в угорському методі. 1. Знаходять мінімальний елемент матриці тривалостей перевезень Т. 2. Розв’язують додаткову задачу з визначеною множиною заборонених для перевезень клітин . 3. Аналогічно першому кроку знову знаходять мінімальний елемент серед тих елементів матриці тривалостей перевезень Т, які відповідають клітинам, забороненим для перевезень. 4. Аналогічно другому кроку розв’язують нову допоміжну задачу з іншою множиною клітин, заборонених для перевезень Серед сучасних методів оптимізації і керування виробничими процесами значна роль належить мережевим методам. Широке коло задач математичного програмування можна подати в мережевому вигляді. На першому етапі складаємо початковий план перевезень На другому етапі для кожної вершини визначаємо потенціал. Перший потенціал вибираємо довільно, пов’язуємо його з довільною вершиною, наприклад, першою. Потенціали інших вершин визначаємо, виходячи з першого потенціалу. Третій етап полягає в перевірці плану на оптимальність, причому використовується звичайна ознака оптимальності плану транспортної задачі, яка формулюється в термінах і позначеннях транспортної задачі на мережі. 29. Методи знаходження початкового опорного плану транспортної задачі. Розглянемо методи північно-західного кута, мінімальної вартості, подвійної переваги та метод апроксимації Фогеля. Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами. Метод подвійної переваги. Якщо розмірність задачі досить велика, то перебір за методом мінімальної вартості ускладнюється. В такому разі спростити пошук клітин з найменшими вартостями можна, застосовуючи метод подвійної переваги. Таблицю починають заповнювати з клітинок, позначених двічі (які містять вартості, що є мінімальними і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (що містять мінімальні вартості або в рядку, або в стовпчику), а вже потім — за методом мінімальної вартості. Застосування для побудови опорного плану даного методу уможливлює отримання найменшого у зіставленні з розглянутими вище значення цільової функції. Отже, такий план є найближчим до оптимального. Метод апроксимації Фогеля. За цим методом на кожному кроці визначають різницю між двома найменшими вартостями в кожному рядку і стовпчику транспортної таблиці. Ці різниці записують у спеціально відведених місцях таблиці — знизу та справа у кілька рядків та стовпчиків, що відповідають крокам заповнення таблиці. З-поміж усіх різниць вибирають найбільшу і у відповідному рядку чи стовпчику заповнюють клітинку з найменшою вартістю. Якщо ж однакових найбільших різниць кілька, то вибирають будь-який відповідний рядок або стовпчик. Коли залишається незаповненим лише один рядок або стовпчик, то обчислення різниць припиняють, а таблицю продовжують заповнювати за методом мінімальної вартості. Даний метод побудови опорного плану враховує не лише маршрути з мінімальними витратами перевезень продукції, але й співвідношення витрат у рядку чи стовпчику, тобто розраховується наскільки, може збільшитися вартість постачання на наступних кроках процедури, якщо не здійснити на поточному кроці постачання в клітину з мінімальною вартістю.Метод апроксимації Фогеля дає змогу особливо для задач великих розмірностей скласти найкращий опорний план. 30. Порівняльна характеристика задач лінійного і нелінійного програмування. Якщо якесь bi від’ємне, то, помноживши i-те обмеження на (– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності аi1х1 + аi2х2 + … + аinxn ? bi, то останню завжди можна звести до рівності, увівши додаткову змінну xn + 1: ai1x1+ai2x2+…+ ain xn + xn + 1 = bi. Аналогічно обмеження виду аk1x1 + ak2x2 + … + aknxn ? bk зводять до рівності, віднімаючи від лівої частини додаткову змінну хn + 2, тобто: ak1x1 + ak2x2 + … + aknxn – xn + 2 = bk (хn+1 ? 0, хn+2 ? 0). Загальна лінійна економіко-математична модель економічних процесів та явищ — так звана загальна задача лінійного програмування подається у вигляді: (2.1) за умов: (2.2) (2.3) Отже, потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (2.2) і (2.3), і цільова функція (2.1) набуває екстремального (максимального чи мінімального) значення. Для загальної задачі лінійного програмування використовуються такі поняття. Вектор Х = (х1, х2, …, хn), координати якого задовольняють систему обмежень (2.2) та умови невід’ємності змінних (2.3), називається допустимим розв’язком (планом) задачі лінійного програмування. Допустимий план Х = (х1, х2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (2.2) у вигляді рівностей, а також обмеження (2.3) щодо невід’ємності змінних. Опорний план Х = (х1, х2, …, хn), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений. Опорний план , за якого цільова функція (2.1) досягає масимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування. Задача пошуку оптимальних обсягів виробництва ґрунтується на допущеннях про лінійність зв’язку між витратами ресурсів і обсягами виготовленої продукції; між ціною, рекламою та попитом тощо. Але такі зв’язки насправді є нелінійними, тому точніші математичні моделі доцільно формулювати в термінах нелінійного програмування. загальновідомим є факт, що за умов ринкової конкуренції питання реалізації продукції є досить складним. Обсяг збуту продукції визначається передусім її ціною, отже, як цільову функцію доцільно брати максимізацію не всієї виготовленої, а лише реалізованої продукції. Необхідно визначати також і оптимальний рівень ціни на одиницю продукції, за якої обсяг збуту був би максимальним. Отже, маємо задачу нелінійного програмування. Також добре відома транспортна задача стає нелінійною, якщо вартість перевезення одиниці товару залежить від загального обсягу перевезеного за маршрутом товару.Нарешті, будь-яка задача стає нелінійною, якщо в математичній моделі необхідно враховувати умови невизначеності та ризик. Загальна задача математичного програмування формулюється так: знайти такі значення змінних xj , щоб цільова функція набувала екстремального (максимального чи мінімального) значення: (8.1) за умов: (); (8.2) Якщо всі функції та , є лінійними, то це задача лінійного програмування, інакше (якщо хоча б одна з функцій є нелінійною) маємо задачу нелінійного програмування. 1. Загальна економіко-математична модель задачі лінійного програмування. Допустимий та оптимальний план задачі лінійного програмування. 2. Завдання економетричного дослідження. 3. Двоїстість у лінійному програмуванні. Економічний зміст двоїстих оцінок. 4. Правила побудови двоїстих задач. 5. Геометрична інтерпретація задачі лінійного програмування. 6. Означення економетричної моделі. 7. Метод множників Лагранжа розв'язування нелінійних задач оптимізації. 8. Симплексний метод зі штучним базисом. Ознака оптимальності плану зі штучним базисом. 9. Етапи побудови економетричної моделі. 10. Довірчі інтервали значень парної лінійної функції регресії із заданою надійністю (. 11 .Довірчі інтервали параметрів парної лінійної функції регресії із заданою надійністю (. 12. Довірчі інтервали прогнозного значення парної лінійної функції регресії із заданою надійністю (. 13. Алгоритм графічного методу розв'язування задач лінійного програмування. 14. Перша основна теорема двоїстості. 15. Друга основна теорема двоїстості. 16. Третя основна теорема двоїстості. 17. Довірчі інтервали для прогнозного значення Yp загальної лінійної економетричної моделі із заданою надійністю (. 18. Оператор оцінювання 1МНК. 19. Економічна та математична постановка задачі дрібно-лінійного програмування. 20. Графічний метод розв'язування задач дрібно лінійного програмування. 21 .Алгоритм симплексного методу для задач лінійного програмування. 22. Метод розв'язування задачі дрібно лінійного програмування у загальному вигляді. 23. Довірчі інтервали значень множинної лінійної функції регресії із заданою надійністю (. 24. Довірчі інтервали параметрів множинної лінійної функції регресії із заданою надійністю (. 25. Форми запису лінійної задачі оптимізації: в скороченому вигляді, в матричній і векторній формах. 26. Метод найменших квадратів (1МНК). (Система нормальних рівнянь). 27. Постановка транспортної задачі. 28. Методи розв'язання транспортної задачі. 29. Методи знаходження початкового опорного плану транспортної задачі. 30. Порівняльна характеристика задач лінійного і нелінійного програмування.
