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

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

KeyCategoriesofLPProblems

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

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

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

Max受眾時間=1,300TV+600M+500SS

st

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

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

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

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

資源分配問題

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

使用的資源數(shù)量

可用的資源數(shù)量

問題類型DataGathering

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

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

H=賓館項目中的投資比例,

SC=購物中心項目中的投資比例.

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é)確認問題的活動類型.明確合適的績效測度以求解問題(一般以利潤測度).估計每一種活動對于總績效測度的單位貢獻.明確分配給各種活動的有限資源.對于每種資源，明確可獲得的數(shù)量以及各種活動的單位使用量.在步驟3和5種輸入數(shù)據(jù)。指定可變單元格來顯示活動水平的決策量在表示每種資源的列種,使用SUMPRODUCT函數(shù)來計算使用的總數(shù)量，在兩個臨近單元格中可以利用的數(shù)量輸入≤。指派目標單元格，使用SUMPRODUCT函數(shù)來輸入總的績效測度。聯(lián)合航空公司的員工排程聯(lián)合航空公司正在準備增加其中心機場的往來航班，所以需要雇傭的顧客服務(wù)代理商。5格授權(quán)的8小時的換班是輪班1: 6:00AMto2:00PM輪班2: 8:00AMto4:00PM輪班3: 中午to8:00PM輪班4: 4:00PMtomidnight輪班5: 10:00PMto6:00AM問題:每一個輪班應(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ī)劃問題，這類問題中，通過選擇各種活動水平的組合，從而以最小的成本來實現(xiàn)最低可接受的各種收益的水平。這類問題的共性是，所有的函數(shù)約束均為收益約束，并具有如下的形式：

完成的水平

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

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

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

令Sij=從i到j(luò)運送的機床的數(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).電子表格建模超級食品公司案例的再研究David和Claire得出結(jié)論：電子表格模型需要拓展從而包括一些附加的考慮事項.特別地，他們覺得應(yīng)該將目標定位為兒童及他們的家長。兩個新的目標廣告應(yīng)該至少有500萬兒童看到.廣告至少至少有500萬兒童的家長看到.此外，有$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ù)目

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

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

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

st

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

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

電視廣告時段: TV≤5

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

兒童家長: 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對于特定的資源使用的數(shù)量

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

RHS對于特定的收益達到的水平

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

RHS=Right-handside(aconstant).回收固體廢棄物塞維特公司經(jīng)營一個回收中心，專門從事四種固體廢棄物的回收，并將回收物處理，混合成為可銷售的產(chǎn)品.可將該產(chǎn)品分為不同的等級（根據(jù)混合時各種材料的比例）.問題：這三種產(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利潤=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

管理視角的建模總績效測度必須是管理層想獲得的現(xiàn)實目標準確細致地描述資源約束管理科學(xué)小組與管理層的有效溝通模型往往要不斷地修改和擴展要進行what-if分析ThreeClassicalApplicationsofLP

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

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