Клочко О. В., Загородня Ю. В.

Вінницький національний аграрний університет, Україна

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

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

Цей метод є універсальним , застосовним до будь-якій задачі лінійного програмування в канонічній формі. Система обмежень тут - система лінійних рівнянь , в якій кількість невідомих більше кількості рівнянь . Якщо ранг системи дорівнює r , то ми можемо вибрати r невідомих , які висловимо через інші невідомі . Для визначеності припустимо, що обрані перші , що йдуть підряд , невідомі X1 , X2 , ... , Xr . Тоді наша система рівнянь може бути записана як

До такого виду можна навести будь-яку спільну систему , наприклад , методом Гаусса. Правда , не завжди можна виражати через інші перші r невідомих (ми це зробили для визначеності запису). Однак такі r невідомих обов'язково знайдуться. Ці невідомі ( змінні ) називаються базисними , решта вільними.

Надаючи певні значення вільним змінним і обчислюючи значення базисних ( виражених через вільні ) , ми будемо отримувати різні рішення нашої системи обмежень. Таким чином , можна отримати будь-яке її рішення. Нас будуть цікавити особливі рішення , одержувані у випадку , коли вільні змінні дорівнюють нулю. Такі рішення називаються базисними , їх стільки ж , скільки різних базисних видів у даної системи обмежень . Базисне рішення називається допустимим базисним рішенням або опорним рішенням, якщо в ньому значення змінних ненегативні . Якщо в якості базисних взяті змінні X1 , X2 , ... , Xr , то рішення { b1 , b2 , ... , br , 0 , ... , 0} буде опорним за умови , що b1 , b2 , ... , br ≥ 0 .

Симплекс - метод заснований на теоремі , яка називається фундаментальною теоремою симплекс - методу . Серед оптимальних планів задачі лінійного програмування в канонічній формі обов'язково є опорне рішення її системи обмежень . Якщо оптимальний план задачі єдиний, то він збігається з деяким опорним рішенням. Різних опорних рішень системи обмежень кінцеве число. Тому рішення задачі в канонічній формі можна було б шукати перебором опорних рішень і вибором серед них того, для якого значення F найбільше . Але , по-перше , всі опорні рішення невідомі і їх потрібно знаходити , a , по-друге , в реальних завданнях цих рішень дуже багато і прямий перебір навряд чи можливий. Симплекс - метод являє собою деяку процедуру спрямованого перебору опорних рішень . Виходячи з деякого , знайденого заздалегідь опорного рішення за певним алгоритмом симплекс - методу ми підраховуємо нове опорне рішення , на якому значення цільової функції F не менше, аніж на старому . Після низки кроків ми приходимо до опорного рішенням , яке є оптимальним планом .

Отже , симплексний метод вносить певний порядок як при знаходженні першого ( вихідного) базисного рішення , так і при переході до інших базисним рішенням. Його ідея полягає в наступному.

Маючи систему обмежень , наведену до загального вигляду , тобто до системи m лінійних рівнянь з n змінними ( m < n ) , знаходять будь базисне рішення цієї системи , піклуючись тільки про те , щоб знайти його якомога простіше.

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

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

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

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

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

Наведена схема симплексного методу явно виражає його алгоритмічний характер ( характер чіткого припису про виконання послідовних операцій) , що дозволяє успішно програмувати і реалізувати цей метод на ЕОМ . Завдання ж з невеликим числом змінних і обмежень можуть бути вирішені симплексним методом вручну.

Тому основний зміст симплексного методу полягає в наступному:

1. Вказати спосіб знаходження оптимального опорного рішення.

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

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

Література:

1.Електронний ресурс: http://www.grandars.ru/student/vysshaya-matematika/simpleksnyy-metod.html

2. Електронний ресурс: http://emm.ostu.ru/lect/lect2_2.html

3. Електронний ресурс: http://matmetod-popova.narod.ru/theme24.htm