1 大学数学实验 Experiments in Mathematics 实验9 整数规划 (Integer Programming) 清华大学数学科学系 基本内容 2. 基本原理与解法 3. LINDO / LINGO软件的使用 1. 实例及其数学模型 ? 分枝定界法 ? 动态规划法 实例1：选课问题 校规： 学生每学期选修的总学分不能少于 20，任选课 学分不能少于总学分的 1/6，也不能超过总学分数的 1/3 675468同时选修要求 1111222333学分 1817161514131211109任选课课号 21同时选修要求 23334455学分 87654321限选课课号 本学期必修课只有一门（ 2学分）；限选课有 8门，任 选课有 10门，最少应该选几门课？ }1,0{ ,,, ,,, 3,6,20,2 222333 23334455.. 146137125114 106987251 2221 18171615141312111092 876543211 18 1 ∈ ≥≥≥≥ ≥≥≥≥ ≥≤≥++= +++++++++= +++++++= ∑ = i i i x xxxxxxxx xxxxxxxx yyyyyyyy xxxxxxxxxxy xxxxxxxxyts xMin 决策变量： x i （ =1选修课程 i， =0不选修课程 i） 目标函数： 选修课程之和 约束条件： 选修课程 i 时必须选修课程 j ： x j ≥x i 0-1规划 (一种特 殊 整数 规划 ) y1， y2 分别表示选修的限选课、任 选课的学分数， y 表示总学分数 线性规划（ LP）最优解：（其他 x i 为 0） x 1 = x 2 = x 4 = x 11 =1， x 3 = 0.0833， x 6 = x 10 = 0.1111 }1,0{ ,,, ,,, 3,6,20,2 222333 23334455 146137125114 106987251 2221 18171615141312111092 876543211 ∈ ≥≥≥≥ ≥≥≥≥ ≥≤≥++= +++++++++= +++++++= i x xxxxxxxx xxxxxxxx yyyyyyyy xxxxxxxxxxy xxxxxxxxy 10 ≤≤ i x LP松弛问题 ? 四舍五入，选 4门课程 1/2/4/11，共 19个学分 , 太少； ? 向上取整，选 7门 (加 3/6/10)，共 27个学分，太多？ 整数规划一般不能通过解 LP松弛问题得到最优解 演示： Course.LTX 问题 1. 如何下料最节省 ? 实例2：钢管下料 问题 2. 客户增加需求： 原料钢管:每根 19米 4米 50根 6米 20根 8米 15根 客户需求 节省的标准是什么？ 由于采用不同切割模式太多，会增加生产和管理成 本，规定切割模式不能超过 3种。如何下料最节省？ 5米 10根 2 按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式 余料1米4米 1根 6米 1根 8米 1根 余料 3米4米 1根 6米 1根 6米 1根 合理切割模式 的余料应小于客户需要钢管的最小尺寸 余料 3米8米 1根 8米 1根 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 合理切割模式 2. 所用原料钢管总根数最少 模式 4米钢管根数 6米钢管根数 8米钢管根数 余料 (米 ) 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3 钢管下料问题1 两种 标准 1. 原料钢管剩余总余量最小 x i ~按第 i 种模式切割的原料钢管根数( i=1,2,…7) 约束 满足需求 决策变量 目标 1（总余量） 76543211 3333 xxxxxxxZMin ++++++= 50234 54321 ≥++++ xxxxx 2032 6542 ≥+++ xxxx 152 753 ≥++ xxx 模式 4米根数 6米根数 8米根数 余料 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3 需求 50 20 15 整数约束： x i 为整数 以上两个模型均是一般 整数线性规划 76543212 xxxxxxxZMin ++++++=目标 2（总根数） 钢管下料问题1 约束条件不变 50234 54321 ≥++++ xxxxx 2032 6542 ≥+++ xxxx 152 753 ≥++ xxx x i 为整数 当余料没有用处时，通常以总根数最少为目标 钢管下料问题2 对大规模问题，用模型的约束条件界定合理模式 增加一种需求： 5米 10根；切割模式不超过 3种。 现有 4种需求： 4米 50根， 5米 10根， 6米 20根， 8米 15根，用枚举法确定合理切割模式，过于复杂。 决策变量 x i ~按第 i 种模式切割的原料钢管根数( i=1,2,3) r 1i , r 2i , r 3i , r 4i ~ 第 i 种切割模式下，每根原料钢管 生产 4米、 5米、 6米和 8米长的钢管的数量 满足需求 50 313212111 ≥++ xrxrxr 10 323222121 ≥++ xrxrxr 20 333232131 ≥++ xrxrxr 15 343242141 ≥++ xrxrxr 模式合理：每根 余料不超过 3米 19865416 41312111 ≤+++≤ rrrr 19865416 42322212 ≤+++≤ rrrr 19865416 43332313 ≤+++≤ rrrr 整数非线性规划 钢管下料问题2 目标函数 （总根数） 321 xxxMin ++ 约束条件 整数约束： x i ,r 1i , r 2i , r 3i , r 4i (i=1,2,3)为整数 3 实例3： 饮料的生产批量问题 ? 安排生产计划 , 满足每周的需求 , 使 4周总费用最小。 生产成本（可变成本） : 50元 /箱 (50千元 /千箱 ) 存贮费: 每周每千箱饮料1千元 饮料厂使用同一条生产线轮流生产 多种 饮料。 若某周开工生产 某种 饮料 , 需支出 生产准备费 3千元。 某种饮料 4周的需求量 周次 需求量 (千箱 ) 1 2 2 3 3 2 4 4 合计 11 生产批量问题的一般提法 c t ~时段 t 生产费用(元/件)； h t ~时段 t (末)库存费(元/件)； s t ~时段 t 生产准备费(元)； d t ~时段 t 市场需求(件)； 假设初始库存为 0 制订生产计划, 满 足需求,并使 T个时 段的总费用最小。 tttt dIxI =?+ ?1 )( min 1 ttttt T t t Ihxcysz ++= ∑ = 0,,0 0 ≥== ttT IxII ? ? ? = > = ,0,0 ,0,1 t t t x x y 决策变量 x t ~时段 t 生产量； I t ~时段 t (末)库存量； y t =1 ~时段 t 开工生产 (y t =0 ~不开工)。 目标 约束 混合线性0-1规划 .1,0 0 = ≤? t tt y Myx 生产批量问题的一般提法 tttt dIxI =?+ ?1 0,,0 0 ≥== ttT IxII ? ? ? = > = ,0,0 ,0,1 t t t x x y )( min 1 ttttt T t t Ihxcysz ++= ∑ = M是一个充分大的正数 （这里可取 M= 11） 混合非线性0-1规划？ 整数规划问题一般形式 ljxg mixhts xf j i Zx n ,...,1,0)( ,...,1,0)(.. )(min =≤ == ∈ ? 整数线性规划 (ILP) 目标和约束均为线性函数 ? 整数非线性规划 (INLP) 目标或约束中存在非线性函数 ? 纯 (全 )整数规划 (PIP) 决策变量均为整数 ? 混合整数规划 (MIP) 决策变量有整数，也有实数 ? 0-1规划 决策变量只取 0或 1 分类 取消整数规划中决策变量为整数的限制（ 松弛 ），对 应的连续优化问题称为原问题的 松弛问题 整数规划问题对应的松弛问题 松弛问题 松弛 整数规划问题 最优解 最 优 解 整数 非整数 整数舍入 下界（对 Min问题） 上界（对 Max问题） 非最优解 原问题 松弛 对松弛问题的最优解（分量）舍入为整数，得到的往 往不是原整数规划问题的最优解（甚至不是可行解） IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x 1 x 2 C A B O 整数规划问题对应的松弛问题 4 且为整数0, 4595 6.. 85max 21 21 21 21 ≥ ≤+ ≤+ += xx xx xxts xxz ．．．． ． ．．．． ． ．．．． ．．．．． x 1 x 2 0 P o 6 9 Z max 5 6 去掉整数限制后，可行域为点（ 0,0), (6,0), (0,5), P (2.25,3.75) 围成的 4边形 LP 最优解 PP的舍入解 最靠近 P 的可行解 IP 最优解 （ 2.25， 3.75）（2， 4）（2， 3）（0， 5） z=41.25 不可行 z=34 z=40 从 LP最优解经过简单的 “移动 ”不一定得到 IP最优解 基本思想：隐式地枚举一切可行解（ “ 分而治之 ”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分枝（或称子域），要计算原 问题的最优解的下界（对极小化问题） . 这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分， 也就是尽可能去掉一些明显的非最优点，避免完全枚举 . 整数规划的分枝定界法 （BB: Branch and Bound） 对于极小化问题，在子域上解 LP，其最优值是 IP限定 在该子域时的下界； IP任意可行点的函数值是 IP的上界 线性规划松弛定界 若在某一时刻，得到一个全整数解的费用为 z m ，则 z m 为原问题的一个上界; 否则得该分枝的一个下界，继续分枝． （P1） ?? n ii T Zx xx x bAxts xc ∈ +≥ ≥ = 1 0 .. min 0 （P2） ?? n ii T Zx xx x bAxts xc ∈ ≤ ≥ = 0 0 .. min nmZA PxbAxts xcz nm T ≤∈ ≥= = × , )0(0,.. min 线性IP 分枝定界算法 – 例 （P0） + ∈ ≥ ≤+ ≥? ??= Zxx x xx xxts xxz 21 2 1 2 2 11 21 2 1 21 21 , 2 2.. min 该问题的LP松弛解为 , 不是整数解,最优值为 z 0 =-4. (P1): (P0)加上 ; (P2): (P0)加上 . T x ),( 2 5 2 30 = 2 1 ≥x 1 1 ≤x 问题(P1)的LP松弛解为 , 不是整数解,最优值为 z 1 =-3.5 (P3): (P1)加上 ; (P4): (P1)加上 . T x ),2( 2 31 = 2 2 ≥x 1 2 ≤x P0 P1 P2 2 1 ≥x 1 1 ≤x P3 P4 2 2 ≥x 1 2 ≤x P5 P6 3 1 ≥x 2 1 ≤x ,T xx )1,2( 6* == 3 6 * ?==zz 无可行解 P0 P1 P2 P3 P4 2 1 ≥x 1 1 ≤x 2 2 ≥x 1 2 ≤x T x ),( 2 5 2 30 = , z 0 =-4 T x ),2( 2 3 1 = , z 1 =-7/2 T x )1,( 4 9 4 = z 0 =-13/4 T x )1,2( 6 = z 0 =-3 无可行解 T x ),1( 2 32 = z 2 =-2.5 > z 6 分枝定界算法(Min问题) STEP4. 转 STEP1. STEP0. 令 activeset={0}(原问题 );U = ∞； currentbest=0. STEP1. 如果 activeset=?, 则已经得到原问题的最优解 , 结束 ; 否 则从活跃分枝点集合 activeset 中选择一个分枝点 k ；将 k 从 activeset中去掉 , 继续 STEP2. STEP2. 生成 k 的各分枝 i=1,2,…,n k 及其对应的下界 z i . STEP3.对分枝 i=1,2,…,n k : 如果分枝 i 得到的是全整数解且 z i <U, 则令 U=z i 且 currentbest=i；如果分枝 i 得到的不是全整数 解且 z i <U, 则把 i 加入 activeset中 . 5 整数规划的动态规划法 例：最短路问题 求各点到 T的最短路 5 6 7 7 4 9 6 8 6 5 8 3 3 6 C 1 B 1 C 2 B 2 A 1 A 2 A 3 T S 6 节点 i到节点 T 的最短路长 ( ) 0)( )(min)( ),( = += ∈ TL jLciL ij Aji 递推计算 “全过程的最优策略具有这样的性质：不管该最优 策略上某状态以前的状态和决策如何，对该状态而 言，余下的诸决策必定构成最优子策略. ”即：最优策 略的任一 后部子策略 都是最优的. 这只是最优性定理的一个推论，即最优策略的必 要条件. 最优化原理 最优子结构 （ Optimal Substructure） : An optimal solution to the problem contains within it optimal solutions to subproblems. （ 1） 正确划分阶段，选择阶段变量 k. （ 2） 对每个阶段，正确选择状态变量 x k . 选择状态变 量时应当注意两点：一是要能够正确描述受控过程的 演变特性，二是要满足 无后效性 . （ 3） 对每个阶段，正确选择决策变量 u k . （ 4） 列出相邻阶段的状态转移方程： x k+1 = T k (x k , u k ). （5） 列出按阶段 可分的准则函数 V 1,n . 假设问题的目标是极小化 建立动态规划模型的基本过程 逆序递推 k=1 k=nkk=2 1 x 2 x 3 x 1+k x 1+n x k x n x )( 11 xf 1 u 2 u k u n u )( 22 xf )( kk xf )( nn xf ? ? ? = += ++ ++ ∈ 边界条件）(0)( )](),([min)( 11 11 nn kkkkk Uu kk xf xfuxvxf kk ),( 1 kkkk uxTx = + f k (x k )表示第 k 阶段初始状态为 x k 时， k后部子过程 (阶段 k,k+1,…,n)的最优准则函数 动态规划基本方程 资源分配问题 ： 某公司现有 M台设备准备分配给该公 司所属的 N家工厂 . 当分配台 u k 设备给工厂 k时，工厂 k 利用这些设备为公司创造的利润（假设非负）为 g k (u k ). 如何分配设备资源，使得公司总利润最大？ 可能是非线性整数规划, 甚至 g k (u k )没有显式表达式 应用动态规划方法的几个例子 + = = ∈ = = ∑ ∑ Zu Muts ugz k k N k k N k k 1 1 .. )(max )( kk ug k u 工厂 k 设备数 1 2 3 0 1 2 3 4 0 4 6 7 7 0 2 5 6 8 0 3 5 7 8 状态变量 x k -第 k阶段初分配者手中拥有的设备台数 . 由题意可知 x 0 = M， x N+1 = 0 阶段的 准则函数 为 共有 N个工厂，可以把问题分解为 N个 阶段 ： 当阶段 k=N时，把手中设备分配给工厂 N； 当阶段 k=N-1时，把手中设备分配给工厂 N-1； 依次类推； 当阶段 k=1时，把手中设备分配给工厂 1. 决策变量 u k ：第 k阶段分配给工厂 k的设备台数 kk xu ≤≤0 状态转移方程 kkk uxx ?= +1 )(),( kkkkk uguxv = 6 资源分配问题 用 f k (x k ) 表示将手中资源 x k 分配给工厂 k,k+1,…, N 时的 最大利润，原问题即为计算 f 1 (M) M=4， N=3，边界条件 f 4 (x 4 ) = f 4 (0) =0 ? ? ? = ?=+= ++ ++ ≤≤ .0)( ,1,,1,)],()([max)( 11 11 0 NN kkkk xu kk xf NNkxfugxf kk L k=3时： （增函数）)()]0()([max)( 33433 0 33 33 xgfugxf xu =+= ≤≤ ;0)0()0( 33 ==gf ;3)1()1( 33 ==gf ;5)2()2( 33 ==gf ;7)3()3( 33 ==gf 8)4()4( 33 ==gf 具体计算（例） k=2时： )]()([max)]()([max)( 22322 0 3322 0 22 2222 uxfugxfugxf xuxu ?+=+= ≤≤≤≤ ;000)0()0()]0()([max)0( 322322 00 2 2 =+=+=?+= ≤≤ fgufugf u ;3}02,30max{ )}0()1(),1()0(max{)]1()([max)1( 32322322 10 2 2 =++= ++=?+= ≤≤ fgfgufugf u ;5}05,32,50max{ )}0()2(),1()1(),2()0(max{)]2()([max)2( 3232322322 20 2 2 =+++= +++=?+= ≤≤ fgfgfgufugf u ;8}06,35,52,70max{ )}0()3(),1()2(),2()1(),3()0(max{ )]3()([max)3( 32323232 2322 30 2 2 =++++= ++++= ?+= ≤≤ fgfgfgfg ufugf u ;10}08,36,55,72,80max{ )}0()4(),1()3(),2()2(),3()1(),4()0(max{ )]4()([max)4( 3232323232 2322 40 2 2 =+++++= +++++= ?+= ≤≤ fgfgfgfgfg ufugf u 资源分配问题 k=1时： )]()([max)]()([max)( 11211 0 2211 0 11 1111 uxfugxfugxf xuxu ?+=+= ≤≤≤≤ .12}07,37,56,84,100max{ )}0()4(),1()3(),2()2(),3()1(),4()0(max{ )]4()([max)4( 2121212121 1211 40 1 1 =+++++= +++++= ?+= ≤≤ fgfgfgfgfg ufugf u 最优解 ,最大利润为 . 1,2,1 * 3 * 2 * 1 === uuu 12)4( 1 * == fz 推广：非线性整数规划问题，如： + ∈ =++ ???++= Zxxx xxxts xxxxxxz 321 321 321 2 3 2 2 2 1 ,, 4.. 5342min M=4, N=3 1 2 111 )( uuug ?= 2 2 222 32)( uuug ?= 3 2 333 54)( uuug ?= 资源分配问题 应用动态规划方法解整数规划 .,,2,1,0, ,0 ,,,2,1 ,0,0 ,0,1 ,,,2,1,.. )(min 0 1 1 TtIx I Tt x x y TtdIxIts Ihxcysz tt t t t tttt ttttt T t t L L L =≥ = = ? ? ? = > = ==?+ ++= ? = ∑ 实例3：单产品、无能力限制的批量问题 可以只考虑 可以证明：一定存在满足条件 的 最优解. 用 f t 表示当 t时段初始库存为0时，从 t时段到 T 时段的 子问题的最优费用值 最优值（费用）为 f 1 . 假设费用均非负，则在最优解中 ，即 0 0 == T II ∑∑ == = T t t T t t dx 11 )1(0 1 TtxI tt ≤≤= ? {} Ttttttt ddddddx ++++∈ ++ LL 11 ,,,,0 ? ? ? ? ? ? ? ≤≤ ? ? ? ? ? >+++ = = = ∑∑∑ ? += ? = ? = +≤≤+ + + .1 ,0,][min .0, ,0 1 1 11 11 1 1 Tt dfhddcs df f f t ti i tj ji ti itt Tt tt t T τ τ τ τ X=(2,5,0,4), 最优值为 561（千元） T=4， （千元）， （千元）， （千元 /千件）50= t c3= t s 1= t h (千件 ) 2 1 =d 3 2 =d 2 3 =d 4 4 =d 具体计算过程如下： f 5 = 0; f 4 = 3+50*4+0+0=203; f 3 = min{3+50(2+4)+1*4+0,3+50*2+0+11}=306; f 2 = min{3+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1*2+11, 3+50*3+0+18}=458; f 1 = min{3+50(2+3+2+4)+1(3+2+4)+1(2+4)+1*4+0, 3+50(2+3+2)+1(3+2)+1*2+11, 3+50(2+3)+1*3+18, 3+50*2+0+26} = 561 7 LINDO 公司软件产品简要介绍 美国芝加哥 (Chicago)大学的 Linus Schrage教授于 1980 年前后开发 , 后来成立 LINDO系统公司（ LINDO Systems Inc.），网址： http://www.lindo.com LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINGO: Linear INteractive General Optimizer (V8.0) LINDO API: LINDO Application Programming Interface (V2.0) What’s Best!: (SpreadSheet e.g. EXCEL) (V7.0) 演示 (试用 )版、学生版、高级版、超级版、工业版、 扩展版 … （求解 问题规模 和 选件 不同） LINDO和LINGO软件能求解的优化模型 LINGO LINDO 优化模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续优化 整数规划 (IP) 例 加工奶制品的生产计划 1桶 牛奶 3公斤 A 1 12小时 8小时 4公斤 A 2 或 获利 24元 /公斤 获利 16元 /公斤 50桶牛奶 时间 480小时 至多加工 100公斤 A 1 制订生产计划，使每天获利最大 ? 35元可买到 1桶牛奶，买吗？若买，每天最多买多少 ? ? 可聘用临时工人，付出的工资最多是每小时几元 ? ? A 1 的获利增加到 30元 /公斤，应否改变生产计划？ 每天： 1桶 牛奶 3公斤 A 1 12小时 8小时 4公斤 A 2 或 获利 24元 /公斤 获利 16元 /公斤 x 1 桶牛奶生产 A 1 x 2 桶牛奶生产 A 2 获利 24× 3x 1 获利 16× 4 x 2 原料供应 50 21 ≤+ xx 劳动时间 480812 21 ≤+ xx 加工能力 1003 1 ≤x 决策变量 目标函数 21 6472 xxzMax +=每天获利 约束条件 非负约束 0, 21 ≥xx 线性 规划 模型 (LP) 时间 480小时 至多加工 100公斤 A 1 50桶牛奶每天 模型求解 max 72x1+64x2 st 2） x1+x2<50 3） 12x1+8x2<480 4） 3x1<100 end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生产 A 1 , 30桶生产 A 2 ，利润 3360元。 Milk01.ltx 模型求解 reduced cost值表 示当该非基变量 增加一个单位时 （其他非基变量 保持不变）目标 函数减少的量 (对 max型问题 ) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 也可理解为： 为了使该非基变 量变成基变量， 目标函数中对应 系数应增加的量 8 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 原料无剩余 时间无剩余 加工能力剩余 40 max 72x1+64x2 st 2） x1+x2<50 3） 12x1+8x2<480 4） 3x1<100 end 三 种 资 源 “资源 ” 剩余为零的约束为紧约束（有效约束） 结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 结果解释 最优解下 “资源 ”增加 1 单位时 “效益 ”的增量 原料增 1单位 , 利润增 48 时间加 1单位 , 利润增 2 能力增减不影响利润 影子价格 ? 35元可买到 1桶牛奶，要买吗？ 35 <48, 应该买！ ? 聘用临时工人付出的工资最多每小时几元？ 2元！ RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 最优解不变时目标 系数允许变化范围 DO RANGE(SENSITIVITY) ANALYSIS? Yes x 1 系数范围 (64,96) x 2 系数范围 (48,72) ? A 1 获利增加到 30元 /千克，应否改变生产计划 x 1 系数由 24×3= 72 增加为 30×3= 90，在允许范 围内 不变！ (约束条件不变 ) 结果解释 结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000 影子价格有意义 时约束右端的允 许变化范围 原料最多增加 10 时间最多增加 53 ? 35元可买到 1桶牛奶，每天最多买多少？ 最多买 10桶 ？ (目标函数不变 ) 注意 : 充分但 可能不必要 使用LINDO的一些注意事项 1. “>”（或 “<”）号与 “>=”（或 “<=”）功能相同 2. 变量与系数间可有空格 (甚至回车 ), 但无运算符 3. 变量名以字母开头，不能超过 8个字符 4. 变量名不区分大小写（包括 LINDO中的关键字） 5. 目标函数所在行是第一行，第二行起为约束条件 6. 行号 (行名 )自动产生或人为定义。行名以 “） ”结束 7. 行中注有 “!”符号的后面部分为注释。如 : ! It’s Comment. 8. 在模型的任何地方都可以用 “TITLE” 对模型命名 （最多 72个字符），如： TITLE This Model is only an Example 9. 变量不能出现在一个约束条件的右端 10. 表达式中不接受括号 “( )”和逗号 “,”等任何符号 , 例 : 400(X1+X2)需写为 400X1+400X2 11. 表达式应化简，如 2X1+3X2- 4X1应写成 -2X1+3X2 12. 缺省假定所有变量非负；可在模型的 “END”语句 后用 “FREE name”将变量 name的非负假定取消 13. 可在 “END”后用 “SUB” 或 “SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于 “x1<=10” 但用 “SUB”和 “SLB”表示的上下界约束不计入模型 的约束，也不能给出其松紧判断和敏感性分析。 14. “END”后对 0-1变量说明： INT n 或 INT name 15. “END”后对整数变量说明： GIN n 或 GIN name 使用LINDO的一些注意事项 9 [注意]二次规划(QP)问题 ? LINDO可求解二次规划 (QP)问题，但输入方式较 复杂，因为在 LINDO中不许出现非线性表达式 – 需要为每一个实际约束增加一个对偶变量 （ LAGRANGE乘子），在实际约束前增加有关变量的 一阶最优条件，转化为互补问题 – “END”后面使用 QCP命令指明实际约束开始的行号， 然后才能求解 ? 建议总是用 LINGO解 QP [注意 ]对 QP和 IP: 敏感性分析意义不大 目标 1（总余量） 76543211 3333 xxxxxxxZMin ++++++= 50234 54321 ≥++++ xxxxx 2032 6542 ≥+++ xxxx 152 753 ≥++ xxx 按模式 2切割 12根,按模式 5切割 15根，余料 27米 最优解： x 2 =12, x 5 =15, 其余为 0； 最优值： 27 x i 为整数 CUT01a.LTX 实例2：钢管下料(问题1) 当余料没有用处时，通常以总根数最少为目标 76543212 xxxxxxxZMin ++++++=目标 2（总根数） 最优解： x 2 =15, x 5 =5, x 7 =5, 其余为 0； 最优值： 25。 50234 54321 ≥++++ xxxxx 2032 6542 ≥+++ xxxx 152 753 ≥++ xxx x i 为整数 按模式 2切割 15根， 按模式 5切割 5根， 按模式 7切割 5根， 共 25根，余料 35米 虽余料增加 8米，但减少了 2根 与目标 1的结果 “共切割 27根， 余料 27米 ” 相比 : CUT01b.LTX 实例2：钢管下料(问题1) LINGO软件简介 ? 目标与约束段 ? 集合段（ SETS ENDSETS） ? 数据段（ DATA ENDDATA） ? 初始段（ INIT ENDINIT） LINGO模型的构成： 4个段 LINGO模型的优点 ?包含了 LINDO的全部功能，并能处理非线性优化 ?提供了灵活的编程语言（矩阵生成器） 集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法 setname [/member_list/] [: attribute_list]; setname(parent_set_list) [/member_list/] [: attribute_list]; SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS SETS: STUDENTS /S1..S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH; ENDSETS 集合循环函数 四个集合循环函数： FOR、 SUM 、 MAX、 MIN @function( setname [ ( set_index_list)[ | condition]] : expression_list); @FOR(STUDENTS( I): [constraints] @SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K)) =1); Example: ∑ ∈PAIRSJI JIMATCHJIBENEFIT ),( ),(*),( 1),( ),( = ∑ = = ∈ IK orIJ PAIRSKJ KJMATCH [objective] MAX = @SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J)); 10 50 313212111 ≥++ xrxrxr 10 323222121 ≥++ xrxrxr 20 333232131 ≥++ xrxrxr 15 343242141 ≥++ xrxrxr 19865416 41312111 ≤+++≤ rrrr 19865416 42322212 ≤+++≤ rrrr 19865416 43332313 ≤+++≤ rrrr 目标函数（总根数） 321 xxxMin ++ x i ,r 1i , r 2i , r 3i , r 4i (i=1,2,3)为整数 实例2：钢管下料(问题2) 增加约束，缩小可行域，便于求解 321 xxx ≥≥ 原料钢管总根数下界： 26 19 158206105504 = ? ? ? ? ? ? ×+×+×+× 特殊生产计划：对每根原料钢管 模式 1：切割成 4根 4米钢管，需 13根； 模式 2：切割成 1根 5米和 2根 6米钢管，需 10根； 模式 3：切割成 2根 8米钢管，需 8根。 原料钢管总根数上界： 31 3126 321 ≤++≤ xxx 模式排列顺序可任定 需求： 4米 50根， 5米 10 根， 6米 20根， 8米 15根 每根原料钢管长 19米 实例2：钢管下料(问题2) Local optimal solution found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式 1：每根原料钢管切割成 3 根 4米和 1根 6米钢管，共 10根； 模式 2：每根原料钢管切割成 2 根 4米、 1根 5米和 1根 6米钢管， 共 10根； 模式 3：每根原料钢管切割成 2 根 8米钢管，共 8根。 原料钢管总根数为 28根。 演示 cut02a.lg4； cut02b.lg4 实例2：钢管下料(问题2)布置实验 目的 1)掌握用 LINDO/LINGO软件求解整数规划， 并对结果作初步分析； 内容 课上布置，或参见网络学堂 2) 通过实例练习用整数规划求解实际问题。