Re: [線代] 線性不等式

[jacky7987 (憶)]

※ 引述《wong0101 (汪汪)》之銘言：
: 請問
: 2X+3Y+Z <= 6   (<= 為大於等於的意思)
: X+2Y+3Z <= 6
: X+Y+Z <= 5
: X,Y,Z 都為正數
: 求4X+4Y+3Z的最大值是多少?
: 答案是
: X=12/5
: Y=0
: Z=6/5
: 先謝謝大家

沒在數學版上打過單行法(Simplex Method)感覺很難試試看XD
(假設是小於等於)

加上slack variable變成

max w=4x+4y+3z s.t

2x+3y+ z+s_1         =6
 x+2y+3z    +s_2     =6
 x+ y+ z        +s_3 =5

畫表格!!

   | x   y   z   s_1  s_2  s_3 | Sol
-----------------------------------
 w |-4  -4  -3    0    0    0  | 0   <---選負最大的(一樣就隨便選XD)
-----------------------------------    choose x be entering variable
s_1| 2   3   1    1    0    0  | 6   minimum ratio test: min{6/2,6/1,5/1}=3
s_2| 1   2   3    0    1    0  | 6   Hence, s_1 is the leaving variable
s_3| 1   1   1    0    0    1  | 5

==================================   <--- 把x column變成[0,1,0,0]^T
                                          然後作高斯消去法

 w | 0   2  -1    2    0    0  | 12  <---在一次選負最大的 選z enters
-----------------------------------
 x | 1  3/2 1/2  1/2   0    0  | 3
s_2| 0  1/2 5/2 -1/2   1    0  | 3   mim ratio test: min{6,6/5,4}=6/5
s_3| 0 -1/2 1/2 -1/2   0    1  | 2        Hence s_2 leaves
===================================
 w | 0  11/5 0   9/5  2/5   0  |16/5 <---都是正的所以得到optimal
-----------------------------------
 x |         0                 |12/5  x=12/5 y=0 z=6/5,w=16/5
 z | 0   5   1   -5   2/5   0  |6/5
s_3|         0                 |7/5

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.240.221.55
→ jacky7987   :最後一個表格太多了有空再填先洗澡XDDD
※ 編輯: jacky7987       來自: 111.240.221.55       (11/27 02:06)
→ jacky7987   :不過如果超出範圍的方法的話就直接忽視吧XDD
推 wong0101    :太謝謝你了!!! 感恩XDD
推 ariainaqua  :太神了!!
→ jacky7987   :靠北XD