運籌學ABC-2線性規(guī)劃建模課

線性規(guī)劃在經濟管理中的應用——線性規(guī)劃建模應用1：生產計劃問題問題1試列出下述產品規(guī)劃問題的線性規(guī)劃模型：某工廠生產A、B、C三種產品，每噸利潤分別為2000元、3000元、1000元；生產單位產品所需的工時及原材料如表所示。若供應的原材料每天不超過3噸，所能利用的勞動力日總工時是固定的，問如何制定日生產計劃，使三種產品總利潤最大？生產每噸產品所需資源產品ABC勞動力所需工時占總工時比例1/31/31/3所需原材料（噸）1/34/37/3解：第一步——確定決策變量為產品A的日產量為產品B的日產量為產品C的日產量第二步——明確約束條件勞動力的約束條件為：原材料的約束條件為：第三步——明確目標總利潤為：此產品規(guī)劃問題的線性規(guī)劃模型為：問題2

某工廠在計劃期內要安排生產I、II兩種產品。已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗，如下表所示。該工廠每生產一件產品I可獲利2元，每生產一件產品II可獲利3元。問I、II兩種產品的產量各為多少時，使該工廠獲取最大利潤？產品I產品II

設備128臺時原材料A4016kg原材料B0412kg約束條件

x1＋2x2≤84x1≤164x2≤12x1，x2≥0該生產計劃問題可用數學模型表示為：目標函數

maxz＝2x1＋3x2問題3某制造企業(yè)有A、B、C、D四種主要產品，所有產品均需四道工序生產：第一階段是沖壓，第二階段是成型，第三階段是裝配，第四階段是噴漆。根據工藝要求及成本核算，單位產品所需的加工時間、利潤以及可供使用的總工時如下表所示。這四種產品每天要各生產多少件才能使獲得的利潤最大？請就這一問題，以利潤最大為目標，建立求解的線性規(guī)劃模型。工序每件產品加工時間每天加工能力（分鐘）ABCD沖壓1111480成型48252400裝配42552000噴漆64843000單位利潤（元）96118解答：

maxZ=9x1+6x2+11x3+8x4

約束條件：

x1+x2+x3+x4≤4804x1+8x2+2x3+5x4≤24004x1+2x2+5x3+5x4≤20006x1+4x2+8x3+4x4≤3000x1≥0，x2≥0，x3≥0，x4≥0應用2：配料問題

某工廠要用四種合金T1，T2，T3和T4為原料，經熔煉成為一種新的不銹鋼G。這四種原料含元素鉻（Cr），錳（Mn）和鎳（Ni）的含量（%），四種原料的單價以及新的不銹鋼材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：

假設熔煉時重量沒有損耗，要熔煉成100公斤不銹鋼G，應選用原料T1，T2，T3和T4各多少公斤，才能使新產品的原材料成本最小。問題

1解：設選用原料T1，T2，T3和T4分別為x1，x2，x3，x4公斤，根據條件，可建立相應的線性規(guī)劃模型如下：

這是一個典型的成本最小化的問題。這個線性規(guī)劃問題的最優(yōu)解是：

x1=26.58，x2=31.57，x3=41.84，x4=0（公斤）最低成本為： z=9549.87（元）

min

z=

115x1

+97x2

+82x3

+76x4

s.t.

0.0321x1

+0.0453x2+0.0219x3

+0.0176x4

≥3.20

0.0204x1

+0.0112x2

+0.0357x3

+0.0433x4

≥2.10

0.0582x1

+0.0306x2

+0.0427x3

+0.0273x4

≥4.30

x1

+x2

+x3

+x4

=100

x1,

x2,

x3,

x4

≥0

問題2某養(yǎng)豬場的豬每天至少需要700g蛋白質，30g礦物質，100mg維生素?，F有五種飼料可選，每種飼料每kg營養(yǎng)成分含量及單價如表所示。要求確定既滿足動物生長應用需要，又使費用最省的選用飼料方案。飼料蛋白質（g）礦物質（g）維生素（mg）價格（元/kg）1234532161810.50.220.50.51.00.220.80.20.70.40.30.8設xi為第i種飼料的數量（公斤），則Minz=0.2x1+0.7x2+0.4x3+0.3x4+0.8x5St.3x1+2x2+1X3+6X4+18X5>=7001x1+0.5x2+0.2X3+2X4+0.5X5>=300.5x1+1x2+0.2X3+2X4+0.8X5>=100應用3：背包及配送問題

一個物料箱最大裝載重量為50公斤?，F有三種物品，每種物品數量無限。每種物品每件的重量、價值如下表所示：

問：要在物料箱中裝入這三種物品各多少件，使箱中的物品價值最高？問題1：物料裝箱

這個問題的最優(yōu)解是：x1=1(件),x2=0(件),x3=2(件),最高價值為：z=87（元）解：設裝入物品1，物品2和物品3各為x1，x2，x3件，由于物品的件數必須是整數，因此物料箱問題的線性規(guī)劃模型是一個整數規(guī)劃問題：Maxz=17x1+41x2+35x3

s.t10x1+41x2+20x3<=50

xi≥0(i=1,2,3)且為整數問題2

設某種物資從兩個供應地A1，A2運往三個需求地B1，B2，B3。各供應地的供應量、各需求地的需求量、每個供應地到每個需求地的單位物資運價如下表所示。

問如何安排運輸計劃，從而使總運費最??？

設xij為從供應地Ai運往需求地Bj的物資數量（i=1,2；j=1,2,3），z為總運費，則總運費最小的線性規(guī)劃模型為：xij≥0

以上約束條件（1）、（2）稱為供應地約束，（3）、（4）、（5）稱為需求地約束。這個問題的最優(yōu)解為：x11=0， x12=30，x13=5（噸）；x21=10, x22=0, x23=15（噸）

最小運費為：z=275元。應用4：優(yōu)化下料問題問題1線材優(yōu)化

現要做100套鋼架，每套用長為2.9m，2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應如何下料，使用的原材料最省。

方案下料數長度IIIIIIIVV2.92.11.510321221213合計料頭7.407.30.17.20.27.10.36.60.8

為了得到100套鋼架，需要混合使用各種下料方案。設第i種方案下料的原材料根數為xi

，（i＝1，2，3，4，5）得數學模型為：

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

x1+2x2+x4

＝100x2+2x3+2x4+x5＝1003x1+x2+2x3+3x5＝100

xi≥0(i=1,2,3,4,5)且為整數問題2板材優(yōu)化

要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數如下表所示：規(guī)格類型第一種鋼板第二種鋼板A規(guī)格B規(guī)格C規(guī)格212131

今需要A,B,C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數最少。解：設需截第一種鋼板x張，第一種鋼板y張，則2x+y≥15,x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*目標函數為

minz=x+y應用5：值班調度問題問題1

某個中型的百貨商場對售貨人員的需求經過統(tǒng)計分析如下表所示，為了保證銷售人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應該如何安排售貨人員的作息，既能滿足工作需要，又使配備的售貨人員的人數最少？問題2某醫(yī)院護士值班班次、每班工作時間及各班所需護士數如下表所示。每班護士值班開始時向病房報到，試決定：若護士上班后連續(xù)工作8h，該醫(yī)院最少需多少名護士，以滿足輪班需要？解：在本例中，每一時段上班的工作人員，既包括本時段開始上班的人，又包括上一個時段開始上班的人。因此，設xi為第i個時段開始上班的人員數，得到數學模型為：Minz=x1+x2+x3+x4+x5+x6x6+x1>=60X1+x2>=70X2+x3>=60

x3+x4>=50X4+x5>=20X5+x6>=30Xj>=0,j=1,2,…6應用6：投資組合問題問題1宏銀公司承諾為某建設項目從2003年起的4年中每年初分別提供以下數額貸款：2003年—100萬，2004年—150萬，2005年—120萬，2006年—110萬元。以上貸款資金均需于2002年底前籌集齊。但為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項目（1）于2003年初購買A種債券，期限3年，到期后本息合計為投資額的140%，但限購60萬元；（2）于2003年初購買B種債券，期限2年，到期后本息合計為投資額的125%，且限購90萬元；（3）于2004年初購買C種債券，期限2年，到期后本息合計為投資額的130%，但限購50萬元；（4）于每年初將任意數額的資金存放于銀行，年息4%，于每年底取出。問宏銀公司應如何運用好這筆籌集到的資金，使2002年底需籌集到的資金數額最少？解：設x為2002年底宏銀公司需籌集到的資金額，y1，y2，