線性規(guī)劃模型經濟數學建模課件(西安交通大學戴雪峰).ppt

《線性規(guī)劃模型經濟數學建模課件(西安交通大學戴雪峰).ppt》由會員分享，可在線閱讀，更多相關《線性規(guī)劃模型經濟數學建模課件(西安交通大學戴雪峰).ppt（106頁珍藏版）》請在裝配圖網上搜索。

數學建模,西安交通大學理學院戴雪峰E-mail:daixuefeng@,線性規(guī)劃（LineProgramming)模型,線性規(guī)劃（LP）問題的模型建立,1、運輸問題：,某機電公司共有三個電機制造廠，并建立五個地區(qū)性倉庫。公司先把產品運到這些倉庫，以備向用戶供貨，三個廠每周生產電機臺數如表：,五個倉庫每周需求量如表,由各廠到各倉庫的運費（每臺）如表,電機公司希望建立一個滿足制造廠的供應量和倉庫的需求量并使總運費為最小的數學模型。,把m個發(fā)點的貨物運到n個收點去，已知第i個發(fā)點的可供應量為ai(i=1,2,…,m),第j個收點的需求量為bj(j=1,2,…,n)，cij為從第i個發(fā)點到第j個收點的運輸單價，應如何運輸才能使總運費最??？,一般的運輸問題可敘述為：,設xij為從第i個發(fā)點到第j個收點的運量,不等式在某些條件下可能成為等式。,2、食譜問題：,一公司飼養(yǎng)動物生長對飼料中三種營養(yǎng)成分：蛋白質、礦物質、維生素特別敏感，每個動物每天至少需要蛋白質70g、礦物質3g、維生素10mg，該公司買到五種不同的飼料，每種飼料1㎏所含營養(yǎng)成分如表,每種飼料1㎏的成本如表,要求確定既能滿足動物生長所需，又使總成本為最低的飼料配方。,建立數學模型：,設xj(j=1,2,…,n)表示1㎏混合飼料中含第j種飼料的數量,一般的食譜問題可敘述為：,設有n種食物，每種食物中含有m中營養(yǎng)成分，用aij表示一個單位的第j種食物含第i種營養(yǎng)的數量，用bi表示每人每天對第i種營養(yǎng)的最低需求量，cj表示第j種食物的單價，xj表示所用第j種食物的數量，應如何搭配，能滿足m種營養(yǎng)成分需求，又使食物總成本最低？,3、河流污染與凈化問題：,某河流邊上有兩個化工廠，流經第一工廠的河水流量是每天500萬m3，在兩廠之間有一條流量為每天200萬m3的支流。第一工廠每天排放工業(yè)污水2萬m3，第二工廠每天排放工業(yè)污水1.4萬m3，從第一工廠排放工業(yè)污水在流到第二工廠之前有20%可以自然凈化，根據環(huán)保要求，河流中的工業(yè)污水含量應不大于2‰，若這兩廠都各自處理一部分污水，第一工廠處理污水的成本為0.1元/m3，第二工廠處理污水的成本為0.08元/m3，問在滿足環(huán)保的要求下，各化工廠應處理多少污水，使兩廠總的處理污水費用最少？,設xj(j=1,2)為第j個化工廠每天處理污水量（河水流量中忽略了工廠的排入量。）,模型為：,4、合理下料問題：,有長10m的鋼管若干，現需裁出2m、3m、4m的鋼管分別為20、15、15根。問如何裁，才能使浪費（根數）最少。,設xj用第j種方式下料所用鋼管數，,請同學們考慮：如何裁，才能使浪費（料頭）最少。,模型為：,一般的合理下料問題可敘述為：,要利用某類鋼材下A1,A2,…,Am一共m種零件毛料，根據省料原則，在一塊鋼材上設計出n種不同的下料方式，設在第j種下料方式中，可得Ai種零件aij個，設第i種零件的需求量為bi（如表）.問應采取什么方式，使既滿足問題需要，又使所用鋼材最少？,設xj為用第j種方式下料所用鋼材數,模型為：,5、指派問題：,某大學打算在暑期對三幢教學樓進行維修,該校讓三個建筑公司對每幢樓的修理費用進行報價承包(見表,單位:萬元),在暑期每個建筑公司只能修理一幢教學樓，因此該大學必須把各教學樓指派給不同建筑公司，為使報價總和最小，應指定建筑公司承包哪一幢教學樓？,模型為：,一般的指派問題可敘述為：,設有n項任務需派n個人去完成，但由于任務性質及個人專長不同，因此各人完成各任務的效率（或需時間、花費成本）不同，試問應如何安排，使總效率（或需時間、花費成本最少）最高？,設tij表示第i個人完成第j件任務的效率,模型為：,6、投資決策問題：,公司擬在某市東、南、西三區(qū)建立連鎖店，擬議中有7個位置Ai(i=1,2,…,7)可供選擇，規(guī)定東區(qū)在A1,A2,A3中至多選2個，西區(qū)在A4,A5中至少選1個，南區(qū)在A6,A7中至少選1個，并選用Ai點，投資bi元，估計每年獲利ci元，但投資總額不得超過B元。問應如何選址，可使每年利潤最大？,模型為：,7、生產配套問題：,設第一、二、三個車間生產零件A、B、C的效率如下,假設三種零件各一個配成一套。應如何分配生產任務，可使生產的成套產品最多？,設xij(i=1,2,3,j=1,2,3)表示第i個零件由第j個車間生產的生產時間。共生產配套產品Z套，,模型如下:,一般的生產配套問題可敘述為：,設有n個車間，要生產m種產品，假設這種產品每種一件配成一套。問如何安排任務，使生產的成套產品最多？,設一天中第j個車間用于生產第i種產品的時間xij(i=1,…,m,j=1,…,n)，每天生產Z套，,模型如下；,8、森林管理問題：,森林中樹木每年要有一批被砍伐出售，為使森林不被耗盡而每年都有所收獲，每砍伐一棵樹，就應補種一棵幼苗，使的森林樹木總數不變，希望有一個方案，在保持收獲穩(wěn)定的前提下，獲得最大的經濟價值。,1）模型假設：,我們把森林中的樹木按高度分成n級，第k級高度在hk-1到hk之間（h0=0），其價值pk元，k=1，…，n，顯然有p1＜p2＜…＜pn，第一級為幼苗，價值為零（p1=0），開始時，森林中樹木高度分布為第k級數量為xk。,設每年砍伐一次，要使每年維持收獲，只能砍伐部分樹木，留下的數目與補種的幼苗其高度狀態(tài)與初始狀態(tài)相同。設yk為每年第k級所砍伐的棵數。設森林樹木總數為S（固定），有,在一個生長期（即兩次收獲之間）假設樹木至多只能生長一個高度級（即從k級進入k+1級，也可能因某些原因留在第k級）。并假設每一棵幼苗都生長到被收獲（不考慮死亡的可能性）。假設在每一個生長期內，第k級的樹木進入第k+1級的比例為gk，于是留在原級的比例為1-gk。,2）模型建立：,設X=(x1,x2,…,xn)T，,所以GX表示經過一個生長期后樹木高度的分布。,每次收獲砍伐總數為,而補種的棵數等于砍伐總數,要保持初始狀態(tài)不變，有,因而有,（否則，各級數目就會越來越少。）,總收益:,數學模型歸納為,以上各問題有以下特點：,1）每一問題都用一組未知量來表示某一方案，其取值就表示特定方案，稱之為決策變量。（通常為非負的）,2）存在一定的限制條件，并用未知量的線性等式或不等式表示。,3）有一個目標要求，并用未知量的線性函數表示，由實際要求，實現其最大化或最小化。,LP的數學描述(數學模型)：,（1）一般形式,（2）緊縮形式,（3）矩陣形式,其中:,（4）向量—矩陣形式：,其中：,線性規(guī)劃問題主要解法是單純形解法，一般用Lingo軟件求解.,線性規(guī)劃（LP）問題的圖解法,若線性規(guī)劃問題只有兩個變量，則可用圖解法求解。圖解法簡單直觀，不但能很快求得LP問題的最優(yōu)解和最優(yōu)值，而且它的結論對多個變量線性規(guī)劃問題也提供了求解思路。,圖解法講解,圖解法求解時，先做出問題的可行解域，它是每個線性約束所確定的半平面的交，再將目標函數Z作為參數，做出目標函數線，它是一簇平行線，根據目標函數的要求，尋找Z在可行解域中的最大或最小值，即可求得問題的最優(yōu)解。,,x+y=0,x+y>0,x+y0,x-y+1<0,x-y+1=0,,3,6,2x+y-6<0,2x+y-6=0,,,,,3,5,-5,x-y+5=0,x+y=0,x=3,,,4,,,,,,,6,8,4,6,3,,A,,B,,C,D,,,,,圖解法求LP問題的示意圖,圖解法的啟示,可行域是一個凸多邊形.,LP的解可能有多種形式,如多解,無界解(發(fā)散,無窮)或無可行域.,最優(yōu)解一定在可行域的邊界上,一般是在頂點上,1.唯一最優(yōu)解,例.用圖解法求解：,可行解域OABC最優(yōu)解B(4,1),即X1=4X2=1最優(yōu)值Z=9,,圖解法求LP問題會出現的幾種情況,2.無可行解,例.用圖解法求解：,此問題無可行解，無最優(yōu)解,,3.無界,例.用圖解法求解：,此例可行解域無界，目標直線可向右上方無限延伸，故目標函數值無界，,稱此情況為無界情況,,線性規(guī)劃（LP）問題的單純形法,1.LP標準型的概念,目標函數約定是極大化Max;,約束條件均用等式表示;,決策變量限于取非負值;,右端常數均為非負值;,2.LP問題的標準化,（1）目標函數的標準化,MinZ=CX,MaxZ’=-CX,,,（2）約束條件的標準化約束條件是≤類型——左邊加非負松弛變量約束條件是≥類型——左邊減非負剩余變量變量符號不限——引入新變量,將下面的線性規(guī)劃問題化為標準型：,LP解的基本概念及基本性質,1.基本概念,滿足約束條件的解稱為線性規(guī)劃問題的可行解,所有可行解的集合稱為可行域。,基、基向量、基變量、非基變量,在mn階約束方程組中,若有一個mm階的非奇異子矩陣B,則B為該LP的一個基。B所在列對應的向量為基向量，對應的變量為基變量，其余向量為非基向量。其余變量為非基變量。,可行解:,基解(也叫“基本解”）,基解的特點：,1.基解的非零分量個數小于等于約束方程數m,2.基解是約束方程的交點。,3.基解只滿足條件約束，不一定滿足非負約束，因此基解中的分量有可能為負數。,4.基解的個數有限，不超過。,取一個基，令其中非基變量為0，可得相應基解。求基解的前提是取m個線性無關向量構成基。,2.基本定理,定理1LP的可行域為凸集,定理2基本可行解可行解的非零分量對應的系數列向量線性無關,定理3基可行解可行域的頂點,定理4若可行域有界，最優(yōu)解一定在其頂點上,,,基本思路：從可行域中某個基可行解開始，根據一定標準，轉換到另一個基可行解，當目標函數最大時，就得到了最優(yōu)解。,單純型核心：關鍵在于判別，使每次轉換后結果更優(yōu)，從而不必窮舉所有頂點即可得到最優(yōu)解。,判別方法：觀察非基變量取值對目標函數的影響。,單純型法：,定理1當所有非基變量的檢驗數,相應的基可行解為最優(yōu)解。,定理2當還有非基變量的檢驗數,則該解不是最優(yōu)解。,1.化標準型,單純型求解步驟,2.建立初始單純型表,確定初始基，求出初始基可行解。,3.計算檢驗數，確定換入基變量和換出基變量。,0,2,3,0000,6,4,－,3,230000,1281612,0000,換入變量的確定計算δｊ，δｊ＝cｊ－∑CBiaij可只計算非基變量的δｊ，換入基變量δk＝max｛δｊ，δｊ≥0｝，k對應的列為主元列。,換出變量的確定計算θi，θi＝bｊ/aik（當aik≥0時）只計算非負的aik對應的行，換出基變量θL＝min｛θi｝，L對應的行為主元行。,k列L行的元素稱為主元素，用［alk］表示,,,,,,,,Z,,,,221000120100400010040001,,,,,b,,,,,,,,,,,,,,,6,4,－,3,230000,1281612,0000,0003,3010001/4,16400010,210010-1/2,620100-1/2,20000-4/3,324-,4.迭代計算（求新的基本可行解）5.重復3、4步，直至最優(yōu)。,X(3)=(2,3,2,0,8,0)Z=13X(4)=(4,2,0,0,0,4)Z=14,線性規(guī)劃（LP）問題的特殊解法,1、運輸問題：,步驟：,1）最小元素法確定初始方案：按運費最小優(yōu)先供應原則（多個最小元素選最上一行最左邊一個），劃去行或列時一次只能劃去一行或一列，最后一個同時劃去行和列，保證表上又m+n-1個格有數字（包括0）。,2）求出檢驗數，判別是否最優(yōu)。（對最小化問題，若每個空格的檢驗數，則方案達到最優(yōu)。）（為了求出檢驗數，需畫出閉回路(閉回路唯一)。）∑第偶數次拐角點運價-∑第奇數次拐角點運價,3）求出調整量，在閉回路上調整。調整量：{奇數次拐角點運量}調整：奇數次拐角點運量-θ；偶數次拐角點運量+θ。（若表中有幾個零出現，將最上一行最左邊一個的零改為空格，其余保留，保證表上又m+n-1個格有數字。）,另一種求檢驗數的方法：1）運價表上有調運量的數字加＊，2）同行或同列同時減去或加上同一個數，使其帶＊數字全部變?yōu)榱?，則未加＊的數字即為對應空格的檢驗數。,3）最大化問題用最大元素法建立初始方案。判別最優(yōu)時,檢驗數達到最優(yōu)，其余與最小元素法相同。,注：,1）運輸問題最優(yōu)解不唯一。,2）對于產銷不平衡問題，可以虛加發(fā)點或收點來進行求解（發(fā)量大于收量，虛加一列，運價增加一列，并全部為零，在用最小元素法時，須先將庫存一列去掉，再逐一選取最小元素）。,2、指派問題：,Theorem1:如果從效率矩陣的任一行（列）各元素減去該行（列）的最小元素（或加上某一正數），不改變問題的最優(yōu)解。,Theorem2:如果從效率矩陣的每一行分別減去該行的最小元素ai，每一列分別減去該列的最小元素bj，得到最優(yōu)解。則目標函數（最小化）的最優(yōu)值等于各行、各列減去數之和，即minZ=∑ai-∑bj,例：4人工作分派，效率矩陣如下,如何分派使得問題最小化。(minZ=29),步驟：,1）每行每列減去各行、各列最小元素，使每行每列至少有一個零元素。,2）從零元素最少的行開始，對一個零元素標＊，表示一種分派，同時把該行、列的其余零元素劃去，防止下次分派落在此行、列上，當某行零元素多于一個，則標注零元素最少的列。至所有零元素標注＊或劃去為止。若得到n個0*，則0*改為1，其余改為0，即為最優(yōu)分派。,3）若0*少于n個，則作0*的最少覆蓋集。,例：求該指派問題的minZ,①對沒有0*的行打√。,②對打√行所有零元素列打√。,③再對打√列上0*行打√。,④重復②、③，到不能打√為止。,⑤對沒有打√行劃線，對打√列劃線，其線條數=0*數。,⑥在沒有劃線的元素中找最小元素，對沒有劃線行各元素減去最小元素，對劃線列各元素加上最小元素，得到新的效率矩陣，返回第2）步。,再例：求該指派問題的minZ,注1：對最大化問題，采用構造一個新的效率矩陣，并取，則,注2：若效率矩陣m≠n（行數不等于列數），可虛設零行（列），使效率矩陣變成方陣，然后再用匈牙利法求解。,3、生產配套問題：,設每個車間都生產效率最高的零件,按開始的原則重新分配得：,（若某列有相同的最大效率，選取時應位于不同行列上。,把第一行的效率再擴大，該行乘以,為使零件A和C的產量相等（配套），得：,,這時有,得：,為使三個車間產量相等（配套），需把第一車間生產零件B的時間的一部分用來生產零件A和C，,,零件A的產量為,零件B的產量為,零件C的產量為,最優(yōu)解為:,(不唯一,可生產392/61(套)),若要求每個車間生產的零件必須為整數，則易得出：,零件A：,零件B：,零件C：,即一天可完成6套產品。,（一車間6個B零件，二車間5個A零件，三車間1個A零件、6個B零件。）,4、森林管理問題：,森林中樹木每年要有一批被砍伐出售，為使森林不被耗盡而每年都有所收獲，每砍伐一棵樹，就應補種一棵幼苗，使的森林樹木總數不變，希望有一個方案，在保持收獲穩(wěn)定的前提下，獲得最大的經濟價值。,1）模型假設：,樹木按高度分成n級，第k級高度在hk-1到hk之間（h0=0），其價值pk元，k=1，…，n，顯然:0=p1＜p2＜…＜pn，第一級為幼苗，價值為零（p1=0），開始時，森林中樹木高度分布為第k級數量為xk。,設每年砍伐一次，要使留下的數目與補種的幼苗其高度狀態(tài)與初始狀態(tài)相同。設yk為每年第k級所砍伐的棵數。設森林樹木總數為S（固定），有,在一個生長期（即兩次收獲之間）假設樹木至多只能生長一個高度級（即從k級進入k+1級，也可能因某些原因留在第k級）。并假設每一棵幼苗都生長到被收獲（不考慮死亡的可能性）。假設在每一個生長期內，第k級的樹木進入第k+1級的比例為gk，于是留在原級的比例為1-gk。,2）模型的分析與建立,記xik+1為k+1年的第i級數目,現在來考慮收獲情形:,維持每年收獲,期初=期末-收獲+新種幼苗數,有收獲模型：,保證對森林有持續(xù)收獲，就相當于要求Y是常量。數學上相當于要求每年森林樹木分布狀況相同，即存在X＊，使得X(k)=X＊，X＊即為模型的平衡解。,它相當于以下關系式：,可以看出，第一個方程為其余n-1個方程之和，且因Y為收獲向量，則yi≧0?？紤]到幼苗的經濟價值為零，故不砍伐幼苗，y1=0，且仍用xk表示x＊，由方程組（1）可得：,所以收獲總價值,再利用方程組（1）可得,（其中p1=0）,數學模型歸納為,3）模型的求解,對于線性規(guī)劃問題，有兩個定理：,定理1：線性規(guī)劃問題的可行域為凸集。,定理2：線性規(guī)劃問題的最優(yōu)解在可行域的頂點上達到。,由定理2知道:只要從某個高度級中收獲全部樹木，而不用收獲其它高度級的樹木，就可以得到最大持續(xù)收獲。,假定只收獲第k級的全部樹木，所以有,由于第k級樹木被全部收獲，所以，當i≧k時，第i級就不存在樹木，即xi=0。,所以收獲第k級樹木的收入：,只要生長參數gi已知，就可以求出P的值，再比較k取不同值時的P值，從中確定持續(xù)收獲的最大經濟收入。,4）數值舉例：,現已知某處森林具有6年的生長期，經過實地測量，得其生長矩陣,各年齡樹木價格分別為：,這里設森林中樹木總數為S，,若只收獲第二年（k=2）,此時,若只收獲第三年（k=3）,若只收獲第四年（k=4）,若只收獲第五年（k=5）,若只收獲第六年（k=6）,比較可知14.7S最大，應砍伐第三年中全部樹木，使收益最大。,即第一年樹木占森林樹木總數的52.5%，第二年樹木占森林樹木總數的47.5%。,作業(yè)：,1.對下表所表示的運輸問題建模并求解,2.現要用10050厘米的板料裁剪出規(guī)格分別為4040厘米與5020厘米的零件，前者需要25件，后者需要30件。問如何裁剪，才能最省料？,電視臺為某個廣告公司特約播放兩套片集。其中片集甲播映時間為20分鐘，廣告時間為1分鐘，收視觀眾為60萬，片集乙播映時間為10分鐘，廣告時間為1分鐘，收視觀眾為20萬。廣告公司規(guī)定每周至少有6分鐘廣告，而電視臺每周只能為該公司提供不多于80分鐘的節(jié)目時間。電視臺每周應播映兩套片集各多少次，才能獲得最高的收視率？,某廠生產甲、乙兩種產品，生產甲種產品每件要消耗煤9噸，電力4千瓦，使用勞動力3個，獲利70元；生產乙種產品每件要消耗煤4噸，電力5千瓦，使用勞動力10個，獲利120元。有一個生產日，這個廠可動用的煤是360噸，電力是200千瓦，勞動力是300個，問應該如何安排甲、乙兩種產品的生產，才能使工廠在當日的獲利最大，并問該廠當日的最大獲利是多少？答案：（甲20件，乙24件，獲利4280元）,藥房有兩種復合維生素制劑，甲種每粒含維生素A、B各1克，D、E各4克和C5克，乙種每粒含維生素A3克，B2克、D1克、E3克和C2克，一顧客每天需攝入維生素A不超過18克、B不超過13克、D不超過24克和E至少12克，問：(1)每天應服兩種維生素各多少才能滿足需要而且盡可能攝入較多的維生素C？(2)甲種復合維生素每粒1.5元，乙種復合維生素每粒1元，選擇怎樣的服法才能花最少的錢而又滿足每天的需要，此時顧客攝入的維生素C是多少？,某牧場所飼養(yǎng)一批動物，平均每頭動物每天至少需要700g蛋白質、30g礦物質和100g維生素.現在有甲、乙、丙、丁和戊五種飼料可選用，每千克飼料的營養(yǎng)成分(單位：g)與價格(單位：元/kg)如表所示,蛋白質礦物質維生素價格,甲31.00.50.4,乙20.51.01.4,丙10.20.20.8,丁62.02.00.6,戊120.50.81.6,試求能滿足動物生長營養(yǎng)需求又最經濟的選用飼料方案.,農場有A、B和C三塊地，分別是200km2、400km2和600km2，計劃種植水稻、大豆和玉米，要求三種作物的最低收獲量分別為375t、120t和750t.估計各塊地種植三種作物的單產(單位:t/km2)如表,ABC,水稻11.2509.7509.000,大豆6.0006.7505.250,玉米15.00013.50012.750,應如何制訂種植計劃能使總產量最高？又若作物的售價為水稻元/t,大豆元/t,玉米950元/t,那么應如何制訂種植計劃能使總收益最高.,鑄鐵廠要生產一種規(guī)格的鑄件共10t.其成分要求為：錳含量至少達到0.45％,硅含量允許在3.25％~5.5％，市場有充分的錳和三種不同型號的生鐵可供作鑄件的爐料使用，它們價格是錳每千克75元，A種生鐵每噸1700元，B種生鐵每噸1900元，C種生鐵每噸1400元.三種生鐵含錳和硅的成分百分比(％)如表所示,ABC,錳0.40.50.35,硅410.5,若不計冶煉鑄造過程中的損耗，問工廠怎樣選擇爐料能使成本最低？,某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數分別為800和900，三種工件的數量分別為400、600和500，且已知用三種不同車床加工單位數量不同工件所需的臺時數和加工費用如下表。問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？,某廠每日8小時的產量不低于1800件。為了進行質量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該廠應聘一級、二級檢驗員各幾名？,