數(shù)據(jù)、模型與決策3

Data,ModelandDecisions數(shù)據(jù)、模型與決策Session3LinearProgrammingFormulationandApplications線性規(guī)劃的建模與應(yīng)用KeyCategoriesofLPProblems線性規(guī)劃問(wèn)題主要類型資源分配問(wèn)題（resource-allocation）

成本收益平衡問(wèn)題（cost-benefit-trade-off）

網(wǎng)絡(luò)配送問(wèn)題（distribution-network）

混合問(wèn)題（mixedProblem）3.1資源分配問(wèn)題資源分配問(wèn)題是將有限的資源分配到各種活動(dòng)（決策）中去的線性規(guī)劃問(wèn)題。這一類問(wèn)題的共性是在線性規(guī)劃模型中每一個(gè)函數(shù)約束均為資源約束,并且每一種資源都可以表現(xiàn)為如下的形式：使用的資源數(shù)量可用的資源數(shù)量對(duì)任何資源分配問(wèn)題，有三種數(shù)據(jù)必須收集：（1）每種資源的可供量；（2）每一種活動(dòng)所需要的各種資源的數(shù)量,對(duì)于每一種資源與活動(dòng)的組合,單位活動(dòng)所消耗的資源量必須首先估計(jì)出來(lái)；（3）每一種活動(dòng)對(duì)總的績(jī)效測(cè)度（如總利潤(rùn)）的單位貢獻(xiàn)（如單位利潤(rùn)）。3.1資源分配問(wèn)題例3.1某公司是商務(wù)房地產(chǎn)開(kāi)發(fā)項(xiàng)目的主要投資商。目前，該公司有機(jī)會(huì)在三個(gè)建設(shè)項(xiàng)目中投資： 項(xiàng)目1：建造高層辦公樓； 項(xiàng)目2：建造賓館； 項(xiàng)目3：建造購(gòu)物中心。每個(gè)項(xiàng)目都要求投資者在四個(gè)不同的時(shí)期投資：在當(dāng)前預(yù)付定金，以及一年、二年、三年后分別追加投資。表3-1顯示了四個(gè)時(shí)期每個(gè)項(xiàng)目所需資金（百萬(wàn)元）。投資者可以按一定的比例進(jìn)行投資和獲得相應(yīng)比例的收益。年份辦公樓項(xiàng)目賓館項(xiàng)目購(gòu)物中心項(xiàng)目0（現(xiàn)在）408090160805029080203107060凈現(xiàn)值457050公司目前有2500萬(wàn)元資金可供投資，預(yù)計(jì)一年后，又可獲得2000萬(wàn)元，兩年后獲得另外的2000萬(wàn)元，三年后還有1500萬(wàn)元以供投資。那么，該公司要在每個(gè)項(xiàng)目中投資多少比例，才能使其投資組合獲得最大的總凈現(xiàn)值？3.1資源分配問(wèn)題解：這是一個(gè)資源分配問(wèn)題。(1)決策變量設(shè)：x1，x2，x3分別為在辦公樓項(xiàng)目、賓館項(xiàng)目、購(gòu)物中心項(xiàng)目中的投資比例(2)目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是總凈現(xiàn)值最大3.1資源分配問(wèn)題(3)約束條件本題的約束條件是公司在各期可獲得的資金限制（資源約束）。但要注意的是：前一期尚未使用的資金，可以在下一期使用（為了簡(jiǎn)化問(wèn)題，不考慮資金可獲得的利息）。因此，每一時(shí)點(diǎn)的資金限制就表現(xiàn)為累計(jì)的資金。表3-2顯示了累計(jì)的資金數(shù)據(jù)。年份辦公樓項(xiàng)目賓館項(xiàng)目購(gòu)物中心項(xiàng)目可用資金0（現(xiàn)在）40809025110016014045219024016065320031022080凈現(xiàn)值4570503.1資源分配問(wèn)題數(shù)學(xué)模型（線性規(guī)劃模型）3.1資源分配問(wèn)題電子表格模型3.2成本收益平衡問(wèn)題成本收益平衡問(wèn)題與資源分配問(wèn)題的形式完全不同，這種差異主要是因?yàn)閮煞N問(wèn)題的管理目標(biāo)不同而造成的。在資源分配問(wèn)題中，各種資源是受限制的因素（包括財(cái)務(wù)資源），問(wèn)題的目標(biāo)是最有效地利用各種資源，使獲利最大。而對(duì)于成本收益平衡問(wèn)題，管理層采取更為主動(dòng)的姿態(tài)，他們指明哪些收益必須實(shí)現(xiàn)（不管如何使用資源），并且要以最低的成本實(shí)現(xiàn)所指明的收益。這樣，通過(guò)指明每種收益的最低可接受水平，以及實(shí)現(xiàn)這些收益的最小成本，管理層期望獲得成本和收益之間的適度平衡。因此，成本收益平衡問(wèn)題是一類線性規(guī)劃問(wèn)題，這類問(wèn)題中，通過(guò)選擇各種活動(dòng)水平的組合，從而以最小的成本來(lái)實(shí)現(xiàn)最低可接受的各種收益水平。3.2成本收益平衡問(wèn)題成本收益平衡問(wèn)題的共性是，所有的函數(shù)約束均為收益約束，并具有如下的形式：

完成的水平最低可接受的水平如果將收益的含義擴(kuò)大，所有以“”表示的函數(shù)約束均為收益約束。成本收益平衡問(wèn)題需要的三種數(shù)據(jù)：（1）每種收益的最低可接受水平（管理決策）；（2）每一種活動(dòng)對(duì)每一種收益的貢獻(xiàn)（單位活動(dòng)的貢獻(xiàn)）；（3）每種活動(dòng)的單位成本。3.2成本收益平衡問(wèn)題排班問(wèn)題是成本收益平衡問(wèn)題研究的最重要的應(yīng)用領(lǐng)域之一。在這一領(lǐng)域中，管理層意識(shí)到在向顧客提供令人滿意的服務(wù)水平的同時(shí)必須進(jìn)行成本控制，因此，必須尋找成本和收益之間的平衡。于是，研究如何規(guī)劃每個(gè)輪班人員才能以最小的成本提供令人滿意的服務(wù)。例3.2某航空公司正準(zhǔn)備增加其中心機(jī)場(chǎng)的往來(lái)航班，因此需要雇傭更多的服務(wù)人員。不同時(shí)段有最少需要服務(wù)人員數(shù)，有5種排班方式，每8小時(shí)為一班。3.2成本收益平衡問(wèn)題例3.2（續(xù)）5種排班方式排班1：6AM～2PM，即早上6點(diǎn)上班；排班2：8AM～4PM，即早上8點(diǎn)上班；排班3：中午～8PM，即中午12點(diǎn)上班；排班4：4PM～午夜，即下午4點(diǎn)上班；排班5：10PM～6M，即晚上10點(diǎn)上班。時(shí)段排班1排班2排班3排班4排班5最少需要人數(shù)6AM～8AM√488AM～10AM√√7910AM～中午√√65中午～2PM√√√872PM～4PM√√644PM～6PM√√736PM～8PM√√828PM～10PM√4310PM～午夜√√52午夜～6PM√15每人每天工資(元)1701601751801953.2成本收益平衡問(wèn)題解:這是一個(gè)純成本收益平衡問(wèn)題。（1）決策變量本問(wèn)題的決策是不同排班的人數(shù)。設(shè)：xi為排班i的人數(shù)(i＝1,2,,5)（2）目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是人員總費(fèi)用（工資）最少，即3.2成本收益平衡問(wèn)題（3）約束條件

①每個(gè)時(shí)段的在崗人數(shù)必須不少于最低可接受水平（最少需要人數(shù)）②非負(fù)3.2成本收益平衡問(wèn)題數(shù)學(xué)模型（線性規(guī)劃模型）3.2成本收益平衡問(wèn)題電子表格模型3.3網(wǎng)絡(luò)配送問(wèn)題通過(guò)配送網(wǎng)絡(luò)能以最小的成本完成貨物的配送，所以稱之為網(wǎng)絡(luò)配送問(wèn)題。與確定資源和收益一樣，在網(wǎng)絡(luò)配送問(wèn)題中，必須確定需求以及相應(yīng)地確定需求的約束條件。確定需求約束的形式如下：提供的數(shù)量＝需求的數(shù)量3.3網(wǎng)絡(luò)配送問(wèn)題例3.3某公司網(wǎng)絡(luò)配送問(wèn)題。某公司在兩個(gè)工廠生產(chǎn)某種產(chǎn)品?，F(xiàn)在收到三個(gè)顧客的下個(gè)月定單要購(gòu)買這種產(chǎn)品。這些產(chǎn)品會(huì)被單獨(dú)運(yùn)送，表3-4顯示了從每個(gè)工廠到每個(gè)顧客的運(yùn)送一個(gè)產(chǎn)品的成本。該表同樣表明了每個(gè)顧客的訂貨量和每個(gè)工廠的生產(chǎn)量?，F(xiàn)在公司的物流經(jīng)理要決定從每個(gè)工廠運(yùn)送多少個(gè)產(chǎn)品到每個(gè)顧客那里才能使總成本最??？

單位運(yùn)輸成本（元/個(gè)）產(chǎn)量（個(gè)）顧客1顧客2顧客3工廠170090080012工廠280090070015訂貨量(個(gè))108927(產(chǎn)銷平衡)3.3網(wǎng)絡(luò)配送問(wèn)題解:由于“總產(chǎn)量（27）＝總訂貨量（27）”，所以本問(wèn)題是一個(gè)平衡運(yùn)輸問(wèn)題。（1）決策變量本問(wèn)題的決策為從每個(gè)工廠運(yùn)送多少個(gè)產(chǎn)品到每個(gè)顧客那里。設(shè)：xi-j為從工廠i運(yùn)輸?shù)筋櫩蚸的產(chǎn)品數(shù)量（i＝F1,F2;j=C1,C2,C3)（2）目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是使得公司總運(yùn)輸成本最低3.3網(wǎng)絡(luò)配送問(wèn)題（3）約束條件①?gòu)墓S運(yùn)送出去的產(chǎn)品數(shù)量等于其產(chǎn)量②顧客收到的產(chǎn)品數(shù)量等于其訂貨量③非負(fù)3.3網(wǎng)絡(luò)配送問(wèn)題數(shù)學(xué)模型（線性規(guī)劃模型）3.3網(wǎng)絡(luò)配送問(wèn)題電子表格模型3.4混合問(wèn)題前面討論了線性規(guī)劃問(wèn)題的三種類型：資源分配問(wèn)題、成本收益平衡問(wèn)題以及網(wǎng)絡(luò)配送問(wèn)題。每一類問(wèn)題都是以一類約束條件為特色的。實(shí)際上，純資源分配問(wèn)題的共性是它所有的函數(shù)約束均為資源約束（≤）而成本收益平衡問(wèn)題的共性是它所有的函數(shù)約束均為收益約束（）網(wǎng)絡(luò)配送問(wèn)題中，主要的函數(shù)約束為一特定類型的確定需求約束（＝）3.4混合問(wèn)題但許多線性規(guī)劃問(wèn)題并不能直接歸入三類中的某一類，一些問(wèn)題勉強(qiáng)可以歸入一類，因其主要的函數(shù)約束與表3-5的相應(yīng)函數(shù)約束大致相同。另一些問(wèn)題卻沒(méi)有一類占主導(dǎo)地位的函數(shù)約束，不能歸入前三類中的某一類。因此，混合問(wèn)題是第四類線性規(guī)劃問(wèn)題，這一類型將包括所有未歸入前述三類中的線性規(guī)劃問(wèn)題。一些混合問(wèn)題僅包含兩類函數(shù)約束，而更多的是包含三類函數(shù)約束。3.4混合問(wèn)題表3-5各類函數(shù)約束類型形式*解釋主要用于資源約束LHSRHS對(duì)于特定的資源使用的數(shù)量

可獲得的數(shù)量資源分配問(wèn)題混合問(wèn)題收益約束LHSRHS對(duì)于特定的收益到達(dá)的水平

最低可接受水平成本收益平衡問(wèn)題混合問(wèn)題確定需求約束LHS=RHS對(duì)于一些數(shù)量提供的數(shù)量=需求的數(shù)量網(wǎng)絡(luò)配送問(wèn)題混合問(wèn)題*LHS=左式（一個(gè)SUMPRODUCT函數(shù)）RHS=右式（一般為常數(shù)）3.4混合問(wèn)題配料問(wèn)題。這類問(wèn)題的一般提法是：由多種原料制成含有m種成分的產(chǎn)品，已知產(chǎn)品中所含各種成分的比例要求、各種原料的單位價(jià)格以及各原料所含成分的數(shù)量。考慮的問(wèn)題是：應(yīng)如何配料，可使產(chǎn)品的總成本最低。例3.4配料問(wèn)題。某公司計(jì)劃要用Ａ、Ｂ、C三種原料混合調(diào)制出三種不同規(guī)格的產(chǎn)品甲、乙、丙，產(chǎn)品的規(guī)格要求和單價(jià)、原料的供應(yīng)量和單價(jià)等數(shù)據(jù)如表3-6所示。問(wèn)：該公司應(yīng)如何安排生產(chǎn)，可使總利潤(rùn)最大？3.4混合問(wèn)題表3-6混合配料數(shù)據(jù)表ABC產(chǎn)品單價(jià)（元/千克）甲50%35%不限90乙40%45%不限85丙30%50%20%65原料供應(yīng)量（千克）200150100原料單價(jià)（元/千克）6035303.4混合問(wèn)題解：（1）決策變量本問(wèn)題的難點(diǎn)在于給出的數(shù)據(jù)是非確定數(shù)值，而且各產(chǎn)品與原料的關(guān)系較為復(fù)雜。為了方便，設(shè)xij表示原料i（i=A，B，C）用于產(chǎn)品j（j=1為甲，j=2為乙，j=3為丙）的數(shù)量。（2）目標(biāo)函數(shù) 本問(wèn)題的目標(biāo)是使總利潤(rùn)最大總利潤(rùn)＝產(chǎn)品收入－原料支出3.4混合問(wèn)題（3）約束條件本題的約束條件：原料供應(yīng)量限制3個(gè)、規(guī)格要求7個(gè)和決策變量非負(fù)。在例3.4中，有9個(gè)決策變量和10個(gè)函數(shù)約束條件，包括5個(gè)資源約束、2個(gè)收益約束和3個(gè)確定需求約束。3.4混合問(wèn)題電子表格模型3.5線性規(guī)劃模型的應(yīng)用前面按照函數(shù)約束的分類，介紹了四種線性規(guī)劃問(wèn)題：資源分配問(wèn)題（,資源約束）成本收益平衡問(wèn)題（，收益約束）網(wǎng)絡(luò)配送問(wèn)題（=，確定需求約束）混合問(wèn)題（包含兩種或三種類型的約束函數(shù)）本節(jié)按照應(yīng)用方面介紹線性規(guī)劃在生產(chǎn)計(jì)劃問(wèn)題、資金管理問(wèn)題、市場(chǎng)調(diào)查問(wèn)題和混合配料問(wèn)題等方面的應(yīng)用3.5線性規(guī)劃模型的應(yīng)用建立線性規(guī)劃模型的過(guò)程可以分為四個(gè)步驟：設(shè)立決策變量；用決策變量的線性函數(shù)表示目標(biāo)，并確定是求最大（Max）還是最?。∕in）；明確約束條件并用決策變量的線性等式或不等式表示；根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。3.5線性規(guī)劃模型的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題是企業(yè)生產(chǎn)過(guò)程中常常遇到的問(wèn)題，其中最簡(jiǎn)單的一種形式可以描述如下（資源分配問(wèn)題）：用若干種原材料（資源）生產(chǎn)某幾種產(chǎn)品，原材料（或某種資源）供應(yīng)量有一定的限制，要求制定一個(gè)產(chǎn)品生產(chǎn)計(jì)劃，使其在給定的資源限制條件下能得到最大收益。3.5線性規(guī)劃模型的應(yīng)用例3.5某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。有關(guān)情況的數(shù)據(jù)如表3-9所示。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄件由本公司鑄造和由外包協(xié)作各應(yīng)多少件？3.5線性規(guī)劃模型的應(yīng)用表3-9自行生產(chǎn)或外包的有關(guān)數(shù)據(jù)產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙工時(shí)限制單件鑄造工時(shí)（小時(shí)）51078000單件機(jī)加工工時(shí)（小時(shí)）64812000單件裝配工時(shí)（小時(shí)）32210000自產(chǎn)鑄件成本（元/件）354外協(xié)鑄件成本（元/件）56－機(jī)加工成本（元/件）213裝配成本（元/件）322產(chǎn)品售價(jià)（元/件）2318163.5線性規(guī)劃模型的應(yīng)用解：（1）決策變量此問(wèn)題的難度是由于產(chǎn)品甲和乙的鑄件既可以外包協(xié)作，也可以自行生產(chǎn)，從而使問(wèn)題復(fù)雜化。如果只設(shè)甲、乙、丙產(chǎn)品的產(chǎn)量分別為x1、x2、x3，則由于產(chǎn)品甲和乙的鑄件來(lái)源不同造成單位利潤(rùn)不同，因此目標(biāo)函數(shù)中x1和x2的系數(shù)不是常數(shù)，目標(biāo)函數(shù)成為非線性函數(shù)，但是如果把它們區(qū)分開(kāi)來(lái)，另設(shè)兩個(gè)變量，則可以較容易地建立問(wèn)題的線性規(guī)劃模型。設(shè)x1、x2、x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)；x4、x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。3.5線性規(guī)劃模型的應(yīng)用（2）目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是使得公司獲得的總利潤(rùn)最大。為了建立目標(biāo)函數(shù)，首先計(jì)算各決策變量的單位利潤(rùn)：?jiǎn)挝焕麧?rùn)＝售價(jià)-成本（鑄造、機(jī)加工、裝配）3.5線性規(guī)劃模型的應(yīng)用（3）約束條件（3個(gè)資源約束、非負(fù)約束） ①鑄造工時(shí)限制 ②機(jī)加工工時(shí)限制 ③裝配工時(shí)限制 ④非負(fù)3.5線性規(guī)劃模型的應(yīng)用數(shù)學(xué)模型（線性規(guī)劃模型）3.5線性規(guī)劃模型的應(yīng)用電子表格模型3.5線性規(guī)劃模型的應(yīng)用例3.7某公司根據(jù)訂單進(jìn)行生產(chǎn)。已知半年內(nèi)對(duì)某產(chǎn)品的需求量、單位生產(chǎn)費(fèi)用和單位存儲(chǔ)費(fèi)用,還已知公司每月的生產(chǎn)能力為100，每月倉(cāng)庫(kù)容量為50。問(wèn)：如何確定產(chǎn)品未