《整数规划问题结课大作业》由会员分享，可在线阅读，更多相关《整数规划问题结课大作业（7页珍藏版）》请在金锄头文库上搜索。
1、整数规划与指派问题实验报告实验序号： 日期：20 年 月 日班级电气 1102姓 名吴刚学 号1111180221实验 名称整数规划与指派问题问题背景描述： 在某些实际问题中要求答案必须为整数，如人数，机器台数。对 求整数规划不是用四舍五入或去尾法对线性规划处理解决，而要 用整数规划的方法加以解决。 实验目的： 1. 理解指派问题这一特殊整数线性规划问题的特点，体会指派问题求解的匈牙利方法；2 掌握用 Matlab 或 LINDO 求解指派问题的方法和步骤，学会利用 Matlab 或 LINDO 求解具体指派问题及其变形问题。3.锻炼应用所学知识解决综合性问题的能力实验所用软件及版本： LIN
2、GO 例题例题：有四个工人，分别指派他们完成四项不同的工作，每个人各项工作所消耗的时间如下 表所示，问应该如何指派工作，才能使总时间为最少？ ABCD 甲15182124 乙19232218 丙26171619 丁19212317 实验原理与数学模型： 设：第 i 个人指派 j 项任务为 Xij;Xij=1 时指派该人完成该任务，Xij=0 时不指派， 则最小时间 min z=15X11+18X12+21X13+24X14+19X21+23X22+22X23+18X24+26X31+17X32+ 16X33+19X34+19X41+21X42+24X43+17X44； s.t. X11+X12
3、+X13+X14=1; X21+X22+X23+X24=1; X31+X32+X33+X34=1; X41+X42+X43+X44=1; X11+X21+X31+X41=1; X12+X22+X32+X42=1; X13+X23+X33+X43=1; X14+X24+X34+X44=1; Xij=0 或 1实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）： 运算程序： model: min =15*X11+18*X12+21*X13+24*X14+19*X21+23*X22+22*X23+18*X24+26*X31+17*X32+ 16*X33+19*X34+19*X41+21*X4
4、2+24*X43+17*X44; X11+X12+X13+X14=1; X21+X22+X23+X24=1; X31+X32+X33+X34=1; X41+X42+X43+X44=1; X11+X21+X31+X41=1; X12+X22+X32+X42=1; X13+X23+X33+X43=1; X14+X24+X34+X44=1; end运算结果： Global optimal solution found.Objective value: 70.00000Infeasibilities: 0.000000Total solver iterations: 7Variable Value R
5、educed CostX11 0.000000 0.000000X12 1.000000 0.000000X13 0.000000 4.000000X14 0.000000 10.00000X21 1.000000 0.000000X22 0.000000 1.000000X23 0.000000 1.000000X24 0.000000 0.000000X31 0.000000 12.00000X32 0.000000 0.000000X33 1.000000 0.000000X34 0.000000 6.000000X41 0.000000 1.000000X42 0.000000 0.0
6、00000X43 0.000000 4.000000X44 1.000000 0.000000Row Slack or Surplus Dual Price1 70.00000 -1.0000002 0.000000 -14.000003 0.000000 -18.000004 0.000000 -13.000005 0.000000 -17.000006 0.000000 -1.0000007 0.000000 -4.0000008 0.000000 -3.0000009 0.000000 0.000000实验结果报告与实验总结： 指派甲完成 B，乙完成 A，丙完成 C 丁完成 D 最小时间
7、为 70 小时习题一： 某公司在今后五年内考虑下列项目投资，已知： 项目 A：从第一年到第四年每年年初需要投资，并于次年收回本 利 115%，但要求第一年投资最低金额为 4 万元，第二、三、四 年不限。 项目 B：第三年初需投资，到第五年末能收回本利 128%，但规 定最底投资金额为 3 万元，最高金额为 5 万元。 项目 C：第二年初需要投资，到第五年末能收回本利 140%，但 规定其投资额或为 2 万元或为 4 万元或为 6 万元或为 8 万元。 项目 D：五年内每年初可购买公债，于但年归还，并加利息 6%，此项投资不限金额。 该部门现有资金 10 万元，问它应如何确定给这些项目的每年投
8、资额，使五年末拥有的资金本利总额为最大。 实验原理与数学模型： 设第 i 年给各项目的投资额为 Xi1,Xi2,Xi3,Xi4;Y1 为第一是否年投资 A，Y2，Y3 为是否投资 B，C 第一年 X11+X14=100000； 第二年 X21+X23+X24=1.06X14； 第三年 X31+X32+X34=1.15X11+1.06X24； 第四年 X41+X44=1.15X21+1.06X34； 第五年 X54=1.15X31+1.06X44； 则 max z=1.15X41+1.28X32+1.40X23+1.06X54; X11=40000Y1; X32=2000Y2 30000Y3=4
9、0000*Y1; X23=30000*Y3; X32=20000*Y2; Y2=4; Y1=1; Y3=1; GIN(Y1);GIN(Y2);GIN(Y3); End 运算结果： Local optimal solution found.Objective value: 147720.0Objective bound: 147720.0Infeasibilities: 0.7275958E-11Extended solver steps: 6Total solver iterations: 116Variable Value Reduced CostX41 800.0000 0.000000X
10、32 60000.00 0.000000X23 50000.00 0.000000X54 0.000000 0.000000Y1 1.000000 0.000000X11 52173.91 0.000000X14 47826.09 0.000000X21 695.6522 0.000000X24 0.000000 0.3036000E-01X31 0.000000 0.000000X34 0.000000 0.000000X44 0.000000 0.2640000E-01Y3 1.000000 0.000000Y2 3.000000 -1220.000Row Slack or Surplus
11、 Dual Price1 147720.0 1.0000002 0.000000 1.4018503 0.000000 1.3225004 0.000000 1.2190005 0.000000 1.1500006 0.000000 1.0600007 12173.91 0.0000008 0.000000 0.7750000E-019 20000.00 0.00000010 0.000000 0.6100000E-0111 1.000000 0.00000012 0.000000 0.00000013 0.000000 3875.000实验结果报告与实验总结： 第一年投 A52173.91D
12、477826.09 第二年投 A695.65C50000 第三年投 B60000 第四年投 A800 为 147720 元 习题二： 现需要将一些不同类型的货物装到一条货船上，货物的单价重量， 单位体积，冷藏需求，可燃性指数都不同，由下表给出 货号单位重量 单位体积 冷藏需要 可燃性指 数价格1201需要0.15 252不要0.210 3103不要0.415 4124需要0.118 5255不要0.225 该船可以装载总质量为 400000kg，总体积 50000m2，可冷藏总体 积 10000m2，容许可燃性指数不超过 750.目标是货物价格最大。实验原理与数学模型： 设 i 货物件数为 Xi Maxz=5X1+10X2+15X3+18X4+25X5; s.t. 20X1+5X2+10X3+12X4+25X5=400000; X1+2X2+3X3+4X4+5X5=50000; X1+4X4=10000; 0.1X1+0.2X2+0.4X3+0.1X4+0.2X5=750; Xi
