最优化方法习题1答案

最优化方法习题1答案

《最优化方法》（研究生）期末考试练习题答案

二.简答题

min -5y1 9y2, s.t. 4y1 3y2 3, -2y1 y2 2, 1．

3y1 4y2 8, y1,y2 0;

x3 x4 0, （以x1为源行生成的割平面方程） 2．

注意：在x1为整数的情况下，因为x3,x4 0，该方程自然满足，这是割平面的退化情形

1

656

111

x3 x4 , （以x2为源行生成的割平面方程）

442

3．

a1 0,b1 3

1 a1 0.382(b1 a1) 0 0.382*3 1.146

1 a1 0.618(b1 a1) 0 0.618*3 1.854 ( 1) (1.146)3 2*1.146 1 0.2131 ( 1) (1.854)3 2*1.854 1 3.6648

事实上,不经计算也可以看出

( 1) ( 1)，所以a2 0,b2 1.854。

即：初始的保留区间为[0，1.854]。近似的最优解：x*

0 1.854

0.927.2

f1(x) x1e x2*( 1) 2.7 x1ex2 2.7

4．令

f2(x) x1e x2*(0) 1 x1 1f1(x) x1e

x2*(1)

0.4 x1e

x2

0.4

f1(x) x1e x2*(2) 0.1 x1e 2x2 0.1

拟合问题等价于求解下列最小二乘问题：min

(f(x))

i

i 1

4

2

三.计算题

1．分别用最速下降方法和修正的牛顿法求解无约束问题 minf(x) x1 4x2。 取初始点x

2

2

1

T

2,2 ， 0.1.

最优化方法习题1答案

解： f 2x 1

在初始点 x 1

2,2 T

8x 2 ，

，

f 4

16

从而最速下降法的搜索方向为：d1 4

16

.

最优步长 *满足f(x(1) *d1) min

f(x(1) d1)

其中

f(x(1) d1) f(2 4 ,2 16 ) (2 4 )2 4(2 16 )2.

求解得到： 17/130, 从而

x 2 2,2 T

17/130*(-4,-16)T (96/65, 6/65)T

在x 2

96/65, 6/65 T

， f 192/65 -48/65 ，

从而最速下降法的搜索方向为：d1 192/65

48/65

.

继续迭代,直至满足精度。

在初始点x 1 2,2 T

，

G 20 1

1/20 08 ,G 01/8

从而修正的牛顿法的搜索方向为：

d1 G 1 f 1/20 4 -2

01/8 16 -2

最优步长 *满足

f(x(1) *d1) minf(x(1) d1

)

f(x(1) d1) f(2 2 ,2 2 ) 5(2 2 )2. 1, 从而x 2 2 2 ,2 2 T

(0,0)T

在x 2 0,0 T

， f 0 0 ，显然满足精度。

2

f 20 x

(2) 正定， 08

x(2)即为所求的极小点。(1分)

易见：

最优化方法习题1答案

min

2．讨论约束极值问题

2

f(x) x12 x2 6x1 6x2 8

s.t.

x1 x2 4 x x 0

2 1

x1 0 x 0 2

的Kuhn-Tucker点。

f(x) [2x1 6,2x2 6]T

g1(x) x1 x2 4, g1(x) [1,1]T g2(x) x1 x2, g2(x) [1, 1]T

g3(x) x1, g3(x) [ 1,0]T。 g4(x) x2, g4(x) [0, 1]T

所以该约束问题的Kuhn-Tucker条件为

2x1 6 1 1 1 0 1 2 1 3 0 4 1 0 2x 6 1

2

(x x 4) 0

2

11

2(x1 x2) 0

3x1 0

4x2 0

x1 x2 4 0 x x 0

2

1

x1 0 x 0 2 1, 2, 3, 4 0

若x1 0,x2 0,则x1 x2 4 4 0, 从而 1 0。

代入第一个式子得到 6 2 3 0 6 2 4 0

从而 2 4 6 0,矛盾。

最优化方法习题1答案

若x1 0,x2 0,则x1 x2 0从而 2 0。又由于x2 0,从而 4 0

代入第一个式子得到 6 1 3 02x2 6 1 0

从而 1 3 6,2x2 6 3 6 2x2 3 0,与x2 0, 3 0矛盾。

若x1 0,x2 0,则x1 x2 0则 2 0, 3 0

代入第一个式子得到2x1 6 1 0 6 1 4 0

从而 1 4 6,2x1 6 4 6 2x1 4 0,与x1 0, 4 0矛盾。

若x1 0,x2 0,且x1 x2 0则 2 0。又由于x1 0,x2 0从而 3 0, 4 0,

代入第一个式子得到2x1 6 1 02x2 6 1 0

从而x1 x2,与x1 x2 0矛盾。

若x1 0,x2 0,x1 x2,但x1 x2 4则 1 0。又由于x1 0,x2 0从而 3 0, 4 0,

代入第一个式子得到2x1 6 2 02x2 6 2 0从而 1 2,

x1 x2 3,这与x1 x2 4矛盾。

x1 0,

x2 0,x1 x2 4,

讨论了所有的情况后,我们可以得出结论,从而(2,2)为该问题的一个Kuhn Tucker点.

3．构造増广函数

最优化方法习题1答案

x) (x 1)2 (x)2 2

12 3k(x1 x2 2)若x1 x2 2 0

k( (x2 (x2

1 1)2 3)

若x1 x2 2 0若x1 x2 2 0,则

由 2(x1 1) 0

k(x) 2(x 3)

2 0 ，可得

x1 1,x2 3,与x1 x2 2 0矛盾.若x1 x2 2 0,则

由 2(x1 1) 2 k(x1 x2 2) 0

k(x) 2(x 3) 2 k(x1 x2 2)

2 0 ，可得

x11

2 x1 2,x1 1 2 .从而x2 2

k1 2k这是对于固定的 k，minx R

2

k(x)的解. lim x1 k

lim

1

1 2 0

k k

x2 x1 2 2从而

x* (0,2)为原问题的最优解。

minf(x) x2

1 6x1 9 2x2

4．用内点法求解非线性规划

s.t. g1(x) x1 3 0 g2(x) x2 3 0

构造増广函数

2k(x) x1 6x1 9 2x2 k(

1x 1

3

)1 3x2

2x k 1 6 由 (x2 1 3) k(x) 0 k ，可得 2 0 (x

2 3)2 x k

1 3 k

2x2 3

2

这是对于固定的 k，min

x R

2

k(x)的解. lim k 3

k 0

x1 lim 0

3 k2

k

lim1 k 0

x lim3

k 0

2

3从而

x* (3,3)为原问题的最优解。

(4分)

(2分)

(4分)

(4分)

(2分)

(4分)

最优化方法习题1答案

5. 构造増广函数

1212

x1 x2 vk(x1 x2 1) k(x1 x2 1)226

x1 vk 2 k(x1 x2 1) 0

由 k(x) 1 0 ，可得 x v 2 (x x 1) 2 kk12

3

2 vk3(2 k vk)

x2 3x1,x1 k.从而x2

1 8 k1 8 k

k(x)

(4分)

(2分)

这是对于固定的 k，min k(x)的解.2

x R

k

lim x1 lim

2 k vk1

k 1 8 4k

(注意vk是一个数)

(4分)

3

x2 3x1

4从而

6．解：首先化成标准形式

13

x* (,)为原问题的最优解。

44

minZ 3x1 2x2 x3 Mx7 Mx8

x1 x2 x3 x4 6

x3 x5 x7 4 x1

x2 x3 x6 x8 3 x,x,x,x,x,x,x,x 0

以x1为换入变量，根据最小比值原则确定x7为换出变量。

最优化方法习题1答案

以x2为换入变量，根据最小比值原则确定x4为换出变量。

检验数全部为正，但人工变量没有完全换出，说明此优化问题没有可行解（可以验证原问题中包含矛盾的条件），此最优单纯形表的最优基是

110 1 10 1

B (p2,p1,p8) 010 ，B 010

101 111

四.应用题

解：设x1,x2 分别为该厂生产甲乙两种产品的数量。该问题的目标规划模型为： (2分)

minz P1d1 P2d2 P3(2d3 5d4)

(3分)

12x1 30x2 d1 d1 2400

x1 2x2 d2 d2 200

(5分)

x1 d3 d3 60 x2 d4 d4 80

最优化方法习题1答案

x1,x2,di ,di 0

(i 1,2,3,4)

其中在P3级目标中，因甲产品的利润与乙产品利润的比值为2：5，故取权系数为2：5. 求解过程见图.

(5分)

满足P1,P2目标的解空间为三角形ABC区域，考虑P3的目标要求时，因d3的权系数小 于d4 的权系数，故先取d4 0，这时解空间为ACD区域，在此区域中，只有D点使d3 取

值最小，故取D点为满意解，其坐标为（40,80），即该厂每年应生产甲产品40个单位，乙产品80个单位.

(5分)

本文来源：https://www.bwwdw.com/article/5ufq.html