Як визначити, що ресурс є дефіцитним (недефіцитним)?

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

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

 Ресурси, що використовуються для виробництва продукції, можна умовно поділити на дефіцитні та недефіцитні залежно від того, повне чи часткове їх використання передбачене оптимальним планом прямої задачі. Якщо двоїста оцінка уі в оптимальному плані двоїстої задачі дорівнює нулю, то відповідний і-й ресурс використовується у виробництві продукції не повністю і є недефіцитним. Якщо ж двоїста оцінка уі > 0, то і-й ресурс використовується для оптимального плану виробництва продукції повністю і називається дефіцитним. У цьому разі величина двоїстої оцінки показує, на скільки збільшиться значення цільової функції Z, якщо запас відповідного ресурсу збільшити на одну умовну одиницю.

 

Суть методу штучного базису.

Більшість задач не може бути зведена до канонічного вигляду. В цьому разі застосовується метод штучного базису. Тобто отримати одиничну матрицю можливо, якщо до кожного рівняння додати додаткову одну змінну. Ці змінні називаються штучними. Їх необхідно вводити в ті рівняння, які не розв’язані відносно базисних змінних. У результаті додавання змінних область допустимих розв’язків задачі розширюється. Тому розв’язок розширеної задачі збігатиметься з розв’язком початкової задачі тільки в тому разі, якщо всі введені змінні будуть виведені з базису. Згідно з симплекс методом до базису вводяться ті змінні, які покращують значення цільової функції. У цільову функцію штучні змінні додаються з коефіцієнтом М, якщо задана завдання на знаходження мінімуму. У цьому випадку величина М передбачається достатньо великим позитивним числом. Якщо необхідно знайти мінімальне значення цільової функції, то штучні змінні записують з коефіцієнтом (-М), який передбачається досить малим негативним числом. Для знаходження оптимального плану у випадку, якщо заздалегідь не задана величина М, застосовується симплекс-метод, який в таблиці має на один рядок більше, ніж звичайна симплекс-таблиця. Після перетворення задачі використовується проста симплекс-процедура.

 

44. Як впливає на оптимальний план введення додаткового обмеження?

Для знаходження оптимальних планів задач цілочислового програмування застосовують такі групи методів:

1) точні методи:

· методи відтинання;

· комбінаторні методи;

2) наближені методи.

Основою методів відтинання є ідея поступового «звуження» області допустимих розв’язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв’язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі введенням у модель спеціальних додаткових обмежень, що враховують цілочисловість змінних, багатогранник допустимих розв’язків послабленої задачі поступово зменшують доти, доки змінні оптимального розв’язку не набудуть цілочислових значень.

До цієї групи належать:

а) методи розв’язування повністю цілочислових задач (дробовий алгоритм Гоморі);

б) методи розв’язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).