線性規(guī)劃模型經(jīng)濟(jì)數(shù)學(xué)建模課件(西安交通大學(xué)戴雪峰).ppt

《線性規(guī)劃模型經(jīng)濟(jì)數(shù)學(xué)建模課件(西安交通大學(xué)戴雪峰).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性規(guī)劃模型經(jīng)濟(jì)數(shù)學(xué)建模課件(西安交通大學(xué)戴雪峰).ppt（106頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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