三章線性建模與應(yīng)用

第三章線性規(guī)劃：建模與應(yīng)用超級(jí)食品公司的廣告混合問題(3.1節(jié)) 資源分配問題&Think-Big的資金預(yù)算(3.2節(jié)) 成本-收益平衡問題&UnionAirways(3.3節(jié)) 網(wǎng)絡(luò)配送問題&Big公司(3.4節(jié)) 超級(jí)食品公司案例的再研究(3.5節(jié)) 混合建模&回收固體廢棄物(3.6節(jié))

KeyCategoriesofLPProblems

線性規(guī)劃問題主要類型資源分配問題（resource-allocation）成本收益平衡問題（cost-benefit-trade-off）網(wǎng)絡(luò)配送問題（distribution-network）混合問題（mixedProblem）超級(jí)食品公司的廣告混合問題目標(biāo):為“脆始”設(shè)計(jì)促銷運(yùn)動(dòng)對(duì)于這種產(chǎn)品的三個(gè)最有效率的廣告媒體是：星期六上午兒童廣告節(jié)目的電視廣告.食品與家庭導(dǎo)向的雜志上的廣告.主要報(bào)紙星期增刊上的廣告該問題的三種有限資源分別為：廣告預(yù)算(4百萬(wàn)美元).計(jì)劃預(yù)算(100萬(wàn)美元).可獲得的電視廣告段(5).目標(biāo)通過期望受眾數(shù)據(jù)來度量.問題:在這三種媒體中每一種的廣告的投入應(yīng)該在什么水平上？成本與廣告受眾數(shù)據(jù)CostsCostCategoryEach

TVCommercialEach

MagazineAdEach

SundayAdAdBudget$300,000$150,000$100,000Planningbudget90,00030,00040,000Expectednumberofexposures1,300,000600,000500,000代數(shù)建模令TV=電視上的廣告時(shí)段數(shù)目

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

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

Max受眾時(shí)間=1,300TV+600M+500SS

st

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

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

電視廣告時(shí)段的數(shù)目: TV≤5且

TV≥0,M≥0,SS≥0.電子表格建模Resource-allocationProblem

資源分配問題

資源分配（resource-allocation）問題是將有限的資源分配到各種活動(dòng)中去的線性規(guī)劃問題。這一類問題的共性是在線性規(guī)劃模型中每一個(gè)函數(shù)限制均為資源限制(resourceconstraint),并且每一種有限資源都可以表現(xiàn)為如下的形式：

使用的資源數(shù)量

可用的資源數(shù)量

問題類型DataGathering

收集數(shù)據(jù)所有活動(dòng)可獲得使用的每種資源的有限數(shù)量每一種活動(dòng)所需要的各種資源的數(shù)量每一種資源與活動(dòng)的組合單位活動(dòng)消耗資源量必須首先估計(jì)每一種活動(dòng)對(duì)總的績(jī)效測(cè)度的單位貢獻(xiàn)

夢(mèng)大資金分配問題夢(mèng)大發(fā)展公司是一個(gè)商務(wù)房地產(chǎn)開發(fā)項(xiàng)目的主要的投資者。他們正在考慮三個(gè)大的建設(shè)項(xiàng)目建設(shè)一個(gè)高層辦公樓.建設(shè)賓館.建設(shè)購(gòu)物中心.每個(gè)項(xiàng)目都要求投資者在四個(gè)不同的時(shí)期投資；在當(dāng)前預(yù)付定金，以及一年，兩年，三年后分別追加投資。問題:夢(mèng)大公司在三個(gè)項(xiàng)目中的每個(gè)項(xiàng)目上投資的比例是多少？項(xiàng)目的財(cái)務(wù)數(shù)據(jù)InvestmentCapitalRequirementsYearOfficeBuildingHotelShoppingCenter0$40million$80million$90million160million80million50million290million80million20million310million70million60millionNetpresentvalue$45million$70million$50million代數(shù)建模令OB=辦公樓項(xiàng)目中的投資比例

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

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

MaxNPV=45OB+70H+50SC

st

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

一年后的總投資: 100OB+160H+140SC≤45 Total兩年后的總投資: 190OB+240H+160SC≤65 Total三年后的總投資: 200OB+310H+220SC≤80且

OB≥0,H≥0,SC≥0.電子表格建模資源分配問題建模的總結(jié)確認(rèn)問題的活動(dòng)類型.明確合適的績(jī)效測(cè)度以求解問題(一般以利潤(rùn)測(cè)度).估計(jì)每一種活動(dòng)對(duì)于總績(jī)效測(cè)度的單位貢獻(xiàn).明確分配給各種活動(dòng)的有限資源.對(duì)于每種資源，明確可獲得的數(shù)量以及各種活動(dòng)的單位使用量.在步驟3和5種輸入數(shù)據(jù)。指定可變單元格來顯示活動(dòng)水平的決策量在表示每種資源的列種,使用SUMPRODUCT函數(shù)來計(jì)算使用的總數(shù)量，在兩個(gè)臨近單元格中可以利用的數(shù)量輸入≤。指派目標(biāo)單元格，使用SUMPRODUCT函數(shù)來輸入總的績(jī)效測(cè)度。聯(lián)合航空公司的員工排程聯(lián)合航空公司正在準(zhǔn)備增加其中心機(jī)場(chǎng)的往來航班，所以需要雇傭的顧客服務(wù)代理商。5格授權(quán)的8小時(shí)的換班是輪班1: 6:00AMto2:00PM輪班2: 8:00AMto4:00PM輪班3: 中午to8:00PM輪班4: 4:00PMtomidnight輪班5: 10:00PMto6:00AM問題:每一個(gè)輪班應(yīng)該指派多少格代理商？排程數(shù)據(jù)TimePeriodsCoveredbyShiftTimePeriod12345Minimum

Numberof

AgentsNeeded6AMto8AM√488AMto10AM√√7910AMtonoon√√65Noonto2PM√√√872PMto4PM√√644PMto6PM√√736PMto8PM√√828PMto10PM√4310PMtomidnight√√52Midnightto6AM√15Dailycostperagent$170$160$175$180$195代數(shù)建模令Si=分派到輪班i的代理商數(shù)目(fori=1to5),

MinCost=$170S1+$160S2+$175S3+$180S4+$195S5

st 6AM–8AM之間的總代理商數(shù): S1≥48

8AM–10AM之間的總代理商數(shù):S1+S2≥79

10AM–12PM之間的總代理商數(shù): S1+S2≥65

12PM–2PM之間的總代理商數(shù): S1+S2+S3≥87

2PM–4PM之間的總代理商數(shù): S2+S3≥64

4PM–6PM之間的總代理商數(shù): S3+S4≥73

6PM–8PM之間的總代理商數(shù): S3+S4≥82

8PM–10PM之間的總代理商數(shù): S4≥43

10PM–12AM之間的總代理商數(shù): S4+S5≥52

12AM–6AM之間的總代理商數(shù): S5≥15

且

Si≥0(fori=1to5)電子表格建模Cost-benefit-trade-offProblem

成本收益平衡問題成本收益平衡問題（Cost-benefit-trade-offProblem

）是一類線性規(guī)劃問題，這類問題中，通過選擇各種活動(dòng)水平的組合，從而以最小的成本來實(shí)現(xiàn)最低可接受的各種收益的水平。這類問題的共性是，所有的函數(shù)約束均為收益約束，并具有如下的形式：

完成的水平

最低可接受的水平問題類型成本收益均衡問題的建模過程總結(jié)確認(rèn)問題的活動(dòng)類型.明確合適的績(jī)效測(cè)度以求解問題(一般以成本測(cè)度).估計(jì)每一種活動(dòng)對(duì)于總績(jī)效測(cè)度的單位貢獻(xiàn).明確每種收益最低可接受水平.明確每一種活動(dòng)對(duì)于對(duì)每種收益的貢獻(xiàn).在步驟3和5種輸入數(shù)據(jù)。指定可變單元格來顯示活動(dòng)水平的決策量使用SUMPRODUCT函數(shù)來計(jì)算使用的總數(shù)量，在兩個(gè)臨近單元格中可以利用的數(shù)量輸入≤。指派目標(biāo)單元格，使用SUMPRODUCT函數(shù)來輸入總的績(jī)效測(cè)度。4.20Distribution-networkProblem

網(wǎng)絡(luò)配送問題網(wǎng)絡(luò)配送問題（distributionnetwork）能以最小的成本完成貨物的配送，所以稱之為網(wǎng)絡(luò)配送問題并具有如下的確定性約束形式：

提供的數(shù)量＝需要的數(shù)量問題類型大M公司的網(wǎng)絡(luò)配送問題大M在兩個(gè)工廠生產(chǎn)一系列重型機(jī)器。產(chǎn)品之一就是大型車床收到了3個(gè)顧客的訂單需要購(gòu)買大型車床。問題:從每個(gè)工廠需要運(yùn)送多少大型車床到每個(gè)顧客？一些數(shù)據(jù)ShippingCostforEachLatheToCustomer1Customer2Customer3FromOutputFactory1$700$900$80012lathesFactory280090070015lathesOrderSize10lathes8lathes9lathes配送網(wǎng)絡(luò)代數(shù)建模

令Sij=從i到j(luò)運(yùn)送的機(jī)床的數(shù)目(i=F1,F2;j=C1,C2,C3).

MinCost=$700SF1-C1+$900SF1-C2+$800SF1-C3

+$800SF2-C1+$900SF2-C2+$700SF2-C3

st

工廠1: SF1-C1+SF1-C2+SF1-C3=12

工廠2: SF2-C1+SF2-C2+SF2-C3=15

顧客1: SF1-C1+SF2-C1=10

顧客2: SF1-C2+SF2-C2=8

顧客3: SF1-C3+SF2-C3=9

且

Sij≥0(i=F1,F2;j=C1,C2,C3).電子表格建模超級(jí)食品公司案例的再研究David和Claire得出結(jié)論：電子表格模型需要拓展從而包括一些附加的考慮事項(xiàng).特別地，他們覺得應(yīng)該將目標(biāo)定位為兒童及他們的家長(zhǎng)。兩個(gè)新的目標(biāo)廣告應(yīng)該至少有500萬(wàn)兒童看到.廣告至少至少有500萬(wàn)兒童的家長(zhǎng)看到.此外，有$1,490,000的商家優(yōu)惠券應(yīng)該分發(fā)出去。收益和固定需求的數(shù)據(jù)NumberReachedinTargetCategory(millions)Each

TVCommercialEach

MagazineAdEach

SundayAdMinimum

Acceptable

LevelYoungchildren1.20.105Parentsofyoungchildren0.50.20.25ContributionTowardRequiredAmountEach

TVCommercialEach

MagazineAdEach

SundayAdRequired

AmountCouponredemption0$40,000$120,000$1,490,000代數(shù)模型令TV=電視商的廣告時(shí)段數(shù)目

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

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

Max廣告受眾量=1,300TV+600M+500SS

st

廣告支出: 300TV+150M+100SS≤4,000($thousand)

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

電視廣告時(shí)段: TV≤5

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

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

確定需求約束: 40M+120SS=1,490($thousand)

且

TV≥0,M≥0,SS≥0.電子表格建模MixedProblem

混合問題問題類型資源分配問題，成本收益平衡問題以及網(wǎng)絡(luò)配送問題，都以一類約束條件為特色的純資源分配問題的共性是它所有的函數(shù)約束均為資源約束成本收益平衡問題的共性是它所有的函數(shù)約束均為收益約束網(wǎng)絡(luò)配送問題主要的函數(shù)約束為一特定類型的確定需求的約束混合問題

是第四類線性規(guī)劃問題，這一類型包括了三類約束函數(shù)

函數(shù)約束的類型總結(jié)類型形式解釋主要用于資源約束LHS

RHS對(duì)于特定的資源使用的數(shù)量

可獲得的數(shù)量資源分配問題混合問題收益約束LHS

RHS對(duì)于特定的收益達(dá)到的水平

最低可接受水平成本收益平衡問題混合問題需求確定約束LHS=RHS對(duì)于一些數(shù)量提供的數(shù)量=需求的數(shù)量網(wǎng)絡(luò)配送問題混合問題*LHS=Left-handside(aSUMPRODUCTfunction).

RHS=Right-handside(aconstant).回收固體廢棄物塞維特公司經(jīng)營(yíng)一個(gè)回收中心，專門從事四種固體廢棄物的回收，并將回收物處理，混合成為可銷售的產(chǎn)品.可將該產(chǎn)品分為不同的等級(jí)（根據(jù)混合時(shí)各種材料的比例）.問題：這三種產(chǎn)品每種產(chǎn)品應(yīng)該生產(chǎn)的數(shù)量應(yīng)該是多少？塞維特公司的產(chǎn)品數(shù)據(jù)GradeSpecificationAmalgamationCostperPoundSellingPriceperPoundAMaterial1:Notmorethan30%oftotal

Material2:Notlessthan40%oftotal

Material3:Notmorethan50%oftotal

Material4:Exactly20%oftotal$3.00$8.50BMaterial1:Notmorethan50%oftotal

Material2:Notlessthan10%ofthetotal

Material4:Exactly10%ofthetotal2.507.00CMaterial1:Notmorethan70%ofthetotal2.005.50塞維特公司的原材料數(shù)據(jù)

MaterialPounds/Week

AvailableTreatmentCost

perPound

AdditionalRestrictions13,000$3.001.Foreachmaterial,atleasthalfofthepounds/weekavailableshouldbecollectedandtreated.

2.$30,000perweekshouldbeusedtotreatthesematerials.22,0006.0034,0004.0041,0005.00代數(shù)建模令xij=每周物料j分配到產(chǎn)品

i

的數(shù)量(i=A,B,C;j=1,2,3,4).

Max利潤(rùn)=5.5(xA1+xA2+xA3+xA4)+4.5(xB1+xB2+xB3+xB4)+3.5(xC1+xC2+xC3+xC4)

st 混合的比例規(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)

可獲得的物料: xA1+xB1+xC1≤3,000

xA2+xB2+xC2≤2,000

xA3+xB3+xC3≤

4,000

xA4+xB4+xC4≤1,000

必須處理的數(shù)量的約束: xA1+xB1+xC1≥1,500

xA2+xB2+xC2≥1,000

xA3+xB3+xC3≥2,000

xA4+xB4+xC4≥500

處理成本的約束: 3(xA1+xB1+xC1)+6(xA2+xB2+xC2)

+4(xA3+xB3+xC3)+5(xA4+xB4+xC4)=30,000

且xij≥0(i=A,B,C;j=1,2,3,4).電子表格建模ModelingfromManagerialPerspective

管理視角的建?？偪?jī)效測(cè)度必須是管理層想獲得的現(xiàn)實(shí)目標(biāo)準(zhǔn)確細(xì)致地描述資源約束管理科學(xué)小組與管理層的有效溝通模型往往要不斷地修改和擴(kuò)展要進(jìn)行what-if分析ThreeClassicalApplicationsofLP

線性規(guī)劃問題的三個(gè)經(jīng)典應(yīng)用潘得羅索工業(yè)公司的產(chǎn)品組合考慮有限資源，確定產(chǎn)品的最佳組合公司的總利潤(rùn)增加了20%.聯(lián)合航空公司的員工排程為最有效率地滿足服務(wù)要求為所有地雇員設(shè)計(jì)工作日程安排.每年節(jié)約$6,000,000.Citgo石油公司供應(yīng)、配送與營(yíng)銷規(guī)劃SDM系統(tǒng)使用線性規(guī)劃協(xié)調(diào)全美的Citgo的主要產(chǎn)品的供應(yīng)，配送和營(yíng)銷.庫(kù)存減少導(dǎo)致Citgo公司每年利潤(rùn)增加$14,000,000.PonderosaIndustrial

潘德羅索工業(yè)公司潘德羅索應(yīng)用成功的因素：以自然語(yǔ)言為用戶界面的財(cái)務(wù)計(jì)劃系統(tǒng)，使用自然語(yǔ)言而不是數(shù)學(xué)符號(hào)來顯示線性規(guī)劃模型各個(gè)組成部分以及輸出的結(jié)果，使得做決策的管理者能夠很容易看懂整個(gè)過程。最優(yōu)化系統(tǒng)是互動(dòng)的（interactive），管理者在從一個(gè)版本的