实验报告——整数规划1

数学 实验序号：                              日期：2012  年  6月  8日 班级 水文1001 姓名 熊元武 学号 1101550120 实验 名称 整数规划之分支定界、割平面 问背景描述： 求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。 实验目的： 1. 理解整数线性规划和普通线性规划的区别，体会整数规划求解的分支定界法、割平面法与隐枚举方法的思想，掌握整数规划求解的方法与步骤。 2 掌握用Matlab或LINDO求解整数规划的方法和步骤，学会利用Matlab或LINDO求解具体整数规划问题。 3.锻炼应用所学知识解决综合性问题的能力 实验原理与数学模型： 整数线性规划是一类特殊的线性规划，在实际生活中大量存在。整数规划问题的求解，通常是这样的一个过程：首先，去掉整数约束，借助普通线性规划求解的单纯形方法得到问题的一个最优解，然后进行整数约束判定，如果得到的是整数最优解，结束；否则，利用分支或者割平面方法去掉不满足整数约束的最优解，重新求解，知道得到问题的整数最优解或判定问题无解为止。本实验的主要目的是帮助学生加深对这一求解过程的认识和理解，掌握一种人机结合的半自动化的问题求解模式，并尝试将这个过程尽量多的自动化。 实验所用软件及版本： LINDO9.0 主要（要点）： 1. 复习整数规划的分支定界法，熟悉分支定界法的步骤 2. 掌握lingo的整数规划解法 3. 用整数规划的方法解决下面关于固定成本和分布系统的例题 实验过程（含：基本步骤、主要程序清单及异常情况记录等）： 例1：高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 解：设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i 种容器, 即 xi ＞ 0 时) 或 0（当不生产第 i种容器即xi = 0 时）。 引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0。 这样我们可建立如下的数学模型： max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xi ≥ 0 yi 为0-1变量，i = 1,2,3 下面是lingo程序： model: data: M=150; enddata max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3<=500; 2*x1+3*x2+4*x3<=300; x1+2*x2+3*x3<=100; x1<=M*y1; x2<=M*y2; x3<=M*y3; @GIN(x1);@GIN(x2);@GIN(x3); @BIN(y1);@BIN(y2);@BIN(y3); end （转下页） 实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页）： Global optimal solution found. Objective value: 300.0000 Extended solver steps: 0 Total solver iterations: 4 Variable Value Reduced Cost M 150.0000 0.000000 X1 100.0000 -4.000000 X2 0.000000 -5.000000 X3 0.000000 -6.000000 Y1 1.000000 100.0000 Y2 0.000000 150.0000 Y3 0.000000 200.0000 Row Slack or Surplus Dual Price 1 300.0000 1.000000 2 300.0000 0.000000 3 100.0000 0.000000 4 0.000000 0.000000 5 50.00000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 解得，最大目标函数值为300，最优解为x1=100，x2=0，x3=0。也就是说生产100台小容器可得最大利润300万元。 例2：已知 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元； 项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大? 解：设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；设yiA， yiB，是0-1变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（ i = 1, 2, 3, 4, 5）。我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C D x1D x2D x3D x4D x5D 实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页）： max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D； x1A ≥ 40000y1A ， x1A ≤ 200000y1A ， x3B ≥ 30000y3B ， x3B ≤ 50000y3B ； yiA， yiB = 0 或 1，i = 1,2,3,4,5 x2C = 0，20000，40000，60000，80000 xiA ，xiB ，xiC ，xiD ≥ 0 ( i = 1、2、3、4、5） 下面是lingo程序： model: max=1.15*x4A+1.40*x2C+1.28*x3B+1.06*x5D; x1A+x1D=100000; x2A+x2C+x2D=1.06*x1D; x3A+x3B+x3D=1.15*x1A+1.06*x2D; x4A+x4D=1.15*x2A+1.06*x3D; x5D=1.15*x3A+1.06*x4D; x1A>=40000*y1A; x1A<=200000*y1A; x3B>=30000*y3B; x3B<=50000*y3B; @BIN(y1A);@BIN(y3B);@GIN(y2C); x2C=20000*y2C; y2C<=4; end Global optimal solution found. Objective value: 147879.2 Extended solver steps: 0 Total solver iterations: 8 Variable Value Reduced Cost X4A 0.000000 0.000000 X2C 60000.00 0.000000 X3B 49905.66 0.000000 X5D 0.000000 0.000000 X1A 43396.23 0.000000 X1D 56603.77 0.000000 X2A 0.000000 0.6617925E-01 X2D 0.000000 0.3187925E-01 X3A 0.000000 0.6100000E-01 X3D 0.000000 0.6100000E-01 X4D 0.000000 0.2640000E-01 Y1A 1.000000 0.000000 Y3B 1.000000 0.000000 Y2C 3.000000 -226.4151 解得，最优值为147879.2 实验结果报告与实验总结： 如果用四舍五入法或去尾法对线性规划的非整数解加以处理，求得的解不一定是线性规划问题的最优整数解。因此解决这类问题必须用整数规划的方法。其中，分支定界法和割平面法是两种比较常用的整数规划方法。 分枝定界: 计算效率高, 应用广泛; 割平面法: 有理论意义, 但计算效率较低 思考与深入： 处理个别实际问题时，如果允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原题整数最优解的近似。这样可节省求解的人力、物力和财力。 教师评语：