三章线性建模与应用

第三章线性规划：建模与应用超级食品公司的广告混合问题(3.1节) 资源分配问题&Think-Big的资金预算(3.2节) 成本-收益平衡问题&UnionAirways(3.3节) 网络配送问题&Big公司(3.4节) 超级食品公司案例的再研究(3.5节) 混合建模&回收固体废弃物(3.6节)

KeyCategoriesofLPProblems

线性规划问题主要类型资源分配问题（resource-allocation）成本收益平衡问题（cost-benefit-trade-off）网络配送问题（distribution-network）混合问题（mixedProblem）超级食品公司的广告混合问题目标:为“脆始”设计促销运动对于这种产品的三个最有效率的广告媒体是：星期六上午儿童广告节目的电视广告.食品与家庭导向的杂志上的广告.主要报纸星期增刊上的广告该问题的三种有限资源分别为：广告预算(4百万美元).计划预算(100万美元).可获得的电视广告段(5).目标通过期望受众数据来度量.问题:在这三种媒体中每一种的广告的投入应该在什么水平上？成本与广告受众数据CostsCostCategoryEach

TVCommercialEach

MagazineAdEach

SundayAdAdBudget$300,000$150,000$100,000Planningbudget90,00030,00040,000Expectednumberofexposures1,300,000600,000500,000代数建模令TV=电视上的广告时段数目

M=杂志上的广告数目.

SS=星期天增刊上的广告数目

Max受众时间=1,300TV+600M+500SS

st

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

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

电视广告时段的数目: TV≤5且

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

资源分配问题

资源分配（resource-allocation）问题是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为资源限制(resourceconstraint),并且每一种有限资源都可以表现为如下的形式：

使用的资源数量

可用的资源数量

问题类型DataGathering

收集数据所有活动可获得使用的每种资源的有限数量每一种活动所需要的各种资源的数量每一种资源与活动的组合单位活动消耗资源量必须首先估计每一种活动对总的绩效测度的单位贡献

梦大资金分配问题梦大发展公司是一个商务房地产开发项目的主要的投资者。他们正在考虑三个大的建设项目建设一个高层办公楼.建设宾馆.建设购物中心.每个项目都要求投资者在四个不同的时期投资；在当前预付定金，以及一年，两年，三年后分别追加投资。问题:梦大公司在三个项目中的每个项目上投资的比例是多少？项目的财务数据InvestmentCapitalRequirementsYearOfficeBuildingHotelShoppingCenter0$40million$80million$90million160million80million50million290million80million20million310million70million60millionNetpresentvalue$45million$70million$50million代数建模令OB=办公楼项目中的投资比例

H=宾馆项目中的投资比例,

SC=购物中心项目中的投资比例.

MaxNPV=45OB+70H+50SC

st

现期的总投资: 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.电子表格建模资源分配问题建模的总结确认问题的活动类型.明确合适的绩效测度以求解问题(一般以利润测度).估计每一种活动对于总绩效测度的单位贡献.明确分配给各种活动的有限资源.对于每种资源，明确可获得的数量以及各种活动的单位使用量.在步骤3和5种输入数据。指定可变单元格来显示活动水平的决策量在表示每种资源的列种,使用SUMPRODUCT函数来计算使用的总数量，在两个临近单元格中可以利用的数量输入≤。指派目标单元格，使用SUMPRODUCT函数来输入总的绩效测度。联合航空公司的员工排程联合航空公司正在准备增加其中心机场的往来航班，所以需要雇佣的顾客服务代理商。5格授权的8小时的换班是轮班1: 6:00AMto2:00PM轮班2: 8:00AMto4:00PM轮班3: 中午to8:00PM轮班4: 4:00PMtomidnight轮班5: 10:00PMto6:00AM问题:每一个轮班应该指派多少格代理商？排程数据TimePeriodsCoveredbyShiftTimePeriod12345Minimum

Numberof

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

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

st 6AM–8AM之间的总代理商数: S1≥48

8AM–10AM之间的总代理商数:S1+S2≥79

10AM–12PM之间的总代理商数: S1+S2≥65

12PM–2PM之间的总代理商数: S1+S2+S3≥87

2PM–4PM之间的总代理商数: S2+S3≥64

4PM–6PM之间的总代理商数: S3+S4≥73

6PM–8PM之间的总代理商数: S3+S4≥82

8PM–10PM之间的总代理商数: S4≥43

10PM–12AM之间的总代理商数: S4+S5≥52

12AM–6AM之间的总代理商数: S5≥15

且

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

成本收益平衡问题成本收益平衡问题（Cost-benefit-trade-offProblem

）是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益的水平。这类问题的共性是，所有的函数约束均为收益约束，并具有如下的形式：

完成的水平

最低可接受的水平问题类型成本收益均衡问题的建模过程总结确认问题的活动类型.明确合适的绩效测度以求解问题(一般以成本测度).估计每一种活动对于总绩效测度的单位贡献.明确每种收益最低可接受水平.明确每一种活动对于对每种收益的贡献.在步骤3和5种输入数据。指定可变单元格来显示活动水平的决策量使用SUMPRODUCT函数来计算使用的总数量，在两个临近单元格中可以利用的数量输入≤。指派目标单元格，使用SUMPRODUCT函数来输入总的绩效测度。4.20Distribution-networkProblem

网络配送问题网络配送问题（distributionnetwork）能以最小的成本完成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：

提供的数量＝需要的数量问题类型大M公司的网络配送问题大M在两个工厂生产一系列重型机器。产品之一就是大型车床收到了3个顾客的订单需要购买大型车床。问题:从每个工厂需要运送多少大型车床到每个顾客？一些数据ShippingCostforEachLatheToCustomer1Customer2Customer3FromOutputFactory1$700$900$80012lathesFactory280090070015lathesOrderSize10lathes8lathes9lathes配送网络代数建模

令Sij=从i到j运送的机床的数目(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得出结论：电子表格模型需要拓展从而包括一些附加的考虑事项.特别地，他们觉得应该将目标定位为儿童及他们的家长。两个新的目标广告应该至少有500万儿童看到.广告至少至少有500万儿童的家长看到.此外，有$1,490,000的商家优惠券应该分发出去。收益和固定需求的数据NumberReachedinTargetCategory(millions)Each

TVCommercialEach

MagazineAdEach

SundayAdMinimum

Acceptable

LevelYoungchildren1.20.105Parentsofyoungchildren0.50.20.25ContributionTowardRequiredAmountEach

TVCommercialEach

MagazineAdEach

SundayAdRequired

AmountCouponredemption0$40,000$120,000$1,490,000代数模型令TV=电视商的广告时段数目

M=杂志上的广告数目.

SS=星期天增刊上的广告数目.

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

混合问题问题类型资源分配问题，成本收益平衡问题以及网络配送问题，都以一类约束条件为特色的纯资源分配问题的共性是它所有的函数约束均为资源约束成本收益平衡问题的共性是它所有的函数约束均为收益约束网络配送问题主要的函数约束为一特定类型的确定需求的约束混合问题

是第四类线性规划问题，这一类型包括了三类约束函数

函数约束的类型总结类型形式解释主要用于资源约束LHS

RHS对于特定的资源使用的数量

可获得的数量资源分配问题混合问题收益约束LHS

RHS对于特定的收益达到的水平

最低可接受水平成本收益平衡问题混合问题需求确定约束LHS=RHS对于一些数量提供的数量=需求的数量网络配送问题混合问题*LHS=Left-handside(aSUMPRODUCTfunction).

RHS=Right-handside(aconstant).回收固体废弃物塞维特公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物处理，混合成为可销售的产品.可将该产品分为不同的等级（根据混合时各种材料的比例）.问题：这三种产品每种产品应该生产的数量应该是多少？塞维特公司的产品数据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塞维特公司的原材料数据

MaterialPounds/Week

AvailableTreatmentCost

perPound

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

2.$30,000perweekshouldbeusedtotreatthesematerials.22,0006.0034,0004.0041,0005.00代数建模令xij=每周物料j分配到产品

i

的数量(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 混合的比例规定: 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

必须处理的数量的约束: 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

管理视角的建模总绩效测度必须是管理层想获得的现实目标准确细致地描述资源约束管理科学小组与管理层的有效沟通模型往往要不断地修改和扩展要进行what-if分析ThreeClassicalApplicationsofLP

线性规划问题的三个经典应用潘得罗索工业公司的产品组合考虑有限资源，确定产品的最佳组合公司的总利润增加了20%.联合航空公司的员工排程为最有效率地满足服务要求为所有地雇员设计工作日程安排.每年节约$6,000,000.Citgo石油公司供应、配送与营销规划SDM系统使用线性规划协调全美的Citgo的主要产品的供应，配送和营销.库存减少导致Citgo公司每年利润增加$14,000,000.PonderosaIndustrial

潘德罗索工业公司潘德罗索应用成功的因素：以自然语言为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。最优化系统是互动的（interactive），管理者在从一个版本的