一、 概论
1.1 整数规划的定义
在工程设计和企业管理中，常常会遇到要求决策变量取整数值的规划问题。安排生产时，投入的人力与机器数量必须是整数，生产的 某些产品（如汽车、机床、船舶等）的数量也是整数。整数规划就是用于研究、处理这一类问题的数学规划。如果在线性规划的基础上，把规划中的变量（部分或全部）限制为整数时，就称之为线性整数规划。大部分的整数规划都是线性的所以我们也称线性整数规划为整数规划。 在许多情况下，我们都可以把规划问题的决策变量看成是连续的变量；但在某些情况下，规划问题的决策变量却被要求一定是整数。例如，完成某项工作所需要的人数或设备台数，进入市场销售的商品件数，以及某一机械设备维修的次数等。当连续的决策变量变为离散变量时非线性优化问题通常会难解得多。但是应用软件就方便多了，本文给了Lingo在规划中的常用方法和程序。
1.2 整数规划的分类
在线性规划的基础上，要求所有变量都取整的规划问题称为纯整数规划问题；如果仅仅是要求一部分变量取整，则称为混合整数规划问题。全部或部分决策变量只能取0，1值的规划问题称为规划问题。
1.3 整数规划的一般模型
目标函数
约束条件
决策集 为整数
目标函数：
约束条件为：
例 1.1 飞船装载问题
设有种不同类型的科学仪器希望装在登月飞船上, 令表示每件第类仪器的科学价值；表示每件第类仪器的重量。每类仪器件数不限, 但装载件数只能是整数。飞船总载荷不得超过数。设计一种方案, 使得被装载仪器的科学价值之和最大。
建模 记为第类仪器的装载数。
目标函数
约束条件
决策集 为正整数
二、 算法简介及应用举例
2.1 解整数规划的一般算法
通常解整数规划有三种方法，下面只介绍算法思想不具体讲解，在限制条件少的情况下分支定界法最为常用。因为Lingo软件可以很好的解决这一类问题，所以给出Lingo的程序以便求解更复杂的问题。
图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。
用分枝定界法：反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解.
枚举法：列出所有可行解逐一比较求出最优解。
2.2例题分析
例 2.1 背包问题
一个旅行者的背包最多只能装 6kg 物品，现有4 件物品的重量和价值分别为 2 kg，3 kg，
3 kg，4 kg；1 元，1.2元，0.9元，1.1元。问应怎样携带那些物品使得携带物品的价值最大?
建模：记为旅行者携带第件物品的件数, 取值只能为 0 或 1。
求目标函数在约束条件下的最大值.
用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个位置（点）可供选择。规定
在东区：由三个点中至多选两个；
在西区：由两个点中至少选一个；
在南区：由两个点中至少选一个。
如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不能超过元。问应选择哪几个点可使年利润为最大？
解题时先引入变量
令
.
于是问题可列写成：
s.t.
例2.3 求目标函数在约束条件:, , ,为自然数下的最大值。
用Lingo软件求解整数规划
model:
max =3*x1+2*x2;
2*x1+3*x2<=14;
2*x1+x2<=9;
@gin(x1);
@gin(x2);
End
计算结果为：最大值14，x1=4，x2=1。
例2.4 钢材截短问题
有一批钢材, 每根长7.3米. 现需做100套短钢材. 每套包括长2.9米, 2.1米,1.5米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省.
分析： 可能的截法和余料
第1种 7.3-(2.9×2+1.5)=0
第2种 7.3-(2.9+2.1×2)=0.2
第3种 7.3-(2.9+1.5×2)=1.4
第4种 7.3-(2.9+2.1+1.5)=0.8
第5种 7.3-(2.1×2+1.5×966人荣获2022年全国五一劳动奖章2)=0.1
第6种 7.3-(2.1×3)=1
第7种 7.3-(2.1+1.5×3)=0.7
第8种 7.3-(1.5×4)=1.3
模型：设决策变量按第种方法截根钢材。
求目标函数的最小值
约束条件
， =1,…,8
编程：
model:
min=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
解得=(40, 20, 0, 0, 30, 0, 0, 0) , = 7
三、集合在整数规划中的应用
例3.1 SAILCO公司需要决定下四个季度帆船的生产量。下四个季度帆船的需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元。假定生产提前期为0，初始库存为10条船，如何安排生产可使总费用最小？
我们用DEM，RP，OP，INV分别表示需求量、正常生产量、加班生产量、库存量，则DEM，RP，OP，INV对每个季度都应该有一个对应的值，也就是说他们都应该是一个由4个元素组成的数组，其中DEM是已知的，而RP，OP，INV是未知的。现在我们可以写出这个问题的模型。首先，目标函数是所有费用的和：
Min （1）
约束条件主要有两个：
（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个季度组成的集合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的元素 造船生产设计 | 1 | 2 | 3 | 4 |
定义在集合 QUARTERS 上的属性 | DEM | DEM（1） | DEM（2） | DEM（3） | DEM（4） |
RP | RP（1） | RP（2） | RP（3） | RP（4） |
OP | OP（1） | OP（2） | OP（3） | OP（4） |
INV | INV（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,其结果正是定义了表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（集合（下标）：关于集合的属性的表达式）”
的方式定义的，这个函数的功能是对语句中冒号后面的表达式，按照“：”前面的集合指定的下标（元素）进行求和。本例中目标函数也可以等价的写成“@SUM(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i))”,这里“@SUM”相当于求和符号“”，而“QUARTERS(i)”相当于“iQUARTERS”的含义。只是由于本例中目标函数对集合QUARTERS的所有元素（下标）都要求和，所有我们在相应的语句中将下标i省去。
约束是用循环函数“@FOR(集合（下标）：关于集合的属性的约束关系式)”的方式定义的，意思是对冒号“：”前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立。
我们先看到能力限制（2），即每个季度正常的生产能力是40条帆船，这正是语句“@FOR（QUARTERS（I）：RP（I）<40）；”的含义。由于对所有元素（下标（I）），约束的形式是一样的，所有也可以像上面定义目标函数是一样，将下标I省去，即这个语句可以简化成“@FOR（QUARTERS：RP<40）；”，效果相同。
但是，对于产品数量的平衡方程（3）及（4）而言，由于下标I=1时的约束关系式于I=2，3，4时有所区别，所以我们这时不能省略下标“I”。实际上，I=1时的约束关系式（3）要用到变量INV（0）是一个已知的常数，即INV（0）=10），但是我们定义的属性变量中不包含台湾光复INV（0）的。为了区别I=1和I=2，3，4，我们在程序中把I=1是的约束条件单独写出，即“INV（1）=10+RP（1）+OP（1）－DET（1）；”（这样一来，约束（4）实际上已经不再需要了；而对I=2，3，4对应的约束，我们对下标集合的元素增加了一个逻辑关系式“I#GT#1”（这个限制条件与集合之间有一个竖线“|”分开，称为过滤条件）。限制条件“I#GT#1”是一个逻辑表达式，意思就是I>1；“#GT#”是逻辑运算符号，意思是“大于”，其他的在后面介绍。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议