1、線性規(guī)劃的計算機求解,Excel 是分析和求解線性規(guī)劃問題一個很好的工具，它不僅可以很方便地將線性規(guī)劃模型所有的參數(shù)錄入電子表格，而且可以利用規(guī)劃求解工具迅速找到模型的解。最重要的是，在解好的模型中，任何參數(shù)的改變都可以立即反映到模型的解中，在不重新應(yīng)用求解工具的情況下就可以知道許多信息，當(dāng)然，即使重新求解也只是點一下鼠標(biāo)就可以了,線性規(guī)劃的計算機求解,作為office家族的一員，Excel的普及性和易學(xué)性也會讓讀者感到利用計算機求解線性規(guī)劃十分容易。當(dāng)然，除Excel外還有很多求解線性規(guī)劃的計算機軟件，但Excel強大的功能、普及性和易學(xué)性足以滿足學(xué)習(xí)運籌學(xué)的讀者理解線性規(guī)劃的計算機求解方法

2、、幫助讀者們學(xué)習(xí)解決線性規(guī)劃問題的要求。,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,線性規(guī)劃的計算機求解,農(nóng)場灌溉問題,某公司有四個農(nóng)場，每個農(nóng)場的耕地作物需要用水灌溉，因灌溉條件限制，農(nóng)場的最大水資源供應(yīng)量有一定限制，各農(nóng)場的總耕地面積與最大水資源供應(yīng)量如表3-1所示。該地區(qū)種植的作物有棉花、玉米和高粱，三種農(nóng)作物每種作物每單位種植面積的凈收入和耗水量以及每種作物最大允許種植面積如表3-2所示。由于水資源短，公司規(guī)定每個農(nóng)場受灌溉面積占農(nóng)場總耕地面積的比例相同

3、，公司決策問題還是如何確定各農(nóng)場種植各種作物的面積，使得公司總收入最大。,例1. 農(nóng)場灌溉問題,例1. 農(nóng)場灌溉問題,我們首先建立此問題的線性規(guī)劃模型。由于此問題是決定四個農(nóng)場中每個農(nóng)場種植三種農(nóng)作物的面積，我們引入決策變量xij（i = 1，2，3，4；j = 1，2，3）表示第i個農(nóng)場種植第j種作物的面積，目標(biāo)是使總收入 Z = 800( x11 + x21 + x31 + x41) + 600(x12 + x22 + x32 + x42 ) + 450(x13 + x23 + x33 + x43)最大化,例1. 農(nóng)場灌溉問題,滿足下列約束條件： 1). 農(nóng)場的耕地面積約束 x11 + x

4、12 + x13 4000 (農(nóng)場1) x21 + x22 + x23 6000 (農(nóng)場2) x31 + x32 + x33 5000 (農(nóng)場3) x41 + x42 + x43 4500 (農(nóng)場4),例1. 農(nóng)場灌溉問題,2). 農(nóng)場最大供水量約束 2x11 + 1.5x12 + x13 6000 (農(nóng)場1) 2x21 + 1.5x22 + x23 9000 (農(nóng)場2) 2x31 + 1.5x32 + x33 5500 (農(nóng)場3) 2x41 + 1.5x42 + x43 5000 (農(nóng)場4),例1. 農(nóng)場灌溉問題,3)農(nóng)作物的種植面積約束 x11 + x21 + x31 + x41 6000

5、 （農(nóng)作物1，棉花） x12 + x22 + x32 + x42 5500 （農(nóng)作物2，玉米） x13 + x23 + x33 + x43 5000 （農(nóng)作物3，高粱） 即各農(nóng)作物種植面積不超過最大允許種植面積。,例1. 農(nóng)場灌溉問題,4)種植作物面積占總耕地面積比例約束 即各農(nóng)場種植作物面積（灌溉面積）占總耕地面積的比例相同。 5) 決策變量的非負約束 xij 0， i = 1，2，3，4；j = 1，2，3。,例1. 農(nóng)場灌溉問題,例2. 證券投資問題,一證券投資者將1000萬元資金用于證券投資，已知各種證券（A、B、C、D、E、F）的評級、到期年限、每年稅后收益如表所示。管理層對該投資者

6、提出下列要求： 國債投資額不能少于300萬元； 投資證券的平均評級不超過1.5； 投資證券的平均到期年限不超過5年。 問：每種證券投資多少可以使得稅后收益最大？,例2. 證券投資問題,例2. 證券投資問題,引入決策變量xA、xB、xC、xD、xE、xF分別表示證券A、B、C、D、E、F的投資金額（單位：萬元），相應(yīng)的目標(biāo)函數(shù)（稅后收益）為： Z = 90.043xA + 120.044xB + 50.032xC + 40.03xD + 30.032xE + 40.045xF 約束條件為： 資金總額約束： xA + xB + xC + xD + xE + xF 1000 國債投資額約束： xC

7、+ xD 300,例2. 證券投資問題,證券平均評級約束： 這是一個非線性約束，容易轉(zhuǎn)化為以下線性約束： 0.5xA + 0.5xB 0.5xC 0.5xD + 2.5xE + 3.5xF 0 證券平均到期年限約束： 它等價于線性約束： 4xA + 7xB xD 2xE xF 0 非負約束: xA 0，xB 0， xC 0， xD 0， xE 0 xF 0,例2. 證券投資問題,例3. 話務(wù)員排班問題,某尋呼公司雇用了多名話務(wù)員工作，他們每天工作3節(jié)，每節(jié)3小時，每節(jié)開始時間為午夜、凌晨3點鐘、凌晨6點鐘，上午9點、中午12點、下午3點、6點、9點，為方便話務(wù)員上下班，管理層安排每位話務(wù)員每天

8、連續(xù)工作3節(jié)，根據(jù)調(diào)查，對于不同的時間，由于業(yè)務(wù)量不同，需要的話務(wù)員的人數(shù)也不相同，公司付的薪水也不相同，有關(guān)數(shù)據(jù)見表。,例3. 話務(wù)員排班問題,問：如何安排話務(wù)員才能保證服務(wù)人數(shù)，又使總成本最低？,例3. 話務(wù)員排班問題,解：這個問題實際上是一個成本效益平衡問題。管理層在向客戶提供滿意服務(wù)水平的同時要控制成本，因此必須尋找成本與效益的平衡。由于每節(jié)工作時間為3小時，一天被分為8班，每人連續(xù)工作3節(jié)，各班時間安排如下表：,例3. 話務(wù)員排班問題,例3. 話務(wù)員排班問題,為了建立數(shù)學(xué)模型，對應(yīng)于一般成本效益平衡問題，我們首先必須明確包含的活動數(shù)目，活動一個單位是對應(yīng)于分派一個話務(wù)員到該班次收，效

9、益的水平對應(yīng)于時段。收益水平就是該時段里上下班的話務(wù)員數(shù)目，各活動的單位效益貢獻就是在該時間內(nèi)增加的在崗位話務(wù)員數(shù)目。我們給出下列成本效益平衡問題參數(shù)表：,例3. 話務(wù)員排班問題,例3. 話務(wù)員排班問題,決策變量Xi表示分派到第班的話務(wù)員人數(shù)（i= 1，2，3，4，5，6，7，8），約束條件為： 0-3時間段： 3-6時間段： 6-9時間段： 9-12時間段： 12-15時間段：,例3. 話務(wù)員排班問題,15-18時間段： 18-21時間段： 21-0時間段： 非負約束： 目標(biāo)函數(shù)為最小化成本：,例3. 話務(wù)員排班問題,例4.多階段生產(chǎn)安排問題,南方機電制造公司為全國各地生產(chǎn)一種大型機電設(shè)備，

10、按照公司的訂單合同，不久要交付使用一定數(shù)量的機電設(shè)備，所以有必要制定為期6個月的設(shè)備生產(chǎn)計劃。根據(jù)合同，公司必須在未來6個月中每個月底交付一定數(shù)量的機電設(shè)備，由于原料價格、生產(chǎn)條件、保修和維修工作等安排不同，每月的生產(chǎn)能力和生產(chǎn)成本也不同，當(dāng)然，可以在成本較低的月份多生產(chǎn)一些設(shè)備，但在供給客戶之前必須存放，需要付一定的存貯費用。管理層需要制定出一個逐月生產(chǎn)計劃，使生產(chǎn)和存貯的總成本達到最小。,例4.多階段生產(chǎn)安排問題,管理科學(xué)小組通過調(diào)查收集到每單位生產(chǎn)成本、每月單位存貯費、每月需求量、最大生產(chǎn)能力等數(shù)據(jù)（見表)。,例4.多階段生產(chǎn)安排問題,解：管理層需要作出的決策是每個月生產(chǎn)多少臺設(shè)備，因此

11、我們引入決策變量 xj表示第個月生產(chǎn)機電設(shè)備的臺數(shù)（j= 1，2，3，4，5，6）。為了建立此問題的一般數(shù)學(xué)模型，我們用dj表示第j月的需求量；用lj表示第j月的最大生產(chǎn)能力；用cj表示第j月的單位生產(chǎn)成本；用hj表示第j月的單位存貯成本；用fj表示第j月的最大存貯量。,例4.多階段生產(chǎn)安排問題,由最大生產(chǎn)能力限制，我們?nèi)菀椎玫郊s束： xj lj , j= 1，2，3，4，5，6 用Ij表示第月底的庫存量（j= 1，2，3，4，5，6），由最大存貯量約束，我們有： Ij fj , j= 1，2，3，4，5，6 各個月份之間生產(chǎn)量、需求量和存貯量之間的關(guān)系可由下圖（圖2-15）表示：,例4.多階

12、段生產(chǎn)安排問題,容易得到下列約束：,例4.多階段生產(chǎn)安排問題,另外有非負約束： xj 0, Ij 0， j= 1，2，3，4，5，6 目標(biāo)為總成本 最小化:,例4.多階段生產(chǎn)安排問題,例5.下料問題,某工廠要做100套鋼架，每套用長為2.9 m, 2.1m, 1.5m的圓鋼各一根。已知原料每根長7.4 m，問：應(yīng)如何下料，可使所用原料最?。?解:考慮下列各種下料方案（按一種邏輯順序給出）,把各種下料方案按剩余料頭從小到大順序列出,假設(shè) x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min z=x1 + x2 + x3 + x4 +

13、 x5 約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3+ 3x5 100 x1,x2,x3,x4,x5 0,模型1,假設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上面前 8種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min z = 0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8 約束條件： s.t. 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x6+ x7 100 x1 +x3+3x4 +2x6+3x7+4x8 100 x1,x2,x

14、3,x4,x5,x6,x7,x8 0，整數(shù),模型2,假設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上面前 8種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min z = x1+x2+x3+x5+x6+x7+x8 約束條件： s.t. 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x6+ x7 100 x1 +x3+3x4 +2x6+3x7+4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 0，整數(shù),模型3,例6醫(yī)藥公司的中草藥配方問題,安康醫(yī)藥公司考慮配制一種中成藥; 市場上有八種中草藥材包含該中成藥所需要的特定成份, 公司準(zhǔn)備采購一些

15、中草藥來配制這種中成藥，要求配制后的中成藥所包含三種特定成份(不妨設(shè)為成份A、成份B和成份C)分別為39、36、38。由于每種中草藥材包含的成份不同, 采購成本也不同; 公司管理層希望以最低的成本來完成中成藥的配制;,各個中草藥材(每單位)包含的三種成份含量及單位采購成本,數(shù)學(xué)建模,決策變量Xi表示第種草藥在中成藥中的使用量（i= 1，2，3，4，5，6, 7, 8）。為了使成本最低我們有: 目標(biāo)函數(shù) Z=10 x1+8x2+16x3+11x4+15x5+10 x6+9x7+12x8 求極小化,約束條件,2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8 =39 3x1+3x2+2

16、x3+2x4+4x5+2x6+2x7+3x8 =36 4x1+3x2+3x3+3x4+4x5+3x6+x7+2x8 =38 Xi 0 , i=1,2,3.8.,安康醫(yī)藥公司的中草藥配方問題的Excel規(guī)劃求解,討論:為什么8種中草藥,最優(yōu)方案只選了三種呢?(草藥1,草藥2和草藥7),事實上, 由于這個問題只有三個函數(shù)約束(成份A、成份B和成份C), 三個等式約束看作一個線性方程組: 2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8 =39 3x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8 =36 4x1+3x2+3x3+3x4+4x5+3x6+x7+2x8 =38,

17、討論:為什么8種中草藥,最優(yōu)方案只選了三種呢?,若將第i種草藥三種成份含量看作一個三維向量Pi則: 由線性代數(shù)知識我們知道向量組P1,P2,P7 線性無關(guān)且構(gòu)成三維向量空間的一個極大無關(guān)組; 任何一個三維向量P可由 的線性組合來表示出來, 即: 存在唯一的一組數(shù),k1,k2,k3, 使得: P=k1P1+k2P2+k3P3,討論,例如: 對于第5種草藥三種成份含量, 可以表示為一個三維向量P5 ,討論,這就意味著一個單位的第5種草藥, 其成份等價于0.5個單位的第1種草藥 + 0.5個單位的第2種草藥 + 0.5個單位的第7種草藥; 即:一個單位的第5種草藥, 可由0.5個單位的第1種草藥,

18、0.5個單位的第2種草藥 和0.5個單位的第7種草藥組合而成; 由于這種組合的成本為0.5X10+0.5X8+0.5X9=13.5 元, 低于第5種草藥的單位成本(15元);因此, 從成本最低的角度出發(fā)中成藥的最優(yōu)方案中不會選用第5種草藥.,討論,由于此問題的約束條件個數(shù)為3, 方程組每個變量系數(shù)向量的維數(shù)為3, 因而, 極大無關(guān)組包含向量的個數(shù)一定是3個; 不管有多少候選草藥, 最終只需要選3種, 其它草藥的成份都可以由這三種“組合”而成. 在方程組中，只要選定了哪三種，意味著同時確定了其余的均不在選擇之列,討論,令沒有入選的其余5種草藥在中成藥中的數(shù)量為零，即: x3=x4=x5=x6=x8=0 此時方程組變?yōu)橹缓齻€變量的方程組: 2x1+5x2+3x7=39 3x1+3x2+2x7=36 4x1+3x2+x7=38,討論,可以求解得到其唯一解: X1=6.5, x2=2.5,x7=4.5. 這就是我們的最優(yōu)配方 . 因此, 只要我們能確定是哪三種中草藥入圍最優(yōu)配方, 通過解一個方程組就可以得到最優(yōu)方案了. 但是, 我們有8種