第四章数学规划方法建模

第4章数学规划方法建模数学规划的一般形式：线性规划（LinearProgramming，简称LP）非线性规划（Nonlinearprogramming，简称NLP）整数规划（Integerprogramming，简称IP）4.1线性规划方法建模4.1.1线性规划方法简介4.1线性规划方法建模4.1.2线性规划方法建模的基本技巧简单上界和下界约束流约束

简单资源约束

物料平衡约束

质量要求约束

4.1线性规划方法建模4.1.3线性规划的Lingo实现

例1求解线性规划4.1线性规划方法建模model:sets:row/1..4/:b;col/1..3/:c,x;

matrix(row,col):A;

endsetsmax=@sum(col:c*x);@for(row(i):@sum(col(j):A(i,j)*x(j))<=b(i));data:c=60,30,20;b=48,20,8,5;A=8,6,14,2,1.52,1.5,0.50,2,0;

enddata

end4.1线性规划方法建模4.1.4线性规划方法建模示例示例1棋子问题有一个木匠作坊制作两种不同大小的黄杨木棋子．小型棋子一套需要车床加工3小时，大型棋子一套需要2小时．木匠作坊内有4个车床和4名熟练操作员，每人每周工作40小时．小型棋子一套需要1千克黄杨木，大型棋子一套需要3千克黄杨木．黄杨木每周只能得到200千克．如果售出，每套大型棋子能够得到20元利润，每套小型棋子能够得到5元利润．确定加工两种棋子的数量，使得总利润最大．4.1线性规划方法建模问题的最优解及最优值为：

4.1线性规划方法建模示例2连续投资问题某部们在今后五年内考虑给下列项目投资，并已知：项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；项目D，五年内每年初可购买公债，于当年末归还，并加利息6%．该部们现在有资金10万元，问它应如何确定给这些项目每年的投资额，使得第五年末拥有的资金的本利总额为最大？

4.1线性规划方法建模4.1线性规划方法建模问题的最优结果为：

第1年投资：A项目34782.61元，D项目65217.39元

第2年投资：A项目39130.43元，C项目30000元，D项目0元

第3年投资：A项目0元，B项目40000元，D项目0元

第4年投资：A项目45000元，D项目0元

第5年投资：D项目0元

第五年末该部们拥有资金总额为143750元，即盈利43.75%

4.1线性规划方法建模示例3货机装运问题

某运货机有三个机舱：前舱，中舱，后舱．三个货舱所能载的货物的最大体积和最大重量如表4-1所示．为了保证飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容量成比例．现有四类货物需飞行装运，有关运送数据见表4-2,试建立数学模型，合理安排装运，使货机本次飞行获利最大．4.1线性规划方法建模

表4-1三个货仓装载货物的最大容许重量和体积

前仓中仓后仓重量限制（吨）10168体积限制（立方米）680087005300表4-2四类货物的装运数据

重量（吨）空间（立方米/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物41239028504.1线性规划方法建模4.1线性规划方法建模问题的最优结果为：第1个货舱装第2种货物10吨；第2个货舱装第3种货物12.79412吨；第3个货舱装第2种货物5吨，第3种货物2.794118吨；最大获利为111558.8元．

4.1线性规划方法建模示例4动物饲料制造问题某饲料公司要生产两种类型的动物饲料：粉状饲料和颗粒饲料．生产这些饲料需要的原料为：燕麦，玉米和糖渣．生产过程中，首先需要将燕麦和玉米磨碎，然后将所有原料混合形成饲料产品，最后将半成品制成颗粒状或粉末状，从而得到最终产品．每种饲料产品都需要满足规定的营养需求，见表4-3．每天各种原料的可用量也有限制，其限定值及原料的价格见表4-4．加工饲料的各道工序的成本见表4-5．如果每天需求量为9吨颗粒饲料，12吨粉状饲料，则各种原材料应分别使用多少，并应怎样混合才能使得总成本最低．4.1线性规划方法建模表4-3营养成分含量百分比

原料蛋白质脂肪纤维素燕麦玉米糖渣13.64.157.12.40.373.725要求含量9.52

6表4-4原材料可用量与价格原料可用量（千克）价格（元/千克）燕麦玉米糖渣11900235007500.130.170.12表4-5加工成本（元/千克）磨碎混合结粒筛粉0.250.050.420.174.1线性规划方法建模4.1线性规划方法建模问题的最优结果为：生产9吨颗粒状饲料需要燕麦288.8889千克，玉米8711.1111千克，糖渣0千克；生产12吨粉状饲料需要燕麦11611.11千克，玉米0千克，糖渣388.8889千克．所需的最低成本为15097.33元．4.1线性规划方法建模示例5自行车生产规划问题某公司生产自行车，表4-6给出了明年各月预期的销售量．此公司的月生产能力为3千辆，通过工人加班，可以将产量提高50%，但是会将每辆自行车的生产成本从30元提高到40元．当前自行车的库存量为2千辆，对库存中的每辆自行车，每个月月底都需支出5元的存储费用，假定此公司的库存能力是无限的．现在是1月1日，在下面的12个月里应生产和存储多少辆自行车才能够满足此销售预期，并使得总成本最少？4.1线性规划方法建模表4-6：明年的销售预期（千辆）

1月2月3月4月5月6月7月8月9月10月11月12月3015152533404545261425304.1线性规划方法建模问题的最优结果见表4-7．生产和库存的最小总成本为1064500元。

表4-7自行车生产规划最优结果表（千辆）月份1月2月3月4月5月6月7月8月9月10月11月12月预期需求301515253340454526142530正常生产281515283030

30

3026142530加班生产000001015150000仓库存储0004000000004.1线性规划方法建模示例6体育馆建设问题某市政府打算修建一个小型体育馆．通过竞标，一家建筑公司获得了此合同．表4-8列出了工程的主要任务，需时均以星期计．有些任务只有在某些其他任务完成之后才能进行．（1）试给出各项任务的施工次序，使得这项工程能尽早完成．（2）市政府希望能够再提前一些时间完工．为此，市政府决定工期每缩短一周，便向此公司支付30千元的奖励．为缩短工期，建筑公司每周需要支付额外费用，见表4-8第5列．问如何施工才能使得建筑公司的利润最大．4.1线性规划方法建模表4-8体育馆施工数据表任务描述耗时先决任务最大缩短时间每周额外开支1工地布置2没有0－2场地平整1613303打地基921264通路及其它道路网络822125底层施工1032176主场地施工64，51157划分更衣室24188看台电器布置260－9顶部施工94，624210照明系统5412111安装阶梯看台3611812封顶290－13更衣室170－14建造售票处7222215第二通路44，1421216信号设施38，11，141617草坪与附属运动设施91231618交付使用1170－4.1线性规划方法建模问题（1）的数学模型：

4.1线性规划方法建模问题的最优解，即各个任务的开工周次为:0，2，18，29，27，37，37，44，43，37，43，52，39，30，37，46，54，63，相应各个任务的完工周次为：2，18，27，37，37，43，39，46，52，42，46，54，40，37，41，49，63，64．最优施工时间安排图，见图4.1（其中横坐标为施工周次，纵坐标为施工项目），最早完工时间为第64周．

图4.1问题（1）的最优施工时间安排图

4.1线性规划方法建模问题（2）的数学模型：

4.1线性规划方法建模

问题的最优解，即各个任务的开工周次为:0，2，18，18，26，34，26，39，39，26，39，48，28，19，26，42，50，56；相应各个任务的完工周次为：2,18,26,26,34,39,28,41,48,31,42,50,29,26,30,45,56,57；较原先施工方案共计提前了7周；各个任务实际缩短的周次为：0，0，1，0，2，1，0，0，0，0，0，0，0，0，0，0，3，0．最优施工时间安排图，见图4.2（其中横坐标为施工周次，纵坐标为施工项目），建筑公司最多可获益87千元．

图4.2问题（2）的最优施工时间安排图

4.1线性规划方法建模示例7农作物种植问题

某农场有625亩的土地可以用来种植农作物．可以种植的农作物有玉米、小麦和高粱．预计有1000亩-尺的灌溉用水可用，农场农民每周可以投入的时间为300小时．这三种农作物每亩的收益分别为400元，200元和250元．每亩农作物所需的资源见表4-9．试确定各种农作物的种植量，使得农场的获益最大．进一步讨论以下3个问题：（1）若用50元可以买到1亩-尺的灌溉用水，应否做此项投资？若投资最多每周购买多少亩-尺的灌溉用水？（2）若可以购买土地增加种植面积，购买1亩土地的费用最多是多少元？（3）由于市场需求变化，每亩高粱的获利增加到300元，应否改变生产计划？

4.1线性规划方法建模表4-9农场每亩农作物所需的资源数据

所需资源（每亩）玉米小麦高粱灌溉用水（亩-尺）3.01.01.5劳动时间（小时/周）0.80.20.34.1线性规划方法建模线性规划模型：

问题的最优方案为：种植玉米41.6667亩，种植小麦0亩，种植高粱583.3333亩，最大收益为162500元．4.1线性规划方法建模

对Lingo模型进行灵敏度分析可得下面报告：（1）土地和灌溉用水这两种资源全部用完，而劳动时间这种资源还剩余91.6667；（2）土地、灌溉用水和劳动时间的影子价格分别为100元、100元和0元，即增加1个单位的土地量、灌溉用水量和劳动时间，总收益会分别增加100元、100元和0元．（3）最优解不变条件下目标函数系数的变化范围分别为[250,400]、[0,200]和[250,400]，即当每亩玉米的收益在[250,400]，每亩小麦的收益在[0,200]，每亩高粱的收益在[250,400]变化时，不需要改变生产计划．（4）土地、灌溉用水和劳动时间这三种资源影子价格有意义条件下约束右端的限制范围分别为[333.3333,666.6667]、[937.5,1275]和[208.3333,]，要保证前面给定的影子价格有意义，土地量、灌溉用水量和劳动时间只能在上述范围内取值．4.1线性规划方法建模根据上述报告可以回答前面的三个问题：问题（1）应该做此项投资，若投资每周最多1275购买亩-尺的灌溉用水；问题（2）可以购买土地，购买1亩土地的费用最多是100元；问题（3）每亩高粱的获利为300元时，仍小于其变化上限400元，所以不需要改变生产计划．

4.1线性规划方法建模4.1.5课后练习

1．某公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年100万，2004年150万，2005年120万，2006年110万．贷款资金需于2002年底前筹集齐．为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目：（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140％，但限购60万；（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125％，且限购90万；（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130％，且限购50万；（4）于每年初将任意数额的资金存放于银行，年息4％，于每年底取出．问此公司如何运用这笔筹集到的资金满足贷款要求，并使得2002年底筹集到的资金数额最少．4.2整数规划方法建模4.2.1整数规划方法简介线性整数规划、纯整数规划、混合整数规划、0-1规划4.2整数规划方法建模整数规划方法建模需要的一些特殊变量：

0-1变量：定义变量的取值要么为0，要么为1。部分整数变量：定义变量如果其值小于用户指定的限制L，则其取值必须为整数值；否则可取任意值。半连续变量：定义变量的取值要么为0，要么位于某限定范围内。半连续整数变量：定义变量的取值要么为0，要么位于某限定范围内的整数值。

4.2整数规划方法建模4.2.2整数规划方法建模的基本技巧处理是/否逻辑问题问题只有两种选择，要么做某件事，要么不做某件事．对此可以借助0-1变量来处理。处理逻辑条件问题问题有一组项目，不妨记为A，B，C，D，E，F，G，和H，每个项目都可以选择做还是不做，可借助0-1变量加以处理。具体问题要求不同，处理的方式也不相同，常见的情况如下：

1.在多个选项中进行选择

4.2整数规划方法建模如“这些项目中至多选一个”：

再如，“选且仅能选择二个项目”：

4.2整数规划方法建模2.简单蕴含式

比如“如果选择项目A，则必须也选择项目B”：

再如“如果选择项目A，则不能选择项目B”：

再如“如果不选择项目A，则必须选择项目B”：

4.2整数规划方法建模3.含有三个变量的蕴涵式

如“如果选择项目A，则必须也选择项目B和项目C”:

再如“如果选择项目A，则必须也选择项目B或项目C”:

“如果同时选择项目B和项目C，则必须选择项目A”:

4.2整数规划方法建模4.一般蕴涵式

比如“如果选择项目B，C,D和E中的两个或两个以上，则必须也选择A”:

处理0-1变量乘积问题

对式，可用借助下面三个不等式将其线性化

4.2整数规划方法建模对乘积等式约束,可利用下面四个不等式约束将其线性化

处理“或”约束问题

比如下面问题:

4.2整数规划方法建模定义0-1变量,表示采用第1个约束条件，否则采用第2个约束条件

处理半连续整数变量问题

如某自行车厂采用流水线作业生产某种自行车，对这种自行车，要么不生产，要生产要求至少生产1500辆。

4.2整数规划方法建模处理固定成本问题

如某手机生产厂打算生产一种新型的手机，如果生产则需要投资固定成本10万元，如果不生产，则此项成本为0。

引入0-1辅助变量，表示生产此种手机，否则为0。

4.2整数规划方法建模处理0-1变量和实数变量的乘积问题

用整数规划方法建模时，有时会遇到实数变量和0-1变量相乘的问题．如，其中为0-1变量，可用下面不等式将其线性化

处理“或”约束问题

数学规划中的约束条件一般都是必须同时满足，但有时对其中的某两个约束条件只须满足一个即可，比如

4.2整数规划方法建模定义0-1变量，令表示采用第1个约束条件，采用第2个条件，则取值为0

4.2整数规划方法建模处理半连续整数变量问题

如某自行车厂采用流水线作业生产某种自行车，对这种自行车，要么不生产，要生产要求至少生产1500辆．定义变量表示生产这种自行车的辆数，则显然为半连续整数变量.定义0-1变量，则有

处理固定成本问题

如某手机生产厂打算生产一种新型的手机，如果生产则需要投资固定成本10万元，如果不生产，则此项成本为0．记

表示生产此种新型手机的个数，

表示投资固定资产的费用，

4.2整数规划方法建模引入0-1辅助变量

表示生产此种手机，否则为0，则

处理0-1变量和实数变量的乘积问题

如为实数变量，而为0-1变量，且有，则

4.2整数规划方法建模4.2.3整数规划方法的Lingo软件实现例

用Lingo软件求解整数规划4.2整数规划方法建模解：在Lingo指令窗中输入下面指令：

model:sets:row/1..2/:b;col/1..2/:c,x;matrix(row,col):A;endsetsmax=@sum(col:c*x);@for(col:@gin(x));@for(row(i):@sum(col(j):A(i,j)*x(j))<=b(i));data:c=1,1;b=1,4;A=-1,1,3,1;enddataend4.2整数规划方法建模4.2.4整数规划方法建模示例示例1指派问题

有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R．现有甲、乙、丙、丁、戊五人，他们将中文说明书翻译成不同语种的说明书所需的时间见表4-15．请从这五人中指派四人完成这项工作，使得所需的总时间最少．4.2整数规划方法建模表4-15各人对每项任务所需时间表

语种EJGR甲乙丙丁戊2109751541486131416111241513974.2整数规划方法建模建立指派问题的数学模型如下：

问题的最优解为:，其余变量为0，最优值为24，即甲翻译俄文，乙翻译日文，丁翻译德文，戊翻译英文所需的总时间最少，为24小时．

4.2整数规划方法建模示例2汽车厂生产计划问题某汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如表4-16所示．由于条件限制，规定如果生产某一类型的汽车，则至少要生产80辆，试制定月生产计划，使工厂的利润最大．表4-16汽车厂相关数据表小型中型大型现有量钢材（吨）1.535600劳动时间（小时）

28025040060000利润（万元）

2344.2整数规划方法建模问题的最优解为:

,即生产小型汽车80辆，中型汽车150辆，大型汽车0辆，工厂获得的最大利润为610万元．4.2整数规划方法建模示例3露天采矿问题某地发现了一个露天铀矿．根据探测钻探的结果，发现这个矿可以分为若干个可开采区．矿坑需要挖掘成阶梯形，以方便卡车开到矿坑底部．铀矿呈东西方向分布，如图4.3所示．铀矿确定有18个可开采区，呈三层分布．为挖掘一个可开采区，首先需要掘开它上方的三个区：正上方的区，左上方的区和右上方的区．挖第一层的区块每吨需要耗费100元，挖的第二层每吨需要耗费200元，挖第三层每吨需要耗费300元．如果区块是由含有很多石英的石头组成（斜线区域），则每吨需要多耗费1000元．只有灰色显示的区才含有铀（即1，7，10，12，17，18区）．其市场价值分别为200，300，500，1000,1200和1400元/吨．第18区，尽管也含有大量矿石，但也同时含有大量非常硬的石头．为使总收益达到最大，应挖掘哪些矿区?4.2整数规划方法建模123456789101112131415161718第1层第2层第3层图4.3：露天矿山结构图4.2整数规划方法建模问题的最优解为:

，其余变量为0，最大收益为1400．即挖掘矿区1，2，3，4，5，6，7，10，11，12，13，17可使得总收益达到最大．4.2整数规划方法建模示例4蔗糖生产问题在澳大利亚，甘蔗的收割已经实现了高度机械化．甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂．一辆货车的运量能够生产的蔗糖量取决于甘蔗收购的地点以及甘蔗成熟的程度．在收割之后，甘蔗中的含糖量由于发酵而迅速下降，一段时间之后，所含糖份将完全流失．现在有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都相同．对每辆货车每小时的损失量以及剩余时间测量的数据见表4-17：

表4-17：每车甘蔗属性货车编号1234567891011损失率（千克/小时）4326372813546249192830剩余时间882848888884.2整数规划方法建模在蔗糖厂有三条生产线，每辆货车都可以选择在哪条生产线上进行加工．一车甘蔗的加工时间为两个小时．必须在这车甘蔗的质量寿命结束之前完成加工．蔗糖厂的经理希望找出一个生产计划，使总的蔗糖损失降到最低．4.2整数规划方法建模问题的最优解为:,其余变量为0，各个货车蔗糖的损失量(单位：千克)分别为：172，208，74，168，52，108，124，196，152，168，180，蔗糖的最小总损失量为1602（千克）．于是得问题的最优加工方案见表4-18．

表4-18最优加工方案表

时间段1时间段2时间段3时间段4货车3货车1货车4货车2货车6货车5货车10货车9货车7货车8货车114.2整数规划方法建模示例5文件备份问题某公司希望将一些重要的文件备份到软盘上．每张空白软盘的容量是1.44MB．一共需要备份16个文件，其大小(单位：KB)分别为：46，55，62，87，108，114，137，164，253,364,372,388,406,432,461和851．假定无法使用压缩文件，但软盘的数量足够，问如何备份这些文件才能使得使用的软盘数目最少？

4.2整数规划方法建模文件备份问题的数学模型：

问题的最优分配方案:

软盘文件大小（KB）使用空间（MB）146,62,87,137,364,372,3881.42192108,406,432,4611.3740355,114,164,253,8511.40034.2整数规划方法建模示例6钢管切割问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m．（1）现有一客户需要50根4m，20根6m和15根8m的钢管，应如何下料最节省？（2）零售商如果采用不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用不同的切割模式不能超过3种．此外，该客户除需要（1）中的三种钢管外，还需要10根5m的钢管，应如何下料最省？4.2整数规划方法建模表4-20钢管的合理切割模式表模式1模式2模式3模式4模式5模式6模式74m钢管根数43211006m钢管根数01021308m钢管根数0010102问题（1）的数学模型：

4.2整数规划方法建模结果：按照模式1切割5根原料钢管，按照模式2切割5根原料钢管，按照模式5切割15根原料钢管，最少需要切割25根原料钢管．

问题（2）的数学模型：

4.2整数规划方法建模运行得切割所需的模式分别为：模式1，将原料钢管切割成4m钢管3根，5m钢管0根，6m钢管1根，8m钢管0根；模式2，将原料钢管切割成4m钢管0根，5m钢管0根，6m钢管0根，8m钢管2根；模式3，将原料钢管切割成4m钢管2根，5m钢管1根，6m钢管1根，8m钢管0根．最少需要切割19m的原料钢管28根．模型结果：4.2整数规划方法建模示例7仓库位置设置某公司希望开设一些新仓库，向销售中心供货．每开设一个新仓库都有一些固定费用．货物将从仓库运输到附近的销售中心，每次运输的运费取决于运输的距离．目前有12个位置可以建造新仓库，这些仓库可以向12个销售中心供货．表4-21给出了每个仓库完全满足每个客户（销售中心）需求所需的总成本（单位：元），如果无法进行送货，取对应的成本为100000．此外，每个仓库的固定建设费用和仓库的容量上限见表4-22．仓库在任何时候都要保证满足客户需求，每个客户的需求量见表4-23．

问此公司应在哪些位置开办仓库才能使得建设成本和运输成本的总费用最低？4.2整数规划方法建模表4-21完全满足客户需求所需的运输总成本客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8仓库9仓库10仓库11仓库121008050506010012090607065110120906070651101401108080751301401108080751301601251001008015016012510010080150190150130100000100000

100000190150130100000100000

100000200180150100000100000

100000200180150100000100000

100000100805050601001008050506010012090607065110120906070651101401108080751301401108080751301601251001008015016012510010080150190150130100000100000

100000190150130100000100000

100000200180150100000100000

100000200180150100000100000

100000100805050601004.2整数规划方法建模表4-22仓库的固定建设费用和仓库的容量上限表仓库123456789101112固定建设费用350090001000040003000900090003000400010000900035000容量上限300250100180275300200220270250230180表4-23客户的货物需求量表客户123456789101112需求量1208075100110100906030150951204.2整数规划方法建模运行得最低总成本为18713.19元，开设的仓库位置分别为：1，4，5，8，9，开设仓库的总费用为17500元，运输的总费用为1213.194元．相应的最优运输方案见表4-24．4.2整数规划方法建模表4-24最优运输方案表

客户1客户2客户3客户4客户5客户6客户7客户8客户9客户10客户11客户12仓库1仓库4仓库5仓库8仓库900050085603000120000701100000000120350000500000045750010000000000025000001509504.2整数规划方法建模示例8求职面试问题

有4名同学到一家公司参加三个阶段的面试．公司要求每个同学都必须首先找公司秘书初试，然后到主管部门复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）．由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表4-25所示（单位：分钟）．4名同学约定他们全部面试完以后一起离开公司．假定现在时间是早晨8:00，问他们最早何时能离开公司．

4.2整数规划方法建模表4-25四名同学各阶段的面试时间表秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁810154.2整数规划方法建模求职面试问题的数学模型：

4.2整数规划方法建模表4-26四名同学面试时间表秘书初试主管复试经理面试同学甲8:08～8:218:21～8:368:36～8:56同学乙8:21～8:318:36～8:568:56～9:14同学丙8:31～8:518:56～9:129:14～9:24同学丁8:00～8:088:11～8:218:21～8:364.2整数规划方法建模4.2整数规划方法建模4.2整数规划方法建模4.2整数规划方法建模4.2整数规划方法建模4.2整数规划方法建模4.2整数规划方法建模模型：课堂练习:某钻井队要从以下十个可供选择的井位：中确定5个钻井探油。十个井位的钻探费用估计分别为。且井位选择必须满足如下限制条件：（1）或选择和，或选择；（2）在三个井位最多只能选择一个；（3）在中最多只能选两个；试建立数学模型使总的钻探费用为最小。课堂练习:混合泳接力队的选拔问题：某班准备从5名游泳队员中选择4人组成接力队，参加学校的4100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如下表所示，问应如何选拔队员组成接力队？如果最近队员丁的蛙泳成绩有较大退步，只有75.2秒;而队员戊经过艰苦训练自由泳成绩有所进步,达到57.5秒,组成接力队的方案是否应该调整?甲

乙

丙

丁

戊蝶泳（秒）

66.857.2787067.4仰泳（秒）

75.66667.874.271蛙泳（秒）

8766.484.669.683.8自由泳（秒）

58.65359.457.262.4示例4选课策略某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、所属类别和先修课要求如表1所示。那么，毕业时学生最少可以学习这些课程中的哪些中的哪些课程。表1运筹学专业的课程属性表课程编号课程名称所属类别先修课要求1微积分数学2线性代数数学3最优化方法数学；运筹学微积分；线性代数4数据结构数学；计算机计算机编程5应用统计数学；运筹学微积分；线性代数6计算机模拟计算机；运筹学计算机编程7计算机编程计算机8预测理论运筹学应用统计9数学实验运筹学；计算机微积分；线性代数模型与结果：示例5销售代理的开发与中断模型

某公司正在考虑在某城市开发一些销售代理业务。经过预测，该公司已经确定了该城市未来5年的业务量，分别为400，500，600，700和800。该公司已经初步物色了4家销售公司作为其代理候选企业，下表给出了该公司与每个候选企业建立代理关系的一次性费用（万元），以及每个候选企业每年所能承揽的最大业务量和年运行费用（万元）。该公司应该与哪些候选企业建立代理关系。候选代理1候选代理2候选代理3候选代理4年最大业务量

350250300200一次性费用

100809070年运行费用

7.54.06.53.0模型与结果：，其它变量为0，最优值为313.5万元若该公司目前已经与上述4个代理建立了代理关系并且都处于运行状态，但每年初可以决定临时中断或重新恢复代理关系，每次临时中断或重新恢复代理关系的费用（万元）如下表所示。该公司应如何对这些代理进行业务调整？

代理1代理2代理3代理4临时中断费用

5342重新恢复费用

5419模型与结果：，即公司应在第1年初临时中断与代理2和代理3的关系，而在第3年初重新恢复与代理2得代理关系。最小总费用为86.5万元。练习：汽车厂生产计划问题

一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示。试制定月生产计划，使工厂的利润最大。由于条件限制，只能生产某一类型汽车，且至少要生产80辆，那么最优的生产计划应作如何改变。小型

中型

大型现有量钢材（吨）1.535600劳动时间（小时）

28025040060000利润（万元）234例6

饮料厂的生产与检修计划某饮料厂生产一种饮料用以满足市场需求。该厂销售科根据市场预测，已经确定了未来四周该饮料的需求量。计划科根据本厂实际情况给出了未来四周的生产能力和生产成本，如下表所示。每周当饮料满足需求后有剩余时，要支出存贮费，为每周每千箱饮料0.2千元。问应如何安排生产计划，在满足市场需求的条件下，使四周的总费用最小？如果工厂必须在未来四周的某一周中安排一次设备检修，检修将占用当周15千箱的生产能力，但会使检修以后每周的生产能力提高5千箱，则检修应安排在哪一周。

周次需求量（千箱）生产能力（千箱）成本（千元/千箱）115305.02

25405.13

35455.4425205.5合计100135表：饮料的生产和需求数据表模型与结果：千元模型与结果：千元例7饮料厂的生产批量问题某饮料厂使用同一条生产线轮流生产多种饮料以满足市场需求。如果某周开工生产其中一种饮料，就要清洗设备和更换部分部件，于是需支出生产准备费8千元。现在只考虑生产一种饮料的生产，假设其未来四周的需求量，生产能力，生产成本和存贮费与例6的完全相同。问应如何安排这种饮料的生产计划，在按时满足市场需求的条件下，使生产该种饮料的总费用最小？模型与结果：千元例8钢管问题某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m。现有一客户需要50根4m，20根6m和15根8m的钢管，应如何下料最节省？（2）零售商如果采用不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用不同的切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5m的钢管，应如何下料最省？表：钢管下料的合理切割模式4m钢管根数6m钢管根数8m钢管根数模式1400模式2310模式3201模式4120模式5111模式6030模式7002模型与结果：模型与结果：例9求职面试问题有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到主管部门复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司。秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015表：面试情况例10蔗糖加工问题在澳大利亚，甘蔗的收割已经实现了高度机械化。甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂。一辆货车的运量能够生产的蔗糖量取决于甘蔗收购的地点以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量由于发酵而迅速下降，一段时间之后，所含糖份将完全流失。现在有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都相同。对每辆货车每小时的损失量以及剩余时间测量的数据见下表：在蔗糖厂有三条生产线，每辆货车都可以选择在哪条生产线上进行加工。一车甘蔗的加工时间为两个小时。必须在这车甘蔗的质量寿命结束之前完成加工。蔗糖厂的经理希望找出一个生产计划，使总的蔗糖损失降到最低。货车编号

1234567891011损失率（千克/小时）4326372813546249192830剩余时间

88284888888例11电力生产问题为满足每日电力需求（单位为兆瓦），可以选用四种不同类型的发电机。每日电力需求如表1所示。每种发电机都有一个最大发电能力，当接入电网时，其输出功率不应低于某一最小输出功率。所有发电机都存在一个启动成本，以及工作于最小功率状态时的固定的每小时成本，并且如果功率高于最小功率，则超出部分的功率每兆瓦每小时还存在一个成本，即边际成本。这些数据均列于表2中。只有在每个时段开始时才允许启动或关闭发电机。与启动发电机不同，关闭发电机不需要付出任何代价。在任意时刻，正在工作的发电机组必须留出20％的发电能力余量，以防用电量突然上升。问题：在每个时段应分别使用哪些发电机才能够使每天的总成本最小？表1每日用电需求（兆瓦）

时段0am-6am6am-9am9am-12pm12pm-2pm2pm-6pm6pm-10pm10pm-12am需求12000320002500036000250003000018000表2发电机描述数据

型号可用量最小输出功率最大输出功率固定成本每兆瓦边际成本启动成本（台）（MW）（MW）（欧元/小时）（欧元/小时）（欧元）1234

10750175022502.7500041000150018002.2160081200200037501.8240031800350048003.81200例12体育馆建设问题为了向本市提供更好的服务，某市政府决定修建一个小型体育馆。通过竞标，一家本地的建筑公司获得了此合同，希望尽快完成此工程。在下表中列出了工程中的主要任务。需时均以星期计。有些任务只有在某些其他任务完成之后才能进行。此表格的最后两列对应于问题2。问题1：最早能在什么时候完成此工程？问题2：市政府希望能够提前完工（比问题1的答案提前）。为此，市政府决定工期每缩短一周，则向此公司支付30千欧元的奖励。为缩短工期，建筑公司需要雇用更多工人，并租借更多设备，以及相关的每周额外支出。如果建筑公司希望使利润最大，那么应在何时完成此工程？表：体育馆施工数据任务描述耗时先决任务最大缩短时间每周额外开支1工地布置2没有0－2场地平整1613303打地基921264通路及其它道路网络822125底层施工1032176主场地施工64，51157划分更衣室24188看台电器布置260－9顶部施工94，624210照明系统5412111安装阶梯看台3611812封顶290－13更衣室170－14建造售票处7222215第二通路44，1421216信号设施38，11，141617草坪与附属运动设施91231618交付使用1170－例9原油采购与加工原油采购与加工问题：某公司用两种原油（和）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油和的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油。原油的市场价为：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000顿时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工？模型与结果：例10易拉罐下料某公司采用一套冲压设备生产一种罐装饮料的易拉罐,这种易拉罐是用镀锡板冲压制成的.易拉罐为圆柱形,包括罐身,上盖和下底,罐身高10cm,上盖和下底的直径均为5cm.该公司使用两种不同规格的镀锡板原料:规格1的镀锡板为正方形,边长24cm;规格2的镀锡板为长方形,长和宽分别为32cm和28cm.由于生产设备和生产工艺的限制,对规格1的镀锡板原理,只可以按照下图中的模式1,模式2或模式3进行冲压;对于规格2的镀锡板原料只能按照模式4进行冲压.使用模式1,2,3,4进行冲压所需的时间分别为1.5秒,2秒,1秒和3秒.该厂每周工作40小时,每周可供使用的规格1,2的镀锡板原料分别为5万张和2万张.目前每只易拉罐的利润为0.1元,原料余料损失为0.001元/厘米(如果周末有罐身,上盖或下底不能配套组装成易拉罐出售,也视作原料余料损失).问工厂应如何安排每周的生产?习题课1.自行车生产规划问题某公司生产儿童自行车。下表中给出了明年预期的销售量（以千辆为单位计）。此公司的生产能力为每个月30000辆自行车。通过工人加班，可以将产量提高50%，但是会将每辆自行车的生产成本从30欧元提高到40欧元。当前自行车的库存量为2000辆。对于库存中的每辆自行车，在每个月月底都需要支出5欧元的存储费用。假定此公司的库存能力是无限的。现在是1月1日，在下面的12个月里应生产和存储多少量自行车才能够满足此销售预期，并最小化总成本？表：明年的销售预期（千辆）1月2月3月4月5月6月7月8月9月10月11月12月3015152533404545261425302.钻井问题某钻井队要从以下十个可供选择的井位：中确定5个钻井探油。十个井位的钻探费用估计分别为。且井位选择必须满足如下限制条件：（1）或选择和，或选择；（2）在三个井位最多只能选择一个；（3）在中最多只能选两个；试建立数学模型使总的钻探费用为最小。3.混合泳接力队的选拔问题某班准备从5名游泳队员中选择4人组成接力队，参加学校的4100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如下表所示，问应如何选拔队员组成接力队？如果最近队员丁的蛙泳成绩有较大退步，只有75.2秒;而队员戊经过艰苦训练自由泳成绩有所进步,达到57.5秒,组成接力队的方案是否应该调整?甲

乙

丙

丁

戊蝶泳（秒）

66.857.2787067.4仰泳（秒）

75.6