0_1线性规划模型的MATLAB实现及应用

收稿日期 :2007209221 作者简介 :管志忠 (19652) ,男 ,安徽池州人 ,副教授 ,硕士 ,主要从事应用数学研究. 第 22 卷第 12 期 徐 州 工 程 学 院 学 报 2007 年 12 月 Vol. 22 No. 12 Journal of Xuzhou Institute of Technology DEC1 2007 021 线性规划模型的 MA TL AB 实现及应用 管志忠1 ,吕 　楠2 (1. 池州职业技术学院 , 　安徽　池州　247100 ; 　2. 徐州工程学院 , 　江苏　徐州　221008) 　　【摘　要】　用 MA TL AB 程序实现了 021 线性规划问题数学模型的求解方法 ,并进一步通过 实例模型求解方法的分析比较 ,证明所采用的程序方法有效快捷. 文中的程序简单明了且具有通 用性 ,只需输入规划模型中对应的相关矩阵 ,立即得到最优解和最优值. 【关键词】　021 线性规划 ;数学模型 ;MA TLAB ;最优解 ;最优值 【中图分类号】　O221. 1 　【文献标识码】A 【文章编号】167320704 (2007) 1220064204 0 - 1 线性规划是一种特殊形式的整数规划. 021 规划在工厂选址问题、运输问题、投资问题、加工问题、 开发新产品问题等方面有着广泛的应用 ,随着一些数学计算软件包如 MA TL AB、L INDO 等的开发与应用 , 021 规划方法在为管理人员作决策时提供了科学的依据 ,是实现管理现代化的有力工具. 本文利用 MA T2 L AB 软件对 021 线性规划模型实施了程序化 ,通过程序的应用以及与其它求解方法的分析对比可以看出 , 用 021 线性规划程序来解 0 - 1 线性规划问题比现有的隐枚举法、排序法、穷举法等方法求解要简单快捷 得多. 1 　021 线性规划的基本模型 在实际管理中 ,很多问题无法归结为线性规划的数学模型 ,但却可以通过设置逻辑变量建立起整数规划 的数学模型. 例如选址决策问题 :随着业务发展 ,某制造公司必须在甲地或乙地建立 1 至 2 个新工厂 ,此外还 考虑建一个仓库. 若仓库与工厂设在同一地点 ,就可以节省运输费用 (若不准备建工厂 ,也就不需要建任何仓 库) . 问题的关键是新厂建在甲地还是乙地 ,或同时在两地建厂 ,建厂同时还必须考虑建一个仓库 ,仓库必须 建在新厂所在地. 当不考虑财务因素时 ,这两个地点的优劣不相上下 ,管理层认为应该在财务分析的基础上 做出决策. 对于这样的问题事实上就是“是 - 否”或“有 - 无”问题 ,可借助整数规划中的 021 整数变量 ,确定目标函 数 ,建立数学模型. 021 线性规划模型的基本形式是 : min Z = ∑ n j = 1 cj x j s. t. ∑αij x j ≤bj 　i = 1 ,2 , ⋯, m x j = 0 或 1 　j = 1 ,2 , ⋯, n 021 线性规划模型的解 ,其实质是各变量间 0 或 1 的组合. 随着变量数目的增加 ,组合数目将会很 多. 目前隐枚举法和排序法求 021 线性规划模型的解 ,除了对特殊结构的 021 线性规划模型有较高的效率 外 ,一般收效较慢 ,特别对于大规模系统 ,求解工作量非常大. 以下程序很好地解决了此问题. 2 　模型求解的 Matlab 程序实现 ·46· 根据以上 021 线性规划数学模型 ,运用 Matlab 软件编写的程序 (不妨取文件名 :L01n. m)如下 : f unction [ xmin ,f ] = L01n (c ,A ,b ,N ,p re) %求 0 - 1 整数规划. min f = c’ 3 x’ , s. t . A 3 x’ ≤b , 其中 N 表示前 N 个约束是等式 ,Pre 是等式约束的精度. 输出最优解 xmin 和最优值 f . if nargin < 5 , p re = 0 ; if nargin < 4 , N = 0 ; end ; end ; c = c ( :) ; b = b ( :) ; [ m ,n ] = size (A) ; f = sum (abs (c) ) ; x = zeros (1 ,n) ; f t = 0 ; while 1 jj = 0 ; f t = dot (c ,x) ; t1 = f t - f ; while (t1 < = 0) &(jj < m) jj = jj + 1 ; t1 = A (jj , :) 3 x - b (jj) ; if jj > N if t1 > 0 jj = 0 ; end ; else if abs (t1) > pre jj = 0 ; break ; end ; end ; end if jj = = m f = ft ; xmin = x ; jj = 0 ; end ; k = 1 ; while x (k) = = 1 x (k) = 0 ; if k = = n ret urn ; end k = k + 1 ; end x (k) = 1 ; end 在本程序中 ,整数变量的个数不受限制 , 并且充分利用已经得到的计算结果来推出下一步的结果 , 使 得程序中只使用了加减运算 ,从而大大地减少了目标函数和约束条件的计算量. 运用此程序解答 021 线性规 划问题时 ,根据实际问题的模型写出矩阵 c、A、b ,确定模型中的约束等式数 N 和等式约束的精度 pre ,然后 在 Matlab 命令窗口中分别输入 c、A、b ,再输入[ xmin ,f ] = L01n (c ,A ,b ,N ,p re) ,立即得到该模型的最优解 X3 和最优值 X30 = f . 3 　模型程序的应用与比较 通常解 021 整数规划问题所采用的是人们所熟悉的隐枚举法、排序法等 ,隐枚举法简单地说就是每次只 检查 021 变量组合的一部分就能确定其是否可能成为最优解的一种方法. 排序法是按目标函数中各变量系 数的大小按从大到小 (或从小到大)重新排列 ,使最优解有较早出现的可能. 它们通过列表、确定初始过滤条 件、过滤、再依次计算过滤 ,最后找到最优解和最优值. 与此相比 ,本文中运用 Matlab 编写的程序求 0 - 1 整 数规划模型的解就显得简单明了、方便快捷. 实例 1 　求 021 线性规划模型 : min z = 3 x1 + 7 x2 - x3 + x4 s. t. 2 x1 - x2 + x3 - x4 ≥1 x1 - x2 + 6 x3 + 4 x4 ≥8 tx 1 + 3 x2 + x4 ≥5 x j = 0 或 1 , j = 1 ,2 ,3 ,4 分析一 (隐枚举法) :将上述模型变为形式 max f = - z = - 3 x1 - 7 x2 - x3 - x4 ·56· 管志忠 ,等 : 021 线性规划模型的 MA TLAB 实现及应用 s. t. - 2 x1 + x2 - x3 + x4 ≤- 1 - x1 + x2 - 6 x3 - 4 x4 ≤- 8 - 5 x1 - 3 x2 - x4 ≤- 5 x j = 0 或 1 , j = 1 ,2 ,3 ,4 根据 021 整数规划模型设计隐枚举法计算表 ,并将 021 变量的所有组合填写在点 (x1 ,x2 ,x3 ,x4 ) 列中 (如 表 1 所示) . 表 1 　隐枚举法计算表 Table 1 　Implicit enumeration calculation table 点 (x1 ,x2 ,x3 ,x4) 条 件 过滤条件 函数约束 1 函数约束 2 函数约束 3 目标函数 f 判断 过滤 条件值 (0 ,0 ,0 ,0) T √ × × (0 ,0 ,0 ,1) T √ × × (0 ,0 ,1 ,0) T √ √ × × (0 ,0 ,1 ,1) T √ × × (0 ,1 ,0 ,0) T √ × × (0 ,1 ,0 ,1) T √ × × (0 ,1 ,1 ,0) T √ × × (0 ,1 ,1 ,1) T √ × × (1 ,0 ,0 ,0) T √ √ × × (1 ,0 ,0 ,1) T √ √ × × (1 ,0 ,1 ,0) T √ √ × × (1 ,0 ,1 ,1) T √ √ √ √ - 3 √ - 3 (1 ,1 ,0 ,0) T × × (1 ,1 ,0 ,1) T × × (1 ,1 ,1 ,0) T × × (1 ,1 ,1 ,1) T × × 通过上述的列表、计算、过滤 ,本例中最优解 X3 = (1 ,0 ,1 ,1) T ,最优值 z 3 = - f 3 = 3. 分析二 (排序法) :我们将目标函数中各变量系数的大小按从大到小重新排列 ,使最优解有较早出现的可 能. 于是将模型变为 min z = 7 x2 + 3 x1 + x4 - x3 s. t. - x2 + 2 x1 - x4 + x3 ≥1 - x2 + x1 + 4 x4 + 6 x3 ≥8 3 x2 + 5 x1 + x4 ≥5 x j = 0 或 1 , j = 1 ,2 ,3 ,4 计算过程见表 2 : 表 2 　排序法计算表 Table 2 　The list of result by ranking method 点 (x2 ,x1 ,x4 ,x3) 条　　件 约束 1 约束 2 约束 3 目标函数 z 过滤条件 (0 ,0 ,0 ,0) T × 0 (0 ,0 ,0 ,1) T √ × - 1 (0 ,0 ,1 ,0) T × 1 (0 ,0 ,1 ,1) T × 0 (0 ,1 ,0 ,0) T √ × 3 (0 ,1 ,0 ,1) T √ × 2 (0 ,1 ,1 ,0) T √ × 4 (0 ,1 ,1 ,1) T √ √ √ 3 Z≤3 (1 ,0 ,0 ,0) T 7 (1 ,0 ,0 ,1) T 6 (1 ,0 ,1 ,0) T 8 (1 ,0 ,1 ,1) T 7 (1 ,1 ,0 ,0) T 10 (1 ,1 ,0 ,1) T 9 (1 ,1 ,1 ,0) T 11 (1 ,1 ,1 ,1) T 10 ·66· 徐州工程学院学报 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2007 年第 12 期 　　通过上述列表可得本例所求的最优解 为 (x2 ,x1 ,x4 ,x3 ) T = (0 ,1 ,1 ,1) T ,即 X3 = ( x1 , x2 , x3 , x4 ) T = (1 ,0 ,1 ,1) T ,最优值 z 3 = 3. 如果是最大化问题 ,则将变量按其在目标函数中的大小由小到大排列即可. 分析三 (MA TLAB 程序法) :在 MA TL AB 命令窗口中 ,输入 c = [3 ,7 , - 1 ,1 ] ; A = [ - 2 ,1 , - 1 ,1 ; - 1 ,1 , - 6 , - 4 ; - 5 , - 3 ,0 , - 1 ] ; b = [ - 1 , - 8 , - 5 ] ; (回车) [ xmin ,f ] = L01n (c ,A ,b ,0 ,0) . (回车) 立即得到 xmin = (1 ,0 ,1 ,1) T 和 f = 3 ,于是原题的最优解 X3 = (1 ,0 ,1 ,1) T 和最优值 z 3 = 3. 最后该说明一下将 0 - 1 线性规划模型程序化的必要性了. 在当今企业的生产经营活动中 ,最高层管理 者主要关心的是企业的目标、方针和基本战略等全面性决策问题 ,这些问题的解决为在变化环境中指导企业 提供一个骨架. 中下层管理的很多决策活动是处于操作层次的 ,可以编写程序 ,让计算机来为管理阶层提供 最优解答. 一旦问题被编成程序 ,则可以把它们移交给一个管理信息系统. 这种运筹模型的程序化可以把 管理者从日常繁琐的计算分析工作中解脱出来 ,以便他们能集中精力解决更为困难的战略性问题. 这种模 型程序化的优越性从以上实例模型的分析比较中已经完全表现出来. 所以 ,本文中的规划模型程序化做法是 非常必要的 ,值得应用和推广. 参 　考 　文 　献 [1 ] 牛映武. 运筹学[ M ] .西安 :西安交通大学出版社 ,2006 :118 - 1231 [2 ] 仉志余. 运筹学基础[ M ] . 北京 :中国科学技术出版社 ,2003 :84 - 901 [3 ] 徐玖平 ,胡知能. 运筹学 - 数据 ·模型 ·决策[ M ] . 北京 :科学出版社 ,2006 :42 - 701 [4 ] 李映红. 线性 0 - 1 规划模型的排序解法[J ] . 西安交通大学学报 ,2001 , (10) :468 - 4711 [5 ] 李南南等. MA TLAB7 简明教程[ M ] . 北京 :清华大学出版社 ,2006 :289 - 3421 MATLAB Realization of the 0 - 1 Linear Programming Model and Its Appl ication GUAN2Zhi zhong1 ,LüNan2 (1. Chizhou Professional and Technical College , Chizhou 247100 , China ; 2. Xuzhou Institute of Technonogy , Xuzhou 221008 , China) 【Abstract】　MA TL AB is employed to realize the solution of 0 - 1 linear p rogramming model . And it is f urt her p roved t hrough example model comparison t hat t he new met hod is bot h effective and efficient . The program int roduced in t he paper is so simple and general t hat the optimal solution and value can be ob2 tained by simply imp uting relative mat rix in t he programming model . 【Key words】　0 - 1linear p rogramming ; mat h model ; MA TLAB ; optimal answer ; optimal value (责任编辑 　燕善俊) ·76· 管志忠 ,等 : 021 线性规划模型的 MA TLAB 实现及应用