Нелинейное программирование. Метод Франка-Вулфа.
Решить задачу условной оптимизации методом Франка-Вулфа.
FX=x1+4×2+x1x2-2×12-2×22→max
При ограничениях:
x1+2×2≤123×1+x2≤15×1,x2≥0
В качестве исходного допустимого решения использовать точку X(0), а в качестве критерия оценки качества получаемого решения – неравенство:
FXk+1-FXk≤ε
Где ε=0,01.
№ вар. X(0)
4 (1, 1)
Решение:
Находим градиент целевой функции:
gradF=∂F∂x1;∂F∂x2=(1+x2-4×1;4+x1-4×2)
Также вычисляем значение целевой функции в точке X(0):
FX0=1*1+4*1+1*1-2*12-2*12=2
Итерация 1.
1. Определяем градиент целевой функции в точке X(0):
gradFX0=1+1*1-4*1;4+1*1-4*1=(-2;1)
2. Определяется угловая точка области допустимых решений, соответствующая предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Для этого решается задача линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-2×1+x2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Поскольку x1,x2≥0, а коэффициент целевой функции около x1 – отрицательный, то очевидно: x1=0.
Тогда получаем систему неравенств для определения x2:
2×2≤12×2≤15×2=6
Это означает, что поиск нового решения будет выполняться в направлении от точки X0=(1;1) к точке X*=(0;6).
3. Составляем уравнения для перехода к новому решению:
x1(1)=x1(0)+λx1*-x10=1+λ0-1=1-λ
x2(1)=x2(0)+λx2*-x20=1+λ6-1=1+5λ
где λ – коэффициент, задающий величину перемещения от текущего решения к новому решению в направлении точки X*. Этот коэффициент определяется на следующем шаге.
4. Определяем коэффициент λ. Этот коэффициент находится таким образом, чтобы переход к новому решению обеспечивал максимальное значение целевой функции. С этой целью уравнения для перехода к новому решению, построенные на шаге 3, подставляются в целевую функцию. В результате целевая функция представляется как функция от коэффициента λ:
Fλ=1-λ+41+5λ+1-λ1+5λ-21-λ2-21+5λ2=
=-57λ2+7λ+2
Значение λ находится из условия экстремума целевой функции, т.е. из условия dF/dλ = 0:
∂F∂λ=-114λ+7
-114λ+7=0
λ=7114≈0,061
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(1)=1-λ=0,939
x2(1)=1+5λ=1,305
Вычисляем значение целевой функции в точке X(1):
FX1=1*0,939+4*1,305+0,939*1,305-2*0,9392-2*1,3052≈2,215
6. Проверяем условие окончания поиска решения:
FX1-FX0=2,215-2=0,215>ε
Требуется следующая операция.
Итерация 2.
1. Определяем градиент целевой функции в точке X(1):
gradFX1=1+1*1,305-4*0,939;4+1*0,939-4*1,305=
=(-1,451;-0,281)
2. Определяем угловую точку области допустимых решений, соответствующую предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Решаем задачу линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-1,451×1-0,281×2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Поскольку x1,x2≥0, а коэффициенты целевой функции – отрицательные, то решение очевидно: x1=x2=0.
Это означает, что поиск нового решения будет выполняться в направлении от точки X1=0,939;1,305 к точке X*=(0;0).
3. Составляем уравнения для перехода к новому решению:
x1(2)=x1(1)+λx1*-x11=0,939+λ0-0,939=0,939(1-λ)
x2(2)=x2(1)+λx2*-x21=1,305+λ0-1,305=1,305(1-λ)
4. Определяем коэффициент λ. Уравнения для перехода к новому решению, построенные на шаге 3, подставляем в целевую функцию:
Fλ=0,9391-λ+4*1,3051-λ+0,939*1,3051-λ2-2*0,93921-λ2-2*1,3051-λ2=-3,944λ2+1,729λ+2,215
Тогда:
∂F∂λ=-7,888λ+1,729
-7,888λ+1,729=0λ=0,219
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(2)=0,939(1-λ)≈0,733
x2(2)=1,3051-λ≈1,019
Вычисляем значение целевой функции в точке X(2):
FX2=1*0,733+4*1,019+0,733*1,019-2*0,7332-2*1,0192≈2,405
6. Проверяем условие окончания поиска решения:
FX2-FX1=2,405-2,215=0,190>ε
Требуется следующая операция.
Итерация 3.
1. Определяем градиент целевой функции в точке X(2):
gradFX2=1+1*1,019-4*0,733;4+1*0,733-4*1,019=
=(-0,913;0,657)
2. Определяем угловую точку области допустимых решений, соответствующую предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Решаем задачу линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-0,913×1+0,657×2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Аналогично итерации 1 получаем, что поиск нового решения будет выполняться в направлении от точки X2=(0,733;1,019) к точке X*=(0;6).
3. Составляем уравнения для перехода к новому решению:
x1(3)=x1(2)+λx1*-x12=0,733+λ0-0,733=0,733(1-λ)
x2(3)=x2(2)+λx2*-x22=1,019+λ6-1,019=1,019+4,981λ
4. Определяем коэффициент λ. Уравнения для перехода к новому решению, построенные на шаге 3, подставляем в целевую функцию:
Fλ=0,7331-λ+4*(1,019+4,981λ)+0,7331-λ*(1,019+4,981λ)-2*0,73321-λ2-2*(1,019+4,981λ)2=-54,346λ2+3,942λ+2,405
Тогда:
∂F∂λ=-108,692λ+3,942
-108,692λ+3,942=0λ=0,036
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(3)=0,733(1-λ)≈0,706
x2(3)=1,019+4,981λ≈1,198
Вычисляем значение целевой функции в точке X(3):
FX3=1*0,706+4*1,198+0,706*1,198-2*0,7062-2*1,1982≈2,477
6. Проверяем условие окончания поиска решения:
FX3-FX2=2,477-2,405=0,072>ε
Требуется следующая операция.
Итерация 4.
1. Определяем градиент целевой функции в точке X(3):
gradFX3=1+1*1,198-4*0,706;4+1*0,706-4*1,198=
=(-0,526;-0,086)
2. Определяем угловую точку области допустимых решений, соответствующую предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Решаем задачу линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-0,526×1-0,086×2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Поскольку x1,x2≥0, а коэффициенты целевой функции – отрицательные, то решение очевидно: x1=x2=0.
Это означает, что поиск нового решения будет выполняться в направлении от точки X3=0,706;1,198 к точке X*=(0;0).
3. Составляем уравнения для перехода к новому решению:
x1(4)=x1(3)+λx1*-x13=0,706+λ0-0,706=0,706(1-λ)
x2(4)=x2(3)+λx2*-x23=1,198+λ0-1,198=1,198(1-λ)
4. Определяем коэффициент λ. Уравнения для перехода к новому решению, построенные на шаге 3, подставляем в целевую функцию:
Fλ=0,7061-λ+4*1,1981-λ+0,706*1,1981-λ2-2*0,70621-λ2-2*1,1981-λ2=-3,021λ2+0,545λ+2,477
Тогда:
∂F∂λ=-6,042λ+0,545
-6,042λ+0,545=0λ=0,090
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(4)=0,706(1-λ)≈0,642
x2(4)=1,198(1-λ)≈1,090
Вычисляем значение целевой функции в точке X(4):
FX4=1*0,642+4*1,090+0,642*1,090-2*0,6422-2*1,0902≈2,501
6. Проверяем условие окончания поиска решения:
FX4-FX3=2,501-2,477=0,024>ε
Требуется следующая операция.
Итерация 5.
1. Определяем градиент целевой функции в точке X(4):
gradFX4=1+1*1,090-4*0,642;4+1*0,642-4*1,090=
=(-0,478;0,282)
2. Определяем угловую точку области допустимых решений, соответствующую предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Решаем задачу линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-0,478×1+0,282×2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Аналогично итерации 1 получаем, что поиск нового решения будет выполняться в направлении от точки X4=(0,642;1,090) к точке X*=(0;6).
3. Составляем уравнения для перехода к новому решению:
x1(5)=x1(4)+λx1*-x14=0,642+λ0-0,642=0,642(1-λ)
x2(5)=x2(4)+λx2*-x24=1,090+λ6-1,090=1,090+4,910λ
4. Определяем коэффициент λ. Уравнения для перехода к новому решению, построенные на шаге 3, подставляем в целевую функцию:
Fλ=0,6421-λ+4*(1,090+4,910λ)+0,6421-λ*(1,090+4,910λ)-2*0,64221-λ2-2*(1,090+4,910λ)2=-52,193λ2+1,691λ+2,501
Тогда:
∂F∂λ=-104,386λ+1,691
-104,386λ+1,691=0λ=0,016
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(5)=0,642(1-λ)≈0,632
x2(5)=1,090+4,910λ≈1,169
Вычисляем значение целевой функции в точке X(5):
FX5=1*0,632+4*1,169+0,632*1,169-2*0,6322-2*1,1692≈2,515
6. Проверяем условие окончания поиска решения:
FX5-FX4=2,515-2,501=0,014>ε
Требуется следующая операция.
Итерация 6.
1. Определяем градиент целевой функции в точке X(5):
gradFX5=1+1*1,169-4*0,632;4+1*0,632-4*1,169=
=(-0,359;-0,044)
2. Определяем угловую точку области допустимых решений, соответствующую предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Решаем задачу линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:
w=-0,459×1-0,044×2→max
x1+2×2≤123×1+x2≤15×1,x2≥0
Поскольку x1,x2≥0, а коэффициенты целевой функции – отрицательные, то решение очевидно: x1=x2=0.
Это означает, что поиск нового решения будет выполняться в направлении от точки X5=0,632;1,169 к точке X*=(0;0).
3. Составляем уравнения для перехода к новому решению:
x1(6)=x1(5)+λx1*-x15=0,632+λ0-0,632=0,632(1-λ)
x2(6)=x2(5)+λx2*-x25=1,169+λ0-1,169=1,169(1-λ)
4. Определяем коэффициент λ. Уравнения для перехода к новому решению, построенные на шаге 3, подставляем в целевую функцию:
Fλ=0,6321-λ+4*1,1691-λ+0,632*1,1691-λ2-2*0,63221-λ2-2*1,1691-λ2=-2,793λ2+0,278λ+2,515
Тогда:
∂F∂λ=-5,586λ+0,278
-5,586λ+0,278=0λ=0,050
5. Из уравнений, составленных на шаге 3, определяем новое решение:
x1(6)=0,632(1-λ)≈0,600
x2(6)=1,169(1-λ)≈1,111
Вычисляем значение целевой функции в точке X(6):
FX6=1*0,600+4*1,111+0,600*1,111-2*0,6002-2*1,1112≈2,522
6. Проверяем условие окончания поиска решения:
FX6-FX5=2,522-2,515=0,007<ε
Т.к. FX6-FX5<0,01, то оптимальное решение найдено:
x=0,600;1,111, FX=2,522
