运筹学整数规划

1、实验报告课程名称：运筹学项目名称：整数规划问题姓名： 专业：、 班级：1班 学号：同组成员： 二实验准备注：1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。2、若是单人单组实验，同组成员填无。注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加实验知识点：在前面我们所研究的线性规划问题中，一般问题的最优解都是非整数解，即 为分数和小数。但是对于实际中的具体问题的解常常要求必须取整数，即称为 整数解。为了求整数解，我们设想把所求的非整数解采用“舍入取整”的方法处 理，似乎是成了整数解，但事实上这样得到的结果未必是可行的。因为取整后就不一定是原问题的可行解了，或者虽然

2、是可行解，但也不一定是最优解。因此， 对于要求最优解整数解的问题，需要寻求直接的求解方法，这就是整数规划问题。如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题，相应的模型称为整数规划模型，在整数规划中，如果 所有的决策变量都为非负整数，则称之为纯整数规划问题；否则称之为混合整数 规划问题。如果整数规划的目标函数和约束都是线性的，则称此问题为整数线性规划问题。实验环境：LINGOS件二、实验过程记录2:例4.5设某部队为了完成某项特殊任务，需要昼夜 24小时不间断值班，但每天不 时段所需要的人数不同，具体情况如表 4-4所示。假设值班人员分别在各时间段5

3、时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名 班人员？表番班次的值晚时间段和人数4时间用需要大致a施次时间厚需要人数。1d： 00-W： 00邂4IS： M72； QQ5g210： 0014： Q07M522： 00也 00314： 0018； 106加62； ClClYf 003卜解：根据题意，假设用xi (i=1,2,3,4,5,6)分别表示第i个班次开始上班的人数,每个人都要连续值班8h,于是根据问题的要求可归结为如下的整数规划模型： TOC o 1-5 h z _6目标函数：min z x i 1x1 + x6 =60 x1 + x2 =70 x2 + x

4、3 =60约束条件：x3 + x4 =50 x4 + x5 =20 x5 + x6 =30 xi0,且为整数(i16)model :sets :num/1,2,3,4,5,6/:b,x;endsetsdata :b=60,70,60,50,20,30;enddataobj min =sum(num(i):x(i);x+x(6)=60;x(1)+x(2)=70;x(2)+x(3)=60;x(3)+x(4)=50;x(4)+x(5)=20;x(5)+x(6)=30;for (num(i): gin (x(i);x(i)=0);end运行该程序得到的结果为：x1=60,x2=10,x3=50,x4=

5、0,x5=30,x6=0 。即值班安排如下：第 班开始上班的人数为 60人，第一班开始上班的人数为10 人，第二班开始上班的人数为50人，第五班开始上班的人数为 30人，第四和第 六班无需新上班的人，共计需要 150人。练习4.5某小姐服装加工E以生产 A,B,C二种不同服装，生产不同种类的服装需要租用不同的加工设备，设备的租金、生产成本、销售价格等指标如表所示。如果各类服装都有足够的市场需求，该厂每月可用人工工时为2000h版厂应如何安排生产计划可使每月有最大的利润？服装种类一设备租金房生产成本/ （元源）E销售价格人工I&J7W 件“设备工时/设备可用工 时W*婷5000-2号卜1。叩/%

6、,*3 口口2000 媪40*-1 300#c炉20加2003底将*30N解：目标函数:max z = (400- 280) * x1 + (40-30) * x2 + (300 - 200) * x3 - 5000 * y1- 2000* y2 - 2000 * y35*x1 +x2 + 4*x3 = 2000约束条件：3*x1= 300*y10.5* x2 = 300* y22*x3 = 300* y3model :sets :num/1,2,3/:x,y;endsetsobjmax =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)

7、-2000*y-2000*y(3);5*x(1)+x(2)+4*x(3)=2000;3*x(1)=300*y(1);0.5*x(2)=300*y(2);2*x(3)=0; bin (y(i););end运行该程序得到的结果是：x1 = 100,x2=600,x3=150,最优值z=24000。即生产第一种服装A 100件，第二种服装B 600件，第三种服装C 150件, 每月的最大利润为24000元。练习4.9某公司现有资金10万元，拟在今后五年内考虑用于下列项目的投资：项目 A:从第一年到第四年每年年初需要投资，并于次年收回本利115% ,但要求第一年投资最低金额为4万元，第二、三、四年不限

8、。项目 B:第三年初需要投资， 到第五年末能收回本利128% ,但规定最低投资额为3万元，最高金额为5万 元。项目C:第二年初需要投资，到第五年末能收回本利 140%，但规定其投资 额或为2万元，或为4万元，或为6万元，或为8万元。项目D:五年内每年 初都可购买公债，于当年末归还，并获利息 6%,此项投资金额不限。试问该公 司应如何确定这些项目的每年投资金额，使得第五年末拥有最大的资金收益。解：由题意，设x为项目各年年初投入向量。xj为i种项目j年的年初的投入。(i=1,2,3,4 ; j=1,2,3,4,5 )。向量c中的元素a为i年末j种项目收回本例的百分比。矩阵A中元素ajj为约束条件中

9、每个变量xj的系数，Z为第5年末能拥有的资 金本利最大总额。目标函数为：z=1.15*x4a+1.28*x3b+1.40*x2c+1.06*x5dx1a + x1d = 100000-1.06*x1dx2a+ x2c+x2d = 0-1.15* x1a-1.06* x2d + x3a + x3b + x3d = 0-1.15* x2a-1.06* x3d + x4a + x4d = 0约束条件为：-1.15* x3a-1.06* x4d = x5dmodel :max =1.15*x4a+1.28*x3b+1.40*x2c+1.06*x5d;x1a+x1d=100000;-1.06*x1dx2

10、a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0;-1.15*x2a-1.06*x3d+x4a+x4d=0;-1.15*x3a-1.06*x4d=x5d;x1a=40000;x2c=20000;x2c=40000;x2c=60000;x2c=80000;x3b=30000;x3b=0;x2a=0;x3a=0;x4a=0;x5a=0;x1b=0;x2b=0;x3b=0;x4b=0;x5b=0; x1c=0;x2c=0;x3c=0;x4c=0; x5c=0;x1d=0;x2d=0;x3d=0; x4d=0;x5d=0;有资金10万元，第一年投入项目 A: 40000.00 ,投入项目D: 60000.00 或者22427.91 ;第二年投入项目 A: 22427.91 ,投入项目C: 20000.00 ,投入项目D: 3773.585 ;第三年投入项目B: 50000.00 ;其余年份几对应项目均没有投资。得到 五年末拥有最大的资金为60000元三、实验小结.规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型 中，变量限制为整数，则称为整数线性规划。.为了满足整数的要求，初看起来似乎只要