Главная | Обратная связь | Поможем написать вашу работу!

Розширена форма математичної моделі

Для використання методів розв’язування задач лінійного програмування кожну математичну модель конкретної задачі треба перетворити на таку форму, яка передбачається розробленими алгоритмами розв’язування. Таку форму будемо називати розширеною. Згідно з нею для розв’язування задач симплекс-методом потрібно, щоб математична модель задачі задовольняла таким вимогам:

– усі вільні члени обмежень ;

– наявність тільки рівнянь-обмежень;

– наявність одиничного базису.

Перші дві вимоги відповідають канонічній формі запису задачі лінійного програмування.

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

Якщо обмеження задані як “ ” або „ ”, то кожний такий вираз перетворюється у рівняння за допомогою додаткових змінних з коефіцієнтами :

де коефіцієнтизнак коефіцієнта „1” при додаткових змінних залежать від знаку нерівності: для “ ” +1 для „ ” -1.

Додаткові змінні вводять до цільової функції з нульовими коефіцієнтами , тобто

Крім того, якщо в будь-якому обмеженні ліва частина , то таке обмеження треба помножити на -1.

Щодо одиничного базису, то він завжди існує, якщо в кожному рівнянні математичної моделі введена нова змінна з коефіцієнтом +1.

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

де входить тільки до і -го обмеження з коефіцієнтом +1.

При утворенні одиничного базису можуть бути такі випадки.

Перший випадок. Одиничний базис створюється автоматично, коли всі обмеження-нерівності перетворюються в обмеження-рівностіяння. У цьому разі задана математична модель має вигляд. Сказати, що всі х невід’ємні?

Щоб одиничний базис існував, кожне обмеження доповнюють додатковими змінними з коефіцієнтами +1:

У цьому разі задачу називають задачею з натуральним базисом.

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

Оскільки

то у першому базисному розв’язку

Другий випадок. Якщо всі або частина обмежень мають вигляд

то одиничний базис треба дістати штучно.

Після зведення таких обмежень до канонічного вигляду маємо

а це означає, що

цим самим не задовольняється умова невід’ємності змінних.

Тому в кожне таке обмеження крім додаткової змінної з коефіцієнтом -1 уводять ще одну змінну з коефіцієнтом +1. Ця змінна фіктивна, тому її називають штучною. Її вводять у модель для того, щоб штучно добути одиничний базис. При цьому перший базисний розв’язок є розв’язком зі штучним базисом.

У цьому разі обмеження мають вигляд

Оскільки штучні змінні не мають економічного змісту, то вони в оптимальному розв’язку задачі не повинні бути в сукупності базисних змінних. Математично це зображується так: усі штучні змінні вводять у цільову функцію з великим коефіцієнтом М, тобто штучні змінні мають значні великі „штрафні” коефіцієнти цільової функції. Причому + М, якщо , та – М, якщо . У цьому разі штучна змінна навіть при нескінченно малих своїх значеннях змінює на достатньо велике протилежне значення цільову функцію за допомогою коефіцієнта М. Тому в оптимальному розв’язку задачі штучні змінні виключаються з базису, тобто дорівнюють нулю.

Цільова функція в цьому випадку має вигляд

Метод розв’язування задачі із штучнім базисом іноді називають М- методом.

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

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒