運籌學(xué) 第二章線性規(guī)劃模型與圖解法

1、運籌學(xué) 課件第二章線性規(guī)劃模型與圖解法第1頁，共24頁，2022年，5月20日，18點41分，星期三第章線性規(guī)劃2.1 線性規(guī)劃的模型與圖解法2.2 單純形法2.3 對偶問題與靈敏度分析2.4 運輸問題第2頁，共24頁，2022年，5月20日，18點41分，星期三2.1 線性規(guī)劃的模型與圖解法2.1.1 問題的引入（）生產(chǎn)安排問題 如何合理使用有限的人力、物力和資金，使得收到最好的經(jīng)濟效益。第3頁，共24頁，2022年，5月20日，18點41分，星期三 例1：某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下： 試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品 資源甲 乙資源

2、限量煤電油9 44 5 3 10360200300單位產(chǎn)品價格 7 12第4頁，共24頁，2022年，5月20日，18點41分，星期三 甲 乙 資源限量 煤(t) 9 4 360 電（kwh) 4 5 200 油（t） 3 10 300 單價（萬元） 7 12解：設(shè)甲乙產(chǎn)品產(chǎn)量分別為x1和x2 kg，決策變量總收入為z萬元。則 max z = 7x1 +12x2 目標(biāo)函數(shù) 9x1 + 4x2 360 4x1 + 5x2 200 3x1 +10 x2 300 x1，x20s.t. 約束條件第5頁，共24頁，2022年，5月20日，18點41分，星期三（）配料問題 如何合理地搭配（混合）材料，以最

3、經(jīng)濟的方式，達到配比要求。例2：（營養(yǎng)配餐問題）假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最?。康?頁，共24頁，2022年，5月20日，18點41分，星期三各種食物的營養(yǎng)成分表第7頁，共24頁，2022年，5月20日，18點41分，星期三解：設(shè)xj(j=1,2,3,4)為第j種食品每天的購入量，z為每天購買食品的總費用，則配餐問題的線性規(guī)劃模型為： min z=14x1+6x2 +3x3+2x4 1000 x1+800 x2

4、 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1,x2 ,x3 ,x4 0第8頁，共24頁，2022年，5月20日，18點41分，星期三（3）下料問題 如何截取原材料，在達到截取要求的情況下，使廢料最少。例3：料長7.4米，截成2.9、2.1、1.5米各200根,方案如下表。如何截取余料最少？ 方案料型 1 2 3 4 5 2.9米 2.1米 1.5米 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 合計 殘料 7.4 7.3 7.2 7.1 6.6 0 0

5、.1 0.2 0.3 0.8第9頁，共24頁，2022年，5月20日，18點41分，星期三解：設(shè)xj(j=1,2,3,4,5)為采用第j種方案截取的原料根數(shù)，z為截取后的余料總米數(shù)，則下料問題的線性規(guī)劃模型為： min z=0 x1+0.1x2 +0.2x3+0.3x4+0.8x5 x1+2x2 + x4 200 2x3+ 2x4 + x5 200 3x1+ x2 +2x3 +3x5 200 xj 0(j=1,2,3,4,5)第10頁，共24頁，2022年，5月20日，18點41分，星期三2.1.2 線性規(guī)劃的模型 一、LP模型的三要素 規(guī)劃問題的數(shù)學(xué)模型包含三個組成要素：（1）決策變量：指決

6、策者為實現(xiàn)規(guī)劃目標(biāo)采取的方案措施，是問題中要確定的未知量。（2）目標(biāo)函數(shù)：指問題要達到的目的要求，表示為決策變量的函數(shù)。（3）約束條件：指決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。第11頁，共24頁，2022年，5月20日，18點41分，星期三二、 LP模型的一般式一般地，線性規(guī)劃模型：1、決策變量：x1,xn2、目標(biāo)函數(shù)：3、約束條件：第12頁，共24頁，2022年，5月20日，18點41分，星期三 簡記為：第13頁，共24頁，2022年，5月20日，18點41分，星期三三、LP模型的矩陣式 表示為：第14頁，共24頁，2022年，5月20日，18點41分，星期

7、三例如：第15頁，共24頁，2022年，5月20日，18點41分，星期三練習(xí)1：某畜牧廠每日要為牲畜購買飼料以使其獲取A、B、C、D四種養(yǎng)分。市場上可選擇的飼料有M、N兩種。有關(guān)數(shù)據(jù)如下：試決定買M與N二種飼料各多少公斤而使支出的總費用為最少？410售價 0.4 0.6 2.0 1.7牲畜每日需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含營養(yǎng)成分 A B C D飼料第16頁，共24頁，2022年，5月20日，18點41分，星期三2.1.3 線性規(guī)劃模型的圖解法（適用于2個變量的一般型）一、線性規(guī)劃問題的解的概念 設(shè)線性規(guī)劃問題的一般型為（1）可行解：滿足全部約束條

8、件的決策變量X為可行解； 全部可行解的集合R稱為可行解域。（2）最優(yōu)解：使目標(biāo)函數(shù)為最大（或最小）的可行解X*。第17頁，共24頁，2022年，5月20日，18點41分，星期三二、線性規(guī)劃的圖解法 圖解法步驟：1、根據(jù)約束條件畫出可行解域；（1）先作非負(fù)約束（2）再作資源限制約束（3）各約束的公共部分即該LP的約束的圖形（可行域）2、畫出目標(biāo)函數(shù)的等值線；（1）任給z兩個不同的值，作相應(yīng)兩條直線（2）將目標(biāo)直線向增大的方向移，直至可行域的邊界， 交點X*即最優(yōu)解。3、求出最優(yōu)解。 由交點二直線聯(lián)立求解出最優(yōu)解X* 的值。第18頁，共24頁，2022年，5月20日，18點41分，星期三x1x20

9、9040405030100Dl1l2l3例1 用圖解法求解下列線性規(guī)劃問題?？尚杏蚰繕?biāo)函數(shù)等值線X*有唯一最優(yōu)解（頂點D）解直線l2,l3組成的線性方程組得：X*=(20,24)T最優(yōu)生產(chǎn)方案Z*=720+1224=428最大收入第19頁，共24頁，2022年，5月20日，18點41分，星期三（2）在模型（1）中，目標(biāo)函數(shù)改為 max z=3x1+10 x2，其它不變。 09040405030100Dl1l2l3AX1易知，目標(biāo)函數(shù)等值線與直線l3平行。X2故線段AD上的點均為最優(yōu)解。有無窮多最優(yōu)解第20頁，共24頁，2022年，5月20日，18點41分，星期三x1x204可行域無界，在可行域上沒有使目標(biāo)函數(shù)值為有限的最優(yōu)解。無有限最優(yōu)解（無界解）第21頁，共24頁，2022年，5月20日，18點41分，星期三1x2012x1-1不存在所有約束條件的公共范圍無可行解第22頁，共24頁，2022年，5月20日，18點41分，星期三小結(jié)：1、線性規(guī)劃問題第23頁，