规划模型求解 指导老师： 组员： 组员分工 实际的内容： 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 )(
整数规划的数学模型及解的特点 整数规划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
甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模 型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的
专业推广者推 广能力的份数，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型整数规划的的数学模型为： 目标函数 n n x c x c x c z M i n M a x +++= 2211)( 约束条件为： ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21 这里，0 | 1表示0或1。 2、0—1型整数规划模型的解法
整数规划模型
实际问题中 x x x x f z Max Min T n "),(),()(1==或的优化模型 m i x g t s i ",2,1,0)(..=≤x ~决策变量f (x )~目标函数g i (x )≤0~约束条件 多元函数决策变量个数n 和数 线性规划条件极值约束条件个数m 较大最优解在可行域学 规 非线性规划解 的边界上取得划 整数规划
Programming +Integer 所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。 型整数规划
+整数线性规划 max(min) n z c x =1j j j n =∑1 s.t. (,) 1,2,,ij j i j a x b i m =≤=≥=∑"12 ,,,0 () n x x x ≥"且为整数 或部分为整数
+例：假设有m 种不同的物品要装入航天飞机，它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？ m 1?1 max j j j c y =∑ 1 0j j y =?被装载 s.t. m j j v y V ≤∑0 j ?没被装载1 j m =1 j j j w y W =≤∑ 0 or 1 1,2,,j y j m =="
(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h 前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：https://www.doczj.com/doc/21863907.html, I）网址htt//li d LINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。 LINGO——解决线性规划LP—Linear Programming，非线性规划NLP—Nonlinear Programming，整数规划IP—Integer Programming g g整划g g g 问题。
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min Λ 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x Λ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
实验四 混合整数规划 一、问题重述 某开放式基金现有总额为15亿元的资金可用于投资，目前共有8个项目可供投资者选择，每个项目可重复投资。根据专家经验，对每个项目投资总额不能太高，应有上限。这些项目所需要的投资额已知，一般情况下投资一年后各项目所得利润也可估算出来，如表1所示。 请帮该公司解决以下问题： (1) 就表1提供的数据，应该投资哪些项目，使得第一年所得利润最高？ (2) 在具体投资这些项目时，实际还会出现项目之间互相影响的情况。公司咨询有关专家后，得到以下可靠信息：同时投资项目A 1，A 3，它们的年利润分别是1005万元，1018.5万元；同时投资项目A 4，A 5，它们的年利润分别是1045万元，1276万元；同时投资项目A 2，A 6，A 7，A 8，它们的年利润分别是1353万元，840万元，1610万元，1350万元，该基金应如何投资？ 其中M 为你的学号后3位乘以10。 (3) 如果考虑投资风险，则应如何投资，使收益尽可能大，而风险尽可能小。投资项目 总体风险可用投资项目中最大的一个风险来衡量。专家预测出各项目的风险率，如表2所示。 二、符号说明 i A :：投资额； i b ：i A 个项目所获得的年利润； i C ：第i A 个项目投资所获得的利润； 'i C ：第i A 个项目同时投资所获得的利润； i m ：投资i A 的上限； i y ：表示0—1变量； i p ：投资第i A 个项目的投资风险； 三、模型的建立 对于问题一 目标函数：8 1max i i i c x ==∑
s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题二 设定0—1变量 131130...,1...,A A y A A ?? ?项目不同时投资项目同时投资 452450...,1...,A A y A A ???项目不同时投资 项目同时投资 2678326780...,,1...,,A A A A y A A A A ?? ?,项目不同时投资 ,项目同时投资 目标函数：'''' 11133111332445524455' '''322 66 77 88 322667788max ()(1)()()(1)()()(1)() y x c x c y x c x c y x c x c y x c x c y x c x c x c x c y x c x c x c x c =++-++++-++ ++++-+++ s.t. 1 13 131 24545 23267826783 1500001000i i i i i i b x k y x x x x y k y x x x x y k y x x x x x x x x y k b x m ?≤?? =??≤??≥?? ≤???≥? ?≤? ?≥?? ≤?∑ 对于问题三： 目标函数： max min max() i i i i i i c x b x p =∑ s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题三模型的简化 固定投资风险，优化收益，设a 为固定的最大风险。 max i i i c x =∑
第五章整数规划 一、填空题 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．匈牙利法 三、多项选择
整数规划问题 要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integer programming，简记IP)。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题(slack problem)。若松弛问题是一个线性规则，则称该整数规划为整数线性规划(integer linear programming，简记ILP 分类 整数规划问题按决策变量取值可分为下列几种类型： 1．纯整数规划(pure integer programming)：指全部决策变量都必须取整数值的整数规划。有时，也称为全整数规划。 2．混合整数规划(mixed integer programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。 3．0-1型整数规划(zero—one integer programming)：指决策变量只能取值0或1的整数规划 1.3 整数规划的一般形式 2 整数规划问题的计算方法 2.1 分支定界法 分支定界法是在20世纪60年代初由Land Doing和Dakin等人提出的适合于解纯整数或混合整数规划问题的方法。 分支定界法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分支——分为两个子规划，再解子规划的伴随规划，以此类推，最后得到原整数规划的伴随规划。这就是所谓的“分支”。 所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处理其它分支的一个依据。 “分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。
经济管理学院《运筹学》结课论文 整数规划问题的求解分析
整数规划问题的求解分析 摘要：整数规划是NP困难]1[的经典问题之一，本文讨论了整数规划问题中分支定界法与割平面法的基本原理和求解过程以及算法思想，当在决策变量和约束条件很多时,用常规的求解法效率很低，针对此种缺陷,提出了遗传算法，实现了快速解决整数规划的问题。 关键词：整数规划；分支定界法；割平面法；遗传算法 1 引言 整数规划(IP)]2[是运筹学领域里的一个重要分支,是规划论中研究决策变量取整数的一类较新、较特殊的线性规划，且大多数的组合优化问题都可以写成一个IP，如背包、旅行商、最短路、选址、分配和生产与存储计划问题等要求决策变量的取值为整数它的求解方法，目前来讲主要有割平面法、分枝定界法以及逐步完善的遗传算法。下面就它们的解法和差异加以讨论。 2 割平面法 2.1 割平面方法思想 割平面法是由高莫瑞(R E Gomory)1958年提出的，故又称为Gomory的割平面法。它的基本思想是：不断增加线性约束条件(几何术语称为割平面)将原规划问题的可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是问题的最优解为止。]3[ 2.2 割平面方法步骤 (1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。 在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。]4[ (2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线
龙源期刊网 https://www.doczj.com/doc/21863907.html, 0-1整数规划模型在混合方案的经济性比选中的应用 作者：王怀亮 来源：《对外经贸》2011年第03期 ［摘要］在技术经济分析评价中，常见一类混合方案的经济性比选，采用传统方法评价比选比较繁琐，通过把混合方案的经济性比选抽象为0-1整数规划模型，并首次利用功能强大的开源、免费统计软件Rglpk包，结合具体混合方案实例求解模型。 ［关键词］0-1整数规划模型；Rglpk包；R语言程序；混合方案 ［中图分类号］F713［文献标识码］B［文章编号］1002-2880(2011)03-0054-02 作者简介：王怀亮(1981-)，男，汉族，山东曹县人，菏泽学院经济系助教，硕士，研究方向：计量经济统计。在方案众多的情况下，方案间相关关系可能包括多种类型，称之为混合方案，传统的混合方案选择的程序如下：1.按组际间的方案互相独立、组内方案互相排斥的原则，形成所有各种可能的方案组合；2.以互斥型方案比选的原则筛选组内方案；3.在总的投资有限额下，以独立型方案比选原则选择最优的方案组合；一般来说比较复杂，很繁琐，容易出错；如果借助于0-1整数规划模型——万加特纳优化选择模型并结合R程序则简单容易操作。 一、0-1整数规划模型 0-1整数规划模型——万加特纳优化选择模型以净现值最大为目标函数。在该目标函数及一定的约束条件下，力图寻求某一项目组合方案，使其净现值比其他任何可能的组合方案的净现值都大。 该模型将影响项目方案相关性的各种因素以约束方程的形式表达出来，这些因素有六类： 1.资金、人力、物力等资源可用量限制 2.方案之间的互斥性 3.方案之间的依存关系 4.方案之间的紧密互补关系