Курсова робота - Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
Подождите немного. Документ загружается.
.0556,60119730,19619730,14019730,1819730,15)19730,1()(
;056,60)1997,1()()(
;19730,1
618,0)19346,120351,1(20351,1;1997,1;20351,1)()(
234
1
12
112221
FxF
FxFxF
xxxxbxFxF
Перевіряємо умову зупинки:
001,001005,019346,120351,1
, тому
продовжуємо процедуру.
.0551,60119584,19619584,14019584,1819584,15)19584,1()(
;0556,60)19730,1()()(
;19584,1
618,0)19346,11997,1(1997,1;19730,1;1997,1)()(
234
1
12
112221
FxF
FxFxF
xxxxbxFxF
Перевіряємо умову зупинки:
001,000624,019346,11997,1
, тому
продовжуємо процедуру.
.0558,60119823,19619823,14019823,18198231,15)19823,1()(
;0556,60)19730,1()()(
;19823,1
618,0)19584,11997,1(19584,1;19730,1;19584,1)()(
234
2
21
221121
FxF
FxFxF
xxxxaxFxF
Перевіряємо умову зупинки:
001,000386,019584,11997,1
, отже
продовжуємо процедуру.
.0559,60119878,19619878,14019878,1819878,15)19878,1()(
;0558,60)19823,1()()(
;19878,1
618,0)19730,11997,1(19730,1;19823,1;19730,1)()(
234
2
21
221121
FxF
FxFxF
xxxxaxFxF
Перевіряємо умову зупинки:
001,00024,019730,11997,1
, отже
продовжуємо процедуру.
.056,60119914,19619914,14019914,1819914,15)19914,1()(
;0559,60)19878,1()()(
;19914,1
618,0)19823,11997,1(19823,1;19878,1;19823,1)()(
234
2
21
221121
FxF
FxFxF
xxxxaxFxF
Перевіряємо умову зупинки:
001,000147,019823,11997,1
, отже
продовжуємо процедуру.
.056,60119935,19619935,14019935,1819935,15)19935,1()(
;056,60)19914,1()()(
;19935,1
618,0)19878,11997,1(19878,1;19914,1;19878,1)()(
234
2
21
221121
FxF
FxFxF
xxxxaxFxF
Перевіряємо умову зупинки:
001,000092,019878,11997,1
. Отже за точку
локального мінімуму можна взяти середину відрізку
199,1
2
1997,119878,1
2
*
ba
x
. При цьому мінімальне значення вихідної
функції буде рівним:
056,601199,196199,140199,18199,15)(
234*
min
xFF
.
Метод дихотомії побудований таким чином, що кожний наступний
інтервал невизначеності менше попереднього. Як бачимо, в порівнянні з
методом золотого перерізу цей метод сходиться значно швидше (тобто через
меншу кількість кроків отримуємо інтервал невизначеності заданої довжини,
що містить
*
x
(в методі дихотомії ми зробили 11 ітерацій, а в методі золотого
11
перерізу - 16). Крім того, метод дихотомії потребує вдвічі менше обчислень,
ніж метод золотого перерізу. Однак мінімальне значення функції знайдене
обома методами співпадає, тому можемо зробити висновок, що доцільніше
використовувати метод дихотомії для зменшення затрат часу на розв’язання
задачі.
метод Фібоначчі
Спочатку згенеруємо послідовність чисел Фібоначчі: 1, 1, 2, 3, 5, 8,
13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … . Початкові
обрахунки проводяться в точках:
N
N
N
N
F
F
abax
F
F
abax
1
1
2
1
)(,)(
, де
N
F
- число Фібоначчі, яке обирається з умови
ab
F
N
, тобто в нашому
випадку це 18-те число Фібоначчі:
2000
001,0
02
2584
18
F
. Ці точки
розташовані симетрично відносно середини відрізку
]2;0[
. На кожному
кроці точка наступного обрахунку обирається симетрично відносно середини
відрізка локалізації до точки уже проведеного обрахунку, що лежить на
цьому відрізку. В силу властивостей чисел Фібоначчі кількість ітерацій
строго обмежена і дорівнює N=18. Отже можемо знайти початкові точки
ділення:
2361,1
2584
1597
)02(0,7639,0
2584
987
)02(0
21
xx
. Далі обчислюємо
значення функції в цих точках:
.9845,59)2361,1()(
;8575,5017639,0967639,0407639,087639,05)7639,0()(
2
234
1
FxF
FxF
Оскільки
)()(
21
xFxF
, то покладаємо, що N=N-1=18-1=17. Нові межі
відрізка тепер будуть рівними
2,7639,0
1
bxa
. Знаходимо нові точки
ділення:
527864,1)7639,02361,1(2)(,2361,1
1221
axbxxx
. Значення
функції в цих точках:
.5866,531527864,196527864,140527864,18527864,15)527864,1()(
9845,59)2361,1()(
234
2
1
FxF
FxF
Оскільки
)()(
21
xFxF
N=16, нові межі відрізка -
527864,1,7639,0
2
xba
.
.9696,581055728,196055728,140055728,18055728,15)055728,1()(
;9845,59)2361,1()()(
;055728,1)236068,1527864,1(7639,0)(,2361,1
234
1
12
2112
FxF
FxFxF
xbaxxx
Оскільки
)()(
21
xFxF
N=15, нові межі відрізка -
527864,1,055728,1
1
bxa
.
.8184,581347523,196347523,140347523,18347523,15)347523,1()(
;9845,59)2361,1()()(
;347523,1)055728,12361,1(527864,1,2361,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=14, нові межі відрізка -
347523,1,055728,1
2
xba
.
12
.998,591167183,196167183,140167183,18167183,15)167183,1()(
;9845,59)2361,1()()(
;167183,1)2361,1347523,1(055728,1,2361,1
234
1
12
112
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=13, нові межі відрізка -
2361,1,055728,1
2
xba
.
.7535,591124613,196124613,140124613,18124613,15)124613,1()(
;998,59)167183,1()()(
;124613,1)167183,12361,1(055728,1,167183,1
234
1
12
112
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=12, нові межі відрізка -
2361,1,124613,1
1
bxa
.
.0537,601193498,196193498,140193498,18193498,15)193498,1()(
;998,59)167183,1()()(
;193498,1)124613,1167183,1(2361,1,167183,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=11, нові межі відрізка -
2361,1,167183,1
1
bxa
.
.0508,601209752,196209752,140209752,18209752,15)209752,1()(
;0537,60)193498,1()()(
;209752,1)167183,11934983,1(2361,1,193498,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=10, нові межі відрізка -
209752,1,167183,1
2
xba
.
.0411,601183437,196183437,140183437,18183437,15)183437,1()(
;0537,60)193498,1()()(
;183437,1)193498,1209752,1(1671838,1,193498,1
234
1
12
112
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=9, нові межі відрізка -
209752,1,183437,1
1
bxa
.
.056,60119969,19619969,14019969,1819969,15)19969,1()(
;0537,60)193498,1()()(
;19969,1)183437,11934983,1(209752,1,193498,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=8, нові межі відрізка -
209752,1,193498,1
1
bxa
.
.055,60
12035604,1962035604,1402035604,182035604,15)2035604,1()(
;056,60)19969,1()()(
;2035604,1)1934983,119969,1(209752,1,19969,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=7, нові межі відрізка -
2035604,1,193498,1
2
xba
.
.05599,60
11973684,1961973684,1401973684,181973684,15)1973684,1()(
;056,60)19969,1()()(
;1973684,1)19969,12035604,1(193498,1,19969,1
234
1
12
112
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=6, нові межі відрізка -
20356,1,197368,1
1
bxa
.
13
.0559,60
1201238,196201238,140201238,18201238,15)201238,1()(
;056,60)19969,1()()(
;201238,1)197368,119969,1(20356,1,19969,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=5, нові межі відрізка -
201238,1,197368,1
2
xba
.
.05594,60
11989164,1961989164,1401989164,181989164,15)1989164,1()(
;056,60)19969,1()()(
;1989164,1)19969,1201238,1(197368,1,19969,1
234
1
12
112
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=4, нові межі відрізка -
2012384,1,198916,1
1
bxa
.
.05598,60
1200464,196200464,140200464,18200464,15)200464,1()(
;056,60)19969,1()()(
;200464,1)198916,119969,1(2012384,1,19969,1
234
2
21
221
FxF
FxFxF
xxx
Оскільки
)()(
21
xFxF
N=3, нові межі відрізка -
200464,1,1989164,1
2
xba
.
.056,60)19969,1()(
;056,60)19969,1()()(
;19969,1)19969,1200464,1(1989,1,19969,1
1
12
112
FxF
FxFxF
xxx
Оскільки
056,60)()(
21
xFxF
, то локальний мінімум досягається в
точці
199,1
21
*
xxx
. При цьому мінімальне значення вихідної функції буде
рівним:
056,601199,196199,140199,18199,15)(
234*
min
xFF
. Отже
мінімальне значення функції, знайдене методом дихотомії, методом золотого
перерізу і методом Фібоначчі співпадають. Однак найбільше ітерацій було
зроблено при розв’занні задачі методом Фібоначчі.
III. Розв’язання задачі мінімізації за допомогою методу
Ньютона і методу найшвидшого спуску
Розв’яжемо задачу мінімізації для функції
2
2
2211
2
1
452)( xxxxxxxF
, використовуючи метод Ньютона. Це метод
другого порядку, який використовує похідну першого і другого порядку від
цільової функції.
Перш ніж розв’язувати дану задачу, з’ясуємо чи має вона точку
локального мінімуму. Для цього побудуємо матрицю Гессе.
Знайдемо частинні похідні першого і другого порядку від функції
)(xF
:
.1;2;4
;42;54
12
2
21
2
2
2
2
2
1
2
21
2
21
1
xx
F
xx
F
x
F
x
F
xx
x
F
xx
x
F
14
Отже матриця Гессе матиме вигляд:
21
14
),(
2
2
2
12
2
21
2
2
1
2
21
x
F
xx
F
xx
F
x
F
xxH
. А оскільки головні мінори додатні:
7
21
14
,4
2221
1211
2111
aa
aa
DaD
, то матриця Гессе додатно визначена. Тобто
достатні умови існування локального мінімуму виконані.
Так як цільова функція є опуклою, тобто це задача опуклого
програмування, а функція
)(xF
є неперервно диференційованою в R
n
, то
якщо точка
*
x
є точкою локального екстремуму, то вона буде і точкою
глобального екстремуму для цієї задачі.
Отже можемо застосувати метод Ньютона. Послідовність точок, яка
прямує до точки мінімуму функції
)(
*
xF
згідно цього методу знаходиться за
формулою:
,...2,1,0),()(
)(
1
)()()1(
kxFxHxx
kkkk
, де
1
)(
)(
k
xH
-
обернена матриця Гессе.
7
4
7
1
7
1
7
2
41
12
7
1
),(
1
21
xxH
.
Обиремо в допустимій області задачі довільну точку – початкове
наближення. Нехай це буде точка
)0;0(
)0(
x
.
Знайдемо градієнт цільової функції:
)42;54()(
2121
xxxxxF
і
обчислимо його в точці
)0(
x
:
)4;5()4020;0504()(
)0(
xF
.
Знайдемо наступне наближення до оптимального розв’язку вихідної
задачі:
3
2
4
5
7
4
7
1
7
1
7
2
0
0
)(),(
)0(
1
21
)0()1(
xFxxHxx
і обчислимо градієнт цільової
функції в цій точці:
0)4322;3524()(
)1(
xF
. Рівність градієнта
цільової функції нулю є необхідною умовою існування екстремуму функції
багатьох змінних. Тобто оптимальний розв’язок задачі
)3;2(
*
x
, причому
11343322522)(
22*
min
xFF
.
Тепер розв’яжемо задачу мінімізації для функції
2
2
2211
2
1
452)( xxxxxxxF
, використовуючи метод найшвидшого спуску.
Цей метод відноситься до градієнтних методів.
За даним методом будується послідовність точок
)()1()0(
,...,,
n
xxx
, яка
прямує до оптимального розв’язку задачі -
*
x
. Від точки
)(k
x
до точки
)1( k
x
рухаються в напрямі градієнта цільової функції, обчисленого в точці
)(k
x
.
Широке застосування цього методу обумовлено тим, що в напряму
антиградієнту —
)(xF
похідна функції за напрямом досягає найменшого
значення.
Алгоритм методу найшвидшого спуску:
1. Обираємо довільну початкову точку
n
Rx
)0(
, яка називається
початковим наближенням розв’язку задачі
min),...,,(
21
п
xxxFz
, і
покладаємо, що
.0k
При цьому функція
),...,,(
21 п
xxxF
вважається опуклою і неперервно диференційованою в
n
R
. Також
обираємо точність обчислень
0
.
15
2. Обчислюємо градієнт цільової функції
)(k
xF
. Якщо
0
)(
k
xF
, то покладаємо
)(,
*
min
)(*
xFFxx
k
і зупиняємо
обчислення, інакше - переходимо до кроку 3.
3. Шукаємо наступне наближення за формулою:
,...2,1,0
)()()1(
k
kkk
xFxx
- для задачі мінімізації, а для задачі
максимізації:
,...2,1,0
)()()1(
k
kkk
xFxx
. Число
- параметр,
який називається довжиною кроку в точці
)(k
x
. Його обирають
довільно, однак зазвичай, параметр
обирається з умови, щоб в
точці
)(k
x
спостерігалося максимальне зменшення (збільшення)
цільової функції
)(xF
.
4. Перевіряємо умову зупинки, а саме:
)()(
)()1( kk
xFxF
. Якщо
умова виконана, то покладаємо
)(,
*
min
)1(*
xFFxx
k
і зупиняємо
обчислення, якщо ні, то переходимо до наступного кроку.
5. Покладаємо, що
1kk
і переходимо до кроку 2.
Тепер перейдемо безпосередньо до нашого прикладу.
Оберемо спочатку точність обчислень
1,0
. За початкове
наближення як і в методі Ньютона візьмемо точку
)0;0(
)0(
x
. З аналізу,
проведеного в методі Ньютона, маємо що цільова функція є опуклою і
неперервно диференційованою в R
n
, отже даний метод застосовувати можна.
З методу Ньютона маємо, що градієнт цільової функції в точці
)0;0(
)0(
x
буде рівним
)4;5()42;54()(
2121
)0(
xxxxxF
. Оскільки
0
)0(
xF
, то шукаємо наступне наближення розв’язку вихідної задачі:
4,5
4
5
0
0
)(
)1(
2
)1(
1
)0()0(
)1(
2
)1(
1
)1(
xxxFx
x
x
x
.
Знайдемо
:
414644)4(4555)5(2)(
222)1(
xF
.
Оскільки
обирається з умови, щоб в точці
)1(
x
спостерігалося
максимальне зменшення
)(xF
, знайдемо похідну від цільової функції в
точці
)1(
x
і прирівняємо її до нуля.
446,0
04192
;0)(
)1(
xF
Отже можемо тепер знайти координати точки
)1(
x
:
)78,1;23,2()446,04;446,05()4,5(
)1(
x
. Обчислимо значення цільової
функції в цій точці:
1252,978,1478,178,123,223,25)23,2(2)(
22)1(
xF
.
Перевіряємо умову зупинки:
1,01252,901252,9)78,1,23,2()0,0()()(
)0()1(
FFxFxF
отже
шукаємо наступне наближення аналогічним чином.
0)67,2;14,2()478,1223,2;78,1523,24()42;54()(
2121
)1(
xxxxxF
67,278,1,14,223,2
67,2
14,2
78,1
23,2
)(
)2(
2
)2(
1
)1()1(
)2(
2
)2(
1
)2(
xxxFx
x
x
x
16
1252,93268,190019,2268,1012,71289,75052,91684,37138,5
8092,3954,59694,37,1015,111592,90888,199458,9)67,278,1(4
)67,278,1()67,278,1()14,223,2()14,223,2(5)14,223,2(2)(
222
2
22)1(
xF
43921,0
03269,190038,44
3269,190038,44)(
)2(
xF
Отже можемо тепер знайти координати точки
)2(
x
:
)95269,2;290091,1()43921,067,278,1;43921,014,223,2()67,278,1;14,223,2(
)2(
x
Обчислимо значення цільової функції в цій точці:
0234,1095269,2495269,295269,2290091,1290091,15)290091,1(2)(
22)2(
xF
.
Перевіряємо умову зупинки:
1,08982,01252,90234,10)95269,2,290091,1()78,1,23,2()()(
)1()2(
FFxFxF
отже шукаємо наступне наближення:
0)615289,0;79233,2(
)495269,22290091,1;95269,25290091,14()42;54()(
2121
)2(
xxxxxF
615289,095269,2
,79233,229,1
615289,0
79233,2
95269,2
290091,1
)(
)3(
2
)3(
1
)2()2(
)3(
2
)3(
1
)3(
x
xxFx
x
x
x
0234,1017567,825466,14461156,28108,11378581,0
63352,3718378,871809,1244873,8793779,080924,39616,1345046,6
59417,1540942,1432867,3)615289,095269,2(4)615289,095269,2(
)615289,095269,2()79233,229,1()79233,229,1(5)79233,229,1(2)(
22
2
22
2)3(
xF
28677,0
017567,850932,28
17567,850932,28)(
)3(
xF
Отже можемо тепер знайти координати точки
)3(
x
:
)776243,2;090857,2()615289,095269,2;79233,229,1(
)3(
x
.
Обчислимо значення цільової функції в цій точці:
9131,10776243,24776243,2776243,2090857,2090857,25)090857,2(2)(
22)3(
xF
Перевіряємо умову зупинки:
1,08897,00234,109131,10)()(
)2()3(
xFxF
отже шукаємо наступне
наближення:
0)53837,0;587185,0()4776243,22090857,2;776243,25090857,24()(
)3(
xF
53837,0776243,2
,587185,0090857,2
53837,0
587185,0
776243,2
090857,2
)(
)4(
2
)4(
1
)3()3(
)4(
2
)4(
1
)4(
x
xxFx
x
x
x
9131,1063463,0
663292,0)53837,0776243,2(4)53837,0776243,2()53837,0776243,2(
)587185,0090857,2()587185,0090857,2(5)587185,0090857,2(2)(
22
2)4(
xF
47839,0
063463,0326585,1
63463,0326585,1)(
)4(
xF
Отже можемо тепер знайти координати точки
)4(
x
:
)033769,3;809952,1()53837,0776243,2;587185,0090857,2(
)4(
x
.
17
Обчислимо значення цільової функції в цій точці:
9202,10033769,34033769,3033769,3809952,1809952,15)809952,1(2)(
22)3(
xF
Перевіряємо умову зупинки:
1,0007,09131,109202,10)()(
)2()3(
xFxF
, тобто умову зупинки
виконано. Отже
9202,10)(),033769,3;809952,1(
)4(
min
)4(*
xFFxx
.
Як бачимо, розв’язки задачі, знайдені обома методами майже однакові,
але при цьому метод Ньютона дав результат вже на першому кроці ( на
відміну від методу найшвидшого спуску, де довелося робити 4 ітерації). Це
пов’язано з тим, що цільова функція є квадратичною, а отже напрям спуску
,...2,1,0),()(
)(
1
)(
kxFxH
kk
завжди співпадає з напрямом в точку
мінімуму
*
x
. Тобто основна перевага методу Ньютона - швидка збіжність,
однак при цьому суттєвим недоліком є залежність збіжності від початкового
наближення
)0(
x
. Крім того у випадку не квадратичної цільової функції
трудомісткість ітерації методом Ньютона може виявитись дуже великою за
рахунок необхідності обчислення матриці других похідних мінімізуємої
функції, що потребує затрат великої кількості часу.
IV. Розв’язання задачі умовної оптимізації за допомогою
методу Франка-Вулфа і методу штрафних функції
Розв’яжемо задачу умовної оптимізації
0
1
2173
max
2
1
24
2,1
21
21
21
2
2
2
121
x
xx
xx
xxxxxxz
a. методом Франка-Вулфа
Функція
),(
21
xxfz
являється вгнутою так як представляє собою суму
лінійної функції (її можна розглядати як вгнуту) і квадратичної форми, яка
являється від’ємно визначеною і тому також являється вгнутою. Перевіримо
завдяки матриці Гессе від’ємну визначеність функції
21
2
2
2
1
2
1
xxxxF
. Для
цього спочатку знайдемо частинні похідні першого і другого порядку від
функції
F
:
.1;2;1
;2;
12
2
21
2
2
2
2
2
1
2
12
2
21
1
xx
F
xx
F
x
F
x
F
xx
x
F
xx
x
F
Отже матриця Гессе матиме вигляд:
21
11
),(
2
2
2
12
2
21
2
2
1
2
21
x
F
xx
F
xx
F
x
F
xxH
18
Головні мінори :
1
21
11
,1
2221
1211
2111
aa
aa
DaD
оскільки в ряді
21
,,1 DD
знаки
чергуються, то дана матриця є від’ємно визначеною, я отже функція
21
2
2
2
1
2
1
xxxxF
- вгнута.
Система обмежень задачі включає тільки лінійні нерівності, які
утворюють опуклу множину, отже дана задача є задачею опуклого
програмування.
Задачу такого типу можна розв’язувати методом Франка-Вулфа. Цей
метод відноситься до групи градієнтних методів.
Розглянемо задачу:
)3(,10
)2(,1
)1(max),...,,(
1
21
njx
mibxa
xxxfz
j
n
j
ijij
n
Алгоритм методу Франка-Вулфа:
1. Спочатку в допустимій області задачі обирають довільну точку
n
Rx
)0(
. Це можна зробити, наприклад, за допомогою методу
штучного базису. Також обирають точність обчислень
0
.
Покладають
.0k
2. Знаходять в цій точці градієнт цільової функції
)(k
xf
.
3. Будують функцію
))((...))(())((
)(
2
)(
2
1
)(
1
n
k
n
kk
xx
x
f
xx
x
f
xx
x
f
F
і
розв’язують задачу максимізації для функції
F
в області 2-3, тобто
таку задачу:
njx
mibxa
xx
x
f
xx
x
f
xx
x
f
F
j
n
j
ijij
n
k
n
kk
,10
,1
)4(max))((...))(())((
1
)(
2
)(
2
1
)(
1
Нехай
)(k
z
- оптимальний розв’язок задачі 4,2,3.
4. Шукаємо наступне наближення за формулою:
)5(
,...2,1,0
)()()()1(
k
kk
k
kk
xFxx
, де
10
k
- крок в точці. Його
обирають довільно, однак краще його вибрати так, щоб
)(
)1( k
xf
при
такому значенні
k
мала найбільше значення. Для цього з формул 5
знаходять вираз координат вектора
)1( k
x
через
k
:
)(
)1()1(
k
kk
xx
і
підставляють цей вираз у функцію
))((
)1(
k
k
xf
. Потім розв’язують
систему
0
)(
k
x
f
. За
k
вибирають найменший з коренів цього
рівняння. Якщо цей корінь більше одиниці, то
1
k
.
19
5. Перевіряють критерії зупинки:
)()(
)()1( kk
xfxf
,
0
)
k
xf
. Якщо
дані умови виконались, то покладають
)(,
*
min
)1(*
xFFxx
k
і
зупиняють обчислення, якщо ні, то переходимо до наступного кроку.
6. Покладають, що
1kk
і переходять до кроку 2.
Тепер перейдемо безпосередньо до нашої задачі. За початкове
наближення до оптимального плану задачі обираємо точку
)0;0(
)0(
x
, а
обчислення будемо проводити з точністю
1,0
,
0k
. Градієнт цільової
функції в точці
)0;0(
)0(
x
2;422;4
1221
xxxxf
.
Розв’яжемо за допомогою симплекс методу задачу:
0
1
2173
max24
2,1
21
21
21
x
xx
xx
xxF
і Базис С
б
В
4 2 0 0
А
1
А
2
А
3
А
4
1 А
3
0 21 3 7 1 0
2 А
4
0 1 1 -1 0 1
3 0 - 4 -2 0 0
1 А
3
0 18 0 10 1 -3
2 А
1
4 1 1 -1 0 1
3 8 0 -6 0 4
1 А
2
2 9/5 0 1 1/10 -3/10
2 А
1
4 14/5 1 0 1/10 7/10
3 74/5 0 0 3/5 11/5
Позначимо через
)0(
F
оптимальний розв’язок даної задачі. Отже
)5/9,5/14(
)0(
F
. Знайдемо новий допустимий розв’язок вихідної задачі за
формулою 5:
)0(0
0
)0()1(
xFxx
0
0
0
)1(
5/9
5/14
0
0
5/9
5/14
0
0
x
20