На головну

Алгоритм пошуку опорного і оптимального рішення

  1. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  2. II. Проблема виродженого базисного рішення
  3. Автомобільного транспорту та шляхи їх вирішення
  4. АЛГОРИТМ 10
  5. алгоритм DES
  6. алгоритм RSA
  7. Алгоритм автоматичного формування парних симетричних ключів шифрування-дешифрування відкритих повідомлень на робочих станціях абонентів корпоративної системи.

Геометрична інтерпретація, якою ми користувалися при вирішенні задач лінійного програмування, перестає бути придатною для цієї мети при числі вільних змінних n-m  , А скрутна вже при n-m = 3. Для знаходження рішення задачі лінійного програмування в загальному випадку (при довільному числі вільних змінних) застосовуються не геометричні, а обчислювальні методи. З них найбільш універсальним є так званий симплекс-метод.

Ідея симплекс-методу відносно проста. Нехай в задачі лінійного програмування бути n змінних і m незалежних лінійних обмежень, заданих у формі рівнянь. Ми знаємо, що оптимальне рішення (якщо воно існує) досягається в одній з опорних точок (вершин ОДР), де, по крайней мере, k = n-m з змінних дорівнюють нулю. Виберемо якісь змінних в якості вільних і висловимо через них інші m базисних змінних. Нехай, наприклад, в якості вільних обрані перші k = n-m змінних х1, х2, ..., Хk, А решта m виражені через них:

 (5.1)

Спробуємо, що буде, якщо покласти всі вільні змінні х1, х2, ..., Хk рівними нулю:

При цьому ми отримаємо:

Це рішення може бути допустимим або неприпустимим. Воно допустимо, якщо всі вільні члени ?k+1, ?k+2, ..., ?n невід'ємні. Припустимо, що ця умова виконана. Тоді ми отримали опорне рішення. Але чи є воно оптимальним? Може бути так, а може бути і немає. Щоб перевірити це, висловимо максімізіруемую лінійну функцію L через вільні змінні х1, х2, ..., Х k:

 (5.2)

Очевидно, що при х1= х2= .... = Хk= 0, L = ?0. Подивимося, чи не можемо ми поліпшити рішення, тобто збільшити функцію L, збільшуючи якісь із змінних х1, х2, ..., Х k (Зменшити ми їх не можемо, так як всі вони дорівнюють нулю, а негативні значення змінних неприпустимі). Якщо всі коефіцієнти ?1, ?2, ..., ?k у формулі (5.2) негативні, то, збільшуючи якісь із змінних х1, х2, ..., Х k понад нуля, ми не можемо збільшити L; отже, знайдене нами опорне рішення є оптимальним. Якщо ж серед коефіцієнтів ?1, ?2, ..., ?k у формулі (5.2) є позитивні, то, збільшуючи деякі з змінних х1, х2, ..., Х k, А саме - ті, коефіцієнти при яких позитивні, ми можемо поліпшити рішення, тобто збільшити L.

Нехай, наприклад, коефіцієнт ?1 у формулі (5.2) позитивний Значить, є сенс збільшити х1, Тобто перейти від даного опорного рішення до іншого, де змінна х1 не дорівнює нулю, а замість неї дорівнює нулю якась інша. збільшення х1 «Корисно» для лінійної функції L, робить її більше. Однак збільшувати х1 треба обережно, так щоб не стали негативними інші змінні хk+1, хk+2, ..., Хn, Виражені через вільні змінні, зокрема, через х1 формулами (5.1).

Подивимося, чи небезпечно для змінних хk+1, хk+2, ..., Хn збільшення х1, Тобто чи може воно зробити їх негативними? Так, небезпечно, якщо коефіцієнт при х1 у відповідному рівнянні негативний. Якщо серед рівнянь (5.1) немає рівняння з негативним коефіцієнтом при х1, То величину х1 можна збільшувати безмежно, а, значить, лінійна функція L не обмежена зверху і оптимального рішення ОЗЛП не існує.

Припустимо, що це не так і серед рівнянь (5.1) є такі, в яких коефіцієнт при х1 від'ємний. Для змінних, що стоять в лівих частинах цих рівнянь, збільшення х1 небезпечно - воно може зробити їх негативними.

Візьмемо одну з таких змінних хi і подивимося, наскільки можна все ж збільшити х1 поки змінна хi не стане негативною? випишемо  -е рівняння з системи (5.1):

Тут вільний член ?i ? 0, а коефіцієнт ?i1 від'ємний. Легко зрозуміти, що якщо ми залишимо х2= ... = Хk= 0, то х1 ми можемо збільшувати тільки до значення, рівного - ?i/ ?i1 , А при подальшому збільшенні х1 змінна хi стане негативною.

Виберемо ту з перемeнних хk+1, хk+2, ..., Хn , Яка раніше всіх звернеться в нуль при збільшенні х1, Тобто ту, для якої величина - ?i/ ?i1 менше всього. Нехай така «найбільш угрожаемая» змінна буде хr . Тоді має сенс «переразрешіть» систему рівнянь (5.1) щодо інших базисних змінних, вивівши з числа вільних змінних х1 і переводячи замість неї в групу вільних змінних хr . Дійсно, ми хочемо перейти від опорного рішення, що задається рівністю х1= х2= .... = Хk= 0, до опорного рішенням, в якому вже х1 ? 0, х2= .... = Хk= хr= 0. Перше опорне рішення ми отримали, поклавши рівними нулю всі колишні вільні змінні х1, х2, хk; друге, ми отримаємо, якщо звернемо в нуль всі нові вільні змінні х2, ..., Хk, хr. Засадничими змінними при цьому будуть х1, хk+1, ..., Хr-1, xr+1, ..., Xn.

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

Простежимо описану процедуру поступового покращуючи рішення ОЗЛП на конкретному прикладі.

Приклад. Є завдання лінійного програмування з обмеженнями-нерівностями:

 (5.3)

Потрібно максимізувати лінійну функцію

Рішення.Наводячи нерівності до стандартного вигляду (?0) і вводячи додаткові змінні у1, у2, у3, Переходимо до умов-равенствам:

 (5.4)

Число змінних n = 7 на 4 перевищує число рівнянь m = 3. Значить, чотири змінних можуть бути обрані в якості вільних.

Спробуємо вибрати в якості вільних змінних х1, х2, х3, х4 і покласти їх рівними нулю. При цьому ми відразу отримаємо опорне рішення: х1= х2= х3= х4 = 0; у1= 2; у2= 5; у3= 7.

При цих значеннях змінних L = 0.

Подивимося, чи є це рішення оптимальним? Ні! Тому що в вираженні лінійної функції L коефіцієнт при х3 позитивний. Значить, збільшуючи х3 , Можна збільшити L.

Спробуємо збільшити х3 . Простежимо за рівнянням (5.4), небезпечно це для інших змінних? Так, небезпечно для у1 і у2 - В обидва ці рівняння змінна х3 входить з негативним коефіцієнтом, значить, при збільшенні х3 відповідні змінні у1 і у2 можуть стати негативними.

Подивимося, яка з цих змінних у1 або у2 є найбільш «загрозливій», яка раніше звернеться в нуль при збільшенні х3. Очевидно, у1: Вона стане рівною нулю при х3= 1, а величина у2 - Тільки при х3= 5.

Тому вибираємо змінну у1 і вводимо її в число вільних замість х3. Щоб «переразрешіть» систему (5.4) щодо нової базисної змінної х3:

.

Цей вислів підставимо замість х3 в друге рівняння, отримаємо

Що стосується третього рівняння, то воно, як що не містить х3 не зміниться. Отже, ми привели систему (5.4) до вигляду:

 (5.5)

з вільними змінними х1, х2, у1, х4 і базисними х3, у2, у3.

Висловимо лінійну функцію L через нові вільні змінні:

L = -5х1+ 5х1+ х21+2

або

L = х21+2 (5.6)

Покладемо тепер вільні змінні рівними нулю. Лінійна функція L стане рівною 2. Це вже краще, ніж колишнє значення L = 0. Але чи є це рішення оптимальним? Все ще немає, так як коефіцієнт при х2 в натуральному вираженні (5.6) позитивний. Отже, будемо збільшувати х2. Подивимося, для якої із змінних, що стоять в лівих частинах системи (5.5) це може бути «небезпечно». Тільки для у2 (В першому рівнянні х2 входить з позитивним коефіцієнтом, а в третьому зовсім не входить).

Отже, обміняємо місцями змінні х2 і у2 - Першу з числа вільних, а другу - введемо. Для цього дозволимо друге рівняння (5.5) щодо х2 і підставимо це х2 в перше рівняння. Отримаємо ще один вид системи (5.4):

 (5.7)

Висловимо L через нові вільні змінні:

L = 3х1-2у2+ у1+2 х4+ 8-у1+2

або

L = 3х1- 2у24+ 10. (5.8)

вважаючи х1= у1= у2= х4 = 0, отримаємо L = 10.

Чи є це рішення оптимальним? На цей раз - так, так як коефіцієнти при всіх вільних змінних у виразі (5.8) негативні.

Отже, оптимально рішення ОЗЛП знайдено:

При таких значеннях змінних лінійна функція L приймає максимальне значення:

Зауважимо, що в розглянутому прикладі нам не довелося шукати опорного рішення: воно відразу ж вийшло, коли ми поклали вільні змінні рівними нулю. Це пояснюється тим, що в рівняннях (5.4) всі вільні члени були невід'ємні і, отже, перше ж ліпше рішення виявилося опорним. Якщо ж виявиться не так, можна буде прийти до опорного рішенням за допомогою такої ж процедури обміну місцями деяких базисних і вільних змінних, переразрешая рівняння до тих пір, поки вільні члени не стануть невід'ємними. Як це робиться, ми побачимо в подальшому (дивись параграф 6).



Попередня   1   2   3   4   5   6   7   8   Наступна

Основне завдання лінійного програмування. | Геометрична інтерпретація основного завдання лінійного програмування. | Відшукання опорного вирішення основного завдання лінійного програмування. | Стаціонарна транспортна задача |

© um.co.ua - учбові матеріали та реферати