作者scan33scan33 (亨利喵)
看板Math
标题Re: [线代] dual LP
时间Mon May 2 10:29:02 2011
※ 引述《asweknow ( )》之铭言：
: 大家好
: 我遇到一个对偶线性的问题
: max z = 1x1+2x2+3x3+4x4
: s.t.
: x1+x2+3x3+3x4>=1
: 2x1+2x2+3x3+4x4=2
: x1+3x2+x3+5x4<=4
: x1,x2,x3,x4>=0
: 限制式大於等於小於都有
: 不知道如何换成dual form
改写一下,
原式等价於：
max z = 1x1+2x2+3x3+4x4
s.t.
(大於，两边乘以负号变小於)
-x1+-x2+-3x3+-3x4 =<1
(等於用大於小於换掉)
2x1+2x2+3x3+4x4<=2
-2x1+-2x2+-3x3+-4x4<=-2
(小於等於的部份不用变...)
x1+3x2+x3+5x4<=4
(simplex constraint也不用变)
x1,x2,x3,x4>=0
也就是说
max z = a^T x
Ax <= b
x >= 0
其中：
a = [1 2 3 4]^T
A = [-1 -1 -3 -3
1 3 1 5
2 2 3 4
-2 -2 -3 -4]
b = [1 4 2 -2]^T
基本上这样一个基本的LP问题，
转dual直接变成：
min b^T y
A^T y >= a
y >= 0
Dual满好解的：
用可爱的simplex method解一下！
会算出答案：z=2
有错误(or看不懂的)请指正，谢谢！
--
I'm
CAT (Combinatorics, Analysis, and Topology)
About Me :
http://columbia.edu/~mt2767
想找程式或数学家教，还是发包程式案件吗？
http://w.csie.org/~b95028/parttime.php
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.90.67
※ 编辑: scan33scan33 来自: 140.112.90.67 (05/02 10:30)
1F：推 pigalan :推 05/02 17:13