運(yùn)籌學(xué)線性規(guī)劃模型與圖解法

第２章線性規(guī)劃2.1線性規(guī)劃的模型與圖解法2.2單純形法2.3對(duì)偶問(wèn)題與靈敏度分析2.4運(yùn)輸問(wèn)題2.1線性規(guī)劃的模型與圖解法2.1.1問(wèn)題的引入（１）生產(chǎn)安排問(wèn)題如何合理使用有限的人力、物力和資金，使得收到最好的經(jīng)濟(jì)效益。

例1：某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下：

試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品

資源甲乙資源限量煤電油9445310360200300單位產(chǎn)品價(jià)格712

甲乙

資源限量

煤(t)94360

電（kw·h)45200

油（t）310300

單價(jià)（萬(wàn)元）712解：設(shè)甲乙產(chǎn)品產(chǎn)量分別為x1和x2kg，——決策變量總收入為z萬(wàn)元。則maxz=7x1+12x2——目標(biāo)函數(shù)9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1，x2≥0s.t.——約束條件（２）配料問(wèn)題如何合理地搭配（混合）材料，以最經(jīng)濟(jì)的方式，達(dá)到配比要求。例2：（營(yíng)養(yǎng)配餐問(wèn)題）假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見(jiàn)下表。問(wèn)如何選擇才能在滿(mǎn)足營(yíng)養(yǎng)的前提下使購(gòu)買(mǎi)食品的費(fèi)用最小？各種食物的營(yíng)養(yǎng)成分表解：設(shè)xj(j=1,2,3,4)為第j種食品每天的購(gòu)入量，z為每天購(gòu)買(mǎi)食品的總費(fèi)用，則配餐問(wèn)題的線性規(guī)劃模型為：

minz=14x1+6x2+3x3+2x41000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1,x2,x3,x4

0（3）下料問(wèn)題如何截取原材料，在達(dá)到截取要求的情況下，使廢料最少。例3：料長(zhǎng)7.4米，截成2.9、2.1、1.5米各200根,方案如下表。如何截取余料最少？

方案料型1

2

3

4

52.9米

2.1米

1.5米120100022131203

合計(jì)殘料7.47.37.27.16.600.10.20.30.8解：設(shè)xj(j=1,2,3,4,5)為采用第j種方案截取的原料根數(shù)，z為截取后的余料總米數(shù)，則下料問(wèn)題的線性規(guī)劃模型為：

minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5x1+2x2+x4

2002x3+2x4+x5

2003x1+x2+2x3+3x5

200xj

0(j=1,2,3,4,5)2.1.2線性規(guī)劃的模型一、LP模型的三要素規(guī)劃問(wèn)題的數(shù)學(xué)模型包含三個(gè)組成要素：（1）決策變量：指決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案措施，是問(wèn)題中要確定的未知量。（2）目標(biāo)函數(shù)：指問(wèn)題要達(dá)到的目的要求，表示為決策變量的函數(shù)。（3）約束條件：指決策變量取值時(shí)受到的各種可用資源的限制，表示為含決策變量的等式或不等式。二、LP模型的一般式

一般地，線性規(guī)劃模型：1、決策變量：x1,…,xn2、目標(biāo)函數(shù)：3、約束條件：

簡(jiǎn)記為：三、LP模型的矩陣式

表示為：例如：練習(xí)1：某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取A、B、C、D四種養(yǎng)分。市場(chǎng)上可選擇的飼料有M、N兩種。有關(guān)數(shù)據(jù)如下：試決定買(mǎi)M與N二種飼料各多少公斤而使支出的總費(fèi)用為最少？410售價(jià)

0.40.62.01.7牲畜每日需要量00.10.20.1N0.100.10.2M每公斤含營(yíng)養(yǎng)成分

ABCD飼料2.1.3線性規(guī)劃模型的圖解法（適用于2個(gè)變量的一般型）一、線性規(guī)劃問(wèn)題的解的概念設(shè)線性規(guī)劃問(wèn)題的一般型為（1）可行解：滿(mǎn)足全部約束條件的決策變量X為可行解；

全部可行解的集合R稱(chēng)為可行解域。（2）最優(yōu)解：使目標(biāo)函數(shù)為最大（或最小）的可行解X*。二、線性規(guī)劃的圖解法圖解法步驟：1、根據(jù)約束條件畫(huà)出可行解域；（1）先作非負(fù)約束（2）再作資源限制約束（3）各約束的公共部分即該LP的約束的圖形（可行域）2、畫(huà)出目標(biāo)函數(shù)的等值線；（1）任給z兩個(gè)不同的值，作相應(yīng)兩條直線（2）將目標(biāo)直線向增大的方向移，直至可行域的邊界，

交點(diǎn)X*即最優(yōu)解。3、求出最優(yōu)解。由交點(diǎn)二直線聯(lián)立求解出最優(yōu)解X*的值。x1x209040405030100Dl1l2l3例1用圖解法求解下列線性規(guī)劃問(wèn)題?？尚杏蚰繕?biāo)函數(shù)等值線X*有唯一最優(yōu)解（頂點(diǎn)D）解直線l2,l3組成的線性方程組得：X*=(20,24)T——最優(yōu)生產(chǎn)方案Z*=7×20+12×24=428——最大收入（2）在模型（1）中，目標(biāo)函數(shù)改為

maxz=3x1+10x2，其它不變。

09040405030100Dl1l2l3AX1易知，目標(biāo)函數(shù)等值線與直線l3平行。X2故線段AD上的點(diǎn)均為最優(yōu)解。有無(wú)窮多最優(yōu)解x1x204可行域無(wú)界，在可行域上