推 pigalan :推 05/02 17:13
※ 引述《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)