Basic Concept of Linear progra

你第一個問題中四數學書不是有解答了嗎?
姑且就兩個變數來說
就ax+by=0
因為這條等式會將平面畫成2個部份﹐一份屬ax+by>0﹐一份屬ax+by<0
只要將所有這些不等式的可行解部份重疊﹐便是整個線性規劃(linear programming )的可行解(feasible solution region )或者叫解集合
詳情可看http://1094.wwwts.au.edu.tw/front/bin/download.phtml?Part=PT06090001&Nbr=19176&Category=
第二個問題問得好﹐因為我中四時都沒有想到。因為我那時是做數機器罷了。事實上很多問題都不是用圖解法的。例如有三個或以上變數時圖解法便不管用。(現實世界裡的線性規劃問題有百至千個變數)現在人們一般用的是單純形法。
其實單純形法要深可以好深﹐要淺也可以不難。大意如下
單純形法是美國數學家G.B.丹齊克於1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重複進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。

你要留意這個方法雖然同樣是由一個頂點開始﹐但因為每次都可以判斷到那個頂點是不是最優﹐而且若果不是﹐它可以去到一個目標函數更大的解(可能大好多)所以比 (blindly checking all the vertex of the boundary of solution region)快好多。

另外單純形法可以做敏感度分析。例如在不重新求解的情況下。
1加多條限制(constraint)
2 某一條限制式的值改變(如2x+3y<100變成2x+3y<150)
對最優解有甚麼影響?

又因為單純形法用到矩陣理論﹐所以有些有趣理論。例如對偶問題


例子：某工廠擁有A、B、C 三種類型的設備，生產甲、乙兩種產品。每件產品在生產中需要佔用的設備機時數，每件產品可以獲得的利潤以及三種設備可利用的時數如下表所示。(略)求獲最大利潤的方案。

另一個問題：若設備A、B、C都用於外協加工，工廠收取加工費。試問：設備 A、B、C 每工時各如何收費才最有競爭力？

事實上用單純形法解到任意一個問題﹐另一個問題也解決了。

值得一提的是線性規畫是最優化理論和運籌學的一個分支﹐基本上不屬純數學範圍﹐所以你老師不懂單純形法也不出奇﹐朋友你有興趣的話可以參考相關書籍。
　　

2009-01-02 22:23:42 補充：
若果你大學讀數學﹐operation research or optiminzation 便是學linear programming。不過optiminzation偏向理論

2009-01-02 22:27:48 補充：
推介:蘇聯青年數學科普叢書(29)什麼是線性規劃？