運(yùn)籌學(xué)-2線(xiàn)性規(guī)劃2

第二章線(xiàn)性規(guī)劃主講：李英俊工商管理系目錄線(xiàn)性規(guī)劃的數(shù)學(xué)模型1線(xiàn)性規(guī)劃的圖解法2線(xiàn)性規(guī)劃模型的應(yīng)用3練習(xí)4第一節(jié)線(xiàn)性規(guī)劃的數(shù)學(xué)模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型線(xiàn)性規(guī)劃(LinearProgramming,LP)在第二次世界大戰(zhàn)期間從軍事應(yīng)用中發(fā)展起來(lái)，20世紀(jì)中葉最重要的科學(xué)進(jìn)步之一線(xiàn)性規(guī)劃是運(yùn)籌學(xué)中研究最早、理論和算法都最成熟的一個(gè)重要分支（絕大多數(shù)運(yùn)籌學(xué)分支的處理方法都是有線(xiàn)性規(guī)劃演變而來(lái)的），自從1947年美國(guó)學(xué)者Dantzig提出單純形法以來(lái)，大量的研究成果相繼問(wèn)世，線(xiàn)性規(guī)劃被廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、經(jīng)濟(jì)管理等領(lǐng)域。1.線(xiàn)性規(guī)劃的概念一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型線(xiàn)性規(guī)劃的研究對(duì)象是稀缺資源最優(yōu)分配問(wèn)題，即將有限的資源以最優(yōu)(Optimal)方法，分配于相互競(jìng)爭(zhēng)的活動(dòng)之中。一般的體現(xiàn)是：合理使用；效益最高；費(fèi)用最低。研究?jī)?nèi)容是在線(xiàn)性等式（或不等式）的限制條件下，使得某一線(xiàn)性目標(biāo)值取得最大值（或最小值）的問(wèn)題。1.線(xiàn)性規(guī)劃的概念一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型線(xiàn)性指量與量之間按比例、成直線(xiàn)的關(guān)系。如果用數(shù)學(xué)式子表示，線(xiàn)性關(guān)系指自變量x

和因變量y之間可以表示為y=ax+b(a,b都為常數(shù))的形式。不能表示為y=ax+b的式子即為非線(xiàn)性關(guān)系，如二次，三次的曲線(xiàn)函數(shù)（y=ax^2+bx+c）。線(xiàn)性等式或線(xiàn)性不等式：y≥ax+b或

y≤ax+b1.線(xiàn)性規(guī)劃的概念一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型最大值或最小值：Max或

Min1）.函數(shù)的最大值：設(shè)函數(shù)y=f(x)的定義域?yàn)镮，如果存在實(shí)數(shù)M滿(mǎn)足①

對(duì)于任意x∈I,都有f(x)≤M,②存在x'∈I，使得f(x')=M。那么稱(chēng)M是函數(shù)y=f(x)的最大值。1.線(xiàn)性規(guī)劃的概念一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型最大值或最小值：Max或

Min1.線(xiàn)性規(guī)劃的概念Max.Min.一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型：線(xiàn)性規(guī)劃的建模過(guò)程一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型例：營(yíng)養(yǎng)配餐問(wèn)題一個(gè)成年人每天需要從食物中獲得3000kJ熱量、55g蛋白質(zhì)和800mg鈣?，F(xiàn)市場(chǎng)上有4種食品可供選擇，它們每千克所含熱量、營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格如下表。如何選購(gòu)才能在滿(mǎn)足營(yíng)養(yǎng)的前提下使購(gòu)買(mǎi)食品的費(fèi)用最?。?.線(xiàn)性規(guī)劃的模型食品序號(hào)食品名稱(chēng)熱量(kJ/kg)蛋白質(zhì)(g/kg)鈣(mg/kg)價(jià)格(元/kg)1雞肉100050400142雞蛋8006020063大米9002030034白菜200105002每天需要量≥3000≥55≥800？？？一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型例：生產(chǎn)安排問(wèn)題某工廠(chǎng)在計(jì)劃期間內(nèi)要安排I、II兩種產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制如下表所示。工廠(chǎng)每生產(chǎn)1單位產(chǎn)品I可獲利50元，每生產(chǎn)1單位產(chǎn)品II可獲利100元，問(wèn)工廠(chǎng)應(yīng)分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品II才能獲利最多？2.線(xiàn)性規(guī)劃的模型產(chǎn)品I產(chǎn)品II資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型例：生產(chǎn)安排問(wèn)題為了容易理解，我們可以進(jìn)行如下的轉(zhuǎn)化：“設(shè)備”為“資源1”；“原料A”為“資源2”；“原料B”為“資源3”；2.線(xiàn)性規(guī)劃的模型產(chǎn)品I產(chǎn)品II可用數(shù)量資源111300資源221400資源301250一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

2.線(xiàn)性規(guī)劃的模型

一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

3.線(xiàn)性規(guī)劃的一般形式一、線(xiàn)性規(guī)劃的數(shù)學(xué)模型

3.線(xiàn)性規(guī)劃的一般形式第二節(jié)線(xiàn)性規(guī)劃模型的圖解法二、線(xiàn)性規(guī)劃的圖解法

對(duì)于只包含兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，可以用圖解法來(lái)求解。x1x2二、線(xiàn)性規(guī)劃的圖解法例：生產(chǎn)安排問(wèn)題某工廠(chǎng)在計(jì)劃期間內(nèi)要安排I、II兩種產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制如下表所示。工廠(chǎng)每生產(chǎn)1單位產(chǎn)品I可獲利50元，每生產(chǎn)1單位產(chǎn)品II可獲利100元，問(wèn)工廠(chǎng)應(yīng)分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品II才能獲利最多？產(chǎn)品I產(chǎn)品II資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg

二、線(xiàn)性規(guī)劃的圖解法

100300100300X1+X2=300x1x2二、線(xiàn)性規(guī)劃的圖解法

1004001003002X1+X2=400x1x2100100300X2=250x1x2二、線(xiàn)性規(guī)劃的圖解法X1+X2=300100400100300x1x2X2=2502x1+x2=400100400100300x1x2B(50,250)A(0,250)C(100,200)D(200,0)E(0,0)

陰影部分的每一點(diǎn)(包括邊界線(xiàn))都是這個(gè)線(xiàn)性規(guī)劃的可行解，而此公共部分是生產(chǎn)安排問(wèn)題的可行解的集合，稱(chēng)為可行域。二、線(xiàn)性規(guī)劃的圖解法X1+X2=300100400100300x1x2X2=2502x1+x2=400Z=10000=50x1+100x2Z=27500=50x1+100x2BB點(diǎn)為最優(yōu)解，坐標(biāo)為（50，250）Z=0=50x1+100x2二、線(xiàn)性規(guī)劃的圖解法例：生產(chǎn)安排問(wèn)題最佳決策為x1=50,x2=250，此時(shí)z=27500。這說(shuō)明該廠(chǎng)的最優(yōu)生產(chǎn)計(jì)劃方案是生產(chǎn)I產(chǎn)品50單位，生產(chǎn)Ⅱ產(chǎn)品250單位，可得最大利潤(rùn)27500元。把x1=50,x2=250代入約束條件得：

50+250=300臺(tái)時(shí)設(shè)備

2×50+250=350千克原料A，

1×250=250千克原料B．這表明了生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有可使用的設(shè)備臺(tái)時(shí)數(shù)和原料B，但對(duì)原料A來(lái)說(shuō)只消耗了350千克，還有(400—350)=50千克沒(méi)有使用。在線(xiàn)性規(guī)劃中，對(duì)一個(gè)≤約束條件中沒(méi)使用的資源或能力的大小稱(chēng)之為松弛量。

二、線(xiàn)性規(guī)劃的圖解法線(xiàn)性規(guī)劃問(wèn)題的解從上面例子的求解過(guò)程，結(jié)合二維坐標(biāo)圖，可以看到線(xiàn)性規(guī)劃問(wèn)題的求解會(huì)有以下4種情況：(1)在線(xiàn)性規(guī)劃問(wèn)題解的集合中，若約束條件能構(gòu)成一個(gè)封閉的可行域，則可行域中的任意點(diǎn)都是問(wèn)題的一個(gè)可行解，這些可行解中必有最優(yōu)解；若最優(yōu)解是可行域中的一個(gè)點(diǎn)，則稱(chēng)這個(gè)解是線(xiàn)性規(guī)劃的唯一最優(yōu)解。唯一最優(yōu)解必落在可行域的頂點(diǎn)上。100400100300x1x2二、線(xiàn)性規(guī)劃的圖解法

二、線(xiàn)性規(guī)劃的圖解法

二、線(xiàn)性規(guī)劃的圖解法

二、線(xiàn)性規(guī)劃的圖解法課堂練習(xí)（按各自學(xué)號(hào)尾數(shù)做相應(yīng)的題目）P21習(xí)題2(1)-(6)

二、線(xiàn)性規(guī)劃的圖解法練習(xí)1：P21，Q2(1)~(6)Minf＝3.6X1=0.2,X2=0.6本題具有唯一最優(yōu)解。Q2(1)二、線(xiàn)性規(guī)劃的圖解法MaxZ無(wú)可行解。

Q2(2)二、線(xiàn)性規(guī)劃的圖解法MaxZ=有無(wú)界解。Q2(3)二、線(xiàn)性規(guī)劃的圖解法MaxZ無(wú)可行解。Q2(4)二、線(xiàn)性規(guī)劃的圖解法MaxZ=66；X1=4X2=6本題有唯一最優(yōu)解。Q2(5)二、線(xiàn)性規(guī)劃的圖解法Q2(6)MaxZ=30.669X1=6.667X2=2.667本題有唯一最優(yōu)解。第三節(jié)線(xiàn)性規(guī)劃模型的應(yīng)用三、線(xiàn)性規(guī)劃模型的應(yīng)用通過(guò)線(xiàn)性規(guī)劃的圖解法，我們對(duì)線(xiàn)性規(guī)劃的求解及靈敏度分析的基本概念、基本原理已有所了解，又通過(guò)線(xiàn)性規(guī)劃問(wèn)題的計(jì)算機(jī)求解的學(xué)習(xí)，我們掌握了用計(jì)算機(jī)軟件這一有用工具去求解線(xiàn)性規(guī)劃問(wèn)題及其靈敏度分析。在這一節(jié)我們來(lái)研究線(xiàn)性規(guī)劃在工商管理中的應(yīng)用，解決工商管理中的實(shí)際問(wèn)題。三、線(xiàn)性規(guī)劃模型的應(yīng)用線(xiàn)性規(guī)劃應(yīng)用應(yīng)用場(chǎng)景合理利用線(xiàn)材問(wèn)題如何下料使用材料最少配料問(wèn)題在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)投資問(wèn)題從投資項(xiàng)目中選取方案，使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃合理利用人力、物力、財(cái)力等使獲利最大勞動(dòng)力安排用最少的勞動(dòng)力滿(mǎn)足工作需求運(yùn)輸問(wèn)題如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小三、線(xiàn)性規(guī)劃模型的應(yīng)用第一類(lèi)問(wèn)題人力資源分配三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題例1：某晝夜服務(wù)的公交線(xiàn)路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時(shí)間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開(kāi)始時(shí)上班，并連續(xù)工作8小時(shí)，問(wèn)該公交線(xiàn)路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿(mǎn)足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題解：48喂！請(qǐng)問(wèn)數(shù)學(xué)模型？三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題設(shè)xi表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù)，可以知道在第i班工作的人數(shù)應(yīng)包括第i-1班次時(shí)開(kāi)始上班的人員數(shù)和第i班次時(shí)開(kāi)始上班的人員數(shù)，例如有x1+x2≥70。又要求這六個(gè)班次時(shí)開(kāi)始上班的所有人員最少，即要求x1+x2+x3+x4+x5+x6最小，這樣我們建立如下的數(shù)學(xué)模型：目標(biāo)函數(shù)：minx1+x2+x3+x4+x5+x6約束條件：x1+x6≥60，x1+x2≥70，

x2+x3≥60，x3+x4≥50，

x4+x5≥20，x5+x6≥30，

x1,x2,x3,x4,x5,x6≥0三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題用“管理運(yùn)籌學(xué)”軟件可以求得此問(wèn)題的解：

x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，

24小時(shí)內(nèi)一共需要司機(jī)和乘務(wù)人員150人。此問(wèn)題的解不唯一，用LINDO軟件計(jì)算得到：X1=60,X2=10,X3=50,X4=0,X5=30,X6=0目標(biāo)函數(shù)值=150三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題例2：福安商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下所示：星期一：15人；星期二：24人；星期三：25人；星期四：19人；星期五：31人；星期六：28人；星期日：28人。為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問(wèn)應(yīng)該如何安排售貨人員的作息，既滿(mǎn)足了工作需要，又使配備的售貨人員的人數(shù)最少?三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題解：52喂！請(qǐng)問(wèn)數(shù)學(xué)模型？三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題

解：設(shè)x1為星期一開(kāi)始休息的人數(shù)，x2為星期二開(kāi)始休息的人數(shù)，…，x7為星期日開(kāi)始休息的人數(shù)。目標(biāo)是要求售貨人員的總數(shù)最少。因?yàn)槊總€(gè)售貨員都工作五天，休息兩天，所以只要計(jì)算出連續(xù)休息兩天的售貨員人數(shù)，也就計(jì)算出了售貨員的總數(shù)。把連續(xù)休息兩天的售貨員按照開(kāi)始休息的時(shí)間分成7類(lèi)，各類(lèi)的人數(shù)分別為X1，X2，…X7，即有目標(biāo)函數(shù):minX1+X2+X3+X4+X5+X6+X7三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題

解：設(shè)x1為星期一開(kāi)始休息的人數(shù)，x2為星期二開(kāi)始休息的人數(shù)，…，x7為星期日開(kāi)始休息的人數(shù)周一周二周三周四周五周六周日x1××√√√√√x2√××√√√√x3√√××√√√x4√√√××√√x5√√√√××√x6√√√√√××x7×√√√√√×≥15≥24≥25≥19≥31≥28≥28三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題再按照每天所需售貨員的人數(shù)寫(xiě)出約束條件，例如星期日需要28人，我們知道商場(chǎng)中的全體售貨員中除了星期六開(kāi)始休息和星期日開(kāi)始休息的人外都應(yīng)該上班，即有x1+x2+x3+x4+x5≥28三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題上機(jī)求解得：x1=12,x2=0,x3=11,x4=5,x5=0,x6=8,x7=0,目標(biāo)函數(shù)最小值=36.

也就是說(shuō)配備36個(gè)售貨員，并安排12人休息星期一、二；安排11人休息星期三、四；安排5人休息星期四、五；安排8人休息星期六、日。這樣的安排既滿(mǎn)足了工作需要，又使配備的售貨員最少。三、線(xiàn)性規(guī)劃模型的應(yīng)用人力資源分配問(wèn)題注意：

實(shí)際中，服務(wù)行業(yè)企業(yè)一周內(nèi)對(duì)人力資源的需求往往像例2所描述的方式變化，而每天各時(shí)間段的需求又像例1所描述的那樣變化。我們只要用例1的方法，分別求出周一到周六、日每天的人員需求，再用例2的方法，即可求出該公司的最小編制。二、線(xiàn)性規(guī)劃的圖解法練習(xí)2：P59，Q2解題如下：(1)臨時(shí)工的工作時(shí)間為4小時(shí)，正式工的工作時(shí)間也是4小時(shí)，則第五個(gè)小時(shí)需要新招人員，臨時(shí)工只要招用，無(wú)論工作多長(zhǎng)時(shí)間，都按照4小時(shí)給予工資。每位臨時(shí)工招用以后，就需要支付16元工資。從上午11時(shí)到晚上10時(shí)共計(jì)11個(gè)班次，則設(shè)Xi(i=1,2,…,11)個(gè)班次招用的臨時(shí)工數(shù)量，如下為最小成本：minf＝16（X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11)二、線(xiàn)性規(guī)劃的圖解法(1)兩位正式工一個(gè)在11－15點(diǎn)上班，在15－16點(diǎn)休息，然后在16－20點(diǎn)上班。另外一個(gè)在13－17點(diǎn)上班，在17－18點(diǎn)休息，18－22點(diǎn)上班。則各項(xiàng)約束條件如下：X1+1>=9X1+X2+1>=9X1+X2+X3+2>=9X1+X2+X3+X4+2>=3X2+X3+X4+X5+1>=3X3+X4+X5+X6+2>=3X4+X5+X6+X7+1>=6X5+X6+X7+X8+2>=12X6+X7+X8+X9+2>=12X7+X8+X9+X10+1>=7X8+X9+X10+X11+1>=7Xi>=0(i＝1,2,…,11)二、線(xiàn)性規(guī)劃的圖解法(1)運(yùn)用計(jì)算機(jī)解題，結(jié)果輸出如下;這時(shí)候臨時(shí)工的安排為：變量

班次

臨時(shí)工班次

時(shí)間

-----------------------

x1811：00－12：00

x2012：00－13：00

x3113：00－14：00

x4014：00－15：00

x5115：00－16：00

x6416：00－17：00

x7017：00－18：00

x8618：00－19：00

x9019：00－20：00

x10020：00－21：00

x11021：00－22：00

目標(biāo)函數(shù)最優(yōu)值為

:320

變量

最優(yōu)解

相差值

-----------------------

x180

x200

x310

x400

x510

x640

x700

x860

x900

x1001

x1101二、線(xiàn)性規(guī)劃的圖解法(2)從輸出結(jié)果看出：在11：00－12：00安排8個(gè)臨時(shí)工的班次在14：00－15：00的剩余變量為8，因?yàn)榕R時(shí)工的工作時(shí)間為4小時(shí)，而實(shí)際工作僅需要3小時(shí)。在13：00－14：00招用的臨時(shí)工，剩余變量為2，在16：00－17：00招用的臨時(shí)工，剩余變量為5。都是因?yàn)閷?shí)際工作要求達(dá)不到4小時(shí)。這部分費(fèi)用為4小時(shí)工作時(shí)長(zhǎng)不合理多支出的成本。因此建議安排3小時(shí)工作時(shí)長(zhǎng)的臨時(shí)工，可以是成本更小。二、線(xiàn)性規(guī)劃的圖解法(3)根據(jù)題意，在滿(mǎn)足工作需要的條件下，可以安排3小時(shí)或者4小時(shí)的臨時(shí)工，工資仍然為4元/小時(shí)。則這時(shí)候確定安排為4小時(shí)的臨時(shí)工工資為16元，安排為3小時(shí)的為12元，設(shè)每個(gè)班次安排的4小時(shí)臨時(shí)工為Xi，3小時(shí)臨時(shí)工為Yi，（i＝1，2，…,11)，則成本最?。篗inf＝16（X1+X2+…+X11)+12(Y1+Y2+…+Y11)二、線(xiàn)性規(guī)劃的圖解法(3)列出約束條件如下：X1+Y1+1>=9X1+X2+Y1+Y2+1>=9X1+X2+X3+Y1+Y2+Y3+2>=9X1+X2+X3+X4+Y2+Y3+Y4+2>=3X2+X3+X4+X5+Y3+Y4+Y5+1>=3X3+X4+X5+X6+Y4+Y5+Y6+2>=3X4+X5+X6+X7+Y5+Y6+Y7+1>=6X5+X6+X7+X8+Y6+Y7+Y8+2>=12X6+X7+X8+X9+Y7+Y8+Y9+2>=12X7+X8+X9+X10+Y8+Y9+Y10+1>=7X8+X9+X10+X11+Y9+Y10+X11+1>=7Xi>=0,Yi>=0(i＝1,2,…,11)二、線(xiàn)性規(guī)劃的圖解法(3)計(jì)算結(jié)果為：

目標(biāo)函數(shù)最優(yōu)值為

:264變量

最優(yōu)解

相差值

-----------------------

x104

x204

x304

x404

x500

x604

x704

x860

x904

x10012x11012x1280x1308x1410x1500x1610x1708x1840x1900x2000x2108x2208即最小成本為264元，比（1）節(jié)省56元。需要安排20個(gè)班次。即：4小時(shí)臨時(shí)工安排6個(gè)班次：X8=6；3小時(shí)臨時(shí)工16個(gè)班次：Y1(X12)=8，Y3(X14)=1，Y5(X16)=1，Y7(X18)=4。三、線(xiàn)性規(guī)劃模型的應(yīng)用第二類(lèi)問(wèn)題生產(chǎn)計(jì)劃三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題例：明興公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問(wèn)題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過(guò)鑄造、機(jī)械加工和裝配三道工序。甲、乙兩種產(chǎn)品的鑄件工序可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠(chǎng)鑄造才能保證質(zhì)量。甲乙丙資源限制每件鑄造工時(shí)(小時(shí))51078000每件機(jī)械加工工時(shí)(小時(shí))64812000

每件裝配工時(shí)（小時(shí))32210000

自產(chǎn)鑄件每件成本(元)354外包鑄件每件成本(元)56—

機(jī)械加工每件成本(元)213

裝配每件成本(元)322每件產(chǎn)品售價(jià)(元)231816公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件?甲、乙兩種產(chǎn)品的鑄造應(yīng)多少由本公司鑄造?應(yīng)多少由外包協(xié)作？三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題解：設(shè)x1、x2、x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，設(shè)x4、x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)

工時(shí)與成本甲乙丙每件鑄造工時(shí)(小時(shí))5107每件機(jī)加工工時(shí)(小時(shí))648

每件裝配工時(shí)（小時(shí))322

自產(chǎn)鑄件每件成本(元)354外協(xié)鑄件每件成本(元)56

機(jī)加工每件成本(元)213

裝配每件成本(元)322每件產(chǎn)品售價(jià)(元)231816計(jì)算每件產(chǎn)品的利潤(rùn)分別如下：三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品甲全部自制的利潤(rùn)=23-(3+2+3)=15(元)產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)=23-(5+2+3)=13(元)產(chǎn)品乙全部自制的利潤(rùn)=18-(5+1+2)=10(元)產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)=18-(6+1+2)=9(元)產(chǎn)品丙的利潤(rùn)=16-(4+3+2)=7(元)

工時(shí)與成本甲乙丙每件鑄造工時(shí)(小時(shí))5107每件機(jī)加工工時(shí)(小時(shí))648

每件裝配工時(shí)（小時(shí))322

自產(chǎn)鑄件每件成本(元)354外協(xié)鑄件每件成本(元)56

機(jī)加工每件成本(元)213

裝配每件成本(元)322每件產(chǎn)品售價(jià)(元)231816三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品自制(鑄造)自制(鑄造)外包外包自制(鑄造)機(jī)械加工裝配機(jī)械加工裝配機(jī)械加工裝配鑄造：8000h可用資源加工：12000h裝配：10000hx1x2x3x4x55x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題建立數(shù)學(xué)模型如下：目標(biāo)函數(shù)：max15X1+10X2+7X3+13X4+9X5

約束條件：

5X1+10X2+7X3≤8000(這里沒(méi)包括外協(xié)鑄造時(shí)間)，

6X1+4X2+8X3+6X4+4X5≤12000(機(jī)加工)，

3X1+2X2+2X3+3X4+2X5≤10000(裝配)，

X1，X2，X3，X4，X5≥0用“管理運(yùn)籌學(xué)”軟件進(jìn)行計(jì)算，計(jì)算機(jī)計(jì)算結(jié)果顯示如下……

工時(shí)與成本甲乙丙每件鑄造工時(shí)(小時(shí))5107每件機(jī)加工工時(shí)(小時(shí))648

每件裝配工時(shí)（小時(shí))322三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題從相差值一欄中可知，如果全部由自己生產(chǎn)的乙產(chǎn)品的利潤(rùn)再增加2元達(dá)到每件12元利潤(rùn)，那么全部自制的乙產(chǎn)品才有可能上馬生產(chǎn)，否則乙產(chǎn)品還是鑄造外協(xié)、其余自制的利潤(rùn)更大。同樣丙產(chǎn)品的利潤(rùn)要再增加13.1元達(dá)到每件利潤(rùn)20.1元，丙產(chǎn)品才有可能上馬生產(chǎn)；鑄造外協(xié)、其余自制的甲產(chǎn)品利潤(rùn)再增加0.5元達(dá)到13.5元，才有可能上馬生產(chǎn)。目標(biāo)函數(shù)最優(yōu)值為：29400

變量最優(yōu)解相差值

x116000x202x3013.1x400.5x56000結(jié)果分析：最大的利潤(rùn)為29400元，其最優(yōu)的生產(chǎn)計(jì)劃為全部由自己生產(chǎn)的甲產(chǎn)品1600件，鑄造外協(xié)、其余自制生產(chǎn)乙產(chǎn)品600件，而丙產(chǎn)品不生產(chǎn)。三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品自制(鑄造)自制(鑄造)外包外包自制(鑄造)機(jī)械加工裝配機(jī)械加工裝配機(jī)械加工裝配鑄造：8000h可用資源加工：12000h裝配：10000hx3=0x4=0x5=600x2=0x1=1600三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題某廠(chǎng)生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠(chǎng)獲利最大。三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III工序2工序1產(chǎn)品三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。工序2工序1產(chǎn)品5x1117x1126x1214x1227x123三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。工序2工序1產(chǎn)品5x111+10x2116x121+8x2214x1227x1237x112+9x212三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1資源：6000設(shè)備B1設(shè)備A2資源：10000設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III設(shè)備A1：5x111+10x211≤60005x111+10x2116x121+8x2217x112+9x212+12x3127x1234x122+11x322設(shè)備A2：7x112+9x212+12x312≤10000設(shè)備B1：6x121+8x221≤4000設(shè)備B2：4x122+11x322≤7000設(shè)備B3：7x123≤4000三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III工序2工序1產(chǎn)品x111x112x121x122x123產(chǎn)品I：x111+x112=x121+x122+x123三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III工序2工序1產(chǎn)品產(chǎn)品I：x111+x112=x121+x122+x123產(chǎn)品II：x211+x212=x221x111x112x121x122x123x211x212x221x312x322產(chǎn)品III：x312=x323三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：代入數(shù)據(jù)整理得到：三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題因此該規(guī)劃問(wèn)題的模型為：三、線(xiàn)性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品I設(shè)備A1設(shè)備B1設(shè)備A2設(shè)備B2設(shè)備B3產(chǎn)品II產(chǎn)品III工序2工序1產(chǎn)品50023057108590500324324Q:你能知道產(chǎn)品I在設(shè)備B2生產(chǎn)的859個(gè)來(lái)自于設(shè)備A1還是A2嗎？1200三、線(xiàn)性規(guī)劃模型的應(yīng)用第三類(lèi)問(wèn)題套裁下料三、線(xiàn)性規(guī)劃模型的應(yīng)用套裁下料問(wèn)題某工廠(chǎng)要做100套鋼架，每套鋼架需要長(zhǎng)度分別為2.9m，2.1m，1.5m的圓鋼各一根，已知原料每根長(zhǎng)7.4m。問(wèn)應(yīng)如何下料，可使所用原料最省？原料2.9m2.1m1.5m料頭0.9m2.9m2.9m1.5m料頭0.1m2.1m2.1m2.1m料頭1.1m1.5m1.5m1.5m1.5m料頭1.4m三、線(xiàn)性規(guī)劃模型的應(yīng)用套裁下料問(wèn)題解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿(mǎn)足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出以下可能的下料方案以供套裁用。三、線(xiàn)性規(guī)劃模型的應(yīng)用套裁下料問(wèn)題設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ、V、VI、VII、VIII下料的原材料根數(shù)分別為xj(j=1,……,8)，可列出下面的數(shù)學(xué)模型：三、線(xiàn)性規(guī)劃模型的應(yīng)用套裁下料問(wèn)題方案長(zhǎng)度IIIIIIIVVVIVIIVIII需求2.9120101001002.1002211301001.531203104100合計(jì)/m7.47.37.27.16.66.56.36.0料頭/m00.10.20.30.80.91.11.4根數(shù)x1x2x3x4x5x6x7x8三、線(xiàn)性規(guī)劃模型的應(yīng)用套裁下料問(wèn)題結(jié)果長(zhǎng)度IIIIIIIVVVIVIIVIII需求2.9120101001002.1002211301001.531203104100合計(jì)/m7.47.37.27.16.66.56.36.0料頭/m00.10.20.30.80.91.11.4根數(shù)30100500000共90三、線(xiàn)性規(guī)劃模型的應(yīng)用第四類(lèi)問(wèn)題配料問(wèn)題三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：?jiǎn)杻煞N食物各食用多少，才能既滿(mǎn)足需要、又使總費(fèi)用最省？三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題解：設(shè)Xj表示Bj

種食物用量三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題某工廠(chǎng)要用三種原料1，2，3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，已知產(chǎn)品的規(guī)格要求、產(chǎn)品的單價(jià)、每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)，見(jiàn)下表。該廠(chǎng)應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大?

產(chǎn)品名稱(chēng)

規(guī)格要求

單價(jià)(元／千克)

甲

原材料1不少于50％，原材料2不超過(guò)25％50

乙原材料1不少于25％，原材料2不超過(guò)50％35丙

不限25三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題解：設(shè)xij表示第i種產(chǎn)品中原材料j的含量(分別用產(chǎn)品1，2，3表示產(chǎn)品甲、乙、丙)。例如x23就表示乙產(chǎn)品中第3種原材料的含量，目標(biāo)是使利潤(rùn)最大，利潤(rùn)的計(jì)算公式如下：

原材料名稱(chēng)

每天最多供應(yīng)量

單價(jià)（元/千克）11006521002536035三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題

X11≥0.5(X11+X12+X13)，(甲中原料1占甲產(chǎn)品數(shù)量不少于50%.)X12≤0.25(X11+X12+X13)X21≥0.25(X21+X22+X23)X22≥0.5(X21+X22+X23)

X11+X21+X31≤100X12+X22+X32≤100X13+X23+X33≤60三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題整理后得到問(wèn)題模型如下：

VARIABLEVALUEREDUCEDCOSTX11100.0000000.000000X1250.0000000.000000X1350.0000000.000000X210.00000015.000000X220.0000000.000000X310.00000045.000000X330.00000010.000000X230.0000000.000000X320.0000000.000000三、線(xiàn)性規(guī)劃模型的應(yīng)用配料問(wèn)題解為：x11=100，x12=50,x13=50，其余的xij=0

，也就是說(shuō)每天只生產(chǎn)甲產(chǎn)品200千克，分別需要用1原料100千克，2原料50千克，3原料50千克。其它乙、丙產(chǎn)品不生產(chǎn)。目標(biāo)函數(shù)值=500元三、線(xiàn)性規(guī)劃模型的應(yīng)用第五類(lèi)問(wèn)題投資問(wèn)題三、線(xiàn)性規(guī)劃模型的應(yīng)用投資問(wèn)題某部門(mén)現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資，已知項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110％。項(xiàng)目B：從第一年到第三年每年年初都可以投資，次年末回收本利125％，但規(guī)定每年最大投資額不能超過(guò)30萬(wàn)元。項(xiàng)目C：第三年初需要投資，到第五年末能回收本利140％，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元。項(xiàng)目D：第二年初需要投資，到第五年未能回收本利155％，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元。三、線(xiàn)性規(guī)劃模型的應(yīng)用投資問(wèn)題據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如下所示：?jiǎn)枺海?）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年末擁有資金的本利金額為最大?（2）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年末擁有資金的本利在330萬(wàn)的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最小?項(xiàng)目風(fēng)險(xiǎn)指數(shù)（每萬(wàn)元每次）A