数学建模社区-数学中国

标题: [求助]一道优化的题目，除了库恩塔克的解法，有些不明白，欢迎指教 [打印本页]

作者: 徐帆 时间: 2003-1-15 11:03
标题: [求助]一道优化的题目，除了库恩塔克的解法，有些不明白，欢迎指教

& E+ y) V# |8 W0 G ) [9 V7 \( O7 e c- D' ]; k7 ?; ~ K: L) E! [: ?# b5 \# Y. q0 B& D1 R, |$ i& \$ \0 h! v6 A! \9 x, T5 r3 v4 ~- m% R7 u& V2 W, }# R9 ]5 c0 N9 O* Q8 D! w4 I6 M9 O" H2 G

再求数学高人

4 u$ Y* R( o$ F% q* l
" ^3 a+ C/ U; b, n& ?6 }7 V
用分段线性函数近似求解非线性规划(不知道标准数学表达法是怎样的)，
' @- e" T# W9 i% V a+ P7 B
Min x₁²-4x₁-2x₂
. b9 [7 ^+ b* Z+ Z
s.t.不等式组条件如下
8 i5 P. w: j' E
X1+X2<=4
4 O, F# J3 S3 \7 K1 @
2X1+X2<=5
* x4 s7 M2 E2 s6 f* A: \, l
-X1+4X2>=2
3 v0 U5 e( ^9 c4 V
X1>=0 X2>=0
; h+ Z- s( D4 i2 N6 {5 D0 I& j
【方法一】:
4 c( H0 q+ L" [ ]" F* H
因目标函数中变量是可分离的，所以用替代变量y代替二次方的变量x₁²，将原目标表示成一次函数，以便于用线性（单纯形）方法求解。
7 c$ J$ H3 F A; }5 [# H) j5 x
首先给定一个取值的区间，设0≤x1≤2.5, 选择一系列x1的值，比如0，1，2 和2.5, 计算对应的函数值y如下:
% n0 B; |0 o& X' F/ g5 a% i/ E: T& ^
点O x1=0 y= x₁²=0
, K) G, @( d/ A2 J
点A x1=1 y= x₁²=1
$ N8 M2 _6 m8 K$ u, O
点B x1=2 y= x₁²=4
6 O5 G! U: K9 [ O, q9 j
点C x1=2.5 y= x₁²=6.25
; a0 W* x. o# m( R
如图1:
+ ~/ ]0 l& j& P/ A7 b9 \

) S; e1 J* ~8 X" }0 Z4 Y
6 l9 U, F- h+ O; d
用分段的线段OA, AB, BC近似代替y=x^2,原规划表达为线性规划如下:
* X) `) `8 Y5 \) H9 \
Min Y-4X1-2X2
2 e2 U) O. G8 v, h
s.t.
) G$ U' e8 N( f1 y) ]
X1+X2<=4
- w* d" I5 }" U& ~
2X1+X2<=5
# P) s; w; O1 X, n* M. b. T
-X1+4X2>=2
/ }* V! n2 `' g+ q" [! A
X1-Y<=0
+ Q. ^- y, t) B4 y$ y d) k9 `: _
3X1-Y<=2
) |1 D& m" W0 k2 |
4.5X1-Y<=5
& a, T$ [3 J7 v$ k/ Z
X1>=0 X2>=0
: G( l* D" e2 r6 q o1 S* O7 b
至此没有问题, 但解下来该怎样解就不知道了.
& R q( h% k/ \# p7 O. A6 G

5 V+ W; F3 |4 ~0 U
【方法二】:
: r9 h0 Z" t0 x
取近似值的方法不一样，
' }1 t+ g1 Q# t c1 m* z
X1=0p1+1P2+2P3+2.5p4
' w# h Y9 J9 s
Y =0p1+1*p2+4*p3+6.25*P4
; }2 U# W3 I3 H5 ~ Q7 t
1 = p1+p2+p3+p4
9 n+ v' T* a: R0 s
9 F# B) q8 t6 O! i; |
原规划可表示如下:
% Q0 j0 [ P5 W7 m! {: n
Min Y-4X1-2X2
. }9 [6 J) X o/ D
s.t.
5 \7 f! E* U' q1 T* l4 N1 f" U v
X1+X2<=4
! t6 R3 z) i4 }
2X1+X2<=5
, N% @7 N9 p0 E; c
-X1+4X2>=2
0 Z! _ l' y1 }/ U
-X1+P2+2P3+2.5P4=0
]- M; R3 s! Y! b3 d4 [% }
-Y+P2+4P3+6.25P4=0
8 {, c5 m( K* d% J
P1+P2+P3+P4=1
7 Y p; m& N) i" r- F; A
Y,X1,X2,P1,P2,P3,P4>=0
, }- H/ H& l3 L" w
同样的问题,到这里就不知道下面怎么解了.
8 s4 N6 j/ q, o& E# a; w
图2
1 R% n2 K; [# J# I

0 l; P. ]% Q8 i9 V; j* G
原规划用Kuhn-Tucker方法可解, 但老师非要求用上面方法解, 所以请不吝赐教, 谢谢!
# ] h$ Y, K! I: i. X# j1 @5 Z 6 C$ U+ o# F z+ P: ^, I & _/ ^9 U1 U7 H j E) W
我用kuhn tucker解得答案为 min=-9， x1=1， x2=3,验算觉得答案是对的，可还是不是老师要求的方法
* t1 V8 D* a; {7 C7 F& s

作者: madio 时间: 2003-1-16 14:55
你不断地加密分点不就可以使得近似成的线性规划的可行域与原先非线性规划的可行域不断接近吗？细分到一定程度就可以认为差不多了呀！这样相当于增加了约束条件的个数来换取目标函数的简化！

作者: 徐帆 时间: 2005-12-29 18:04
这些我都明白，就是到了最后，不知道该怎么解这个不等式组了

作者: madio 时间: 2005-12-29 22:37

晕，大型线性不等式的求解问题至今好像没有什么好的办法呀！

作者: 徐帆 时间: 2005-12-29 22:45

不用大型的，就一般的，比如这一题，算三个点就好了，

如下了，该怎么解这个不等式，我在国内是英文专业，现在上物流master，碰到这种玩意实在不知道从哪里下手了，谢谢拉

Min Y-4X1-2X2

s.t.

X1+X2<=4

2X1+X2<=5

-X1+4X2>=2

X1-Y<=0

3X1-Y<=2

4.5X1-Y<=5

X1>=0 X2>=0

[em06][em06]

作者: madio 时间: 2005-12-29 22:55
好在是三维的向量不等式，你把每个不等式看成三维空间中的半平面，将这些半空间画出图来然后做交集就可以了！

作者: chenyugf 时间: 2006-3-13 15:58
唉,都是高手,就我不是

作者: yjshappy 时间: 2006-4-23 02:23

没看明白哦。。。。。。

作者: youshanglanyu 时间: 2007-1-14 23:34
还没看懂

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5