Chapter04-線性規(guī)劃：建模與應(yīng)用

Chapter4.

LinearProgramming:FormulationandApplications第四章.線性規(guī)劃：建模與應(yīng)用運(yùn)籌學(xué)線性規(guī)劃模型滿(mǎn)足以下三個(gè)條件的模型稱(chēng)為線性規(guī)劃模型每一個(gè)問(wèn)題都用一組決策變量(通常非負(fù))表示某一方案，這組決策變量的值就代表一個(gè)具體方案存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)(稱(chēng)為目標(biāo)函數(shù))來(lái)表示，按照問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化線性規(guī)劃模型的一般形式線性規(guī)劃問(wèn)題的分類(lèi)資源分配問(wèn)題(resource-allocation)：資源約束。偉恩德玻璃制品公司產(chǎn)品組合問(wèn)題成本收益平衡問(wèn)題(cost-benefit-trade-off)：收益約束。利博公司廣告組合問(wèn)題，大沼澤地金色年代公司的現(xiàn)金流問(wèn)題網(wǎng)絡(luò)配送問(wèn)題(distribution-network)：確定需求約束?；旌蠁?wèn)題(mix)：多種約束。線性規(guī)劃建模與應(yīng)用超級(jí)食品公司的廣告組合問(wèn)題資源分配問(wèn)題和夢(mèng)大發(fā)展公司的資金預(yù)算問(wèn)題成本收益平衡問(wèn)題和聯(lián)合航空公司問(wèn)題網(wǎng)絡(luò)配送問(wèn)題和大M公司超級(jí)食品公司案例的再研究混合問(wèn)題和賽維特公司固體廢棄物回收問(wèn)題主要內(nèi)容超級(jí)食品公司的廣告組合問(wèn)題目標(biāo)：為早點(diǎn)谷類(lèi)食品“脆始”設(shè)計(jì)出具有獎(jiǎng)勵(lì)性的商業(yè)計(jì)劃該產(chǎn)品三種最有效的廣告媒介是星期六上午兒童節(jié)目的電視廣告食品與家庭導(dǎo)向的雜志上的廣告主要報(bào)紙星期天增刊上的廣告該問(wèn)題的有限資源如下廣告預(yù)算400萬(wàn)美元計(jì)劃預(yù)算100萬(wàn)美元可獲得的電視廣告時(shí)段有5個(gè)單位超級(jí)食品公司的廣告組合問(wèn)題廣告受眾的期望數(shù)量作為問(wèn)題的總績(jī)效測(cè)度確定各種媒介的廣告力度以獲得最有效的廣告組合？成本和廣告受眾數(shù)據(jù)成本（美元）成本分類(lèi)每次電視廣告每份雜志廣告每份星期天增刊廣告廣告預(yù)算$300,000$150,000$100,000規(guī)劃預(yù)算90,00030,00040,000廣告受眾期望量1,300,000600,000500,000數(shù)學(xué)模型設(shè)定TV=電視上的廣告時(shí)段數(shù)目M=雜志上的廣告數(shù)目

SS=星期天增刊上的廣告數(shù)目

最大化廣告受眾量MaximizeExposure=1,300TV+600M+500SS約束 廣告總費(fèi)用300TV+150M+100SS≤4,000($thousand)

計(jì)劃總成本90TV+30M+30SS≤1,000($thousand)

電視廣告的時(shí)段數(shù)目

TV≤5

TV≥0,M≥0,SS≥0.電子表格模型超級(jí)食品公司問(wèn)題探討假設(shè)是否合理？數(shù)學(xué)模型是否和實(shí)際問(wèn)題相吻合？可行域的小數(shù)問(wèn)題正比的線性關(guān)系是否成立？不同媒介之間是否相關(guān)？目標(biāo)函數(shù)的選取是否可行？市場(chǎng)細(xì)分的問(wèn)題促銷(xiāo)優(yōu)惠券的問(wèn)題模型需要不斷完善！！線性規(guī)劃建模與應(yīng)用資源分配問(wèn)題資源分配問(wèn)題是將有限的資源分配到各種活動(dòng)中去的線性規(guī)劃問(wèn)題。共性在于函數(shù)約束均可表現(xiàn)為： 使用的資源數(shù)量≤可用的資源數(shù)量確定資源、資源可用量、活動(dòng)、活動(dòng)水平、活動(dòng)消耗的資源數(shù)量以及活動(dòng)對(duì)績(jī)效測(cè)度的貢獻(xiàn)等目標(biāo)就是在滿(mǎn)足資源限制的條件下使活動(dòng)水平能夠最大化所選擇的績(jī)效測(cè)度資源分配問(wèn)題決策變量是活動(dòng)水平活動(dòng)水平與績(jī)效測(cè)度的貢獻(xiàn)成正比活動(dòng)水平與資源使用量成正比需要確定三類(lèi)數(shù)據(jù)：資源可用量、單位活動(dòng)消耗的資源量和單位活動(dòng)對(duì)績(jī)效測(cè)度的貢獻(xiàn)量線性規(guī)劃建模與應(yīng)用夢(mèng)大發(fā)展公司的資金預(yù)算問(wèn)題夢(mèng)大發(fā)展公司是商務(wù)房地產(chǎn)開(kāi)發(fā)項(xiàng)目的主要投資商他們正在考慮三個(gè)大型的建筑項(xiàng)目建造高層辦公樓建造賓館建造購(gòu)物中心每個(gè)項(xiàng)目都要求投資者在四個(gè)不同時(shí)期投資：在當(dāng)前預(yù)付定金，以及一年、二年、三年后分別追加投資夢(mèng)大發(fā)展公司的資金預(yù)算問(wèn)題夢(mèng)大公司要在每個(gè)項(xiàng)目中投資多少百分比，才能獲得最大收益？目前2500萬(wàn)美元可供投資，一年后2000萬(wàn)美元，兩年后2000萬(wàn)美元，三年后1500萬(wàn)各項(xiàng)目的財(cái)務(wù)數(shù)據(jù)所需投資資金（百萬(wàn)美元）Year辦公樓項(xiàng)目賓館項(xiàng)目購(gòu)物中心項(xiàng)目0$40$80$90160805029080203107060Netpresentvalue$45$70$50數(shù)學(xué)模型假定OB=辦公樓項(xiàng)目中的投資比例,

H=賓館項(xiàng)目中的投資比例,

SC=購(gòu)物中心項(xiàng)目中的投資比例.

最大化總投資凈現(xiàn)值

MaximizeNPV=45OB+70H+50SCSubjectto(約束)

現(xiàn)期總投資:40OB+80H+90SC≤25($million)

一年后的總投資:100OB+160H+140SC≤45($million)

兩年后的總投資:190OB+240H+160SC≤65($million)

三年后的總投資:200OB+310H+220SC≤80($million)

OB≥0,H≥0,SC≥0.電子表格Summary資源分配問(wèn)題的建模步驟總結(jié)：確定當(dāng)前問(wèn)題的活動(dòng)類(lèi)型確定一個(gè)合適的總體績(jī)效測(cè)度，通常為利潤(rùn)估計(jì)每一種活動(dòng)對(duì)于總績(jī)效測(cè)度的單位貢獻(xiàn)明確分配給各種活動(dòng)的有限資源對(duì)于每一種資源，確定可獲得的數(shù)量以及各種活動(dòng)的單位使用量把第3步和第5步中的數(shù)據(jù)錄入數(shù)據(jù)單元格Summary指定可變單元格來(lái)顯示活動(dòng)水平的決策變量在表示資源的每一行中，使用SUMPRODUCT函數(shù)計(jì)算總的資源使用量，在兩個(gè)連續(xù)單元格中輸入≤符號(hào)和可用資源量指定目標(biāo)單元格，使用SUMPRODUCT函數(shù)計(jì)算績(jī)效測(cè)度聯(lián)合航空公司問(wèn)題聯(lián)合航空公司正準(zhǔn)備增加其中心機(jī)場(chǎng)的往來(lái)航班，因此需要雇用更多的客戶(hù)服務(wù)代理商五個(gè)審定的8小時(shí)輪班如下Shift1: 6:00AMto2:00PMShift2: 8:00AMto4:00PMShift3: Noonto8:00PMShift4: 4:00PMtomidnightShift5: 10:00PMto6:00AM聯(lián)合航空公司人員安排問(wèn)題每個(gè)輪班需要安排多少人？排程數(shù)據(jù)輪班的時(shí)段時(shí)段12345最少需要代理商的數(shù)量6AMto8AM√488AMto10AM√√7910AMtonoon√√65Noonto2PM√√√872PMto4PM√√644PMto6PM√√736PMto8PM√√828PMto10PM√4310PMtomidnight√√52Midnightto6AM√15Dailycostperagent$170$160$175$180$195數(shù)學(xué)描述假定 Si=Numberworkingshifti(fori=1to5),

最小化 Cost=$170S1+$160S2+$175S3+$180S4+$195S5

Subjectto(約束)

Totalagents6AM–8AM: S1≥48

Totalagents8AM–10AM: S1+S2≥79

Totalagents10AM–12PM:S1+S2≥65

Totalagents12PM–2PM: S1+S2+S3≥87

Totalagents2PM–4PM: S2+S3≥64

Totalagents4PM–6PM: S3+S4≥73數(shù)學(xué)描述Subjectto(約束)

Totalagents4PM–6PM: S3+S4≥73

Totalagents6PM–8PM: S3+S4≥82

Totalagents8PM–10PM:S4≥43

Totalagents10PM–12AM:S4+S5≥52

Totalagents12AM–6AM:S5≥15

and

Si≥0(fori=1to5)電子表格成本收益平衡問(wèn)題成本收益問(wèn)題是通過(guò)選擇各種活動(dòng)水平的組合，以最小的成本來(lái)實(shí)現(xiàn)最低可接受的各種收益的一類(lèi)線性規(guī)劃問(wèn)題。共性在于函數(shù)約束均可表現(xiàn)為 完成的水平≥最低可接受水平指明每種收益的最低可接受水平，以及實(shí)現(xiàn)收益的最小成本，獲得成本與收益之間的適度平衡成本收益平衡問(wèn)題需要的三類(lèi)數(shù)據(jù)：每種收益的最低可接受水平、每種活動(dòng)對(duì)每一收益的貢獻(xiàn)、每種活動(dòng)的單位成本Summary成本收益平衡問(wèn)題建模步驟的總結(jié)確定當(dāng)前問(wèn)題的活動(dòng)類(lèi)型確定一個(gè)合適的總體績(jī)效測(cè)度，通常為成本估計(jì)每一種活動(dòng)對(duì)于總績(jī)效測(cè)度的單位貢獻(xiàn)確定必須取得的收益對(duì)于每一項(xiàng)收益，確定其最小可接受水平和每項(xiàng)活動(dòng)對(duì)該收益的貢獻(xiàn)大小Summary將第3步和第5步的數(shù)據(jù)輸入數(shù)據(jù)單元格指定可變單元格用于顯示決策變量在表示收益的每一行中，用SUMPRODUCT函數(shù)計(jì)算獲得的收益水平，在兩個(gè)連續(xù)的單元格中輸入≥號(hào)和最小可接受水平)指定一個(gè)目標(biāo)單元格，用SUMPRODUCT函數(shù)計(jì)算其績(jī)效測(cè)度大M公司網(wǎng)絡(luò)配送問(wèn)題大M公司在兩個(gè)工廠生產(chǎn)一系列中型機(jī)器，產(chǎn)品之一是一種大型的六角車(chē)床該六角車(chē)床的訂單來(lái)自于3個(gè)客戶(hù)大M公司網(wǎng)絡(luò)配送問(wèn)題應(yīng)該從每一個(gè)工廠運(yùn)載多少車(chē)床到每一個(gè)客戶(hù)？)有關(guān)數(shù)據(jù)單位運(yùn)輸成本（美元）To顧客1顧客2顧客3From運(yùn)出工廠1$700$900$80012lathes工廠280090070015lathes訂貨量10lathes8lathes9lathes配送網(wǎng)絡(luò)數(shù)學(xué)模型假定Sij=Numberoflathestoshipfromitoj

(i=F1,F2;j=C1,C2,C3)最小化Cost=$700SF1-C1+$900SF1-C2+$800SF1-C3+ $800SF2-C1+$900SF2-C2+$700SF2-C3數(shù)學(xué)模型subjectto(約束)

Factory1: SF1-C1+SF1-C2+SF1-C3=12

Factory2: SF2-C1+SF2-C2+SF2-C3=15

Customer1:SF1-C1+SF2-C1=10

Customer2:SF1-C2+SF2-C2=8

Customer3:SF1-C3+SF2-C3=9

and

Sij≥0(i=F1,F2;j=C1,C2,C3).電子表格模型配送網(wǎng)絡(luò)問(wèn)題配送網(wǎng)絡(luò)問(wèn)題的函數(shù)約束是確定的需求約束，可表示為： 提供的數(shù)量=需要的數(shù)量線性規(guī)劃建模與應(yīng)用超級(jí)食品公司案例的再研究大衛(wèi)和克萊略認(rèn)為公司的電子表格模型還需要進(jìn)一步擴(kuò)展以增加一些考慮事項(xiàng)他們尤其覺(jué)得必須將目標(biāo)觀眾定位為兒童及他們的家長(zhǎng)兩個(gè)新的目標(biāo)必須至少有500百萬(wàn)兒童看到該廣告必須至少有500萬(wàn)兒童家長(zhǎng)看到該廣告而且正好還有149萬(wàn)美元的預(yù)算可以分配到商家優(yōu)惠卷修正的收益和需求數(shù)據(jù)數(shù)學(xué)模型假定TV=電視上的廣告時(shí)段數(shù)目

M=雜志上的廣告數(shù)目

SS=星期天增刊上的廣告數(shù)目Maximize(最大化廣告受眾量)

Exposure=1,300TV+600M+500SS數(shù)學(xué)模型subjectto(約束)

廣告花費(fèi):300TV+150M+100SS≤4,000($thousand)

計(jì)劃成本:90TV+30M+30SS≤1,000($thousand)

TV廣告時(shí)段數(shù):TV≤5

兒童:1.2TV+0.1M≥5(millions)

家長(zhǎng):0.5TV+0.2M+0.2SS≥5(millions)

優(yōu)惠卷:40M+120SS=1,490($thousand)and

TV≥0,M≥0,SS≥0.電子表格各類(lèi)函數(shù)約束類(lèi)型形式解釋

主要應(yīng)用資源約束LHS≤RHS對(duì)于特定的資源,

使用的數(shù)量≤

可獲得的數(shù)量資源分配問(wèn)題混合問(wèn)題收益約束LHS≥RHS對(duì)于特定的收益,

達(dá)到的水平≥

最低可接受水平成本收益平衡問(wèn)題混合問(wèn)題確定需求約束LHS=RHS對(duì)于一些數(shù)量,

提供的數(shù)量=

需求的數(shù)量網(wǎng)絡(luò)配送問(wèn)題混合問(wèn)題

*LHS=Left-handside(aSUMPRODUCTfunction).

RHS=Right-handside(aconstant).混合問(wèn)題混合問(wèn)題也是一類(lèi)典型的線性規(guī)劃問(wèn)題，它包含的約束是多種多樣的，即可能有資源約束，也可能有收益約束，還可能有確定需求的約束線性規(guī)劃建模與應(yīng)用賽維特公司經(jīng)營(yíng)一個(gè)回收中心，專(zhuān)門(mén)從事四種固體廢棄物的回收，并將回收物處理、混合成為可銷(xiāo)售的產(chǎn)品不同的原料混合，一共可以生成3種不同等級(jí)的產(chǎn)品：A、B和C賽維特公司固體廢棄物回收問(wèn)題賽維特公司固體廢棄物回收問(wèn)題四種原料各應(yīng)使用多少？三種不同等級(jí)的產(chǎn)品各應(yīng)生產(chǎn)多少？賽維特公司的產(chǎn)品數(shù)據(jù)等級(jí)規(guī)格說(shuō)明每磅的混合成本每磅的售價(jià)A材料1:不超過(guò)總量的30%材料2:不少于總量的40%材料3:不超過(guò)總量的50%材料4:總量的20%$3.00$8.50B材料1:不超過(guò)總量的50%材料2:不少于總量的10%材料4:總量的10%2.507.00C材料1:不超過(guò)總量的70%2.005.50賽維特公司固體廢棄物的有關(guān)數(shù)據(jù)

材料每周可獲得的數(shù)量（磅）每磅處理成本（美元）附加約束13,000$3.001.對(duì)于每種材料，每周必須至少收集并處理一半以上數(shù)量.

2.每周有30000美元可用于處理這些材料.22,0006.0034,0004.0041,0005.00數(shù)學(xué)描述假定xij=每周原料j分配給產(chǎn)品i的數(shù)量(i=A,B,C;j=1,2,3,4)最大化收益MaximizeProfit=5.5(xA1+xA2+xA3+xA4)+4.5(xB1+xB2+xB3+xB4)+ 3.5(xC1+xC2+xC3+xC4)數(shù)學(xué)描述subjectto(約束)混合比例規(guī)定: xA1≤0.3(xA1+xA2+xA3+xA4) xA2≥0.4(xA1+xA2+xA3+xA4) xA3≤0.5(xA1+xA2+xA3+xA4) xA4=0.2(xA1+xA2+xA3+xA4) xB1≤0.5(xB1+xB2+xB3+xB4) xB2≥0.1(xB1+xB2+xB3+xB4) xB4=0.1(xB1+xB2+xB3+xB4) xC1≤0.7(xC1+xC2+xC3+xC4)數(shù)學(xué)描述可獲得的材料: