【正文】 3 3 4 62 2 93 2 2 4..4 2 3 3 6, , , , , 0x x x x xx x x x xstx x x xx x x x x x? ? ???? ? ? ? ??? ? ???? ? ? ? ???? ???? ? ? ???? ??? ???線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計算步驟 ?單純形法進(jìn)一步討論 ?其他應(yīng)用例子 圖解法 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程 。 圖 解 法 () ???????????????????0,52426155..2m ax212121221xxxxxxxtsxxz() () () 圖解法 (a)可行域有界 (b)可行域有界 (c)可行域無界 唯一最優(yōu)解 多個最優(yōu)解 唯一最優(yōu)解 (d)可行域無界 (e)可行域無界 (f)可行域為空集 多個最優(yōu)解 目標(biāo)函數(shù)無界 無可行解 線性規(guī)劃及單純形法 ?線性規(guī)劃問題及數(shù)學(xué)模型 ?圖解法 ?單純形法原理 ?單純形法計算步驟 ?單純形法進(jìn)一步討論 ?數(shù)據(jù)包絡(luò)分析 ?其他應(yīng)用例子 單純形法原理 ? 線性規(guī)劃問題的解的概念 ? 凸集及其頂點 ? 幾個基本定理 解 的 概 念 可行解 ： 變量滿足所有約束條件的一組值 可行解集 ： 所有可行解構(gòu)成的集合 可行域 ： 可行解集構(gòu)成 n維空間的區(qū)域 ?????0xbAX}0{ ??? xb,Ax|xD??????????????）（ njxmibxatsxcjnjijijnjjj,2,10), . . ,1(..zm a x 11?線性規(guī)劃問題 解的概念 最優(yōu)解： 使得目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解 最優(yōu)值： 最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值 目的： 求最優(yōu)解和最優(yōu)值 求解方法： 單純形法 CXZ ?m a x?????0.. XbAXts解的概念 先研究 AX=b 設(shè) 系數(shù)矩陣 A是 m n矩陣，秩為 m， B是 A中 m m階非奇異子矩陣（即 |B|≠0）， 則稱 B是線性規(guī)劃問題的一個 基 。 幾個事實 1 ． 基本可行解不一定都是最優(yōu)解， 最優(yōu)解也不一定都是基本解 2 ． 如果有兩個基本可行解是最優(yōu)解， 則兩解的凸組合也都是最優(yōu)解。 理 論 方 法 定理 （ 最優(yōu)性準(zhǔn)則 ）如果0??，則基可行解 x 為原問題的最優(yōu)解。把 Z 看成變量在 單純形表中加上一列，同時加上一行描述方程bBcxz B 1???? ?，則可以 得到新的單純形表： Z 1x … rx … mx 1?mx … kx … nx 1 0 … 0 … 0 1?m? … k? … n? bBc B 1?? 1 11 ?ma … ka 1 … na 1 ? ? ? ? ? ? 1 1?rma … rka … rna ? ? ? ? ? ? 1 1?mma … mka … mna 1b ? rb ? mb 當(dāng)進(jìn)行轉(zhuǎn)換時只需要把k?轉(zhuǎn)換成 0 對應(yīng)其它位置等價變換即可。 對 偶 理 論 ? 對偶規(guī)劃 ? 對偶理論 ? 對偶單純形算法 規(guī) 范 形 式 的 對 偶 規(guī) 劃 規(guī)范形式的線性規(guī)劃 ??????0..m i nxbAxtsxc ???????0,..m i nyxbIyAxtsxc 其對偶規(guī)劃為 ? )0,(),(..m a x??? cIAtsb?? ??????0..m a x???cAtsb 一般形式的對偶規(guī)劃 對于一般形式的線性規(guī)劃 通過把其轉(zhuǎn)化為標(biāo)準(zhǔn)形式同樣可以得到其對偶規(guī)劃為 ： ???????????????????????qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn, . . . ,2,1。1226..215m i n5321432131jxxxxxxxxxtsxxj 其對偶規(guī)劃為 ?????????????????????00212605..2m a x2121212121??????????ts ???????????????????00212605..2m a x2121212121??????????ts ?????????????3,2,1。 ????????NBNcNBc1? bBcxcB1~ ??????非 基 變 量 改變非基變量 kx 的價值向量 kc ? kc? ： kBkcNBc ?????? 1? ?kkkkcc ????? ?? 為了使原最優(yōu)解還是最優(yōu)解則要求 0??????kkkkcc?? ， 即kkkcc ???? 基 變 量 改變基變量 kx 的價值向量 kc ? kc ? ，基變量 kx 對應(yīng)的約束為第 l 個 ??????????NkkBcNBccNBc11)0,0,0,0( ?? )(1))((lkkTNNBcc????? ? lkkBBBbccbcbcbBc )(1??????????? ????????NBNcNBc1?算 例 問題 的目標(biāo)函數(shù)中變量2x的系數(shù)由 0 變成 1. ????????????????5,4,3,2,1。 而車間 1每周可用于生產(chǎn)這兩種新產(chǎn)品的時間為 4小時 、 車間 2為 12小時 、 車間 3為 18小時 。 例如利潤最大 、 成本最小 等 。 ?車間 1每周可用工時限制： x1 ? 4 ?車間 2每周可用工時限制： 2x2 ? 12 ?車間 3每周可用工時限制： 3x1 +2x2 ? 18 ?非負(fù)約束 :x1 ? 0, x2 ? 0 例 線性規(guī)劃模型 : 12121212M ax z 3 0 0 5 0 0 4 2 12s .t . 3 2 1 8, 0xxxxxxxx???????????? ??這是一個典型的 利潤最大化 的生產(chǎn)計劃