管理運(yùn)籌學(xué)01

1、管 理 運(yùn) 籌 學(xué),7號(hào)樓B座215電話：86689923(O)，661199(M)E-mail: prcctv@163.com,人文與管理學(xué)院魏晉才,第二章 線性規(guī)劃的圖解法,§1　問(wèn)題的提出§2　圖解法§3　圖解法的靈敏度分析,線性規(guī)劃的廣泛應(yīng)用是計(jì)算機(jī)時(shí)代的產(chǎn)物。1902年，Julius Farkas 發(fā)表論文，闡述有關(guān)線性規(guī)劃問(wèn)題。1938年，英國(guó)人康德進(jìn)行較詳細(xì)研究。194

2、7年，美國(guó)學(xué)者George Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線性規(guī)劃的推廣奠定了基礎(chǔ)。有人認(rèn)為，求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。,第二章　線性規(guī)劃的圖解法,在管理中一些典型的線性規(guī)劃應(yīng)用合理利用線材問(wèn)題：如何在保證生產(chǎn)的條件下，下料最少配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、

3、物力、財(cái)力等，使獲利最大勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小,線性規(guī)劃的組成：目標(biāo)函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號(hào)來(lái)表示可控制的因素,例1. 某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別

4、生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？,線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400

5、 x2 ≤ 250 x1 , x2 ≥ 0,建模過(guò)程1.理解要解決的問(wèn)題，了解解題的目標(biāo)和條件；2.定義決策變量（ x1 ，x2 ，… ，xn ），每一組值表示一個(gè)方案；3.用決策變量的線性函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表

6、示解決問(wèn)題過(guò)程中必須遵循的約束條件一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （

7、=, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0,§1　問(wèn)題的提出,例

8、1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2

9、≥ 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500,§2　圖 解 法,對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。 下面通過(guò)例1詳細(xì)講解其方法：,§2　圖 解 法,(1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決

10、策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。,§2　圖 解 法,（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。,（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。,§2　圖 解 法,（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行

11、域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。,§2　圖 解 法,重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙ax z=50x1+50x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；無(wú)可行解

12、。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200，則可行域?yàn)榭沼颍淮嬖跐M足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。,§2　圖 解 法,線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：——引入松馳變量（含義是資源的剩余量） 例1 中引入 s1， s2， s3 模型化為 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 約束條件：s.t.

13、 x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2

14、 , s1 , s2 , s3 ≥ 0 對(duì)于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 說(shuō)明：生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。,進(jìn) 一 步 討 論,例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由

15、于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A，B兩種原料，使得購(gòu)進(jìn)成本最低？,進(jìn) 一 步 討 論,解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件：s.t.

16、 x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解800萬(wàn)。,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 +

17、c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……

18、 am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 標(biāo)準(zhǔn)形式(P18)目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + … + cn xn 約束條件：

19、 s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……

20、 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0，bi ≥0,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)

21、形式:,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,1.極小化目標(biāo)函數(shù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即 Max z = - c1x1 - c2x2 - … - cnxn 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即

22、 Min f ＝ - Max z,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,2、約束條件不是等式的問(wèn)題： 設(shè)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引進(jìn)一個(gè)新的變量s ，使它等于約束右邊與左邊之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn )顯然，s 也具有非負(fù)約束，即s≥0， 這時(shí)新的約束條件成為 ai1 x1+

23、ai2 x2+ … +ain xn+s = bi,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,當(dāng)約束條件為 ai1 x1+ai2 x2+ … +ain xn ≥ bi 時(shí)， 類似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn-s = bi,§3　線性規(guī)劃的

24、標(biāo)準(zhǔn)化,為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”；當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。,3.右端項(xiàng)有負(fù)值的問(wèn)題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：-ai1 x1-ai2 x2- … -ain

25、 xn = -bi。,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,例：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式  Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = -9 x1 , x2 , x3

26、 ≥ 0 解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z= -f = -2x1+3x2-4x3 其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量x4，x5 ≥0。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘-1。,§3　線性規(guī)劃的標(biāo)準(zhǔn)化,通過(guò)以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題： Max z = - 2x1 + 3 x2 - 4x3 s

27、.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0*** 變量無(wú)符號(hào)限制的問(wèn)題***： 在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令

28、 xj = xj’- xj” 其中 xj’≥0，xj”≥0 即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然xj的符號(hào)取決于xj’和xj”的大小。,§4　圖解法的靈敏度分析,靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci , aij , bj 變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。(P18)3.1 目標(biāo)函數(shù)中的系數(shù) ci 的靈敏度分析 考慮例

29、1的情況， ci 的變化只影響目標(biāo)函數(shù)等值線的斜率，目標(biāo)函數(shù) z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率為0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率為 -1 )之間時(shí)，原最優(yōu)解 x1 = 50，x2 = 250 仍是最優(yōu)解。一般情況： z = c1 x1 + c2 x2 寫(xiě)成斜截式 x2 = -

30、 (c1 / c2 ) x1 + z / c2 目標(biāo)函數(shù)等值線的斜率為 - (c1 / c2 ) ， 當(dāng) -1 ? - (c1 / c2 ) ? 0 （*） 時(shí)，原最優(yōu)解仍是最優(yōu)解。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,x1,x2,z=20000=50x1+100x2,,,,圖2-2,,,,,z=27500=50x1+100x2,z=0=50x1+100x2,z

31、=10000=50x1+100x2,C,B,A,D,E,,,,§4　圖解法的靈敏度分析,假設(shè)產(chǎn)品Ⅱ的利潤(rùn)100元不變，即 c2 = 100，代到式（*）并整理得 0 ? c1 ? 100 假設(shè)產(chǎn)品Ⅰ的利潤(rùn) 50 元不變，即 c1 = 50 ，代到式（*）并整理得 50 ? c2 ?

32、 + ? 假若產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)均改變，則可直接用式（*）來(lái)判斷。假設(shè)產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)分別為60元、55元，則 - 2 ? - (60 / 55) ? - 1 那么，最優(yōu)解為 z = x1 + x2 和 z = 2 x1 + x2 的交點(diǎn) x1 = 100，x2 = 200 。,§4　圖解法的靈敏度分析,3

33、.2 約束條件中右邊系數(shù) bj 的靈敏度分析 當(dāng)約束條件中右邊系數(shù) bj 變化時(shí)，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。 考慮例1的情況： 假設(shè)設(shè)備臺(tái)時(shí)增加10個(gè)臺(tái)時(shí)，即 b1變化為310，這時(shí)可行域擴(kuò)大，最優(yōu)解為 x2 = 250 和 x1 + x2 = 310 的交點(diǎn) x1 = 60，x2 = 250 。 變化后的總利潤(rùn) - 變化前的總利潤(rùn) =

34、增加的利潤(rùn) (50×60+ 100×250) - (50 × 50+100 × 250) = 500 ，500 / 10 = 50 元 說(shuō)明在一定范圍內(nèi)每增加（減少）1個(gè)臺(tái)時(shí)的設(shè)備能力就可增加（減少）50元利潤(rùn)，稱為該約束條件的對(duì)偶價(jià)格。,§4　圖解法的靈敏度分析,假設(shè)原料 A 增加10 千克時(shí)，即 b2變化為410，這時(shí)可行域擴(kuò)大，但最優(yōu)解仍為 x

35、2 = 250 和 x1 + x2 = 300 的交點(diǎn) x1 = 50，x2 = 250 。此變化對(duì)總利潤(rùn)無(wú)影響，該約束條件的對(duì)偶價(jià)格為 0 。 解釋：原最優(yōu)解沒(méi)有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫(kù)存，而不會(huì)增加利潤(rùn)。 在一定范圍內(nèi)，當(dāng)約束條件右邊常數(shù)增加1個(gè)單位時(shí) （1）若約束條件的對(duì)偶價(jià)格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改善（變好）； （2）若約束條

36、件的對(duì)偶價(jià)格小于0，則其最優(yōu)目標(biāo)函數(shù)值受到影響（變壞）； （3）若約束條件的對(duì)偶價(jià)格等于0，則最優(yōu)目標(biāo)函數(shù)值不變。,作業(yè),P22—24：1、2、3、4、6.某制藥廠用甲、乙兩臺(tái)機(jī)器生產(chǎn)A、B兩種藥物。每種藥物要經(jīng)過(guò)兩道工序，在甲機(jī)器上攪拌，在乙機(jī)器上包裝。已知在未來(lái)兩周內(nèi)，甲乙機(jī)器使用時(shí)間分別不能超過(guò)40和30小時(shí)，生產(chǎn)每公斤A藥物在甲乙機(jī)器上分別所需時(shí)間為2小時(shí)和3小時(shí)，每公斤B藥物所需時(shí)間非別為4小時(shí)和2小時(shí)，如果A、B兩種