【正文】 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 8 【 例 】 某商場(chǎng)決定：營(yíng)業(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ì) 費(fèi)用（元 /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ī)劃模型 注意 ， 礦石在實(shí)際冶煉時(shí)金屬含量會(huì)發(fā)生變化 ， 建模時(shí)應(yīng)將這種變化考慮進(jìn)去 ， 有可能是非線性關(guān)系 。 現(xiàn)有 2臺(tái)設(shè)備 A和 3臺(tái)設(shè)備 B， 每天可供加工時(shí)間為 8小時(shí) 。 則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成 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? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??????或或或?yàn)榱藭?shū)寫方便，上式也可寫成： 線性規(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????? ? ? ???? ????? 或在實(shí)際中一般 xj≥0,但有時(shí) xj≤0或 xj無(wú)符號(hào)限制 。 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 ????????????????????????無(wú)符號(hào)要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【解】（１）因?yàn)?x3無(wú)符號(hào)要求 ，即 x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 0, 33333 ????????? xxxx 其中 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/4/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 39 (3)第二個(gè)約束條件是 ≥號(hào)，在 ≥號(hào) 左端減去剩余變量 (Surplus variable)x5， x5≥0。 WinQSB軟件求解時(shí)，不必化成標(biāo)準(zhǔn)型。 基變量 、 非基變量是針對(duì)某一確定基而言的 ， 不同的基對(duì)應(yīng)的基變量和非基變量也不同 。 01 ?）（X ）（ 2X反之 ， 可行解不一定是基本可行解 例如 滿足式 （ ） ～ （ ） ， 但不是 任何基矩陣的基本解 。A點(diǎn)是基本最優(yōu)解 ,同時(shí)也是最優(yōu)解、基本可行解、基本解和可行解。 定理 關(guān)系 ， 極點(diǎn)是基本可行解 ， 反之 ， 基本可行解一定是極點(diǎn) ， 但它們并非一一 對(duì)應(yīng) ， 有可能兩個(gè)或幾個(gè)基本可行解對(duì)應(yīng)于同一極點(diǎn) （ 退化基本可行解時(shí) ） 。 當(dāng)系數(shù)矩陣 A中可以觀察得到一個(gè)可行基時(shí) （ 通常是一個(gè)單位矩陣或 m個(gè)線性無(wú)關(guān)的單位向量組成的矩陣 ） ， 可以通過(guò)解線性方程組求得基本可行解 。 計(jì)算步驟： ，列出初始單純形表，求出檢驗(yà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進(jìn)基 ， 而 a120， a220， 沒(méi)有比值 ， 從而線性規(guī)劃的最優(yōu)解無(wú)界 。 （ b）選出基變量 ，求最小比值： 單純形法 Simplex Method ： （ a）選進(jìn)基變量 設(shè) λk=max｛ λj | λj 0｝ ,xk為進(jìn)基變量 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可作為初始基變量，單純法計(jì)算結(jié)果如表 。參看表 （ a）。 下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法 。 X是凸集 K的極點(diǎn)即 X不可能是 K中某一線段的內(nèi)點(diǎn)，只能是 K中某一線段的端點(diǎn)。 21 21Q基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。 TX )1,27,21,0,0(? 基本解 (basis solution) 對(duì)某一確定的基 B，令非基變量等于零，利用式（ ） 解出基變量，則這組解稱為基 Ｂ 的基本解。 基本概念 Basic Concepts 基 (basis)A中 m m子矩陣 B并且有 r（ B） =m，則稱 B是線性規(guī)劃的一個(gè)基（或基矩陣 basis matrix ）。 當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束 974 321 ??? xxx將其化為兩個(gè)不等式 ??????????974974321321xxxxxx再加入松馳變量化為等式。 先過(guò)原點(diǎn)作一條矢量指向點(diǎn)（ c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形； 。產(chǎn)品的產(chǎn)量 y等價(jià)于 21 31,21 xyxy ??整理得到線性規(guī)劃模型 約束線性化。 投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多 。 某鋼鐵公司生產(chǎn)一種合金 ， 要求的成分規(guī)格是：錫不少于 28%， 鋅不多于 15%， 鉛恰好 10%， 鎳要界于35%~55%之間 ， 不允許有其他成分 。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是 ， 1， （ m），這些軸需要用同一種圓鋼來(lái)做，圓鋼長(zhǎng)度為 4 m。 企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃 ， 使企業(yè)在計(jì)劃期內(nèi)總的利潤(rùn)收入最大 ？ 線性規(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 利潤(rùn)（元 /件） 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 利潤(rùn)（元 /件） 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