龙源期刊网
整数规划模型Excel求解的简化方法
作者：陈候炎 徐玉娥 陈其嶙
来源：《科学与财富》2011年第12期
[摘 要] 整数规划是一类典型的线性规划问题。对于这类问题，运筹学中已有解决的方法，但比较繁琐。本文利用Excel软件的“规划求解”工具，对整数规划问题求解的模型建立和求解作了较详尽的论述。
[关键词] 整数规划问题 Excel 规划求解
整数规划是线性规划中的一类典型问题，应用于解决生产实际的许多问题，有着广泛的应用前景。对于这类问题，运筹学中已有解决方法，如分枝定界法、穷举法等，但很繁琐。也有借助于Matlab、Mathematics和 Lingo等软件求解,但专业性太强。相比之下,Excel功能强大，汉化水平高，菜单操作方便，拥有大量的函数、公式等，不需专门购买和安装。为解决整数规划问题提供了一种很好的工具。本文结合实例说明利用在Excel软件中“规划求解”工具，建立数学模型并求解整数规划问题。
1 “规划求解”工具
Microsoft Excel的“规划求解”工具取自于Leon Lasdon和Allan Waren共同开发的非线性最优化代码。“规划求解”是Execl中的一个加载宏。
1.1 安装 “规划求解”
加载宏是Excel的一个可选安装模块，在安装Microsoft Excel时，系统默认的安装方式不会安装宏程序，只有在选择“完全／定制安装”时才可选择安装这个模块。如果采用“典型安装”，则“规划求解”工具没有安装 ，就必须重新启动Office安装程序并且选择Excel选项，在加载宏区段中选择 “规划求解”，然后进行安装。
1.2 加载“规划求解”
安装了“规划求解”之后，在“工具”菜单下可能仍然找不到“规划求解”，此时您可以选择“工具/加载宏”，在打开的“加载宏”对话框中选中 “规划求解”复选框，确定后，就可以将“规划求解”命令添加到“工具”菜单栏中了。
1
甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模
型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的 2 专业推广者推
广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广
工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a −b批兼职推广员，其余的b批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若不行，考虑争取4 人。§5.4 0—1型整数规划模型
1、 0—1型整数规划模型概述
整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。
0—1型整数规划的的数学模型为：
目标函数 nnxcxcxczMinMax2211)(
约束条件为：
1 | 0 ) ,() ,() ,(22112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa, , ,21
线性规划与整数规划模式
介绍
在线性规划（Linear Programming）中，我们寻求一组决策变量的最优值，以使得对应的线性目标函数取得最大或最小值，同时满足一组线性约束条件。然而，有些情况下，我们需要求解的决策变量只能取整数值，而不能取非整数值。这就引入了整数规划（Integer Programming）。
线性规划和整数规划都是数学编程方法，主要用于优化问题的求解。在现实生活中，我们经常遇到需要优化某个目标函数或满足一组约束条件的问题，例如资源分配、生产排程、运输问题等。
本文将介绍线性规划和整数规划的基本概念、模型建立方法以及求解算法。
线性规划
基本概念
在线性规划中，我们需要定义决策变量、目标函数和约束条件。
• 决策变量：表示需要优化的变量，可以是任意实数值。
• 目标函数：表示我们希望最大化或最小化的线性函数。
• 约束条件：表示对决策变量的线性限制，可以是等式或不等式。
模型建立方法
模型建立是线性规划的关键步骤，需要根据具体问题进行数学建模。
1. 定义决策变量：确定需要优化的变量，并给出变量的取值范围。
2. 建立目标函数：根据问题要求，将目标转化为线性函数。
3. 建立约束条件：将问题的限制条件转化为一组线性不等式或等式。
4. 确定问题类型：确定是最大化问题还是最小化问题。
5. 完善模型：考虑特殊约束条件，如非负约束、整数约束等。
求解算法
一般来说，线性规划可以使用各种方法进行求解，常见的算法包括：
1. 单纯形法（Simplex Method）：通过在可行域内移动到更优解的方式求解线性规划问题。
2. 内点法（Interior Point Method）：通过在可行域内寻找内点的方式求解线性规划问题。 3. 分支定界法（Branch and Bound）：将整数规划问题转化为多个线性规划子问题，通过不断分支和界定来搜索可行解空间。
4. 割平面法（Cutting Plane Method）：通过添加额外的约束条件来逼近整数解的方法。
第１１卷第３期 ２０１１年６月 金华职业技术学院学报 Ｖ０ｌ＿ｌ１ Ｎｏ．３ Ｊｕｎ．２０１ｌ
数独问题的整数规划模型
胡英武
（金华职业技术学院，浙江金华３２１００７）
摘要：数独是近年流行的一种益智游戏，其最常见模式是在一个 行× 列又再分成 区共 ｚ个小格的方中，填 入适＂－－３的数字，使每一行、每一列、每一区都含有数字１ 。不重复．运用０—１规划的方法建立数独问题的整数规划模 型，给出了９阶数独模型求解的Ｌｉｎｇｏ程序，最后对模型进行了评价． 关键词：数独；Ｏ－１规划：整数规划模型 中图分类号：Ｏ１４１．４ 文献标识码：Ａ 文章编号：１６７１—３６９９（２０１１）０６—００８６—０３ ＤＯ１：１０．３９６９／ｉ．ｉｓｓｎ．１６７１－３６９９．２０１１．０６．０２３
数独是一种智力游戏，它要求在事先给定部分
数字的九个九宫格中，填入１到９的数，使每个数
在每行、每列、每个九宫格里都只出现一次，且满足 上述条件的填法有且仅有一种．图１就是一个填好
的９阶数独方，其中粗体字是已知数字．文【１ ６］介
绍了解决数独问题的若干方法，如候选数法、图论方 法、“顾氏不动点法”等，有关数独方可行解的存在
与唯一性的讨论可参阅文［１，７，８］．现在考虑一般问
题：有一事先给定部分数字的１１，ＸＩ￣方．再分成１１，个形 状相同的区，填入自然数ｌ－ｎ，使每个数在每行、每
列、每区都出现一次，且满足上述条件的填法有且
仅有一种，称该方为 阶数独方．引入三维的０—１
变量并结合整数规划的方法。给出了ｎ阶数独方问
题的整数规划模型．
１ 阶数独方的必要条件
因为一个ＩｔＸｌ￣的方要能再分成ｎ个区．就必须 满足条件ｎ＝ｐｑ，而Ｐ或ｇ如果为１，就退化为行或
列，就不能构成数独方中的区．所以．构成数独方的
必要条件是
－ｐｇ（ｐ，ｑ＞１２） 因此，所有非质数的 都能构成数独方，有些
还能构成两种或更多种数独方．而质数的ｎ都不可
