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

Chapter4.

LinearProgramming:FormulationandApplications第四章.線性規(guī)劃：建模與應(yīng)用運(yùn)籌學(xué)線性規(guī)劃模型滿足以下三個(gè)條件的模型稱為線性規(guī)劃模型每一個(gè)問題都用一組決策變量(通常非負(fù))表示某一方案，這組決策變量的值就代表一個(gè)具體方案存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來表示，按照問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化線性規(guī)劃模型的一般形式線性規(guī)劃問題的分類資源分配問題(resource-allocation)：資源約束。偉恩德玻璃制品公司產(chǎn)品組合問題成本收益平衡問題(cost-benefit-trade-off)：收益約束。利博公司廣告組合問題，大沼澤地金色年代公司的現(xiàn)金流問題網(wǎng)絡(luò)配送問題(distribution-network)：確定需求約束?；旌蠁栴}(mix)：多種約束。線性規(guī)劃建模與應(yīng)用超級食品公司的廣告組合問題資源分配問題和夢大發(fā)展公司的資金預(yù)算問題成本收益平衡問題和聯(lián)合航空公司問題網(wǎng)絡(luò)配送問題和大M公司超級食品公司案例的再研究混合問題和賽維特公司固體廢棄物回收問題主要內(nèi)容超級食品公司的廣告組合問題目標(biāo)：為早點(diǎn)谷類食品“脆始”設(shè)計(jì)出具有獎勵性的商業(yè)計(jì)劃該產(chǎn)品三種最有效的廣告媒介是星期六上午兒童節(jié)目的電視廣告食品與家庭導(dǎo)向的雜志上的廣告主要報(bào)紙星期天增刊上的廣告該問題的有限資源如下廣告預(yù)算400萬美元計(jì)劃預(yù)算100萬美元可獲得的電視廣告時(shí)段有5個(gè)單位超級食品公司的廣告組合問題廣告受眾的期望數(shù)量作為問題的總績效測度確定各種媒介的廣告力度以獲得最有效的廣告組合？成本和廣告受眾數(shù)據(jù)成本（美元）成本分類每次電視廣告每份雜志廣告每份星期天增刊廣告廣告預(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.電子表格模型超級食品公司問題探討假設(shè)是否合理？數(shù)學(xué)模型是否和實(shí)際問題相吻合？可行域的小數(shù)問題正比的線性關(guān)系是否成立？不同媒介之間是否相關(guān)？目標(biāo)函數(shù)的選取是否可行？市場細(xì)分的問題促銷優(yōu)惠券的問題模型需要不斷完善?。【€性規(guī)劃建模與應(yīng)用資源分配問題資源分配問題是將有限的資源分配到各種活動中去的線性規(guī)劃問題。共性在于函數(shù)約束均可表現(xiàn)為： 使用的資源數(shù)量≤可用的資源數(shù)量確定資源、資源可用量、活動、活動水平、活動消耗的資源數(shù)量以及活動對績效測度的貢獻(xiàn)等目標(biāo)就是在滿足資源限制的條件下使活動水平能夠最大化所選擇的績效測度資源分配問題決策變量是活動水平活動水平與績效測度的貢獻(xiàn)成正比活動水平與資源使用量成正比需要確定三類數(shù)據(jù)：資源可用量、單位活動消耗的資源量和單位活動對績效測度的貢獻(xiàn)量線性規(guī)劃建模與應(yīng)用夢大發(fā)展公司的資金預(yù)算問題夢大發(fā)展公司是商務(wù)房地產(chǎn)開發(fā)項(xiàng)目的主要投資商他們正在考慮三個(gè)大型的建筑項(xiàng)目建造高層辦公樓建造賓館建造購物中心每個(gè)項(xiàng)目都要求投資者在四個(gè)不同時(shí)期投資：在當(dāng)前預(yù)付定金，以及一年、二年、三年后分別追加投資夢大發(fā)展公司的資金預(yù)算問題夢大公司要在每個(gè)項(xiàng)目中投資多少百分比，才能獲得最大收益？目前2500萬美元可供投資，一年后2000萬美元，兩年后2000萬美元，三年后1500萬各項(xiàng)目的財(cái)務(wù)數(shù)據(jù)所需投資資金（百萬美元）Year辦公樓項(xiàng)目賓館項(xiàng)目購物中心項(xiàng)目0$40$80$90160805029080203107060Netpresentvalue$45$70$50數(shù)學(xué)模型假定OB=辦公樓項(xiàng)目中的投資比例,

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

SC=購物中心項(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資源分配問題的建模步驟總結(jié)：確定當(dāng)前問題的活動類型確定一個(gè)合適的總體績效測度，通常為利潤估計(jì)每一種活動對于總績效測度的單位貢獻(xiàn)明確分配給各種活動的有限資源對于每一種資源，確定可獲得的數(shù)量以及各種活動的單位使用量把第3步和第5步中的數(shù)據(jù)錄入數(shù)據(jù)單元格Summary指定可變單元格來顯示活動水平的決策變量在表示資源的每一行中，使用SUMPRODUCT函數(shù)計(jì)算總的資源使用量，在兩個(gè)連續(xù)單元格中輸入≤符號和可用資源量指定目標(biāo)單元格，使用SUMPRODUCT函數(shù)計(jì)算績效測度聯(lián)合航空公司問題聯(lián)合航空公司正準(zhǔn)備增加其中心機(jī)場的往來航班，因此需要雇用更多的客戶服務(wù)代理商五個(gè)審定的8小時(shí)輪班如下Shift1: 6:00AMto2:00PMShift2: 8:00AMto4:00PMShift3: Noonto8:00PMShift4: 4:00PMtomidnightShift5: 10:00PMto6:00AM聯(liá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)電子表格成本收益平衡問題成本收益問題是通過選擇各種活動水平的組合，以最小的成本來實(shí)現(xiàn)最低可接受的各種收益的一類線性規(guī)劃問題。共性在于函數(shù)約束均可表現(xiàn)為 完成的水平≥最低可接受水平指明每種收益的最低可接受水平，以及實(shí)現(xiàn)收益的最小成本，獲得成本與收益之間的適度平衡成本收益平衡問題需要的三類數(shù)據(jù)：每種收益的最低可接受水平、每種活動對每一收益的貢獻(xiàn)、每種活動的單位成本Summary成本收益平衡問題建模步驟的總結(jié)確定當(dāng)前問題的活動類型確定一個(gè)合適的總體績效測度，通常為成本估計(jì)每一種活動對于總績效測度的單位貢獻(xiàn)確定必須取得的收益對于每一項(xiàng)收益，確定其最小可接受水平和每項(xiàng)活動對該收益的貢獻(xiàn)大小Summary將第3步和第5步的數(shù)據(jù)輸入數(shù)據(jù)單元格指定可變單元格用于顯示決策變量在表示收益的每一行中，用SUMPRODUCT函數(shù)計(jì)算獲得的收益水平，在兩個(gè)連續(xù)的單元格中輸入≥號和最小可接受水平)指定一個(gè)目標(biāo)單元格，用SUMPRODUCT函數(shù)計(jì)算其績效測度大M公司網(wǎng)絡(luò)配送問題大M公司在兩個(gè)工廠生產(chǎn)一系列中型機(jī)器，產(chǎn)品之一是一種大型的六角車床該六角車床的訂單來自于3個(gè)客戶大M公司網(wǎng)絡(luò)配送問題應(yīng)該從每一個(gè)工廠運(yùn)載多少車床到每一個(gè)客戶？)有關(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ǎng)絡(luò)問題的函數(shù)約束是確定的需求約束，可表示為： 提供的數(shù)量=需要的數(shù)量線性規(guī)劃建模與應(yīng)用超級食品公司案例的再研究大衛(wèi)和克萊略認(rèn)為公司的電子表格模型還需要進(jìn)一步擴(kuò)展以增加一些考慮事項(xiàng)他們尤其覺得必須將目標(biāo)觀眾定位為兒童及他們的家長兩個(gè)新的目標(biāo)必須至少有500百萬兒童看到該廣告必須至少有500萬兒童家長看到該廣告而且正好還有149萬美元的預(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)

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

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

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

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

使用的數(shù)量≤

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

達(dá)到的水平≥

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

提供的數(shù)量=

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

*LHS=Left-handside(aSUMPRODUCTfunction).

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

材料每周可獲得的數(shù)量（磅）每磅處理成本（美元）附加約束13,000$3.001.對于每種材料，每周必須至少收集并處理一半以上數(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é)描述可獲得的材料: