7-整数规划
第7章 整数规划
在我们讨论线性规划问题时，其中的变量j x 是非负实数，它可以是整数，也可以是分数、小数.但是，在实际问题中，常常要求问题中全部或部分变量只能取整数值.例如，在研究经济管理问题时，装货的车辆数，工人看管的机器数，完成工作的人员数等，都要求取非负整数值.此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x ，令1x =表示在该地建厂，0x =表示不在该地建厂，逻辑变量也是只允许取整数值的一类变量.这就需要我们研究整数规划问题. 整数规划是在1958年由R.E.戈莫里提出割平面法之后形成独立分支的,几十多年来发展出很多方法以解决各种问题.
0-1规划在整数规划中占有重要地位:一方面，许多实际问题,如指派问题、选址问题、送货问题都可归结为此类规划；另一方面，任何有界变量整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究.
7.1 整数规划模型
7.1.1 整数规划的定义
如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题．其模型称为整数规划模型．
如果整数规划的目标函数和约束条件都是线性的，则称此问题为整数线性规划问题．在这里我们只就整数线性规划问题进行讨论，整数线性规划的一般模型为：
j n
j j x c z ∑==1
max(min),
1(,)(1,2,,)..
.0,(1,2,,)
n
ij j i j j
j a x b i m s t x x j n =?≤=≥=???≥=?∑为整数 (7.1) 7.1.2 整数规划的分类
整数规划问题根据对设计变量的取值要求的不同可以分为四类： （1）纯（完全）整数规划：所有决策变量全限制为整数的整数规划； （2）混合整数规划：部分决策变量限制为整数的整数规划； （3）0-1整数规划：所有决策变量全限制为0-1的整数规划； （4）混合0-1整数规划：部分决策变量限制为0-1的整数规划.
7.1.3 整数规划的模型
例7.1 背包问题 有一辆最大货运量为10t 的货车，用它装载3种货物，每种货物的单位重量及相应单位价值如表7-1所示．问应如何装载，可使得价值最大．
表7-1 每种货物的单位重量及相应单位价值表
解: 设第i 种货物装载件的数量为i x （i =1,2,3）,则所述问题可表为：
max 123456z x x x =++
12334510...0,(1,2,3)
i i x x x s t x x i ++≤??≥=?为整数 例7.2 二维装包问题 有一船能装的货物有5种，各种货物的单位重量i w 和单位体积i v 以及它们相应的价值i R 如表7-2表示：
表7-2 各种货物的单位重量、单位体积及它们相应的价值表
解: 设第i 种货物装载件数为i x （i =1,2,3,4,5）．则所述问题为 m a x x x x x x
++++12345z =47654 ..
.i
i x x x x x s t x x x x x x x i ++++≤??
++++≤??≥=?1234512345为整数58327112
86541090,(1,...,5) 7.1.4 整数规划求解思想和方法分类
对于实际中的某些整数规划问题,我们有时候可以想到先略去整数约束的条件,即视为一
个线性规划问题,求得线性规划问题的最优解后,对其进行取整处理.实际上,这样得到的解未必是原整数规划问题的最优解,因此不能按照线性规划问题实数最优解简单取整而获得.但可借鉴这种思想.
整数规划求解方法总的基本思想是：去掉整数规划问题(7.1)中的整数约束,使构成易于求解的新问题：松弛问题(A ),如果这个问题(A )的最优解是原问题(7.1)的可行解,则就是原问题(7.1)的最优解；否则，在保证不改变松弛问题(A )的可行性的条件下，修正松弛问题(A )的可行域（增加新的约束），变成新的问题(B ),再求问题(B )的解,重复这一过程直到修正问题的最优解在原问题(7.1)的可行域内为止,即得到了原问题的最优解.
注：如果每个松弛问题的最优解不是原问题的可行解,则这个解对应的目标函数值z 一定是原问题最优值*
z 的上界(最大化问题),即z z ≤*；或下界(最小化问题),即z z ≥*
.
整数规划求解方法分类：
（1）分枝定界法：可求纯或混合整数线性规划； （2）割平面法：可求纯或混合整数线性规划；
（3）隐枚举法：求解0-1整数规划，有过滤隐枚举法和分枝隐枚举法； （4）匈牙利法：解决指派问题（0-1规划特殊情形）； （5）蒙特卡洛法：求解各种类型规划. 下面将简要介绍常用的几种求解整数规划的方法.
7.2 分枝定界法
对于求解整数规划问题，大家往往会有如下两种想法.
（1）通过枚举法对结果进行比较总能求出最好方案这种想法对于维数很低的整数规划问题行得通，但是随着决策变量维数的增加，该方法的计算量是不可想象的，因而此种想法不可行.
（2）考虑先忽略整数约束，解一个线性规划问题，然后用四舍五入法取得其整数解，事实证明，这样经过四舍五入的结果甚至不是问题的可行解.下面看一个例子 . 例7.3 求解如下整数规划问题：
12
121212
max 586..5945.,0,f x x x x s t x x x x =++≤??+≤??≥?且取整数值 （7-2） 若忽略整数约束，可得最优解和目标函数值为[]*94,154T
x =;*
1654f =,对其进行四舍五
入，可得一组整数解[](1)
2,4T
x
=,发现其不满足125945x x +≤，故不是整数规划式（7-2）的
可行解；我们再尝试一下舍位归整，得到另一组整数解[](2)
2,3T
x =,它是原整数规划的可行
解，目标函数值(2)
34f
=,但(2)x 不是最优解，因为若令[](3)0,5T
x =,可以验证(3)x 为原整数
规划的可行解，且(3)(2)40f f =>所以上述两种想法均不可行.
下面给出求解整数规划的一般方法：分枝定界法.
对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容.通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界．在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝．这就是分枝定界法的主要思路．
分枝定界法可用于解纯整数或混合整数规划问题．在二十世纪六十年代初由Land Doig 和Dakin 等人提出．由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法．目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等．
设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么问题B 的最优目标函数值必是整数规划问题A 的最优目标函数值*
z 的上界，记作z ；而A 的任意可行解的目标函数值将是*
z 的一个下界z ．分枝定界法就是将B 的可行域分成子区域再求其最大值的方法．逐步减小z 和增大z ，最终求到*
z ．现用下例来说明：
例7.4 用分枝定界法求解下述整数规划问题
219040max x x z +=
121212
9756..72070.,0x x s t x x x x +≤??+≥??≥?且为整数 解：（1）记原整数规划问题为(A ),去掉21x x ,为整数的约束，得到松弛问题(B )，求解得(B )的最优解为：355.87798168180924021===z x x ,.,.,可见它不符合整数条件.这时
0z 是问题A 的最优目标函数值*z 的上界，记作z .而0,021==x x 显然是问题A 的一个整数
可行解，这时0=z ，是*z 的一个下界，记作z ，即3560*
≤≤z .
（2）分枝：因为21,x x 当前均为非整数，故不满足整数要求，任选一个进行分枝.设选1
x 进行分枝，把可行集分成2个子集：44.8092]
[1=≤x ，514.8092][1=+≥x ,因为4与5之间无整数，故这两个子集内的整数解必与原可行集整数解一致.这样将(B )分为两个子问题(1B )和(2B )：
问题1B ： 219040max x x z +=
1212129756..
72070.04,0
x x s t x x x x +≤??
+≤??≤≤≥?
最优解为：349,1.2,0.4121===z x x .
问题2B ： 219040max x x z +=
12121
29756..
72070.5,0
x x s t x x x x +≤??
+≥??≥≥? 最优解为:4.341,57.1,0.5121===z x x .
再定界：3490*
≤≤z .
（3）对问题1B 再进行分枝得问题11B 和12B ，它们的最优解为 340,2,4:112111===z x x B
327.14,00.3x 1.43,:
122112===z x B
再定界：341340*
≤≤z ，并将12B 剪枝.
（4）对问题2B 再进行分枝得问题21B 和22B ，它们的最优解为 083001x 5.44,212121===z x B ,.: 22B :无可行解. 将2221,B B 剪枝.
于是可得原整数问题（A ）的最优解为：
3402421===*,,z x x .
从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题A ，将与它相应的线性规划问题称为问题B . （1）解问题B 可能得到以下情况之一:
①B 没有可行解，这时A 也没有可行解，则停止．
②B 有最优解，并符合问题A 的整数条件，B 的最优解即为A 的最优解，则停止. ③B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为z .
（2）用观察法找问题A 的一个整数可行解，一般可取n j x j ,,1,0 ==，试探，求得其
目标函数值，并记作z .以*
z 表示问题A 的最优目标函数值；这时有
z z z ≤≤*
进行迭代.
第一步：分枝，在B 的最优解中任选一个不符合整数条件的变量j x ，其值为j b ，以][j b 表示小于j b 的最大整数.构造两个约束条件
][j j b x ≤ 和 1][+≥j j b x
将这两个约束条件，分别加入问题B ，求两个后继规划问题1B 和2B .不考虑整数条件求解这两个后继问题.
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z .从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z ，若无则用0=z .
第二步：比较与剪枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了.若大于z ，且不符合整数条件，则重复第一步骤.一直到最后得到z z =*为止.得最优整数解n j x j ,,1,*
=.
7.3 0-1整数规划
0-1整数规划是整数规划中的特殊情形，它的变量j x 仅取0或1两个数值．这时j x 称为0-1变量，或称二进制变量．j x 仅取值0或1这个条件可由下述约束条件：
10≤≤j x ，且为整数
所代替，是和一般整数规划的约束条件形式一致的．在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了．我们先介绍0-1变量在建立数学模型中的作用，再研究解法．
7.3.1 0-1变量在建立数学模型中的作用
一、 m 个约束条件中只有k 个起作用 设m 个约束条件可表为：
),,,(m i b x
a i j
n
j ij 211
=≤∑= (7.2)
定义
?
?
?=个约束条件起作用假定第个约束条件不起作用
假定第，01i i i y , 又M 为任意大的正数,则
???????-=+≤∑∑==k m y My b x a m
i i i i j n
j ij 1
1
表明(7.2)的m 个约束条件中只有(k m -)个的右端项为 (M b i +)，不起约束作用，因而只有
k 个约束条件真正起到约束作用.
二、约束条件的右端项可能是r 个值r b b b ,,, 21中的某一个，即 121
或或或n
ij j
r j a x
b b b =≤???∑ (7.3)
定义
??
?=否则
假定约束右端项为，01i
i b y , 由此,上述约束条件(7.3)可表示为:
???????=≤∑∑∑===11
1
1r
i i i r
i i j n
j ij y y b x a 三、两组条件中满足其中一组
若41≤x ，则22≥x ，否则（即41>x 时），32≤x 定义
),(,21，01组条件起作用
第组条件不起作用
第=???=i y i i i
又M 为任意大的正数,则问题可表达为：
?????
????=++≤->-≥+≤1
3424212
2211211y y M
y x M y x M y x M y x 四、关于固定费用的问题（Fixed Cost Problem ）在讨论线性规划时，有些问题是要求
使成本为最小．那时总设固定成本为常数，并在线性规划的模型中不必明显列出．但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例．
例7.5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加．所以必须全面考虑．今设有三种方式可供选择，令
j x 表示采用第j 种方式时的产量；
j c 表示采用第j 种方式时每件产品的变动成本； j K 表示采用第j 种方式时的固定成本.
为了说明成本的特点，暂不考虑其它约束条件．采用各种生产方式的总成本分别为
?????=>+=
0 00)(,)
(,)(j j j j j j j x x x c K x C 3,2,1=j （7.4）
式中j K 是同产量无关的生产准备费用．问题的目标是使所有产品的总生产成本为最小．即
)()()(m i n 333322221111x c y k x c y k x c y k z +++++= （7.5）
在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量j y ，令
??
???==>时0种生产方式，即当不采用第时
0种生产方式，即当采用第01j j j x j x j y ,,
于是将（7.4）、（7.5）表达为：
)()()(m i n 333322221111x c y k x c y k x c y k z +++++=
0..1,2,3.01
j j
j x My s t j y ≤≤??=?
=??或 （7.6）
其中M 是个充分大的常数.（7.6）式说明，当0>j x 时j y 必须为1；当0=j x 时，为使z 极小化，应有0=j y .
五、 投资场所的选定——相互排斥的计划
例7.6 某公司拟在市东、西、南三区建立门市部.有7个位置（点）(1,2,...,7)i A i =可供选择.规定
在东区：由321,,A A A 三个点中至多选两个； 在西区：由54,A A 两个点中至少选一个；
在南区：由76,A A 两个点中至少选一个．
如选用i A 点，设备投资估计为i b 元，每年可获利润估计为i c 元，但投资总额不能超过B 元.问应选择哪几个点可使年利润为最大？
解题时先引入0-1变量(1,2,...,7)i x i = 令
??
?=点没被选中
当点被选中
当，01i i i A A x , 1,2,...,7i = 于是问题可列写成：
7
1
max i i i z c x ==∑
7
1
12345
672 (1101)
i i i i b x B x x x s t x x x x x =?≤??++≤??+≥??+≥?
=?∑或
六、相互排斥的约束条件
1.有两个相互排斥的约束条件244521≤+x x 或453721≤+x x .为了统一在一个问题中，引入0-1变量y ，则上述约束条件可改写为：
??
?
??=-+≤++≤+10145372445或2121y M y x x yM x x )( 其中M 是充分大的正数.
2.约束条件01=x 或 8005001≤≤x 可改写为:
??
?=≤≤1
08005001或y y
x y 3.如果有m 个互相排斥的约束条件：
111,2,...,i in n i
a x a x
b i m ++≤= (7.7)
为了保证这m 个约束条件只有一个起作用，我们引入m 个0-1变量(1,2,...,)i y i m =和一个充分大的正数数M ，则问题可表达为： 1111,2,...,1
i in n i i m a x a x b y M i m
y y m ++≤+=??
++=-? （7.8）
7.3.2 0-1整数规划的应用
例7.7 资金分配问题 某企业在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用如表7-3所示.假定每一项已经批准的工程要在整个3年内完成.企业应如何选择工程，使企业总收入最大？
表7-3 每项工程的期望收入和年度费用表
解 作决策变量1x ，2x ，3x ，4x ，5x ：
,,选择第项工程
放弃第项工程
10i i x i ?=?
? i =1,2,3,4,5 这样，所述问题的数学模型为：
max 123452*********z x x x x x =++++
...i x x x x x x x x x x s t x x x x x x i ++++≤??++++≤??++++≤??==?
123451234512345可用基金限制可用基金限制可用基金限制或5437825,794625,81021025,01(1,2,3,4,5)
例7.8 选课策略 某大学规定，运筹学专业硕士生毕业时必须至少学习过两门数学类课
程，两门运筹学类课程和两门计算机类课程．课程中有些只归属某一类，如微积分归属于数
学类，计算机程序归属计算机类，但有些课程是跨类的，如运筹学可以归为运筹学类和数学类，数据结构归属于计算机类和数学类，管理统计归属数学类和运筹学类，计算机模拟归属计算机类和运筹学类，预测归属运筹学类和数学类．凡归属两类的课程选学后可认为两类中各学一门课．此外有些课程要求先学习先修课，如学计算机模拟或数据结构必须先修计算机程序，学管理统计须先修微积分，学预测必须先修管理统计．问一个硕士生最少应学几门，哪几门，才能满足上述要求？
解: 对微积分、运筹学、数据结构、管理统计、计算机模拟、计算机程序、预测7门课程分别编号为1、2、…、7. 设 ,,选学第门课程
不选学第门课程
10i i x i ?=?? 1,,
7i = 至此可得本题的数学模型如下：
min 1234567z x x x x x x x =++++++
...i x x x x x x x x x x x x s t x x x x x x x x x i ++++≥??+++≥??++≥??≥≥??≥≥?
==?????12347245735614656347或222,,01,1,,
7
例7.9 集装箱装载问题 今有一集装箱，拟运装物品12345,,,,A A A A A ．13、A A 由于体积大，集装箱内只能装其中之一；45、A A 由于重量大也只能装一件；1A 是食品不能与化工产品4A 放在一起；2A 与5A 是配套产品，必须一起运输.1A 的运费是1500元，2A 的运费是2000元，3A 的运费是1300元，4A 的运费是2300元，5A 的运费是2800元．问集装箱应如何装箱才能使运费收入最大？
解：设1A ~5A 是否装运的控制变量是1x ～5x ,i x =0,表示i A 不装，i x =1，表示i A 装箱运输．由此可知所述问题的数学模型
max .12345152 1.3 2.3 2.8z x x x x x =++++
......i x x x x s t x x x x x i +≤??+≤??=??+=?==??13452514二者取一二者取一
同时装箱或同时不装箱二者取一但必装其一
或1,
1,-0,1,,01
(1,,5)
例7.10 当决策变量是连续变量时的选择
Good Products 公司的研究与发展部开发了三种可行的新产品．然而，为了使产品的生产线不至于过分多样化，管理层决定实施以下限制：
限制1 在三种新产品中，至多有两个被投入生产．每一种产品可能由两个工厂中的任何一个生产，出于管理的考虑，管理层实施了第二条限制：
限制2 两个工厂中，仅有一个能作为新产品的唯一生产者．
对于两个工厂来说，每种新产品的单位生产成本都是相同的．然而，由于两个工厂的生产设备不同，对每种产品的单位生产时间可能是不同的．数据在表7-4中给出，还有一些其他信息，包括在投产后每周每种新产品的预期销售数量．目标是选择新产品、工厂和生产新产品的生产率，以使总利润最大化．
表7-4:例7.9的数据（Good Products 公司的问题）
在某种程度上，这个问题类似一个标准的产品混合问题，实际上，如果我们去掉两个约
束条件并且满足表7-4列出的两个工厂（所以这两个工厂生产产品的工艺是不同的）生产每种新产品所用的时间，那么原问题就变成了此类问题．特别地，令1x 、2x 、3x 分别代表新产品的生产率，那么模型变为
s.t .max .,,z x x x x x x x x x x x x x x x =++++≤??++≤??≤??
≤?
?≤?≥≥≥??1231231
231
231235733423046240
759000
对于实际问题，必然会给模型加入约束： 严格大于零的决策变量),,(321x x x 数必须2≤
这个约束条件无法用一个线性或整数规划模型，所以关键问题是怎样把它转化成此类模
型，以便使用相应的算法求解总体模型．如果决策变量是0-1变量，那么约束条件就可以表达为2321≤++x x x ．然而，我们需要一个更为复杂的模型，不仅涉及辅助0-1变量，还包含连续变量．第二个约束要求前两个约束条件12334230x x x ++≤与12346240x x x ++≤被下述约束条件代替：
30243321≤++x x x
或
40264321≤++x x x
至于哪个约束条件被保留，对应于选择哪个工厂来生产新产品，我们在前面的已讨论了怎样把或约束转化为一个线性或整数规划形式，我们再次用到一个辅助0-1变量．
使用辅助0-1变量建模
为了处理第一个要求，我们引入三个辅助0-1变量),,(321y y y ，它们的含义如下
,,
如果被保留生产成品如果被保留不生产成品10（）
00（）
j j j x j y x j >??=?
=??
3,2,1=j ．为了把该含义融入模型中，我们把M （一个非常大的正数）加到约束条件当中
,,112233
123是变量20-1,123
j x My x My x My y y y y j ≤≤≤++≤=
或约束与非负约束使决策变量的可行域是有限的（每个M x j ≤）．因此，在每个约束条件j j My x ≤中，1=j y 使j x 能取到可行域中的任何值，
而0=j y 强迫0=j x （反过来，0>j x 强迫1=j y ，而0=j x 是允许j y 等于0或1）．结果，因为第四个约束条件令至多能有两个j y 等于1，所以它等价于至多能有两种新产品被投入生产．
为了处理第二个要求，我们引入第二个辅助0-1变量4y ，其含义如下
12341231,
4200,
34230x x x y x x x ++≤?=?
++≤?如果被保留（选择第二个工厂）
如果被保留（选择第一个工厂）
６４
正如7.3节所论述的，通过加上如下约束条件来表达该含义，
)
1(402643024343214
321y M x x x My x x x -+≤+++≤++
4y 是0-1变量．
结果，在我们把所有变量移到约束条件的左边后，完整的模型是：
max 123573z x x x =++
...
,,,,,j x x x x My x My x My s t y y y x x x My x x x My M x x x y j ≤?
?≤??≤?
-≤?
?-≤?
-≤?
?++≤?
?++-≤?
+++≤+???
≥≥≥??=?
12311223312312341234123且是变量759000234230462400000-1,1234
现在这是一个MIP 模型，三个变量j x 不要求是整数，四个0-1变量，所以可以用MIP 算法来求解这个模型．求得结果是（在用一个相当大的数替换M 之后），最优解是11=y ，
02=y ，13=y ，14=y ，2
1
51=x ，02=x 和93=x ；也就是，选择生产第一和第三个新
产品，选择第二个工厂生产新产品，并且第一个产品的生产率是每周2
1
5个，第三个产品的生
产率是每周9个．结果总利润是每周54500美元．
7.4 指派问题
在生产管理上，为了完成某项任务，总是希望把有关人员最合理地分派，以发挥其最大工作效率，创造最大的价值.
例7.11 设某单位有5个人，每个人都有能力去完场5项科研任务中的任一项，由于5个人的能力和经验不同，所需完成各项任务的时间如表7-5所示．问分配何人去完成何项任务使完成所有任务的总时间最少？
解 设决策变量ij x 表示第i 个人去完成第j 项任务，即
,,),ij j j i x i j i ?=≤≤?? 当第个人去完成第项任务时 当第个人不去完成第项任务时
1 （150
每个人去完成一项任务的约束为
11121314152122232425313233343541424344455152535455+=1+=1+=1+=1+=1
x x x x x x x x x x x x x x x x x x x x x x x x x +++??+++??
+++??+++?+++?? 每一项任务必有一个人去完成的约束为
11213141511222324252132333435314243444541525354555+=1+=1+=1+=1+=1
x x x x x x x x x x x x x x x x x x x x x x x x x +++??+++??
+++??+++?+++?? 目标函数为完成任务的总时间最少：
min 11121314152122232425
313233343541424344453132333435
3821038729764275842359106910z x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++++++++++++++++++ 记系数矩阵为
()38
2103872
9764
27584235910
6
9
10ij C c ?????
???==?
???????
称为效益矩阵，或价值矩阵，ij c 表示第i 个人去完成第j 项任务时有关的效益（时间、费用、价值等）.故该问题为一个0-1规划模型：
55
11
min ij ij i j z c x ===∑∑,
(,,...,),..(,,...,),(,,,...,).
ij j ij
i ij x i s t x j x i j ==?==????==??==??∑∑5
151或1125112501125
一般的指派（或分配）问题：
设某单位有n 个人，有n 项任务需要完成，由于各项任务的性质和每人的专长不同，如果分配每个人仅能完成一项任务，应如何分派才能使完成n 项任务的总效益最高？
设该指派问题的效益矩阵()ij n n C c ?=，其元素ij c 表示分配第i 个人去完成第j 项任务时效益.或者说：以ij c 表示给定的第i 单位资源分配用于第j 项活动时的有关效益.
设问题的决策变量为ij x 是0-1变量，即
,,,,
,),当第个人去完成第项任务时,
当第个人不去完成第项任务时
1 （=120ij j j i x i j n i ?=??
5
5
11min ij ij i j z c x ===∑∑,
(,,,),..(,,,),(,,,,).
ij j ij
i ij x i s t x j x i j ==?==????==??==??∑∑5
151或1125112501125
其数学模型为
11
min n
n
ij ij i j z c x ===∑∑,
(,,,),..(,,,),(,,,,).
n
ij j n ij
i ij x i n s t x j n x i j n ==?==????==??==??∑∑11或1121120112
7.5 应用MATLAB 解整数规划问题
在本节中，将主要讲解如何用MATLAB 求解一般整数规划中的问题，其中包括一般混合
整数规划问题和0-1规划问题.
7.5.1 整数规划枚举法
整数规划的解法有分枝定界法和割平面法等，7.2节内容我们介绍了分枝定界法，割平面法有兴趣的读者可参考有关运筹学著作．我们现在介绍整数规划枚举法，它利用计算机运算速度快，存储量大，而把所有可能的整型点的函数值都计算出来，再从中选取最优的方法．
整数规划枚举法计算步骤如下： （1）用线性规划函数linprog 求出最优解和最优值，其最优解可作为选取整数变化范围的参考；
（2）用for-end 语句作决策变量的整数型参数变化的循环，有多少个非决策变量，就要实施多少重循环；
（3）用if-end 语句作不等式和等式结束满足的判断；
（4）对符合约束条件的一组决策变量，进行目标函数计算并储存，否则滑过； （5）用指令max 和min ，搜索目标函数的最大值和最小值及相应决策变量. 例7.12 用整数规划枚举法求解例7.1.
解 先取消整数限制，求出最优值和最优解. >>clear all; f=[4,5,6]; f1=-f;
a=[3,4,5]; b=[10];
vlb=[0,0,0]’;
[w,fval,exitflag]=linprog(fl,a,b,[],[],vlb,[])
此处求得fv=13.3333和w=[3.3333,0,0]’.
由以上结果定出决策变量321x x x 、、的取值范围如下：
:1x 0~5；:2x 0~2；:3x 0~2．
下面用枚举法求解. 编写M 文件zsgh_1.m ： k=1;
for x1=0:5 for x2=0:2
for x3=0:2
q=[x1,x2,x3]’; p=a*q; if p<=b
z(k)=f*q; v(k,:)=q ’; k=k+1; end end end end
[zm,mi]=max(z) x=v(mi,:) zv=[z ’,v]
当程序zsgh_1.m 执行后，输出如下： zm = 13
mi = 11 x =
2 1 0 zv =
0 0 0 0 6 0 0 1 12 0 0 2 5 0 1 0 11 0 1 1 10 0 2 0 4 1 0 0 10 1 0 1 9 1 1 0 8 2 0 0 13 2 1 0 12 3 0 0
这说明所述整数解的最大值为13，其最优解为1x =2，2x =1，3x =0．
可以看到，取消整数时，其最大值为13.3333.这样，我们得到最优方案为：第一种货物装2件，第二种货物装1件，其总价值为13.
7.5.2 用MATLAB 求解一般混合整数规划问题
由于MATLAB 欧化工具箱中并未提供纯整数规划和混合整数规划的函数，因此需要自行根据需求和设定相关算法来实现，这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命为intprog.笔者在源程序的基础上做了简单的修改，将其选择用分枝变序的算法由自然序改造成按本章7.2节中所述分枝变量选择原则中的一种，即选择与整数值相差最大的非整数变量首先进行分枝，intprog 函数的调用格式如下.
[x,fval,exitflag]=intprog(c,a,b,Aeq,Beq,lb,ub,M,TolXInteger) 该函数所解决的整数规划问题为
min ...0j f cx
Ax b Aeqx beq s t vlb x vub x =≤??=??≤≤??≥?且取整数值
在上述标准问题中，假设x 为n 维设计变量，且线性规划问题具有不等式约束1m 个，等式约束2m 个，则：c 为n 维行向量12(,,,)n c c c ,x 为n 维列向量12(,,
,)T n x x x ，b 为1m 维
列向量，beq 为2m 维列向量，A 为1m n ?维矩阵，Aeq 为2m n ?维矩阵.
在该函数中，输入参数有c,A,b,Aeq,beq,vlb,vub ，M 和TolXInteger.其中，c 为目标函数所对应设计变量的系数，A 为整数规划对应的不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量，Aeq 为整数规划对应的等式约束方程组构成的系数矩阵，beq 为等式约束方程组右边的值构成的向量。vlb 和vub 为设计变量对应的上界和下界，M 为具有整数约束条件限制的设计变量的序号，例如，问题设计变量为12,,
,n x x x ，要
求23,x x 和6x 为整数，则M=[2；3；6]；若要求全为整数，则M=1:6,或者M=[1；2；3；4；5；6].TolXInteger 为判定整数的误差值，即若某数x 和最临近整数相差小于该误差值，则认为x 即为该整数.
该函数的输出参数有x ，fval 和exitflag.其中x 为整数规划问题的最优解向量，fval 为整数规划问题的目标函数在最优解向量x 处的函数值，exitflag 为函数计算终止时的状态指示变量.
在MATLAB 中实现intporg 的代码和分析如下 %整数规划的MATLAB 实现
%Originally Designed By Sherif A. Tawfik, Faculty of Engineering, Cairo % University Revised By LiMing, 2009-12-29
%函数调用形式[x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger) %函数求解如下形式的整数规划问题 %min f'*x %subject to
% A*x<=b % Aeq*x=beq % lb<=x<=ub
% M 存储有整数约束的变量编号的向量 % TolXInteger 是判定整数的误差限 %
%函数返回变量
%x:整数规划的最优解
%fval:目标函数在最优解处的函数值 %exitflag = 1 收敛到解x
% 0 达到线性规划的最大迭代次数 % -1 无解 %
function [x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger) %设置不显示求解线性规划过程中的提示信息 options = optimset('display','off'); %上界的初始值 bound=inf;
%求解原问题P0的松弛线性规划Q0，首先获得问题的初始解 [x0,fval0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options);
%利用递归法进行二叉树的遍历，实现分枝定界法对整数规划的求解
[x,fval,exitflag,b]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x0,fval0,M,TolXInteg er,bound);
%分枝定界法的递归算法
%x为问题的初始解，v是目标函数在x处的取值
function [xx,fval,exitflag,bb]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x,v,M, TolXInteger,bound)
options = optimset('display','off');
%求解不考虑整数约束的松弛线性规划
[x0,fval0,exitflag0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options);
%如果算法结束状态指示变量为负值，即表示无可行解，返回初始输入
%或者所目标函数值大于已经获得的上界，返回初始输入
if exitflag0<=0 | fval0>bound
xx=x;
fval=v;
exitflag=exitflag0;
bb=bound;
return;
end
%确定所有变量是否均为整数，如是，则返回
%该条件表示x0(M)不是整数
ind=find(abs(x0(M)-round(x0(M)))>TolXInteger);
%如果都是整数
if isempty(ind)
exitflag=1;
%如果当前的解优于已知的最优解，则将当前解作为最优解
if fval0 x0(M)=round(x0(M)); xx=x0; fval=fval0; bb=fval0; %否则，返回原来的解 else xx=x; fval=v; bb=bound; end return; end %程序运行至此，说明松弛线性规划的解是一个可行解且目标函数值比当前记录的上界 割平面法 求解整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2?14 4x 1+2x 2?18 x 1,x 2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9 x 1,x 2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1 最优解为：x 1=13/4, x 2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如： x 2+1/2x 3-1/2x 4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即： (1+0)x 2+(0+1/2)x 3+(-1+1/2)x 4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x 2 - x 4-2 =1/2-(1/2x 3+1/2x 4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x 2和x 4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x 3,x 4?0，所以必有： 由于(2)式右端必为整数，于是有： 1/2-(1/2x 3+1/2x 4)?0 (3) 或 x 3+x 4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x 1+2x 2?11 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x 5，得： -1/2x 3-1/2x 4+x 5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x 1+2x 2 2x 1+3x 2+x 3=14 2x 1+x 2+x 4=9 规划模型求解 指导老师： 组员： 组员分工 实际的内容： 1·简要介绍线性规划的历史 线性规划是运筹学中最基本、应用最广泛的分支。规划模型是一类有着广泛应用的确定性的系统优化模型，1939年，苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书. 1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法. 1951年，美国经济学家库普曼斯（J.C.Koopmans,1910—1985）出版《生产与配置的活动分析》一书. 1950～1956年，线性规划的对偶理论出现. 1960年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法. 1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖. 1978年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义. 1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法——Karmarkar算法. 线性规划的基本点就是在满足一定约束条件下，使预定的目标达到最优. 现在线性规划已不仅仅是一种数学理论和方法，而且成了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术. 历史表明，重要数学概念对数学发展的作用是不可估量的，函数概念对数学发展的影响，可以说是贯穿古今、旷日持久、作用非凡，回顾函数概念的历史发展，看一看 函数概念不断被精炼、深化、丰富的历史过程，是一件十分有益的事情，它不仅有助于我们提高对函数概念来龙去脉认识的清晰度，而且更能帮助我们领悟数学概念 对数学发展，数学学习的巨大作用。 2·线性规划的原理：线性规划是合理利用、调配资源 的一种应用数学方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务完成的最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值(极小值和极大值)问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此，线性规划是辅助企业“转轨”、“变型”的十分有利的工具，它在辅助企业经营决策、计划优化等方面具有重要的作用。其一般形式为： n n n n n n b x a x a x a b x a x a x a x c x c x c x f =+++=+++→+++= 2 2222121112121112211min )( 四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示： 根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省? 1． 某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数 最少? 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2，约束形式为“≤”，X 3，X 4为松驰变量．表中解代入目标函数后得Z=10 (1)求表中a ～g 的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x 1+2x 2+4x 3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25 割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x2?14 4x1+2x2?18 x1,x2?0，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x2?0，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1 最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x4?0，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)?0 (3) 或 x3+x4?1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x2?11 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部 分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i?0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2 整数规划 若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2．…，S 10相应的钻探费用为C 1 ,C 2 ,… C 10，并且井位选择要满足下列限制条件： (1) 在s 1，s 2，S 4中至多只能选择两个； （2）在S 5，s 6中至少选择一个；（3）在s 3，s 6，S 7，S 8中至少选择两个。 试建立这个问题的整数规划模型 解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0 科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6 大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z 若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2．…，S 10相应的钻探费用为C 1 ,C 2 ,… C 10，并且井位选择要满足下列限制条件： (1)在s 1，s 2，S 4中至多只能选择两个； （2）在S 5，s 6中至少选择一个；（3）在s 3，s 6，S 7，S 8中至少选择两个。 试建立这个问题的整数规划模型 解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,102542126255104814181520765432176 54321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 解：引入0—1变量x i , x i =1表示在该区设消防站，,x i =0表示不设 ????? ??????=≥++≥++≥++≥+≥++≥++++++=0 1111111min 65 2 654 543 436 2 121654321或i x x x x x x x x x x x x x x x x x x x x x x x z 解得： X*=(0,1,0,1,0,0)’ Z*=2 某公司现有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表所示： 该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下条件的 约束：（1）在项目1、2和3中必须有一项被选中，（2）项目3和项目4只能选中一项，（3）项目5被选中的前提是项目1必须被选中。试就这一问题建立运筹学研究模型。 5.2某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表5–2所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。 第六章整数规划 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 . 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 . 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0 求解下列整数规划问题 1、 min f=4x1+3x2+2x3 . 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 . -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 . 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋ x6-10 x16≤0 x7+ x8＋ x9-20 x17≤0 x10+ x11＋ x12-30 x18≤0 x13+ x14＋ x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表： 第章整数规划割平面法 This manuscript was revised on November 28, 2020 割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x214 4x1+2x218 x1,x20，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x20，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1 最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得： x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)0 (3) 或 x3+x41 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x211 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E，2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5，得： -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中，得到新的整数规划问题： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i 0，且为整数，i=1,2,…,5 该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。具体计算过程见表2： 表2 第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择 《运筹学》课程学习指南 第二章线性规划模型 （一）学习指导 1．本章的学习内容 1）线性规划模型及其单纯形法 2）线性规划的对偶理论及其灵敏度分析 3）线性规划问题案例建模及讨论 4）递阶练习 2．本章的教学目的 1）掌握线性规划问题数学模型的基本形式； 2）比较熟练地使用单纯形法； 3）了解使用LINGO软件求解线性规划模型的过程； 4）能够利用LINGO软件进行初步的灵敏度分析及拓展研究； 5）具备基本的建模能力。 3．本章的教学重点 1）单纯形法的步骤； 2）利用LINGO软件进行灵敏度分析； 3）基本问题的建模及利用LINGO软件求解并拓展分析。4．本章的教学难点 1）确定入基变量和出基变量的原则； 2）原问题变量与对偶变量之间的关系； 3）利用LINGO软件进行灵敏度分析并对结果给予解释； 4）建立实际问题的数学模型。 5．本章的计划学时数 本章共计10学时，具体分配如下： 1）线性规划模型实例：2学时 2）线性规划问题的数学模型：2学时 3）求解线性规划模型的单纯形法及LINGO程序：2学时 4）线性规划的对偶理论、灵敏度分析及其应用：2学时 5）线性规划问题案例建模及讨论：2学时 （二）学习建议 1．对前期基础扎实，准备继续深造学生的学习建议 1）准确、熟练运用单纯形法求解线性规划模型； 2）掌握相关的理论推导、证明； 3）能够准确地建立一般问题的线性规划模型。 2．对于热衷于运筹学的应用，准备参加数学建模竞赛学生的学习建议1）掌握单纯形法的基本步骤及解题思路； 2）能够对较为复杂实际问题建立线性规划模型； 3）熟练应用LINGO软件求解线性规划问题； 4）能够对实际问题进行拓展研究。 3．对于其他学生的学习建议 1）掌握单纯形法的基本步骤及解题思路并熟练计算； 2）能够准确地建立简单问题的线性规划模型。 第三章线性规划模型 （一）学习指导 1．本章的学习内容 1）运输问题的数学模型 2）表上作业法 教学基本文件模板 课程教学大纲： 《运筹学》课程教学大纲 课程编号： 课程名称：运筹学/Operational Research 课程总学时/学分：72/4 （其中理论60学时，实验12学时） 适用专业：适用本科四年制信息管理与信息系统专业 一、课程简介 本课程的授课对象是信息管理与信息系统专业本科生，属管理类专业专业基础必修课。《运筹学》是以定量分析为主来研究经济管理问题，将工程思想和管理思想相结合，应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型获得最优决策方案。本课程的主要内容包括线性规划、运输问题、整数规划、目标规划、动态规划、网络分析等与经济、管理和工程领域密切相关的运筹学分支的基本模型、方法和应用。运用科学的模型化方法来描述、求解和分析问题，从而支持决策。 二、教学目的和任务 本课程旨在使同学们正确、全面地掌握各级管理工作中已被广泛应用、发展比较成熟的最优化理论与方法，并能运用所学理论和方法解决管理工作中出现的各种优化问题，为后续课程奠定定量分析基础。在已学过高等数学、微积分、线性代数等课程基础上学习本课程，通过教授、自学、复习、作业练习、辅导、上机等教学环节达到上述目的。学习中要注意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。注重基本概念、基本思路、基本方法、算法步骤的掌握，了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。应注重实际应用中建立模型，选择可行求解的理论方法，运用计算机工具求解这三方面训练的有机结合。 三、教学基本要求 信息管理与信息系统专业的学生应系统地学习《运筹学》的全部内容。系统掌握线性规划、运输问题、目标规划、整数规划、动态规划、图与网络分析的理论和方法；能借助Excel、Lingo等电子计算手段，运用所学理论和方法解决实际问题。通过该课程的学习，进一步培养学生的分析问题和解决问题的能力。四、教学内容与学时分配 绪论（2学时） 第一节运筹学的定义与发展简史 1、运筹学名称的来历； 2、运筹学的发展简史。 第二节运筹学研究的基本特征与基本方法 运筹学（Operational Research）复习资料 第一章绪论 一、名词解释 1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 二、选择题 1.运筹学的主要分支包括（ABDE ） A图论B线性规划C非线性规划D整数规划E目标规划 2. 最早运用运筹学理论的是（ A ） A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B . 美国最早将运筹学运用到农业和人口规划问题上 C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上 第二章线性规划的图解法 一、选择题/填空题 1.线性规划标准式的特点： （1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位： （1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。 （2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。 （3）如果对偶价格等于0，则其最优目标函数值不变。 3.LP模型（线性规划模型）三要素： （1）决策变量（2）约束条件（3）目标函数 4. 数学模型中，“s·t”表示约束条件。 5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。 6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。7．下列图形中阴影部分构成的集合是凸集的是A 运筹学知识点： 绪论 1.运筹学的起源 2.运筹学的特点 第一章线性规划及单纯形法 1.规划问题指生产和经营管理中如何合理安排，使人力、物力等各种资源得到充分利用，获得最大效益。 2.规划问题解决两类问题：一是给定一定数量的人力、物力等资源，研究如何充分利用，以发挥其最大效果；二是已给定计划任务，研究如何统筹安排，用最少的人力和物力去完成。 3.规划问题的数学模型包含三个组成要素：决策变量、目标函数（单一）、约束条件（多个）。 线性规划问题的数学模型要求：决策变量为可控的连续变量，目标函数和约束条件都是线性的。 4.线性规划问题的标准形式：目标函数为极大、约束条件为等式、决策变量为非负、变量为非负 5.划标准型时添加的松驰变量、剩余变量和人工变量 6.理解可行解、最优解、基、基解、基可行解等概念，且掌握各类解间的关系 7.用图解法理解线性规划问题的四种解的情况：无穷多最优解、无界解、无可行解、唯一最优解 8.用图解法只有解决两个变量的决策问题 9.线性规划问题存在可行解，则可行域是凸集。 10.线性规划问题的基可行解对应线性规划问题可行域的顶点。 11.线性规划问题的解进行最优性检验：当所有的检验数小于等于零时为最优解；尤其当检验数小于零时（即不等于零）有唯一最优解；当某个非基变量检验数为时，有无穷多最优解；当存在某个检验数大于零且对应的系数又小于等于零时，有无界解。 12.单纯形法的计算过程，可能出计算题 13.入单纯形表前首先要化成标准形式。 14.确定换出变量时根据θ值最小原则，且要求公式中对应的系数大于零。 15.当线性规划中约束条件为等式或大于等于时，划为标准型后，系数矩阵中又不包含单位矩阵时，需要添加人工变量构造一个单位矩阵作为基。 16.人工变量的系数为足够大的一个负值，用—M代表 17.一般线性规划问题的数学建模题（生产计划问题、人才资源分配问题、混合 《运筹学》综合练习题 第一章线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充：判断下述说法是否正确 ●LP问题的可行域是凸集。 ●LP问题的基本可行解对应可行域的顶点。 ●LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 ●若LP 问题有两个最优解,则它一定有无穷多个最优解. ●求解LP问题时,对取值无约束的自由变量，通常令 " - ' = j j j x x x ,其中∶ ≥ " ' j j x x ,在用单纯 形法求得的最优解中,不可能同时出现 " ' j j x x . ●当用两阶段法求解带有大M的LP模型时，若第一阶段的最优目标函数值为零，则可断言原LP模型 一定有最优解。 7、补充：建立模型 （1）某采油区已建有n个计量站B1，B2…B n，各站目前尚未被利用的能力为b1，b2…b n（吨液量/日）。为适应油田开发的需要，规划在该油区打m口调整井A1，A2…A m，且这些井的位置已经确定。根据预测，调整井的产量分别为a1，a2…a m（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定A i到B j的距离d ij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。 （2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米。从第一个工厂排出的污水流到第二个工厂之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应大于0.2%，若这两个工厂都各自处理一部分污水，第一个工厂的处理成本是1000元/万立方米，第二个工厂的处理成本是800元/万立方米。试问在满足环保要求的条件下，每厂各应处理多少污水，才能使总的污水处理费用为最小?建立线性规划模型。 第 1 页共 6 页 第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m in x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m in x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2m in ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系 运筹学与最优化MATLAB 编程 实验报告 割平面法求解整数规划问题 一、 引言： 通过对MATLAB 实践设计的学习，学会使用MATLAB 解决现实生活中的问题。该设计是在MATLAB 程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规划问题。经实验，该算法可成功运行并求解出最优整数解。 二、 算法说明： 割平面法有许多种类型，本次设计的原理是依据Gomory 的割平面法。Gomory 割平面法首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的全部整数可行解。 算法具体设计步骤如下： 1、首先，求解原整数规划对应的线性规划 ,*)(min x c x f =???≥≤0 ..x b Ax t s ，设最优解为x*。 2、如果最优解的分量均为整数，则x*为原整数规划的最优解；否则任选一个x*中不为整数的分量，设其对应的基变量为x p ，定义包含 这个基变量的切割约束方程con j j ij p b x r x =+∑，其中x p 为非基变量。 3、令][ij ij ij r r r -=，][con con con b b b -=，其中[]为高斯函数符号，表示不大于某数的最大整数。将切割约束方程变换为 ∑∑-=-+j j ij con con j j ij p x r b b x r x ][][，由于0 整数规划的数学模型及解的特点 整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。 松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式 ∑==n j j j x c Z 1 min)max(或 中部分或全部取整数n j n j i j ij x x x m j n i x b x a t s ,...,,...2,1,...,2,10 ),(.211 ==≥=≥≤∑= 整数线性规划问题可以分为以下几种类型 1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。 2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。 1 解整数规划问题 0—1型整数规划 0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的 ???? ? ????≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z 作业题答案 第二章单纯形法 3.两阶段法求解： 解：引入松弛变量x3，x4≥0，人工变量x5，x6≥0,得第一阶段模型： Min z= x5+x6 s.t. x1+2x2-x3+x5＝80 3x1+x2-x4+x6＝75 x1, x2, X3, X4X5, X6≥0 目标函数求minZ，根据min（-4，-3）=-4得x1为换入变量，θ=min{80/1,75/3}=25得到x6为换 min（-5/3，-1/3）=-5/3,得x2为换入变量，θ=min{55/(5/3),25/(1/3)}=33得到x5为换出变量。 所有Cj-Zj≥0，取得最优解，人工变量x5=x6=0，故有最优解，转入第二阶段： 目标函数变为 Min z= 4x1 +6x2 所有检验数非负，故已取得最优解（x1，x2，x3，x4）=（14，33，0，0），MinZ=4*14+6*33=254. 4、M法求解，并讨论 解：引入松弛变量x4和x5，x6，人工变量x7，得到线性规划标准形： max z= 10x1+15x2+12x3 -Mx7 s.t. 5x1+3x2+x3+x4=9 -5x1+6x2+15x3 +x5=15 2x1+x2+x3 -x6+x7= 5 x1, x2, x3x4x5x6X7≥0 构造初始单纯形表： Max(Cj-Zj)=（10+2M，15+M，12+M）=10+2M，选择x 做换入变量，根据最小比值法 1 则θ=min{9/5,5/2}=9/5,选择x4做换出变量，在（1，1）处进行基变换得： Max(Cj-Zj)=（10+3M/5）>0，选择x 做换入变量，根据最小比值法则 3 θ=min{(9/5)/(1/5),24/16,(7/5)/(3/5)}=3/2,选择x5做换出变量，在（2，3）处进行基变换得： 所有检验数≤0，所以已得最优解。注意到人工变量x7≠0，故没有可行解。 《运筹学》课程练习题 第一章 线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充：判断下述说法是否正确 ● LP 问题的可行域是凸集。 ● LP 问题的基本可行解对应可行域的顶点。 ● LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 ● 若LP 问题有两个最优解,则它一定有无穷多个最优解. ● 求解LP 问题时,对取值无约束的自由变量，通常令 "-'=j j j x x x ,其中∶ ≥"' j j x x ,在用单纯形法求得的最优解中,不可能同时出现 "' j j x x . ● 当用两阶段法求解带有大M 的LP 模型时，若第一阶段的最优目标函数值为零， 则可断言原LP 模型一定有最优解。 7、补充：建立模型 （1）某采油区已建有n 个计量站B 1，B 2…B n ，各站目前尚未被利用的能力为b 1，b 2…b n （吨液量/日）。为适应油田开发的需要，规划在该油区打m 口调整井A 1，A 2…A m ，且这些井的位置已经确定。根据预测，调整井的产量分别为a 1，a 2…a m （吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定A i 到B j 的距离d ij 已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。 （2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米 。从第一个工厂排出的污水流到第二个 第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk 的检验数σk> 0 ，但其对应的系数列向量P k' 中，每一个元素a ik' (i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。整数规划割平面法
整数规划的两种数学模型解法
《管理运筹学》复习题及参考答案
整数规划(割平面法)
整数规划
单纯形法典型例题
整数规划
第六章---运筹学-整数规划案例
第章整数规划割平面法
第六章整数规划
《运筹学》课程学习指南
运筹学课程教学大纲
管理运筹学期末复习资料【韩伯棠】
运筹学知识点
《运筹学》综合练习题
第二章 整数规划
割平面法求解整数规划问题实验报告
整数规划的数学模型及解的特点
运筹课后题答案
课程练习题
管理运筹学课后答案