Page 21 - 6416

не можуть бути одночасно введеними у базис. Аналогічно змінні  і w не можуть
одночасно приймати додатні значення (бути одночасно базисними змінними). Остання умова
носить назву обмеженого доступу до базису.
Процес знаходження розв’язку задачі квадратичного програмування закінчується тоді,
коли штучні змінні набувають нульових значень і це означає, що початкова задача має
непусту множину допустимих розв’язків.
Аналіз отриманих умов показує, що базисними змінними будуть: w , r і r ; інші змінні –
1 2
небазисні.
У цільовій функції виразимо базисні змінні r і r через небазисні
1 2
r  14 8x  2x    u ,
1 1 2 1
r  54 2x  12x  2  u
2 1 2 2

і їх значення підставимо у вираз   r . У результаті отримаємо
R

R  x, ,u  68  6x  10x  3  u  u 2  ,
1
2
1
x  2x  w  9 ,
1 2
8x  2x    u  r  14 ,
1 2 1 1
 2x  12x  2  u  r  54 ,
1 2 2 2
u x  0, u x  , w 
0
0
1 1 2 2
x , x  ,   ,
0
0
1 2
u  0 , u  , w  .
0
0
1 2
Будуємо симплекс-таблицю (табл. 6.2), за допомогою якої здійснюється процес
знаходження розв’язку задачі.
К1. Аналізуємо індексний рядок. Маємо три додатних значення - s  , s  10 і s  .
6
3
1 2 3
Оскільки умова max : s виконується для змінної x , то цю змінну необхідно ввести у базис,
i 2
при цьому повинна виконуватись умова обмеженого доступу до базису. Оскільки u  (u -
0
2 2
небазисна змінна), то така умова виконується. Отже, другий стовпець табл. 6.2 буде
 b 


провідним. Провідний рядок визначимо із умови min  i  , де l - провідний рядок. Маємо
0
il a  0   a 0 il  
0
 b   9 9   b 




min :  i   min :  ;  . Оскільки умова min :  i  виконується для двох змінних, одну із
il a  0   a 0 il   il a  0  2 2  il a  0   a 0 il  
0
0
0
них необхідно вилучити із базис. Нехай це буде змінна r і відповідно другий рядок таблиці
2
буде провідним. На перетині провідного рядка і провідного стовпця будемо мати провідний
елемент (табл. 6.2). Отже, x буде базисною змінною, а змінну r виводимо із базису.
2 2
К2. Перераховуємо всі елементи таблиці за правилами, які сформовані раніше.
Результати розрахунків заносимо у табл. 6.2.
К3. Оскільки у індексному рядку максимальний коефіцієнт знаходиться при змінній x
1
0
(u  ), то провідним буде перший стовпець (табл. 6.2). Аналіз отриманої табл. показує, що
1
на першому кроці ітерації базисна змінна w отримала нульове значення і її необхідно
вивести із базису, тобто перший рядок буде провідним. Провідний елемент знаходимо на
перетині провідного стовпця і провідного рядка. Після того як знайдений провідний елемент
перерахунок всіх елементів табл. 6.2 здійснюється за правилами, які сформовані раніше.
Результати обчислень заносимо у таблиці 6.2.
К4. В індексному рядку маємо тільки один додатний елемент. Це означає, що третій
стовпець є провідним. Відповідно змінну  вводимо в базис. Перевіряємо умови
0
входження до базису w  . Вони виконуються так як w - небазисна змінна і w  . Отже,
0
18