运筹学优化建摸

运筹帷幄之中决胜千里之外运筹学课件绪论Introduction线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容线性规划模型（1）线性(linearprogramming)规划主要解决：如何利用现有的资源，使得预期目标达到最优。某公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1解：设公司制造Ⅰ、Ⅱ两种家电分别为件。问题：x1=?x2=?利润Z最大？线性规划模型（1）线性规划模型设备A工时限制：设备B工时限制：项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1线性规划模型调试工序时间限制：利润：即要求：目标函数约束条件资源约束非负约束线性规划模型（1）初试LINDO解如下LP问题:

LINDO

中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“<=”及“>=”可用“<”及“>”代替.上述问题用键盘输入如下线性规划模型（1）：MAX2X1+3X2?

ST(说明:也可写成S.T.,

SUCHTHAT

或SUBJECTTO

等）?5X2<15?6X1+2X2<24

?X1+X2<5?

END

：GO线性规划模型（1）线性规划模型（3）LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)8.500000VARIABLEVALUEREDUCEDCOST

X1

3.5000000.000000

X2

1.500000

0.000000ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?线性规划模型（2）捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。线性规划模型（2）月份

1234所需仓库面积15102012表1-2表1-3合同租借期限

1个月2个月3个月4个月合同期内的租费2800450060007300单位：100m2单位；元/100m2解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12目标函数约束条件线性规划模型（2）:min2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13+6000x23+7300x14?st?x11+x12+x13+x14>15?x12+x13+x14+x21+x22+x23>10?x13+x14+x22+x23+x31+x32>20?x14+x23+x32+x41>12?end:go线性规划模型（2）LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)118400.0VARIABLEVALUEREDUCEDCOSTX113.0000000.000000X210.0000002800.000000X318.0000000.000000X410.0000001100.000000X120.0000001700.000000X220.0000001700.000000X320.0000000.000000X130.000000400.000000X230.0000001500.000000X1412.0000000.000000线性规划模型（2）整

数

规

划

在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等.对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题.

整数规划(integerprogramming)简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题.例2.0.1

某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表2.1.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413表2.1表2.1货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解

设

分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:求解整数规划IP（整数规划）问题的输入与LP类似，但在END标志后需定义整型变量。0-1型整数变量可用INTEGER（可简写为INT）命令来标示；其它整数变量可用GIN命令来标示.标示方法有两种：1）INTEGERVname

或GINVname表示将变量Vname标示为0-1型或为一般整数变量。2）INTn或GINn表示将当前模型中前n个变量标示为0-1型变量或为一般整数变量。例3

求解0-1整数规划:max3x1-2x2+5x3?st?x1+2x2-x3<2?x1+4x2+x3<4?x1+x2<3?4x2+x3<6?end:intx1:intx2:intx3:goInt3LINDO输出下列结果：

LPOPTIMUMFOUNDATSTEP2OBJECTIVEVALUE=8.00000000NEWINTEGERSOLUTIONOF8.00000000ATBRANCH0PIVOT2RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)8.000000VARIABLEVALUEREDUCEDCOSTX1

1.000000-3.000000X2

0.0000002.000000X3

1.000000-5.000000ROWSLACKORSURPLUSDUALPRICES2)

2.0000000.0000003)

2.0000000.0000004)

2.0000000.0000005)

5.0000000.000000例4

求解0-1整数规划在LINDO中输入下列命令：:min3x1+7x2-x3+x4?st?2x1-x2+x3-x4>1?x1-x2+6x3+4x4>8?5x1+3x2+x4>5?end:int4:goLINDO输出下列结果：

LPOPTIMUMFOUNDATSTEP4OBJECTIVEVALUE=2.10526323NEWINTEGERSOLUTIONOF3.00000000ATBRANCH0PIVOT4RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)3.000000VARIABLEVALUEREDUCEDCOSTX1

1.0000003.000000X2

0.0000007.000000X3

1.000000-1.000000X4

1.0000001.000000ROWSLACKORSURPLUSDUALPRICES2)

1.0000000.0000003)

3.0000000.0000004)

1.0000000.000000例5求解下列整数线性规划问题在LINDO中输入下列命令：:MINX1+X2+X3+X4+X5+X6?ST?X2+2X3+3X4+4X5+5X6>10000?6X1+5X2+3X3+2X4+X5>20000?END:GIN6:GOLINDO运行后输出以下结果：STATUS：OPTIMALLPOPTIMUMFOUNDATSTEP3OBJECTIVEVALUE=5200.00000FIXALLVARS.(4)WITHRC>0.400000E-01NEWINTEGERSOLUTIONOF5200.00000ATBRANCH0PIVOT3BOUNDONOPTIMUM:5200.000ENUMERATIONCOMPLETE.BRANCHES=0PIVOTS=3LASTINTEGERSOLUTIONI