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

ми отримали, поклавши рівними нулю всі колишні вільні змінні друге ми отримаємо, якщо обернемо в нуль все нові вільні змінні

Базисними змінними при цьому будуть   

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

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

  (2. 24)

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

 

Наводячи нерівності до стандартного вигляду і вводячи додаткові змінні переходиться до умов-рівності:

  (2. 25)

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

Хай як вільні змінні виступають    Покладемо їх рівними нулю і отримаємо опорне рішення:

 

 

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

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

Спробуємо збільшувати З виразів (2. 25) видно, що в  змінна входить з негативним коефіцієнтом, значить, при збільшенні відповідні змінні можуть стати негативними.

Визначимо, яка з цих змінних   раніше перетвориться на нуль при збільшенні Вочевидь, що це вона стане рівною нулю при а величина — лише при  = 5.

Вибирається змінна в, і вводиться в число вільних замість Аби вирішити систему (2. 25) відносно  поступимо таким чином. Вирішимо перше рівняння (2. 25) відносно нової базисної змінної

 

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

  (2. 26)

Що стосується третього рівняння, то воно, як те, що не містить   не зміниться

Система (2. 25) приведена до вигляду з вільними змінними і базисними

Виразимо функцію Z через нові вільні змінні:

  (2. 27)

Покладемо тепер вільні змінні рівними нулю. Функція набуває значення Z=-2, що менше (краще), ніж колишнє значення Z= 0.

Це рішення все ще не оптимально, так

як коефіцієнт при у вираженні (2. 27) негативний, і змінна  може бути збільшена. Це збільшення, як це видно з системи (2. 26), може зробити негативною (у перше рівняння входить з позитивним коефіцієнтом, а в третьому — відсутній).

Поміняємо місцями змінні — першу виключимо з числа вільних, а другу — включимо. Для цього вирішимо друге рівняння (2. 26) відносно і підставимо в перше рівняння. Отримаємо наступний вигляд системи (2. 25):

  (2. 28)

Виразимо Z через нові вільні змінні:

  (2. 29)

Вважаючи , отримаємо Z = -10.

Це рішення є оптимальним, оскільки коефіцієнти при всіх вільних змінних у вираженні (2. 29) ненегативні. Отже, оптимальне рішення ОЗ знайдено:

 

При таких значеннях змінних лінійна функція Z набуває мінімального значення:

 

Відмітимо, що в розглянутому прикладі нам не довелося шукати опорне рішення: воно відразу ж вийшло, коли ми поклали вільні змінні рівними нулю. Це пояснюється тим, що в рівняннях (2. 25) всі вільні члени були ненегативні і, значить, перше ж рішення, що попалося, виявилося опорним. Якщо це виявиться не так, можна буде прийти до опорного рішення за допомогою такої ж процедури обміну місцями деяких базисних і вільних змінних, повторно вирішуючи рівняння до тих пір, поки вільні члени не стануть ненегативними [7].

 

1 2

Схожі роботи

Реферати

Курсові

Дипломні