整数规划

2014年数学与应用数学专业学年论文题目整数规划在资源分配中的应用成员姓名学号成绩1李素平11201040111良2李玉如11201040112良3孙泳铵11201040223良指导教师钟坚敏、黄正刚吴永、吕贵臣教师评语1摘要在工程设计和企业管理中，常常会遇到要求决策变量取整数值的规划问题。如安排生产计划时，投入的人力、机器数量必须是整数，生产的某些产品（如汽车、机床、船舶等）的数量也是整数。整数规划就是用于研究、处理这一类问题的一种数学规划。通过此论文的论述，可以对整数规划问题有一定程度的了解和认识,并运用于实际。在经济和科技研究中，我们会遇到要求决策变量取整数值的规划问题。整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻；资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低；生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析方面也有新的应用。关键字：整数规划；线性规划；资源分配优化；整型变量2整数规划在资源分配中的应用1.1整数规划简介整数规划（IP）是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。1.2问题的提出与数学模型1.2.1整数规划模型——资源分配优化问题例1：某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19米。（1）现有一客户需要50根4m、20根6m和15根8m的钢管。应该如何下料最节省？（2）零售商如果能采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用不同的切割模式不能超过3种。此外，该客户除（1）中的三种钢管外，还需要10根5m的钢管。应该如何下料最节省？问题（1）的求解问题分析首先，应当确定哪些切割模式是可行的。所谓的一个切割模式，是按照客户的需要在原料钢管上安排切割的一个组合。例如：可以将19m的钢管切割成3根4m的钢管，余料为7m；或者将19m的钢管切割成4m、6m和8m的钢管各一根，余料为1m，显然，可行的切割模式是很多的。其次，应当确定哪些是合理的切割模式。通常假设一个合理的切割模式的余料不应该大于或等于客户需要钢管的最小尺寸。例如：将19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可以进一步将7m的余料切割成4m的钢管（余料为3m），或者将7m的余料切割成6m（余料为1m）。在这种合理性假设下，切割模式一共有7种，如下表1所示。表1一根钢管的各种可能的切割模式4m钢管根数6m钢管根数8m钢管根数余料模式14003模式23101模式32013模式41203模式51111模式60301模式700233模型建立决策变量用ix表示按照第i种模式（，，，...i）切割的余料钢管的根数，显然它们应当是非负数。即0ix。决策目标以切割后剩余的总余料量最小为目标，则由表1可得：xxxxxxzmin(1)以切割后原料钢管的总根数最少为目标，则有xxxxxxzmin(2)下面分别在这两种目标下求解。约束条件为满足客户的要求：需要50根4m、20根6m和15根8m的钢管。按照表1中数据应有满足以下条件：xxxxx(3)xxxx(4)xxx(5)模型求解1.将（1），（3），（4），（5）构成的整数线性规划模型，以及整数约束条件。输入LINGO软件求解，可得到最优解：251346712150000=0xxxxxxx，，，，，，。即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共121527根，总余料量为121+151=27m。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和模式5的余料为1m），这会导致切割原料钢管的总数根数较多。2.将（2），（3），（4），（5）构成的整数线性规划模型（加上整数约束条件）输入LINGO求解，可得到最优解：1253467515,000=0xxxxxxx，，，，。即按照模式1切割5根原料钢管，按照模式2切割5根原料钢管，按照模式5切割15根原料钢管，共551525根，总余料量为535115135m。与上面得到的结果相比，总余料量增加了35278m，但是所用的原料钢管的总根数减少了27252根。在余料没有什么用途的情况下，通常选择总根数最少的为目标。问题（2）的求解模型建立决策变量由于不同的切割模式不能超过3种，可以用ix表示按照第i种模式（，，i）切割的余料钢管的根数，显然它们应该是非负整数。设所使用的第i种切割模式下每根原料钢管生产4m，5m，6m和8m的钢管数量分别为1234,,,iiiirrrr，且12340000iiiirrrr，，，。4决策目标切割钢管的总根数最少，目标为xxxzmin(6)约束条件为满足客户的需求，需要50根4m、10根5m、20根6m和15根8m的钢管，应有：xrxrxr(7)xrxrxr(8)xrxrxr(9)xrxrxr(10)每一种切割模式必须合理、可行，所以每根原料钢管的成品量不能超过19m，也不能少于16m（余量不能大于3m），即：rrrr(11)rrrr(12)rrrr(13)模型求解由LINGO软件输出结果可知，按照模式1、2、3分别切割13、7、6根原料钢管，使用原料钢管的总根数为26根，即可满足要求，且为最优解。例2：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。见表2.表2各类型每辆车的数据情况小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234（1）制订月生产计划，使工厂的利润最大。（2）如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？模型建立决策变量设每月生产小、中、大型汽车的数量分别为123xxx，，。决策目标根据月生产计划，使工厂的利润最大，则有123max234zxxx5约束条件根据表格中各类资源数据，有1231.535600xxx1231.535600xxx结果出现小数情况：1）舍去小数：取1264167xx，，算出目标函数值629z，与最优值632.2581相差不大。2）试探：如取12126516764168xxxx，；，等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。3）模型中增加条件：123080xxx，，或。均为整数，重新求解。1.3建立整数规划问题的数学模型步骤(1)确定问题的决策变量。(2)确定问题的目标，并表示为决策变量的整型函数。(3)找出问题的所有约束条件，并表示为决策变量的线性方程或不等式。1.4整数规划的数学模型用x表示决策变量，)(xf表示目标函数。实际问题一般对决策变量x的取值范围有限制，不妨记x，称为可行域。优化问题的数学模型可表示为Min（或max）)(xf，x。实际中的优化问题通常有多个决策变量，用n维向量12(,,)Tnxxxx表示，目标函数)x(f是多元函数，可行域比较复杂，常用不等式组（也可以有等式）()0(1,2,...,)igxim来界定，称为约束条件。一般地，这类模型可表述成如下形式min()..01,2,xizfxstgim，2整数规划模型的解法目前常用的求解ILP问题的方法有：1.分支定界法；2.割平面法；3.分解算法；4.松弛算法；5.群论算法等。分支定界法是实际工作中使用较多的一种。2.1分支定界法分支定界法的基本思想是反复的划分可行域，定出最优值z*的界限*z。对于极大化问题来说，下界即为有计算已求得的所有可行整数点中的最大目标值，上界可由松弛问题的最优值或尚未查清的子问题的最大目标值得到，分支定界法就是一个将问题不断地分支为几个子问题的集合，并确定6新的各个子问题的界限，直到求得所要求的解为止。分支定界法的计算步骤程序框图如下该框图是针对纯整数规划问题的，即J={1,2…n}的情况，对于混合型整数规划问题，可行域仅由整数变量来形成。入口图1分支定界法的计算步骤程序框图否P的可行解是是否是否否是是是否是P没有可行解？IxJxi,现行解为最优解停止确定问题P的最优值*z的上下界*z松弛问题0P松弛问题P选未分析完的子问题，并求解LP有可行解？各问题都分析完了吗？该子问题不需要再分支Z的问题P的最优解，与此相应的解为最优解有LP解中的非整数变量形成子问题z令z为它的最优值？zLP的解各分量都是整数吗？停止73总结整数线性规划在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须去整数值。要求全部决策变量取整数值的规划问题称为纯（或全）整数规划问题，仅要求部分决策变量取整数值的规划问题称为混合型整数规划问题，全部（或部分）决策变量只能取0，1值得规划问题称为0-1规划问题。整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。参考文献[1]姜启源谢金星叶俊，数学模型（第四版），北京：高等教育出版社；[2]刘卫国，MATLAB程序设计与应用（第二版），北京：高等教育出版社；[3]薛毅，数学建模基础，北京：北京工业大学出版社2004,4,1。附录附录一：例1问题（1）程序(LINGO)及输出：min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;4*x1+3*x2+2*x3+x4+x5=50;x2+2*x4+x5+3*x6=20;x3+x5+2*x7=15;x1=0;x2=0;x3=0;x4=0;x5=0;x6=0;x7=0;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7);运行结果：Globaloptimalsolutionfoundatiteration:13Objectivevalue:27.00000VariableValueReducedCostX10.0000003.000000X212.000001.000000X30.0000003.000000X40.0000003.000000X515.000001.000000X60.0000001.000000X70.0000003.0000008RowSlackorSurplusDual