Re: [線代] 作業研究 simplex method 一題請問

[chemmachine (chemmachine)]

※ 引述《fish890315 (小瑜瑜;D)》之銘言：

樓上兩位OR專家已經解決原PO的問題了。
我剛好算出一個不同於單形法的方法，不知運籌界有沒有，懶的去查，
在PTT複製網站做個記錄。
KKT計算高維次很容易做出很多組拉格朗日，計算量會比較大。
維度不要太高理論上搭配運算軟體可解。

參考以下網站李柏堅有很好的教學：
https://www.youtube.com/watch?v=NXseqFK2BEo
基本上單形法是用加入人工輔助變數將不等式轉變為等式限制。
網站介紹的列運算是線代高斯消去法的一種變形，本質是加減消去法(高斯消去法)
我用高斯消去法計算網站例題和你的課本例題都可以得解。
這個是高斯消去法的使用。

另介紹代入消去法，
以網站例題為例，
P=5X+3Y+Z  加入人工輔助變數 t u v都為負數使
設2x+4y+z+t=8
  x+2y+2z+u=10
  2x+y+v=6
上列三個式子形成一組不定方程，其交集是可參數化的，仿照frideberg線代求特徵
向量的方法

三式消去x得3y+4z+2u-v=14
          3y+z+t-v=2
可解得y=-4/9t+2/9u+1/3v-2/3 z=1/3t-2/3u+4
兩者可得x=3-2/9t+1/9u-1/3v-1/3
x y z三者代入P=2X+3Y+Z，可得17-19/9T+5/9U-2/3V因TUV為輔助變數，且我推文
剛論證極值在邊界，故LET T U V->0 不用管正負號得極值17。這方法高維
也能用，且代入消去法應該和高斯消去法一樣有演算法，有實戰性。
驗證過代入消去法你的EX24也可以做，
不過我想你考試作業還是依照網站跟課本的類似高斯消去法(單形法)。

--
處心積慮 才不負猜疑
怕錯過最好的光陰
越忘記 越刻骨銘心
越沉迷 越遙不可及

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.132.141 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1587883310.A.9C1.html
推 illousion   : 如果我沒有理解錯的 你逐一消去變數的算法叫做
→ illousion   : Fourier-Motzkin Elimination 確實可以解線性規劃
→ illousion   : 可是他的計算時間對於高維的問題非常的慢 不實用
→ chemmachine : 謝樓上大大解我疑惑
→ chemmachine : 恩恩有印象加減消去法就是比代入消去法快
→ illousion   : 如果有m個不等式n個變數 時間複雜度為O(m^(2^n))
→ illousion   : 現代線性規劃的求解器solver的code都是基於單形法