【正文】 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 8 【 例 】 某商場決定：營業(yè)員每周連續(xù)工作 5天后連續(xù)休息 2天 ，輪流休息 。 表 1． 3 下料方案 方案 規(guī)格 1 2 3 4 5 6 7 8 9 10 需求量 y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000 y2 1 0 2 1 0 4 3 2 1 0 1000 y3 0 1 0 2 3 0 1 2 4 5 1000 余料（ m） 0 0 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 12 設(shè) xj(j=1,2… ,10)為第 j種下料方案所用圓鋼的根數(shù) 。 表 礦石的金屬含量 合金 礦石 錫 % 鋅 % 鉛 % 鎳 % 雜質(zhì) 費用（元 /t ） 1 25 10 10 25 30 340 2 40 0 0 30 30 260 3 0 15 5 20 60 180 4 20 20 0 40 20 230 5 8 5 15 17 55 190 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 15 解 : 設(shè) xj（ j=1,2， … ， 5）是第 j 種礦石數(shù)量，得到下列線性規(guī)劃模型 注意 ， 礦石在實際冶煉時金屬含量會發(fā)生變化 ， 建模時應(yīng)將這種變化考慮進去 ， 有可能是非線性關(guān)系 。 現(xiàn)有 2臺設(shè)備 A和 3臺設(shè)備 B， 每天可供加工時間為 8小時 。 則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 2m a x( m in)( , )( , )( , )0 , 1 , 2 , ,nnnnnnm m m n n mjZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx j n? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??????或或或為了書寫方便，上式也可寫成： 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 22 11m a x( m in)( , ) 1 , 2 , ,0 , 1 , 2 , ,njjjnij j ijjZ c xa x b i nx j n????? ? ? ???? ????? 或在實際中一般 xj≥0,但有時 xj≤0或 xj無符號限制 。 TnxxxX ), 21 ?＝（m a x0Z C XAX bX??????其中 : 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 38 【例 】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 3213min xxxZ ????????????????????????無符號要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【解】（１）因為 x3無符號要求 ，即 x3取正值也可取負值，標(biāo)準(zhǔn)型中要求變量非負，所以令 0, 33333 ????????? xxxx 其中 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 39 (3)第二個約束條件是 ≥號，在 ≥號 左端減去剩余變量 (Surplus variable)x5， x5≥0。 WinQSB軟件求解時，不必化成標(biāo)準(zhǔn)型。 基變量 、 非基變量是針對某一確定基而言的 ， 不同的基對應(yīng)的基變量和非基變量也不同 。 01 ?）（X ）（ 2X反之 ， 可行解不一定是基本可行解 例如 滿足式 （ ） ～ （ ） ， 但不是 任何基矩陣的基本解 。A點是基本最優(yōu)解 ,同時也是最優(yōu)解、基本可行解、基本解和可行解。 定理 關(guān)系 ， 極點是基本可行解 ， 反之 ， 基本可行解一定是極點 ， 但它們并非一一 對應(yīng) ， 有可能兩個或幾個基本可行解對應(yīng)于同一極點 （ 退化基本可行解時 ） 。 當(dāng)系數(shù)矩陣 A中可以觀察得到一個可行基時 （ 通常是一個單位矩陣或 m個線性無關(guān)的單位向量組成的矩陣 ） ， 可以通過解線性方程組求得基本可行解 。 計算步驟： ，列出初始單純形表，求出檢驗數(shù)。 單純形法 Simplex Method 表 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 71 21max xxZ ???????????????0,42123212121xxxxxx【例 】求解線性規(guī)劃 【 解 】 化為標(biāo)準(zhǔn)型 21max xxZ ????????????????4,1,042123421321?jxxxxxxxj 單純形法 Simplex Method 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 72 初始單純形表為 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 λj － 1 1 0 0 λ2=10, x2進基 ， 而 a120， a220， 沒有比值 ， 從而線性規(guī)劃的最優(yōu)解無界 。 （ b）選出基變量 ，求最小比值： 單純形法 Simplex Method ： （ a）選進基變量 設(shè) λk=max｛ λj | λj 0｝ ,xk為進基變量 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 67 【 例 】 用單純形法求解 321 2max xxxZ ???????????????02053115232321321321xxxxxxxxx、【 解 】 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式： 321 2max xxxZ ????????????????????5,2,1,0205311523253214321?jxxxxxxxxxj不難看出 x x5可作為初始基變量，單純法計算結(jié)果如表 。參看表 （ a）。 下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法 。 X是凸集 K的極點即 X不可能是 K中某一線段的內(nèi)點，只能是 K中某一線段的端點。 21 21Q基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。 TX )1,27,21,0,0(? 基本解 (basis solution) 對某一確定的基 B，令非基變量等于零，利用式（ ） 解出基變量，則這組解稱為基 Ｂ 的基本解。 基本概念 Basic Concepts 基 (basis)A中 m m子矩陣 B并且有 r（ B） =m，則稱 B是線性規(guī)劃的一個基（或基矩陣 basis matrix ）。 當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束 974 321 ??? xxx將其化為兩個不等式 ??????????974974321321xxxxxx再加入松馳變量化為等式。 先過原點作一條矢量指向點（ c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形； 。產(chǎn)品的產(chǎn)量 y等價于 21 31,21 xyxy ??整理得到線性規(guī)劃模型 約束線性化。 投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多 。 某鋼鐵公司生產(chǎn)一種合金 ， 要求的成分規(guī)格是：錫不少于 28%， 鋅不多于 15%， 鉛恰好 10%， 鎳要界于35%~55%之間 ， 不允許有其他成分 。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是 ， 1， （ m），這些軸需要用同一種圓鋼來做，圓鋼長度為 4 m。 企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃 ， 使企業(yè)在計劃期內(nèi)總的利潤收入最大 ？ 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 應(yīng)用模型舉例 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 5 產(chǎn)品 資源 甲 乙 丙 現(xiàn)有資源 設(shè)備 A 3 1 2 200 設(shè)備 B 2 2 4 200 材料 C 4 5 1 360 材料 D 2 3 5 300 利潤（元 /件） 40 30 50 表 產(chǎn)品資源消耗 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 6 321 503040max xxxZ ???????????????????????????0003005323605420232220233321321321321321xxxxxxxxxxxxxxx，【解】設(shè) x x x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為： 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 產(chǎn)品 資源 甲 乙 丙 現(xiàn)有資源 設(shè)備 A 3 1 2 200 設(shè)備 B 2 2 4 200 材料 C 4 5 1 360 材料 D 2 3 5 300 利潤（元 /件） 40 30 50 最優(yōu)解 X=(50,30,10)。數(shù)據(jù)、模型與決策 線性規(guī)劃 Linear Programming LP的數(shù)學(xué)模型 Mathematical Model of LP 圖解法 Graphical Method 標(biāo)準(zhǔn)型 Standard form of LP 基本概念 Basic Concepts 單純形法 Simplex Method 2/4/2023 數(shù)學(xué)模型 Mathematical Model 2/4/2023