Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Метод штучного базису.




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

Нехай потрібно знайти максимум функції

F=c1x1 + c2x2+... + cnxn (32)

при умовах

xj 0 (j = (34)

де bi 0 (i = , т<п і серед векторів

немає т одиничних.

Визначення 1.13. Задача, що полягає у визначенні максимального значення функції

F=c1x1 + c2x2+... + cnxnMxn+1 –…– Mxn+m (34)

При умовах

xj 0 (j = ) (35)

де М – деяке досить велике додатне число, конкретне значення якого звичайно не задається, називається розширеною задачею стосовно задачі (32)-(34).

Розширена задача має опорний план

Х =(0; 0;...; 0; b1; b2;...; bm),

п нулів

визначається системою одиничних векторів Рп+1, Рп+2,..., Рп+т,щоутворюють базис т -го векторного простору, що називається штучним. Самі вектори, так само як і змінні xп+i (i = ),називаються штучними. Так як розширена задача має опорний план, то її розв’язок може бути знайдений симплексним методом.

Теорема 1.8. Якщо в оптимальному плані Х*= (x*1; x*2;...; x*n; х*n+1;...; х*n+т) розширеної задачі (35)-(37) значення штучних змінних х*n+i =0 (i = ), то Х*= (x*1; x*2;...; x*n) є оптимальним планом задачі (32)-(34).

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

При опорному плані Х= (0; 0;...; 0; b1; b2;...; bm)розширеної задачі значення лінійної форми є , а значення Δ j = zj - cj, рівні . Таким чином, F0 і різниці zjcj складаються із двох незалежних частин, одна з яких залежить від М, а інша – ні.

Після обчислення F0 і Δ j їх значення, а також вихідні дані розширеної задачі заносять у таблицю, що містить на один рядок більше, ніж звичайна симплексна таблиця. При цьому в (т +2)-ий рядок поміщають коефіцієнти при М, а в (т +1)-ий – доданки, що не містять М.

При переході від одного опорного плану до іншого в базис уводять вектор, що відповідає найбільшому по абсолютній величині від’ємному числу (т +2)-го рядка. Штучний вектор, виключений з базису в результаті деякої ітерації, надалі не має змісту вводити ні в один з наступних базисів і, отже, перетворення стовпців цього вектора зайве. Однак якщо потрібно знайти розв’язок двоїстої задачі для даної (про що буде сказано в § 1.6), то таке перетворення необхідне. Може трапитися так, що в результаті деякої ітерації жоден зі штучних векторів з базису не буде виключений.

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

Ітераційний процес по (т +2)-у рядку ведуть доти, поки:

1) або всі штучні вектори не будуть виключені з базису;

2) або не всі штучні вектори виключені, але (т +2)-ий рядок не містить більше від’ємних елементів у стовпцях векторів P1, P2,...; Pn+m

У першому випадку базис відповідає деякому опорному плану вихідної задачі й визначення її оптимального плану продовжують по (т +1)-у рядку.

У другому випадку, якщо елемент, що стоїть в (т +2)-у рядку стовпця вектора F0 від’ємний, вихідна задача не має розв’язку; якщо ж він дорівнює нулю, то знайдений опорний план вихідної задачі є виродженим і базис містить принаймні один з векторів штучного базису.

Якщо вихідна задача містить кілька одиничних векторів, то їх варто включити в штучний базис.

Отже, процес знаходження розв’язок задачі (32)-(34) методом штучного базису включає наступні основні етапи:

1. Знаходять розширену задачу (35)-(37).

2. Знаходять опорний план розширеної задачі.

3. За допомогою звичайних обчислень симплекс-методу виключають штучні вектори з базису. У результаті або знаходять опорний план вихідної задачі (32)-(34), або встановлюють її нерозв’язність.

4. Використовуючи знайдений опорний план задачі (32)-(34), або знаходять симплекс-методом оптимальний план вихідної задачі, або встановлюють її нерозв’язність.

1.44. Знайти мінімум функції F= – 2 x1 +3 x2 –6 x3х4 при умовах

х1, х2, х3, х4 ≥ 0

Розв’язок. Запишемо дану задачу у формі основної задачі: знайти максимум функції F= 2 x1 –3 x2 +6 x3 + х4 при умовах

хj 0 (j = )

У системі рівнянь останньої задачі розглянемо вектори з коефіцієнтів при невідомих:

;

Серед векторів Р1, Р2, Р3, Р4, Р5 і Р6 тільки два одиничних (Р4 і Р5). Тому в ліву частину третього рівняння системи обмежень задачі додамо додаткову невід’ємну змінну х7 і розглянемо розширену задачу, що полягає в максимізації функції

F= 2 x1 –3 x2 +6 x3 + х4–Mх7

при умовах

xj 0(j = )

Розширена задача має опорний план Х= (0; 0; 0; 24; 22; 0; 10), обумовлений системою трьох одиничних векторів: Р4, Р5, Р7.

 

Таблиця 1.13

i Базис C6 P0   –3         M
P1 P2 P3 P4 P5 P6 P7
  Р4 Р5 Р7   –M –10 –1 –1 –2 –8 –2     –1  

 

Складаємо таблицю I ітерації (табл. 1.13), що містить п’ять рядків. Для заповнення 4-го і 5-го рядків знаходимо F0 і значення різниць zjcj (j = ):

F0 =24 – 10 М; z1 c1= 0– М; z2c2 =4+ M; z3c3 =8 – 2 М;

z4c4 = 0; z5c5 = 0; z6c6 = 0+ M; z7c7 = 0.

Значення F0 і zjcj складаються із двох доданків, один з яких містить М, а інший – ні. Для зручності ітераційного процесу число, що складається при М, записуємо в 5-му рядку, а доданок, що не містить М, – в 4-му рядку.

В 5-у рядку табл. 1.13 у стовпцях векторів Р j (j = ) є два від’ємних числа (–1 і –2). Наявність цих чисел говорить про те, що даний опорний план розширеної задачі не є оптимальним. Переходимо до нового опорного плану розширеної задачі. У базис уводимо вектор Р3. Щоб визначити вектор, що виключається з базису, знаходимо θ0= тіп (22/4; 10/2) = 10/2. Отже, вектор Р7 виключаємо з базису. Цей вектор не має змісту вводити ні в один з наступних базисів, тому надалі стовпець даного вектора не заповнюється (табл. 1.14 і 1.15).

Складемо таблицю II ітерації (табл. 1.14). Вона містить тільки чотири рядки, так як штучний вектор з базису виключений.

 

Таблиця 1.14

i Базис C6 P0   –3        
P1 P2 P3 P4 P5 P6
  Р4 Р5 Р3       –1 1/2 –1/2       –1 –1/2 –4

 

Як видно з табл. 1.14, для вихідної задачі опорним є план Х= (0;0; 5; 34; 2). Перевіримо його на оптимальність. Для цього розглянемо елементи 4-го рядка. У цьому рядку в стовпці вектора Р6 є від’ємне число (–4). Отже, даний опорний план не є оптимальним і може бути поліпшений завдяки введенню, у базис вектора Р6 З базису виключається вектор Р5 Складемо таблицю III ітерації.

Таблиця 1.15

i Базис C6 P0   –3        
P1 P2 P3 P4 P5 P6
  Р4 Р6 Р3     11/2 5/2 –1/2 1/4 1/2     1/2 1/2 1/4  

 

В 4-му рядку табл. 1.15 серед чисел Δ j немає від’ємних. Це означає, що знайдений новий опорний план вихідної задачі Х*= (0;0; 11/2; 35; 0; 1) є оптимальним. При цьому, плані значення лінійної форми Fтах =68. Розв’язок даної задачі можна було б проводити, використовуючи одну таблицю (табл. 1.16), у якій послідовно записані всі три ітерації.

 

Таблиця 1.16

i Базис C6 P0   –3         M
P1 P2 P3 P4 P5 P6 P7
  Р4 Р5 Р7   M –10 –1 –1 –2 –8 –2     –1  
  Р4 Р5 Р3       –1 1/2 –1/2       –1 –1/2 –4  
  Р4 Р6 Р3     11/2 5/2 –1/2 1/4 1/2     1/2 1/2 1/4    

Таблиця 1.18

 

В 5-му рядку табл. 1.18 у стовпцях векторів Р1, Р2,..., Р7 не міститься від’ємних елементів. У стовпці ж вектора Р0 цього рядка перебуває від’ємне число (–36). Отже, вихідна задача не має опорного плану.

 

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...