【正文】 2 1 0 2 2 5 120 1 1 2 1 12/3 1 3 1/3 2/3 2/3 5/3 40 0 2/3 4/3 4/3 7/3 9 0 0 1/3 1/3 2/3 1M 1/3 0 ? 由于人工變量 x6 = x7 = 0, 所以 ,得原問題的最優(yōu)解 x*=(4,1,9,0,0)T 目標(biāo)函數(shù)最優(yōu)值 zmax = 2 Note: 在計算過程中 ,某個人工變量一旦變?yōu)榉腔兞?,則該列可被刪去 167。 6 單純形法的進(jìn)一步討論 (2)兩階段法 第一階段 ： max z = c1x1 + c2x2 +… + xn (1c) . a11x1 + a12x2 +… + a1nxn = b1 a21x1 + a22x2 +… + a2nxn = b2 …… …… . (2c) am1x1 + am2x2 +… + amnxn = bm xj≥0 （ j = 1,2,… , n） (3c) w = – xn+1 – xn+2 –… – +m (1d) .t. a11x1 + a12x2 +… + a1nxn + xn+1 = b1 a21x1 + a22x2 +… + a2nxn + xn+2 = b2 …… …… (2d) am1x1 + am2x2 +… + amnxn + xn+m = bm xj≥0 （ j = 1,2,… , n, n+1,… , n+m） (3d) 判斷原 LP 問題 （ 1c） ~ （ 3c） 是否存在可行解，如果存在就找出一 個初始基可行解； 解之可得： （ a） 如果 wmax 0, 則原問題無可行解，停止計算； （ b） 如果 wmax = 0, 且人工變量都不是基變量，則轉(zhuǎn)入 第二階段； 第一章 線性規(guī)劃及單純形法 （ c） 如果 wmax = 0, 但仍有取零的人工變量為基變量； x1 x2 … xn xn+1 … xn+k … xn+m b a’l1 a’l2 … a’ln a’ln+1 … 1 … a’n+m 0 如 x n+k =0 是基變量，在最終單純形表中： a’l1 a’l2 … a’ln 不可能全為零，必有某個 a’lj ≠ 0， 這時 xj 不是基變量，與 x n+k 交換即可。 第二階段 ： 從第一階段所求得的初始可行基出發(fā)，求解原問題 167。 6 單純形法的進(jìn)一步討論 二、關(guān)于退化和循環(huán) 1955 年 Beale 給出如下例子： 4 5 6 71 4 5 6 72 4 5 6 73631m a x 20 6421. . 8 9 041112 3 02210 ( 1 , 2 , , 7 )jz x x x xs t x x x x xx x x x xxxxj? ? ? ?? ? ? ? ?? ? ? ? ?????m a x35( , 0 , 0 , 1 , 0 , 1 , 0) ,44Txz? ??最優(yōu)解： 第一章 線性規(guī)劃及單純形法 Bland 法則： （對極大值問題而言） 則選擇 xk 作為進(jìn)基變量。 (1)選擇進(jìn)基變量：選取 σj 0（ 1≤ j≤ n） 中下標(biāo) 最小的檢驗(yàn)數(shù) σk 所對應(yīng)的非基變量 xk作為進(jìn)基變量， 即如果 ? ?m in 0 , 1jk j j n?? ? ? ?(2) 選擇出基變量：當(dāng)按 θ 規(guī)則計算此值時 ， 如果 存在 n 個 ， 同時達(dá)到最小值 ， 就選其中下標(biāo) 最小的那個基變量作為出基變量 。 即如果 則選擇 xl作為出基變量 。 39。39。rrkba ?39。39。39。m in m in 0 , 1rrikrirk rkbbl r a i maa?????? ? ? ? ?? ? ???? 167。 7 線性規(guī)劃應(yīng)用舉例 生產(chǎn)計劃問題 某工廠明年根據(jù)合同 ， 每個季度末向銷售公司提供產(chǎn) 品 ， 有關(guān)信息如表 ， 若當(dāng)季生產(chǎn)的產(chǎn)品過多 ， 季末有積余 ， 則一個季度每積壓一噸產(chǎn)品需支付存貯費(fèi) . 現(xiàn)該廠 考慮明年的最佳生產(chǎn)方案 ， 使該廠在完成合同的情況下 ， 全 年的生產(chǎn)費(fèi)用最低 .試建立線性規(guī)劃模型 . 季度 j 生產(chǎn)能力 （ aj） 生產(chǎn)成本（ dj） 需求量（ bj） 1 30 15． 0 20 2 40 14． 0 20 3 20 15． 3 30 4 10 14． 8 10 第一章 線性規(guī)劃及單純形法 解： 方法一 設(shè)工廠第 j 季度生產(chǎn)產(chǎn)品 xj 噸 需求約束： 第一季度末需交貨 20 噸， x1≥ 20 第二季度末需交貨 20 噸， x120+x2≥ 20 這是上季末交貨后積余 第三季度末需交貨 30 噸， x1+x2 40+x3 ≥ 30 第四季度末需交貨 10 噸， x1+x2 +x3 70 +x4 = 10 生產(chǎn)能力約束： 0≤ xj ≤ aj j =1,2,3,4 季度 j 生產(chǎn)能力 （ aj） 生產(chǎn)成本（ dj） 需求量（ bj） 1 30 15． 0 20 2 40 14． 0 20 3 20 15． 3 30 4 10 14． 8 10 生產(chǎn)、存儲費(fèi)用： 第一季度： 15x1 第二季度 : 14x2+(x120) 第三季度 : +(x1+x2 40) 第四季度 : +(x1+x2 +x3 70 ) min z = + + + 26 . x1+x2 ≥40 , x1+x2 +x3 ≥70 x1+x2 +x3 + x4 =80, 20≤ x1≤30,0 ≤ x2≤40,0 ≤ x3≤20,0≤ x4≤10. 167。 7 線性規(guī)劃應(yīng)用舉例 季度 j 生產(chǎn)能力 （ aj） 生產(chǎn)成本（ dj） 需求量（ bj） 1 30 15． 0 20 2 40 14． 0 20 3 20 15． 3 30 4 10 14． 8 10 方法二 設(shè)第 i 季度生產(chǎn)而用于第 j 季度末交貨的產(chǎn) 品數(shù)量為 xij 噸 . 需求約束： x11=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 生產(chǎn)能力約束： x11 + x12 + x13+ x14 ≤ 30 x22 +x23 +x24 ≤ 40, x33 +x34 ≤20, x44 ≤ 10 xij 的費(fèi)用 cij= di+( ji ) min z =15 x11 + + + +14x22 + + + + + . x11=20 x11 + x12 + x13+ x14 ≤30 x12+x22=20 x22 +x23 +x24 ≤40 x13+x23+x33=30 x33 +x34 ≤20 x14+x24+x34+x44=10 x44 ≤10 xij ≥0 i =1,…,4。 j=1,…,4, j ≥i 第一章 線性規(guī)劃及單純形法 合理下料問題 某工廠要制作 100套專用鋼架，每套鋼架需要用長 為 、 。已知原料每根長 ， 現(xiàn)考慮應(yīng)如何下料，可使所用原料最?。? 解： 一根原料做一套，料頭. 下料方案表 方案 毛坯 /m 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 2． 9 2 1 1 1 0 0 0 0 2． 1 0 2 1 0 3 2 1 0 1． 5 1 0 1 3 0 2 3 4 合 計 7． 3 7． 1 6． 5 7． 4 6． 3 7． 2 6． 6 6． 0 料 頭 0． 1 0． 3 0． 9 0． 0 1． 1 0． 2 0． 8 1． 4 去掉料頭 ≥ 的方案可以嗎？ 167。 7 線性規(guī)劃應(yīng)用舉例 解： 設(shè) xj ( j=1,…,8 )分別按 8種方案下料的原材料根數(shù) 方案 毛坯 /m 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8 2． 9 2 1 1 1 0 0 0 0 2． 1 0 2 1 0 3 2 1 0 1． 5 1 0 1 3 0 2 3 4 合 計 7． 3 7． 1 6． 5 7． 4 6． 3 7． 2 6． 6 6． 0 料 頭 0． 1 0． 3 0． 9 0． 0 1． 1 0． 2 0． 8 1． 4 約束條件： : 2x1+x2+x3 +x4 ≥100 : 2x2+x3 +3x5 + 2x6 +x7 ≥100 : x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 第一章 線性規(guī)劃及單純形法 目標(biāo)函數(shù)分別為： 材料根數(shù)最少； min z= x1 +x2 +x3+x4 +x5 +x6 +x7+x8 . 2x1+x2+x3 +x4 ≥100 2x2+x3 +3x5 + 2x6 +x7 ≥100 x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 用單純形法求解可得： x*=（ 10， 50， 0， 30， 0， 0， 0， 0） T， 最少使用的材料為 90根，各種圓鋼數(shù)均正好 100個 . 167。 7 線性規(guī)劃應(yīng)用舉例 剩余料頭最少 min z = + x2 ++0x4 + + ++ . 2x1+x2+x3 +x4 ≥100 2x2+x3 +3x5 + 2x6 +x7 ≥100 x1 +x3+3x4 +2x6 +3x7+4x8 ≥100 xj ≥0 ( j=1,…,8 ) 用單純形法求解可得： x*=（ 0， 0， 0， 100， 0， 50， 0， 0） T， 最少的剩余料頭為 10m， 但原料使用了 150根。不是最 優(yōu)的。 什么原因？ 第一章 線性規(guī)劃及單純形法 完 演講完畢，謝謝觀看！