9. Економіко-математичний аналіз оптимальних розв’язків прямої та двоїстої задач. Аналіз стійкості оптимального плану відносно обмежень по ресурсам.

Теорема (перша теорема двоїстості). Якщо одна з двоїстої пари задач має розв’язок, то інша також розв’язувана, причому екстремальні значення цільових функцій однакові. Якщо цільова функція одної із задач не обмежена на множині планів, то система обмежень іншої задачі суперечна.

Примітки 1. Якщо в ході побудови математичної моделі двоїстої задачі і-те обмеження вихідної задачі множили на l, то значення і-ї компоненти оптимального плану двоїстої задачі треба поділити на l. В процесі доведення цієї теореми доводиться: якщо вихідна задача розв’язується СМ, в цих же таблицях розв’язується і двоїста задача. При цьому оптимальний план двоїстої задачі виписується із останьої симплексної таблиці вихідної задачі - з індексного рядка на перетині зі стовпцями тих векторів, які були базисними в першій симплексній таблиці, якщо до того числа додати відповідний коефіцієнт цільової функції.

2. Твердження, обернене другій частині теореми взагалі кажучи, неправильне. Якщо система основних обмежень одної з пар двоїстих задач суперечна, це не означає, що друга задача обов’язково має непорожню множину планів і не обмежену на ньому цільову функцію. В обох задачах система основних обмежень може бути суперечною.

Теорема Для того щоб плани X* = ( і Y* = ( вихідної та двоїстої задач були оптимальними, необхідно й достатньо, щоб виконувались умови

Економіко-математичний аналіз розв’язку ЗЛП: ЕМА проводиться за допомогою властивостей двоїстих оцінок (об’єктивно-обумовлених оцінок за виразом Л.В. Кантаровича), які є оптимальним планом двоїстої задачі.

Властивості двоїстих оцінок:

оцінка як міра дифіцитності ресурсів – ця властивість випливає із співвідношення 2.76 – 2.77: якщо оцінка і-того ресурсу >0, тобто y_i^* >0, то для виконання умов 2.77 необхідно щоб витрати ресурса і-того виду на весь план виробництва дорівнював його запасу в_і. Тому якщо оціка y_i^* >0, то цей ресурс використаний повністю і він є дифіцитним. Якщо ж витрати ресурсу і-того виду на весь план виробництва меньше його запасу, то для виконання умови 2.77 необхідна рівність нулю y_i^*, тільки якщо y_i^*=0, то і-ий ресурс повністю не використаний, він є в надлишку;

1. оцінка як міра впливу обмеження на цільову функцію

2. оцінка як інструмент аналізу різних варіантів плана виробництва

3. оцінка як інструмент балансування сумарних витрат і сумарного ефекту – випливає із І теореми двоїстості Z_max=F_min;

4. оцінка як міра взаємозамінності ресурсів.

10. Постановка та математична модель відкритих транспортних задач (ТЗ). Зведення їх до закритої ТЗ. Нехай сумарний попит перевищує пропозицію, тобто .

В цьому разі неможливо задовольнити попит усіх споживачів, тому економічна постановка задачі така: скласти план перевезень, за якого весь товар від усіх постачальників вивозиться, попит споживачів по можливості задовольняється (споживачі одержують товари в кількостях, які не перевищують їх попиту) і сумарні транспортні витрати мінімальні.

Розглянемо математичну модель такої задачі.

Увесь товар, який мають постачальники, вивозиться: Споживачі одержують товар у кількостях, які менші або дорівнюють попиту на нього:

.

Умова невід’ємності і цільова функція не змінюються

x_ij ³ 0 .

Якщо сумарна пропозиція перевищує сумарний попит , задоволення попиту споживачів не супроводжується повним вивезенням товару від постачальників. Отже, економічна постановка задачі така: скласти план перевезень, за якого потреби всіх споживачі задовольняються, від постачальників вивозяться товари в кількості, до не перевищує їх потужності, й сумарна вартість перевезень мінімальна.

Першу умову задачі можна записати у вигляді

; друга умова

Окрім того, зберігаються умови невід’ємності

x_ij ³ 0 .

і цільова функція

Очевидно, що моделі являють собою ЗЛП, задані не в канонічному вигляді. Щоб звести їх до канонічного вигляду, в нерівності треба ввести додаткові невід’ємні змінні, які ввійдуть до цільової функції з нульовими коефіцієнтами.

З метою змістовної економічної інтерпретації цих змінних позначимо їх таким чином.

Підсумувавши співвідношення за j, дістанемо

.

Змінивши порядок підсумовування в першому доданку, з урахуванням отримаємо

+ ,

або

–.

Ліва частина отриманого співвідношення – це кількість товарів, що вивозяться від А_{т + 1} до всіх споживачів, тобто потужність (т + 1)-го постачальника.

Отже, щоб звести відкриту ТЗ до канонічного вигляду, тобто до закритої ТЗ, вводять (т + 1)-го фіктивного постачальника, потужність якого , і тарифи перевезень від нього дорівнюють нулю.

Аналогічно з випливає, що набір {x_{іп + 1}} можна інтерпретувати як перевезення до деякого (п + 1)-го фіктивного споживача. Отже, ввівши фіктивного споживача чи постачальника, відкриту ТЗ можна звести до закритої й таким чином звести задачу до канонічної форми.

11. Постановка та математична модель закритої ТЗ. Теорема про існування розв’язку ТЗ. ТЗ називається закритою, якщо сумарний попит дорівнює сумарній пропозиції:

= .

Скласти план перевезень, за якого вивозиться весь товар від постачальників, попит усіх споживачів задовольняється й транспортні витрати мінімальні.

Щоб скласти математичну модель, уведемо матрицю змінних Х = ||х_ij||, де х_ij - запланований обсяг перевезень від A_i до B_j. Очевидно, що розмірність цієї матриці m ´ n і матриця визначає шуканий план перевезень.

Знайдемо вираз кількості товарів, щo вивозиться від A_i. Першому споживачеві заплановано поставку х_і1, другому – х_і2 і т.д., п-му – х_1п. Сума цих величин х_і1 + х_і2 + ... + х_1п, або в скороченому запису визначає запланований вивіз товару від A_i. За умовою задачі весь товар треба вивезти, отже, має виконуватися умова

.

Аналогічно запланована кількість товару, що надходить до B_j, складається з поставок від А₁ – х_1j, від А₂ – х_2j, від А_m – х_mj. Сума х_1j + х_2j + ...+ х_mj = – це кількість товару, що направляється до B_j. Оскільки всіх споживачів треба задовольнити, отримуємо таку систему обмежень:

Розглянемо можливий знак невідoмих x_ij. Величина x_ij> 0 означає, що планується перевезення від А_і до B_j, якщо x_ij = 0, перевезення не планується. Випадку x_ij < 0 відповідає перевезення від B_j до А_і, що суперечить умові задачі. Отже,

x_ij ³ 0

Найдемо математичний вираз цільової функції задачі – сумарної вартості перевезень. Тариф перевезень, тобто вартість перевезення одиниці товару за маршрутом А_іB_j становить с_ij. Якщо за цим маршрутом перевозиться x_ij одиниць товару, то затрати становитимуть с_ijx_ij. Вираз відображує вартість перевезень від А_і до всіх B_j. Підсумовуючи його за j, дістаємо вартість перевезень

Згідно з умовою задачі треба знайти план, який забезпечує мінімум транспортних витрат, отже, цільова функція задачі має вигляд

Теорема(умова існування розв’язку транспортної задачі). Необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість, тобто =