整数规划简介及Lingo求解

《整数规划简介及Lingo求解》由会员分享，可在线阅读，更多相关《整数规划简介及Lingo求解（9页珍藏版）》请在装配图网上搜索。

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

2、市场销售的商品件数，以及某一机械设备维修的次 数等。当连续的决策变量变为离散变量时非线性优化问题通常会难解得多。但是 应用软件就方便多了，本文给了 Lingo在规划中的常用方法和程序。1.2 整数规划的分类 在线性规划的基础上，要求所有变量都取整的规划问题称为 纯整数规划问题；如果仅仅是要求一部分变量取整，则称为混合整数规划问题。全部或部分决 策变量只能取0，1值的规划问题称为0-1规划问题。1.3 整数规划的一般模型目标函数max(min) = ex + ex Hbex1 1 2 2 n nax+ axbb ax k约束条件11 112 21n n1ax+ axbb a x kS.t.v21

3、 122 22 n n2a x + a x bb a x 0表示每件第j 类仪器的科学价值；a 0表示每件第j类仪器的重量。每类仪器件数不限，但 装载件数只能是整数。飞船总载荷不得超过数b。设计一种方案，使得被装载仪 器的科学价值之和最大。建模 记 x 为第 j 类仪器的装载数。j目标函数ma=Y e x约束条件工a x b决策集x 为正整数算法简介及应用举例2.1 解整数规划的一般算法 通常解整数规划有三种方法，下面只介绍算法思想不具体讲解，在限制条件 少的情况下分支定界法最为常用。因为Lingo软件可以很好的解决这一类问题， 所以给出 Lingo 的程序以便求解更复杂的问题。图解法：解两个

4、变量的线性规划问题，在平面上画出可行域，计算目标函数 在各极点处的值，经比较后，取最值点为最优解。用分枝定界法：反复划分可行域并确定最优值的界限,将原问题不断地分枝 为若干个子问题, 且缩小最优质的取值范围,直到求得最优解.枚举法：列出所有可行解逐一比较求出最优解。 2.2例题分析例 2.1 背包问题 一个旅行者的背包最多只能装 6kg 物品，现有 4 件物品的重量和价值分别 为 2 kg， 3 kg， 3 kg， 4 kg；1 元， 1.2 元， 0.9 元， 1.1 元。问应怎样携带那些物 品使得携带物品的价值最大?建模：记x.为旅行者携带第j件物品的件数，取值只能为0或1。求目标函数 f

5、 = x +1.2x + 0.9x + 1.1x 在约束条件 2x + 3x + 3x + 4x 612341234下的最大值.用 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(x1);bin(x2);bin(x3);bin(x4);End 计算结果最优结果图 1 结果解释例 2.2 某公司要在市东、西、南三区建立分公司。拟议中有7 个位置(点)A (i二1,2,7)可供选择。规定i在东区：由A , A , A三个点中至多选两个；123在西区：由 A ,A 两个点中至少选一个；45在南区

6、：由 A ,A 两个点中至少选一个。67如选用A点，设备投资估计为b元，每年可获利润估计为c元，但投资总额iii不能超过B元。问应选择哪几个点可使年利润为最大？解题时先引入0 -1变量x (i二1,2,7)i1,当人?点被选中，.-宀ii = 1,2, ,7.0,当人,点没被选中i于是问题可列写成：Max z = c xii b x Biii=1x + x + x 145x + x 1,67s.t. Si=112例2.3 求目标函数f = 3x + 2x在约束条件：2x + 3x 14 , 2x + x 9,1 2 1x1, x 为自然数下的最大值。 用1 Li2ngo 软件求解整数规划 mo

7、del： max =3*x1+2*x2;2*x1+3*x2=14;2*x1+x2 0 , i=l,.,8编程：model:imin=0.2*x2+1.4*x3+0.8*x4+0.1*x5+x6+0.7*x7+1.3*x8; 2*x1+x2+x3+x4=100;2*x2+x4+2*x5+3*x6+x7=100; x1+2*x3+x4+2*x5+3*x7+4*x8=100; gin(x1);gin(x2);gin(x3);gin(x4); gin(x5);gin(x6);gin(x7);gin(x8);end解得 x =(40, 20, 0, 0, 30, 0, 0, 0) ,f (x ) = 7

8、ii三、集合在整数规划中的应用例 3.1 SAILCO 公司需要决定下四个季度帆船的生产量。下四个季度帆船 的需求量分别是 40 条， 60 条， 75 条， 25 条，这些需求必须按时满足。每个季 度正常的生产能力是 40 条帆船，每条船的生产费用为 400 美元。如果加班生产， 每条船的生产费用为 450 美元。每个季度末，每条船的库存费用为 20 美元。假 定生产提前期为0，初始库存为10条船，如何安排生产可使总费用最小？我们用DEM, RP, OP, INV分别表示需求量、正常生产量、加班生产量、 库存量，则DEM，RP，OP，INV对每个季度都应该有一个对应的值，也就是说 他们都应该

9、是一个由4个元素组成的数组，其中DEM是已知的，而RP，OP， INV是未知的。现在我们可以写出这个问题的模型。首先，目标函数是所有费用 的和：Min 工 仃00RP(I) + 450OP(I) + 20INV(I)(1)/=1,2,3,4约束条件主要有两个：(1) 能力限制RP(I) 40，I=1，2，3，4；(2)(2) 产品数量的平衡方程INV(I) =INV(I-1) +RP(I) -DEM(I)，I=1， 2， 3， 4；(3)INV(0) =10；(4)当然还要加上变量的非负约束，构成了这个问题的模型。可以看出，如果利用数组的概念，这个模型是比较容易建立的，记 4个季度 组成的集合

10、QUARTERS=1, 2, 3, 4,它们就是上面数组的下标集合，而数组 DEM, RP, OP, INV对集合QUARTERS中的每个元素1, 2, 3, 4分别对应于 一个值，如图3-13所示。LINGO正是充分利用了这种数组及其下标的关系，引 入了“集合”及其“属性”的概念，把QUARTERS=1, 2, 3, 4称为集合，把 DEM, RP, OP, INV 称为该集合的属性（即定义在该集合上的属性）。表 1 更 清楚地列出了集合元素及其属性所确定的所有变量。图 2 集合及其属性表 1 集合元素及集合的属性确定的所有变量集合QUARTERS的元素1234定义在集合 QUARTERS

11、上的属性DEMDEM（1）DEM（2）DEM（3）DEM（4）RPRP（1）RP（2）RP（3）RP（4）OPOP（1）OP（2）OP（3）OP（4）INVINV（1）INV（2）INV（3）INV（4）下面我们看看LINGO中具体如何定义集合及其属性。例3.1的LP模型在 LINGO 中的一个典型的输入方式见图 3.我们可以看到这个输入方式以 “MODEL：”开始，以“END”结束，它们之间有语句构成，可以分为三个部 分：图 3 输入方式（1） 集合定义部分（从“SETS：”到“ENDSET”）：定义集合及其属性， 语句“ QUARTERS/1,2,3,4/:DEM,RP,OP,INV其结果

12、正是定义了表1所列出的16 个变量名（并不一定都是决策变量，如下面马上就看到 DEM 对应的 4 个变量是 已知的）。（2） 数据输入部分（从“ DATA ”到“ENDDATA”）： “DEM=40, 60， 75，25；”给出常量DEM （给定的需求量）的值，即DEM（1）=40，DEM（2） =60， DEM（ 3） =75， DEM（ 4） =25.（3）其他部分：给出优化目标函数和约束。目标函数（“MIN =”后面所接的表达式）是用求和函数“SUM （集合（下标）：关于集合的属性的表达式）” 的方式定义的，这个函数的功能是对语句中冒号后面的表达式，按照“：”前面 的集合指定的下标（元素

13、）进行求和。本例中目标函数也可以等价的写成“ SUM（QUARTERS（i）:400*RP（i）+450*OP（i）+20*INV（i）” ,这里“ SUM ”相 当于求和符号“工 ”，而“QUARTERS（i）”相当于“ig QUARTERS”的含义。 只是由于本例中目标函数对集合QUARTERS的所有元素（下标）都要求和，所 有我们在相应的语句中将下标i省去。约束是用循环函数“FOR（集合（下标）：关于集合的属性的约束关系式）” 的方式定义的，意思是对冒号“：”前面的集合的每个元素（下标），冒号“：” 后面的约束关系式都要成立。我们先看到能力限制（2），即每个季度正常的生产 能力是40条帆

14、船，这正是语句“FOR（QUARTERS（I）： RP（I）1； “#GT#”是逻辑运算符号，意思是“大于”， 其他的在后面介绍。现在运行菜单命令“LINGOISolve”，则可以得到图3-15所示的解答报告， 全局最优解 RP=（40， 40， 40， 25）， OP=（0， 10， 35， 0），最小成本=78450. 这就是我们模型的计算结果。四、Lingo程序解释及常用函数简介4.1 Lingo 注意事项1. Lingo中模型以“MODEL:”开始，以“END”结束，对于简单的模型，这两 个语句都可以省略；2. Lingo中每行后面均增加了一个分号“”;3. 所有符号都需在英文状态下输

15、入；4. min=函数，max=函数，表示求函数的最小，最大值；5. Lingo 中变量不区分大小写，变量名可以超过 8 个，不能超过 32 个，需 以字母开头；6. 用Lingo解优化模型时已假定所有变量非负，如果想解除这个限制可以用 函数free(x)，这样x可以取到任意实数；7. 变量可以放在约束条件右端，同时数字也可以放在约束条件左边；8. Lingo 模型语句由一系列语句组成，每一个语句都必须以“;”结尾；9. Lingo 中以“！”开始的是说明语句，说明语句也以“ ;” 结束。4.2 Lingo 中的其他常用函数1. ABS (X)：绝对值函数，返回X的绝对值；2. EXP (X)

16、：指数函数(以自然对数e为底)，返回eX的值；3. LOG (X)：自然对数函数，返回X的自然对数值；4. POW (X，Y)：指数函数，返回XY的值；5. SQR (X)：平方函数，返回X2的值；6. SQRT (X)：平方根函数，返回X的平方根；7. FLOOR (X)：取整函数，返回X的整数部分(向靠近0的方向取)；8. SMAX (X)：取最大值，返回一列数(LIST)的最大值；9. SMIN (X)：取最大小值，返回一列数(LIST)的最小值；10. 三角函数：COS (X)，SIN (X)，TAN (X)； 变量定界函数对变量的取值范围附加限制，共有以下四种：1. BND (L，X

17、，U)：限制 L = X = required(J);end计算的部分结果为Global optimal solution found at iteration: 0Objective value: 22.00000VariableValueReduced CostREQUIRED( MON)20.000000.000000REQUIRED( TUE)16.000000.000000REQUIRED( WED)13.000000.000000REQUIRED( THU)16.000000.000000REQUIRED( FRI)19.000000.000000REQUIRED( SAT)14.

18、000000.000000REQUIRED( SUN)12.000000.000000START( MON)8.0000000.000000START( TUE)2.0000000.000000START( WED)0.0000000.3333333START( THU)6.0000000.000000START( FRI)3.0000000.000000START( SAT)3.0000000.000000START( SUN)0.0000000.000000从而解决方案是：每周最少需要22个职员，周一安排 8人，周二安排 2 人，周 三无需安排人，周四安排 6 人，周五和周六都安排 3 人，周日无需安排人。