作者chemmachine (chemmachine)
看板Math
标题Re: [线代] 作业研究 simplex method 一题请问
时间Sun Apr 26 14:41:42 2020
※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1587883310.A.9C1.html
1F：推 illousion : 如果我没有理解错的 你逐一消去变数的算法叫做 04/26 14:57
2F：→ illousion : Fourier-Motzkin Elimination 确实可以解线性规划 04/26 14:58
3F：→ illousion : 可是他的计算时间对於高维的问题非常的慢 不实用 04/26 14:58
4F：→ chemmachine : 谢楼上大大解我疑惑 04/26 14:58
5F：→ chemmachine : 恩恩有印象加减消去法就是比代入消去法快 04/26 14:59
6F：→ illousion : 如果有m个不等式n个变数 时间复杂度为O(m^(2^n)) 04/26 15:00
7F：→ illousion : 现代线性规划的求解器solver的code都是基於单形法 04/26 15:00