数学模型：第四章 数学规划模型

第四章数学规划模型

4.1奶制品的生产与销售4.2自来水输送与货机装运4.3汽车生产与原油采购4.4接力队选拔和选课策略数学规划模型

实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析链接:/s/1o7IkogM密码:kfxuLingo软件下载及相关资料企业生产计划4.1奶制品的生产与销售

空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划.时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划.本节课题例1加工奶制品的生产计划1桶牛奶

3公斤A1

12小时

8小时

4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：问题1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天基本模型模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工A1,A2的数量,时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解

软件实现

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三种资源“资源”剩余为零的约束为紧约束（有效约束）原料无剩余时间无剩余加工能力剩余40结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下“资源”增加1单位时“效益”的增量影子价格35元可买到1桶牛奶，要买吗?35<48,应该买！

聘用临时工人付出的工资最多每小时几元?2元！原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最优解不变时目标函数系数允许变化范围敏感性分析

(“LINGO|Ranges”)

x1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/公斤，应否改变生产计划?x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶,每天最多买多少?最多买10桶!(目标函数不变)充分条件!例2奶制品的生产销售计划

在例1基础上深加工1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤0.8公斤B12小时,3元1公斤获利44元/公斤0.75公斤B22小时,3元1公斤获利32元/公斤制订生产计划，使每天净利润最大30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480小时至多100公斤A1

B1，B2的获利经常有10%的波动，对计划有无影响？

每天销售10公斤A1的合同必须满足，对利润有什么影响？1桶牛奶3kgA1

12小时8小时4kgA2

或获利24元/kg

获利16元/kg

0.8kgB12小时,3元1kg获利44元/kg

0.75kgB22小时,3元1kg获利32元/kg

出售x1kgA1,

x2kgA2，

x3kgB1,x4kgB2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5kgA1加工B1，x6kgA2加工B2附加约束

基本模型模型求解

软件实现

LINGO

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000Globaloptimalsolutionfound.Objectivevalue:3460.800

Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000

MILK0.0000003.160000

TIME0.0000003.260000

CPCT76.000000.000000

50.00000044.00000

60.00000032.00000结果解释每天销售168kgA2和19.2kgB1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24kgA1全部加工成B1

除加工能力外均为紧约束结果解释Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000

MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000增加1桶牛奶使利润增长3.16×12=37.92增加1小时时间使利润增长3.2630元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶,可赚回189.6元。(大于增加时间的利润增长)结果解释B1,B2的获利有10%的波动，对计划有无影响Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.0000001.680000INFINITYX216.0000008.1500002.100000

X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY

……

……敏感性分析

B1获利下降10%，超出X3系数允许范围B2获利上升10%，超出X4系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000结果解释x1从0开始增加一个单位时，最优目标函数值将减少1.68ReducedCost有意义也是有条件的(LINGO没有给出)每天销售10公斤A1的合同必须满足，对利润有什么影响？公司利润减少1.68×10=16.8（元）最优利润为3460.8–16.8=3444

奶制品的生产与销售

由于产品利润、加工时间等均为常数，可建立线性规划模型.

线性规划模型的三要素：决策变量、目标函数、约束条件.

用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.

建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做（分析例2的建模）.4.2

自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大?运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少?其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1

自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<总需求量：120+180=300总收入900160=144,000(元)收入：900元/千吨

其他费用:450元/千吨

支出引水管理费其他支出450160=72,000(元)使引水管理费最小供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量模型求解

部分结果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变求解部分结果：ObjectiveValue:88700.00VariableValueReducedCost

X110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X3150.0000000.000000X320.00000020.000000X3330.0000000.000000运输问题总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030供应点需求点物资供需平衡或不平衡如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例.

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知参数i=1,2,3,4（货物）j=1,2,3(分别代表前、中、后仓)货舱j的重量限制WETj体积限制VOLj第i种货物的重量wi，体积vi，利润pi货机装运决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差.

模型建立货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量j,k=1,2,3;j≠k

!定义集合及变量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!对已知变量赋值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=@sum(wu(i):p(i)*@sum(cang(j):x(i,j)));@for(wu(i):@sum(cang(j):x(i,j))<w(i));@for(cang(j):@sum(wu(i):x(i,j))<WET(j));@for(cang(j):@sum(wu(i):v(i)*x(i,j))<VOL(j));@for(cang(j):

@for(cang(k)|k#GT#j: !#GT#是大于等于的含义; @sum(wu(i):x(i,j)/WET(j))=@sum(wu(i):x(i,k)/WET(k))););END货机装运LINGO程序

Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000货物2：前仓7,后仓8；

货物3:前仓3,中仓13；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点装载平衡要求运输问题运输问题的扩展

如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.

小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234

制订月生产计划，使工厂的利润最大.4.3

汽车生产与原油采购设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解

3）模型中增加条件：x1,x2,x3

均为整数，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大.2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解.

但必须检验它们是否满足约束条件.为什么？IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)IP的最优解x1=64，x2=168，x3=0，最优值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划

若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或

80

x1=80，x2=150，x3=0，最优值z=610LINGO中对0-1变量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1变量，化为整数规划

M为大的正数,本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生产某类汽车，则至少生产80辆，求生产计划.x1=0或

80x2=0或

80x3=0或

80最优解同前

max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1*(x1-80)>0;x2*(x2-80)>0;x3*(x3-80)>0;@gin(x1);@gin(x2);@gin(x3);方法3：化为非线性规划

非线性规划（Non-LinearProgramming，简记NLP）

若生产某类汽车，则至少生产80辆，求生产计划.x1=0或

80x2=0或

80x3=0或

80最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.

汽车厂生产计划

决策变量为整数,建立整数规划模型.

求解整数规划和非线性规划比线性规划困难得多(即便用数学软件).

当整数变量取值很大时,可作为连续变量处理,问题简化为线性规划.

对于类似于“x=0或

80”这样的条件，通常引入0-1变量处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）.应如何安排原油的采购和加工

？

例2原油采购与加工市场上可买到不超过1500吨的原油A：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨.售价4800元/吨售价5600元/吨库存500吨库存1000吨汽油甲(A

50%)原油A原油B汽油乙(A

60%)决策变量

目标函数问题分析

利润：销售汽油的收入

购买原油A的支出.

难点：原油A的购价与购买量的关系较复杂.甲(A

50%)AB乙(A

60%)购买x

x11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？原油供应

约束条件x

500吨单价为10千元/吨；

500吨

x

1000吨，超过500吨的8千元/吨；1000吨

x

1500吨，超过1000吨的6千元/吨.目标函数购买x

ABx11x12x21x22库存500吨库存1000吨

目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解.

汽油含原油A的比例限制约束条件甲(A

50%)AB乙(A

60%)x11x12x21x22x1,x2,x3~以价格10,8,6(千元/吨)采购A的吨数目标函数

只有当以10千元/吨的价格购买x1=500(吨)时，才能以8千元/吨的价格购买x2方法1

非线性规划模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x)=10x1+8x2+6x3

500吨

x

1000吨，超过500吨的8千元/吨增加约束x=x1+x2+x3,c(x)=10x1+8x2+6x3

类似地有方法1：LINGO求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12<x+500;x21+x22<1000;x11-x21>0;2*x12-3*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1<500;x2<500;x3<500;end

Localoptimalsolutionfound.Objectivevalue:4800.000Totalsolveriterations:14VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.2666667X220.0000000.000000X10.0000000.4000000X20.0000000.000000X30.0000000.000000X0.0000000.000000LINGO得到的是局部最优解,还能得到更好的解吗？

用库存的500吨原油A、500吨原油B生产汽油甲，不购买新的原油A，利润为4800千元。

方法1：LINGO求解计算全局最优解：选LINGO|Options菜单；在弹出的选项卡中选择“GeneralSolver”；然后找到选项“UseGlobalSolver”将其选中；应用或保存；重新求解。

Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:1Totalsolveriterations:43VariableValueReducedCost

X110.0000000.000000X210.0000000.900000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2500.00000.000000X30.0000000.000000X1000.0000.000000

还有其他建模和求解方法吗？

购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，共生产2500吨汽油乙，利润为5000千元

。

y1,y2,y3=1~以价格10,8,6(千元/吨)采购A增加约束方法2

0-1线性规划模型,可用LINGO求解.y1,y2,y3=0或1购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，生产汽油乙，利润为5000千元。x1,x2,x3~以价格10,8,6(千元/吨)采购A的吨数y=0x=0x>0

y=1与方法1（全局最优解）的结果相同引入0-1变量b1b2

b3

b4方法3

b1

x

b2，x=z1b1+z2b2，z1+z2=1，z1,z2

0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2

x

b3，x=z2b2+z3b3，z2+z3=1，z2,z3

0,c(x)=z2c(b2)+z3c(b3).b3

x

b4，x=z3b3+z4b4，z3+z4=1，z3,z4

0,c(x)=z3c(b3)+z4c(b4).

直接处理处理分段线性函数c(x)IP模型，LINGO求解，得到的结果与方法2相同.bk

x

bk+1

yk=1,否则,yk=0方法3

bk

x

bk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+1

0,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2

b3

b4对于k=1,2,3

方法3:

直接处理分段线性函数，方法更具一般性.

分段函数无法直接用非线性规划方法或软件求解.原油采购与加工

方法1:

增加约束化为非线性规划,可以用LINGO求解,但可能得到的是局部最优解.

方法2:

引入0-1变量,化为线性规划模型,可用LINGO求解.分派问题4.4

接力队选拔和选课策略

若干项任务分给一些候选人来完成，每人的专长不同,完成每项任务取得的效益或需要的资源不同，如何分派任务使获得的总效益最大，或付出的总资源最少?

若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出抉择，使得收益最大或成本最小?讨论:丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4

100米混合泳接力队?例1混合泳接力队的选拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种.目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(秒)~队员i

第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人模型求解

MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata输入LINGO求解

min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END

模型求解

最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2输入LINGO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.6

75.2(秒)，戊自由泳c54=62.4

57.5(秒),方案是否调整？

敏感性分析？新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.最优解：x21=x32=x43=x51=1,成绩为4’17”7c43,c54

的新数据重新输入模型，用LINGO求解

原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.讨论混合泳接力队的选拔指派(Assignment)问题：有若干项任务,

每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?

人员数量与任务数量相等

人员数量大于任务数量(本例)

人员数量小于任务数量

?建立0-1规划模型是常用方法为了选修课程门数最少，应学习哪些课程？

例2选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学

2线性代数4数学

3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机

8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？

0-1规划模型

决策变量

目标函数

xi=1~选修课号i的课程（xi=0~不选）

选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课.课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机