整数规划简介及lingo求解

《整数规划简介及lingo求解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、整数规划及Lingo求解概论1・1整数规划的定义在工程设计和企业管理中，常常会遇到要求决策变量取整数值的规划问题。安排生产时，投入的人力与机器数量必须是整数，生产的某些产品(如汽车、机床、船舶等)的数量也是整数。整数规划就是用于研究、处理这一类问题的数学规划。如果在线性规划的基础上，把规划中的变量(部分或全部)限制为整数时，就称Z为线性整数规划。大部分的整数规划都是线性的所以我们也称线性整数规划为整数规划。在许多情况下，我们都可以把规划问题的决策变量看成是连续的变量；但在某些情况下，规划问题的决策变量却被要求一定是整数。例如，完成某项工作所需要的人数或

2、设备台数，进入市场销售的商品件数，以及某--机械设备维修的次数等。当连续的决策变量变为离散变量时非线性优化问题通常会难解得多。但是应用软件就方便多了，本文给了Lingo在规划中的常用方法和程序。1.2整数规划的分类在线性规划的基础上，要求所有变量都取整的规划问题称为纯整数规划问题；如果仅仅是要求一部分变量取整，则称为混合整数规划问题。全部或部分决策变量只能取0,1值的规划问题称为0-1规划问题。1.3整数规划的一般模型目标函数max(min)=(?內4-c2x2+•••+cnxn约束条件s.t.<^21^1+。22兀2+・・・+。2”兀”§k2色"內+

3、~2兀2+…+5“冉*决策集X为整数如果用集合表示上面的式子目标函数：max(min)=Cx约束条件为：Ax=b例1・1飞船装载问题设有斤种不同类型的科学仪器希望装在登月飞船上，令s>0表示每件第j类仪器的科学价值；勺>0表示每件第丿类仪器的重量。每类仪器件数不限，但装载件数只能是整数。飞船总载荷不得超过数b。设计一种方案，使得被装载仪器的科学价值之和最大。建模记®为第丿类仪器的装载数。目标函数max=》CjXj约束条件cijXj

4、制条件少的情况下分支定界法最为常用。因为Lingo软件可以很好的解决这一类问题，所以给岀Lingo的程序以便求解更复杂的问题。图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。用分枝定界法：反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题，且缩小最优质的取值范围，直到求得最优解.枚举法：列出所有可行解逐一比较求出最优解。2.2例题分析例2.1背包问题一个旅行者的背包最多只能装6kg物品，现有4件物品的重量和价值分别为2kg,3kg,3kg,4kg；1元，1.2元，0.9元，1

5、.1元。问应怎样携带那些物品使得携带物品的价值最大？建模：记形为旅行者携带第丿•件物品的件数，取值只能为0或1。求目标函数f=X、+1.2兀2+0・9兀3+1・1兀4在约束条件2兀1+3兀2+3形+4*4S6下的最大值.用Lingo软件求解0-1规划Model:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4<=6;@bin(xl);@bin(x2);@bin(x3);@bin(x4);End优结果匚二计算结果一~…图1结果解释例2.2某公司要在市东、西、南三区建立分公司。拟议中有7个位置(点)4(「=1,

6、2,・・・,7)可供选择。规定在东区：由三个点中至多选两个；在西区：由人,人两个点中至少选一个；在南区：由人两个点中至少选一个。如选用4点，设备投资估计为勺元，每年可获利润估计为q元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？解题时先引入0-1变量兀•(心1,2,…,7)1,当心•点被选中,"0,料点没被选中•日2…,7.于是问题可列写成:<=1x,+x2+<2七+£»1兀6+曲-1，Xi~0或1例2.3求目标函数/=3%!+2x2在约束条件：+3x2<14,+x2<9,兀］，兀2为自然数下的最大值。用Lingo软件求解整数规划mode

7、l:max=3*xl+2*x2;2*xl+3*x2<=14;2*xl+x2<=9;@gin(xl);@gin(x2);End计算结果为:最大值14,xl=4,x2=lo例2.4钢材截短问题有一批钢材，每根长7.3米•现需做100套短钢材.每套包括长2.9米，2.1米,1.5米的各一根.至少用掉多少根钢材才能满足需要，并使得用料最省.分析：可能的截法和余料第1种7.3-(2.9X2+1.5)=0第2种7.3・(2.9+2」X2)=0.2第3种7.3-(2.9+1.5X2)=1.4第4种7.3-(2.9+2.1+1.5)=0.8第5种7.3・(2.1X2+

8、1.5X2)=0.1第6种7.3-(2.IX3)=1第7种7.3-(2」+1.5X3)=0.7