数学规划模型

数学规划模型第一页，共二十六页，编辑于2023年，星期三数学规划模型

实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值n和m较大最优解在边界上取得数学规划线性规划非线性规划整数规划本课程重点：模型的建立和结果的分析不等式约束无法用微分法求解第二页，共二十六页，编辑于2023年，星期三优化模型的简单分类

线性规划(LP)目标和约束均为线性函数

非线性规划(NLP)目标或约束中存在非线性函数

二次规划(QP)目标为二次函数、约束为线性

整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划连续优化离散优化数学规划第三页，共二十六页，编辑于2023年，星期三优化模型的简单分类和求解难度

优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加

第四页，共二十六页，编辑于2023年，星期三企业生产计划4.1奶制品的生产与销售

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

12小时8小时4公斤A2

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

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：第六页，共二十六页，编辑于2023年，星期三1桶牛奶3公斤A1

12小时8小时4公斤A2

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

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

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

50桶牛奶每天第七页，共二十六页，编辑于2023年，星期三模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型第八页，共二十六页，编辑于2023年，星期三模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。第九页，共二十六页，编辑于2023年，星期三模型求解

软件实现

LINGO10.0[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.00000020桶牛奶生产A1,30桶生产A2，利润3360元。迭代2次第十页，共二十六页，编辑于2023年，星期三运行状态窗口Variables（变量数量）：变量总数（Total）、非线性变量数（Nonlinear）、整数变量数（Integer）。Constraints（约束数量）：约束总数（Total）、非线性约束个数(Nonlinear)。Nonzeros（非零系数数量）：总数（Total）、非线性项系数个数(Nonlinear)。GeneratorMemoryUsed(K)(内存使用量)ElapsedRuntime(hh:mm:ss)（求解花费的时间）第十一页，共二十六页，编辑于2023年，星期三运行状态窗口求解器(求解程序)状态框当前模型的类型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以I开头表示IP，以PI开头表示PIP）当前解的状态:"GlobalOptimum","LocalOptimum","Feasible","Infeasible“(不可行),"Unbounded“(无界),"Interrupted“(中断),"Undetermined“(未确定)解的目标函数值当前约束不满足的总量(不是不满足的约束的个数):实数（即使该值=0，当前解也可能不可行，因为这个量中没有考虑用上下界命令形式给出的约束）目前为止的迭代次数第十二页，共二十六页，编辑于2023年，星期三运行状态窗口扩展的求解器(求解程序)状态框使用的特殊求解程序:B-and-B(分枝定界算法)Global(全局最优求解程序)Multistart(用多个初始点求解的程序)目前为止找到的可行解的最佳目标函数值目标函数值的界特殊求解程序当前运行步数：分枝数(对B-and-B程序)；子问题数(对Global程序)；初始点数(对Multistart程序)有效步数第十三页，共二十六页，编辑于2023年，星期三注：凡是可以从一个约束直接解出变量取值时，这个变量就不认为是决策变量而是固定变量，不列入统计中；只含有固定变量的约束也不列入约束统计中。运行状态窗口第十四页，共二十六页，编辑于2023年，星期三结果解释

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ3360.0001.000000ST10.00000048.00000

ST20.0000002.000000

ST340.000000.000000原料无剩余时间无剩余加工能力剩余40[obj]max=72*x1+64*x2;[st1]x1+x2<50;[st2]12*x1+8*x2<480;[st3]3*x1<100;三种资源“资源”剩余为零的约束为紧约束（有效约束）第十五页，共二十六页，编辑于2023年，星期三Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPriceOBJ

3360.0001.000000ST10.00000048.00000ST20.0000002.000000ST340.000000.000000结果解释

最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！第十六页，共二十六页，编辑于2023年，星期三第十七页，共二十六页，编辑于2023年，星期三

Rangesinwhichthebasisisunchanged:

ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000最优解不变时目标函数系数允许变化范围x1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)第十八页，共二十六页，编辑于2023年，星期三结果解释

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseST150.0000010.000006.666667ST2480.000053.3333380.00000ST3100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)加工能力可任意增加原料最多减少10时间最多减少53加工能力最多减少40第十九页，共二十六页，编辑于2023年，星期三例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%的波动，对计划有无影响？第二十页，共二十六页，编辑于2023年，星期三1桶牛奶

3千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/kg

0.8千克

B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5千克A1加工B1，x6千克A2加工B2附加约束

第二十一页，共二十六页，编辑于2023年，星期三模型求解

软件实现

LINGO10.0[obj]max=24*x1+16*x2+44*x3+32*x4-3*x5-3*x6;[st1]4*x1+3*x2+4*x5+3*x6<=600;[st2]4*x1+2*x2+6*x5+4*x6<=480;[st3]x1+x5<=100;[st4]x3=0.8*x5;[st5]x4=0.75*x6;第二十二页，共二十六页，编辑于2023年，星期三LINGO10.0模型求解

软件实现

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000“ReducedCost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率。其中基变量的reducedcost值应为0，对于非基变量Xj,相应的reducedcost值表示当某个变量Xj增加一个单位时目标函数减少的量(max型问题)。本例中：变量X1对应的reducedcost值为1.68，表示当非基变量X1的值从0变为1时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值=3460.8–1.68=3459.12。(基本不用它)第二十三页，共二十六页，编辑于2023年，星期三

Globaloptimalsolutionfound.

Objectivevalue:3460.800Totalsolveriterations:2

VariableValueReducedCost

X10.0000001.680000

X2168.00000.000000

X319.200000.000000

X40.0000000.000000

X524.000000.000000

X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000ST376.000000.000000ST40.00000044.00000ST50.00000032.00000结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1

除加工能力外均为紧约束第二十四页，共二十六页，编辑于2023年，星期三结果解释

Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000

X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPriceOBJ3460.8001.000000ST10.0000003.160000ST20.0000003.260000