Вирішення ЗЦЛП методом округлення
Метод округлення - найпростіший метод наближеного вирішення ЗЦЛП. Його сутність полягає в тому, що вирішується ослаблена задача (як задача лінійного програмування) і отримане оптимальне рішення ЗЛП округляється до цілочислового рішення. Цей метод має два суттєвих недоліки: 1) у результаті округлення може вийти неприпустиме рішення; 2) рішення, отримане в результаті округлення, будучи припустимим, може значно відрізнятися від оптимального.
Приклад 1. Вирішивши геометрично ослаблену задачу, одержуємо оптимальне рішення: Зробимо округлення: 1) x1=2; x2=0. Одержимо неприпустиме рішення - не задовольняється обмеження 7x1+4x2<=13 (дійсно, 7*2+4*0<=13 – хибна нерівність). 2)х1=1; х2=0. Це припустиме рішення. Значення цільової функції f=21*1+11*0=21, що значно відрізняється від оптимального значення. Оптимальне рішення цієї ЗЦЛП таке: х1=0; х2=3; fmax =33. Метод округлення можна використовувати тоді, коли цільова функція малочутлива до змін змінних у межах одиниці.
Метод гілок і меж
Цей метод точного вирішення ЗЦЛП найчастіше використовується на практиці. Він полягає в наступному. Спочатку вирішується ослаблена задача. Якщо отримане оптимальне рішення цілочислове, то ЗЦЛП вирішена. Якщо ж оптимальне рішення ЗЛП не є цілочисловим, то робимо "розгалуження" у такий спосіб. Нехай змінна хs прийняла в оптимальному рішенні значення qs, що не є цілим. Тоді розглядаємо дві ЗЦЛП. Перша виходить додаванням обмеження хs <=[qs], друга – додаванням обмеження хs >=[qs] + 1, де [qs] - ціла частина числа qs . Кожна із цих двох задач аналогічним способом може розбитися ще на дві задачі і т.д. Якщо в результаті вирішення якої-небудь із задач виходить цілочисловий оптимальний план, то значення Ацільової функції при цьому плані відіграє роль "межі": якщо в результаті вирішення чергової ЗЛП з'ясується, що оптимальне значення цільової функції "гірше" А, тоді така задача "не гілкується". Недолік методу гілок і меж полягає в тому, що часто оптимальне рішення ЗЦЛП досягається після дуже великої кількості розгалужень.
Повернемося до ЗЦЛП прикладу 1. Використовуємо геометричний метод вирішення для відшукання оптимальних планів ослаблених задач.
Вихідна ЗЦЛП №1 ( оптимальний план )
оптимальний план ОПР порожня.
оптимальний план оптимальний план х1=1, х2=1, fmax=32 х1= , х2=2, fmax=37 A=32- межа
оптимальний план ОПР порожній х1=0, х2= , fmax=35,75
Оптимальний план ОПР порожній х1=0, х2=3, fmax=33>A
Оптимальний план ЗЦЛП: х1=0, х2=3, fmax=33.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|