轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 来个线性代数的 [打印本页]

作者: 天痕 时间: 2005-1-13 03:50

第一个方程组：
min z = SIGMA (j=1..n) CjXj
方程为SIGMA (j=1..n) aij*Xj>=bi    (i=1,..,m)
                                    Xj>=0    (j=1,..,n)

第二个方程组：
max g = SIGMA(i=1..m) bi*yi
方程为SIGMA (i=1..m) aij*yi<=cj    (j=1,..,n)
                                    yi>=0    (i=1,..,m)

例：
min z = 4x1+7x2+6x3
3x1+1x2+2x3>=7
1x1+1x2+1x3>=2
x1,x2,x3>=0

max g =7y1+2y2
3y1+1y2<=4
1y1+1y2<=7
2y1+1y2<=6
y1,y2>=0

求证：所有满足上面条件的方程组若都存在解，则有z=g。

作者: 天宫公主 时间: 2005-1-13 09:08

Cj = cj 吧？

作者: 天宫公主 时间: 2005-1-13 10:03

先把问题写成矩阵形式,

Ax >= b (向量的每个单位/component此不等式成立)
Ay <= c

min z = <c, x> >= <A^*y, x> (因 x_i > 0)
max g = <b, y> <= <Ax, y>

但, <A^*y , x> = <y, Ax> = <Ax, y> (因问题只牵扯实数).
因此, min z >= max g, 而z = g.

作者: 天痕 时间: 2005-1-13 23:40

天公将军 2005-01-13 ￥ 200 轩辕通宝

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)