運籌學線性規(guī)劃模型與圖解法

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

例1：某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源?，F將有關數據列表如下：

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

資源甲乙資源限量煤電油9445310360200300單位產品價格712

甲乙

資源限量

煤(t)94360

電（kw·h)45200

油（t）310300

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

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

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1,x2,x3,x4

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

方案料型1

2

3

4

52.9米

2.1米

1.5米120100022131203

合計殘料7.47.37.27.16.600.10.20.30.8解：設xj(j=1,2,3,4,5)為采用第j種方案截取的原料根數，z為截取后的余料總米數，則下料問題的線性規(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ī)劃問題的數學模型包含三個組成要素：（1）決策變量：指決策者為實現規(guī)劃目標采取的方案措施，是問題中要確定的未知量。（2）目標函數：指問題要達到的目的要求，表示為決策變量的函數。（3）約束條件：指決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。二、LP模型的一般式

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

簡記為：三、LP模型的矩陣式

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

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

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

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

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

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

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