【正文】 ) ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可以進行圖解了。 。 凸 集 的 概 念 頂點 ——設 K是凸集， X?K； 若 K中不存在兩個不同的點 X（ 1） ? K， X（ 2） ? K 使 X=αX（ 1） +（ 1α） X（ 2） （ 0α1） 則稱 X為 K的一個 頂點 （也稱為極點或角點）。 線性規(guī)劃問題的基可行解 x對應線性規(guī)劃問題可行域 (凸集 )的頂點 解的幾何意義 猜想 1 線性規(guī)劃的可行域是凸集； 猜想 2 最優(yōu)解若存在 ， 則可以在可行域的頂點上得到； 猜想 3 可行域的頂點的個數是有限的； 猜想 4 若有兩個最優(yōu)解，則其連線上的點也是最優(yōu)解，即最優(yōu)解有無窮多個 猜想 5 對于標準型的線性規(guī)劃 X是可行域頂點的充分必要條件是 X是基本可行解。 剩余的問題是如何判斷一個基可行解是最優(yōu)解， 如果不是則如何從一個基可行解轉到另一個基可行解。 如果 01 ?? bB 則稱該 基可行解為非退化的 ，如果一個線性規(guī)劃的所有基可行解都是非退化的則稱該 規(guī)劃為非退化的 。 給定一個非退化的基可行解 x，對應的可行基為 B ，則等式約束變?yōu)椋? bBNxBx NB 11 ?? ?? 典式 NB NxBbBx11 ?? ?? 目標函數NNBB xcxcxc??? ?? ?NNNB xcNxBbBc???? ?? )( 11 ?NNBB xcNBcbBc )(11 ????? ?? 令??? ??NBN cNBc1?，0?B?， 則xbBcxc B ???? ?? ?1 規(guī)劃等價于 ????????????0..m i n111xbBNxBxtsxbBcNBB? 例 考慮問題： ?????????????????????5,4,3,2,1。 目標函數NNBB xcNBcbBcz )(11 ????? ???等價于 bBcxcNBcz BNNB 11 )( ????? ??? 由于0?B?，??? ??NBN cNBc1?，所以bBcxz B 1???? ?。021322..2m i n53243232132jxxxxxxxxxxtsxxzj 初 始 單 純 形 表 以1x 、4x 和5x 為基變量就可以得到初始基可行解?)2,1,0,0,2( ， 其對應的單純形表為 1x 2x 3x 4x 5x 1 2 1 2 1 1 3 1 1 1 1 2 1 2 迭 代 1 由于 012??? ，所以該基可行解不是最優(yōu)解，同時系數矩陣該列有大于 0的元素，所以取2x 為入基變量。 2 . 現在還有待解決的問題是如何給出初始基可行 解以及出現退化的時候如何處理。, . . . ,2,1。..m a x????實 例 例 寫出下列規(guī)劃的對偶規(guī)劃 ???????????????5, . . . ,2,1。 定理 如果一個線性規(guī)劃有最優(yōu)解，則其對偶規(guī)劃也有最優(yōu) 解， 且它們的最優(yōu)值相等。以此為初始基可行解進行迭代就可以求出 新問題的解。 為了使原最優(yōu)解依然是新問題的最優(yōu)解， 2x 的系數最小 可以變?yōu)?/122??? c?。 經測算 ，每生產一扇門需要在車間 1加工 1小時 、 在車間 3加工 3小時；每生產一扇窗需要在車間 2和車間 3各加工 2小時 。 ?問該 工廠應如何安排這兩種新產品的生產計劃 ，可使總利潤最大 ？ ?在該問題中 ， 目標是總利潤最大化 ， 所要決策的變量是新產品的每周產量 ， 而新產品的每周產量要受到三個車間每周可用于生產新產品時間的限制 。 （ 2） 目標函數 是指對問題所追求的目標的數學描述 。 解： 例可用下表 表示 。 由于門和窗的單位利潤分別為 300元和 500元 ， 而其每周產量分別為x1和 x2， 所以每周總利潤 z為： z = 300x1＋ 500x2 （ 元 ） （ 3） 約束條件 本問題的約束條件共有 四 個 。 ?在 Excel電子表格中建立線性規(guī)劃模型 ?用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ?在用電子表格建立數學模型 （ 這里是一個線性規(guī)劃模型 ） 的過程中 ， 有三個問題需要得到回答： （ 1） 要作出的決策是什么 ？ （ 決策變量 ） （ 2） 在作出這些決策時 ， 有哪些約束條件 ？（ 約束條件 ） （ 3） 這些決策的目標是什么 ？ （ 目標函數 ） ? 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 （如果 “ 工具 ” 菜單中沒有 “ 規(guī)劃求解 ” 選項，請參見 SOLVER文件夾下的 “ Excel規(guī)劃求解工具的安裝說明 .doc”） 在用 Excel的 “ 規(guī)劃求解 ” 工具求解線性規(guī)劃問題 ， 為 單元格命名 能使線性規(guī)劃問題的電子表格模型更加容易理解 。 用 Excel“規(guī)劃求解 ” 工具求解線性規(guī)劃問題 線性規(guī)劃結束！ 。 所以 ， 一般給跟公式和模型有關的四類單元格命名 。其中，“ Max”是英文單詞“ Maximize”的縮寫，含義為“最大化”； “ .”是“ subject to”的縮寫，表示“滿足于 ……”。 可設： x1為每周門的產量 （ 扇 ） ； x2為每周窗的產量 （ 扇 ） 。 （ 3） 約束條件 是指實現問題目標的 限制因素 。 ?實際上 ， 所有的線性規(guī)劃問題都包含這三個因素： （ 1） 決策變量 是問題中有待確定的 未知 因素 。已知每扇門的利潤為 300元 ， 每扇窗的利潤為 500元 。 Bx Nx RHS Z Bx 0 ??? ? NB cNBc 1 bBcB 1?? I NB 1? bB 1? 當只改變一個分量ssbb ?? 時： 11111)()(???????????????????sssBbbbbBbBbbbBbBb 其中1?sB 為1?B 的第 s 列。1226..215m i n5321432131jxxxxxxxxxtsxxzj1x 2x 3x 4x 5x 1/2 1 1/4 9/4 31 /4 1/2 1 1/4 1/4 1 2 1/2 3/2 1/4 1/2 由于 2x 為非基變量，所以系數的改變只影響 2x 的檢驗數， 新的檢驗數為 2/3102/12222 ??????????? cc??。0)( ????njxAc jj ,...,2,1。1226..215m i n32132131jxxxxxxxtsxxj 對 偶 理 論 定理 若x和 ?分別是原規(guī)劃和對偶規(guī)劃的可行解，則 x和 ? 分別是原規(guī)劃和對偶規(guī)劃的最優(yōu)解的 充要條件是bxc ???。0,...,2,1。, . .