Симплекс-метод розв’язування задач ЛП. Перехід від одного опорного плану до іншого

СИМПЛЕКСНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчис¬лень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом – так званий симплексний метод, або симплекс-метод. Ідея методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за поперед¬ній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум). Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує. Отже,симплекс-метод – це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.

1.1 Початковий опорний план

Розглянемо задачу лінійного програмування, записану в канонічній формі:

Неможливо розібрати вираз (невідома помилка): \max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n}

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} b_{1}=a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}+x_{n+1} \\ b_{2}=a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}+x_{n+2} \\ ...................................................... \\ b_{m}=a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}+x_{n+m} \\ \end{array}} \right.

Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0\,\,\,\,\,\,(j=1,2,...,n).

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

Неможливо розібрати вираз (невідома помилка): \max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n}~~~~~~~~~~~~~~~~~~~~~~~~~~~(1.1)

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} x_{1} \,\,\,\,\,\,\,\,\,\,\,+a_{1,m+1} x_{m+1} +...+a_{1n} x_{n} =b_{1} ; \\ \,\,\,\,\,x_{2} \,\,\,\,\,\,+a_{2,m+1} x_{m+1} +...+a_{2n} x_{n} =b_{2} ; ~~~~~~~~~~~~~~~~(1.2) \\ ................................................................. \\ \,\,\,\,\,\,\,\,\,\,x_{m} +a_{m,m+1} x_{m+1} +...+a_{mn} x_{n} =b_{m} . \\ \end{array}} \right.

Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0\,\,\,\;(j=1,2,...,n).~~~~~~~~~~~~~~~~~~~~~~~~~(1.3)

Система обмежень (1.2) у векторній формі матиме вигляд:

Неможливо розібрати вираз (невідома помилка): x_{1} A_{1} +x_{2} A_{2} +...+x_{m} A_{m} +x_{m+1} A_{m+1} +...+x_{n} A_{n} =A_{0} ,~~~~~~~~~~~~(1.4)

де

????????

Неможливо розібрати вираз (невідома помилка): A_{1} ,A_{2} ,...,A_{m}

– лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (1.4) базисними змінними будуть Неможливо розібрати вираз (невідома помилка): x_{1} ,x_{2} ,...,x_{m}

, а інші змінні – вільні. Прирівняємо всі вільні змінні до нуля, тобто Неможливо розібрати вираз (невідома помилка): x_{m+1} =0,\,x_{m+2} =0,...,x_{n} =0 .Оскільки Неможливо розібрати вираз (невідома помилка): b_{i} \ge 0\;\,\,\,(i=\overline {1,m} ) ,а вектори Неможливо розібрати вираз (невідома помилка): A_{1} ,A_{2} ,...,A_{m}

– одиничні, то отримаємо один із розв’язків системи обмежень (1.2):

Неможливо розібрати вираз (невідома помилка): X_{0} =\left( {x_{1} =b_{1} ,\,x_{2} =b_{2} ,...,x_{m} =b_{m} ,x_{m+1} =0,...,x_{n} =0} \right),~~~~~~~~~~~~~~(1.5)

тобто допустимий план. Такому плану відповідає розклад

Неможливо розібрати вираз (невідома помилка): x_{1} A_{1} +x_{2} A_{2} +...+x_{m} A_{m} =A_{0} ,~~~~~~~~~~(1.6)

де Неможливо розібрати вираз (невідома помилка): A_{1} ,A_{2} ,...,A_{m} — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (п.3.4) план Неможливо розібрати вираз (невідома помилка): X_{0}

є кутовою точкою багатогранника розв’язків, а отже, може бути почат¬ковим опорним планом.

1.2 Перехід від одного опорного плану до іншого

Розглянемо, як, виходячи з початкового опорного плану (1.6), перейти до наступного опорного плану, що відповідає ціле¬спрямованому процесу перебору кутових точок багатогранника розв’язків. Оскільки Неможливо розібрати вираз (невідома помилка): A_{1} ,A_{2} ,...,A_{m}

 є базисом m-вимірного простору, то кожен з векторів співвідношення (1.5) може бути розкладений за цими векторами базису, причому у єдиний спосіб:

Неможливо розібрати вираз (невідома помилка): A_{j} =\sum\limits_{i=1}^m {x_{ij} A_{i} } ,\,\,\,j=1,2,...,n.

Розглянемо такий розклад для довільного небазисного вектора, наприклад, для Неможливо розібрати вираз (невідома помилка): A_{m+1}

 :

Неможливо розібрати вираз (невідома помилка): x_{1,m+1} A_{1} +x_{2,m+1} A_{2} +...+x_{m,m+1} A_{m} =A_{m+1} .~~~~~~~~~(1.7)

Припустимо, що у виразі (1.7) існує хоча б один додатний коефіцієнт Неможливо розібрати вираз (невідома помилка): x_{i,m+1}

 .

Введемо деяку поки що невідому величину Неможливо розібрати вираз (невідома помилка): \theta >0

, помножимо на неї обидві частини рівності (1.7) і віднімемо результат з рівності (1.6). Отримаємо:

Неможливо розібрати вираз (невідома помилка): (x_{1} -\theta \cdot x_{1,m+1} )A_{1} +(x_{2} -\theta \cdot x_{2,m+1} )A_{2} +...+(x_{m} -\theta \cdot x_{m,m+1} )A_{m} +\theta \cdot A_{m+1} =A_{0} .~~~~~~~~~~~~~(1.8)

Отже,вектор

Неможливо розібрати вираз (невідома помилка): X_{1} =(x_{1} -\theta \cdot x_{1,m+1} ;\,\;x_{2} -\theta \cdot x_{2,m+1}  ;...x_{m} -\theta \cdot x_{m,m+1} ;\;\theta ;\;0,\;...,\;0)

є планом задачі у тому разі, якщо його компоненти невід’ємні. За допущенням Неможливо розібрати вираз (невідома помилка): \theta >0 , отже, ті компоненти вектора Неможливо розібрати вираз (невідома помилка): X_{1}

, в які входятьНеможливо розібрати вираз (невідома помилка): x_{i,m+1} \le 0

, будуть невід’ємними, тому необхідно розглядати лише ті компоненти, які містять додатніНеможливо розібрати вираз (невідома помилка): x_{i,m+1} \,\,\,(i=1,2,...,m) . Тобто необхідно знайти таке значення Неможливо розібрати вираз (невідома помилка): \theta >0

, за якого для всіх Неможливо розібрати вираз (невідома помилка): x_{i,m+1} \le 0
 буде виконуватися умова невід’ємності плану задачі:

Неможливо розібрати вираз (невідома помилка): x_{i} -\theta \,\cdot x_{i,m+1} \ge 0.~~~~~~~~~~~~~(1.9)

Для визначення наступного опорного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить у базис, розкласти за базисними векторами, а потім визначити таке Неможливо розібрати вираз (невідома помилка): \theta^{\ast }>0

, для якого один з векторів виключається з базису.

Отже, узагальнюючи розглянутий процес, можемо висновувати: визначення но-вих опорних планів полягає у виборі вектора, який слід ввести в базис, і вектора, який необхідно вивести з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гаусса. Необхідно зазначити, що для випадку, коли вектор Неможливо розібрати вираз (невідома помилка): A_{m+1}

  підлягає включенню в базис, а в його розкладі (1.7) всі Неможливо розібрати вираз (невідома помилка): x_{i,m+1} \le 0 

, то, очевидно, не існує такого значення Неможливо розібрати вираз (невідома помилка): \theta >0 , яке виключало б один з векторів. У такому разі план Неможливо розібрати вираз (невідома помилка): X_{1}

 містить m+1 додатних компонент, отже, система векторів Неможливо розібрати вираз (невідома помилка):  A_{1} ,A_{2} ,...,A_{m} ,A_{m+1} 
 буде лінійно залежною і визначає не кутову точку багатогранника розв’язків. Функціонал не може в ній набирати максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.

Загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.

5. Повторення дій, починаючи з п.3. Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі. У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки. 1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язуваль¬ний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.

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

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