线性规划整数规划0-1规划

《线性规划整数规划0-1规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、引言二、线性规划模型三、整数线性规划模型四、0-1整数规划模型五、非线性规划模型六、多目标规划模型七、动态规划模型一、引言我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常见的

2、一类数学模型.从历年全国大学生数模竞赛越多的人所重视.随着计算机的逐渐普及，它越试题的解题方法统计结果来看，每年至少有一道题涉及到利用规划理论来分析、求解.二、线性规划模型线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有n种食物，各含m种营养素，第j种食物中第i中营养素的含量为aij,n种食物价格分别为c1,c2,…,cn，请确定食谱中n种食物的数量x1,x2,…,xn，要求在食谱中m种营养素简单的一种.2.1线性规划模型的标准形式的含量分别不低于b1,b2,…,bm的情况下，使得总总的费用最低.首先根据食

3、物数量及价格可写出食谱费用为其次食谱中第i种营养素的含量为因此上述问题可表述为：解上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，线性规划模型的三种形式⑴一般形式目标函数价值向量价值系数决策变量右端向量系数矩阵非负约束自由变量⑵规范形式⑶标准形式三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.目标函数的转化xoz-z约束条件和变量的转化①．为了

4、把一般形式的LP问题变换为规范形式，我们必须消除等式约束和符号无限制变量.在一般形式的LP中，一个等式约束可用下述两个不等式约束去替代这样就把一般形式的LP变换为规范形式.对于一个无符号限制变量，引进两个非负变量和，并设②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量.对于一个不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行.可引入一个剩余变量，用对于不等式约束代替上述的不等式约束这样就把一般形式的LP变换为标准形式.可引入一个松弛变量，用针对标准形式的线性规划问题

5、，其解的理论分析已经很完备，在此基础上也提出了很好的算单纯形方法是线性规划问题的最为基础、也法——单纯形方法及其相应的变化形式（两阶段2.2线性规划模型的求解法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献[1].在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一

6、般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO和LINDO.运输问题例2.设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？1572521甲15375151乙DCBA表1.1销地运费产地乙甲DCBA解一般的运输问题可以表述如下：数学模

7、型：若其中各产地的总产量等于各销地的总销量，即类似与将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题.总产量>总销量和总产量<总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题.从而，我们的重点就是解决平衡运输问题的求解.产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型mnminf=cijxij（1）i=1j=1ns.t.xijaii=1,2,…,m（2）j=1mxij(=,)bjj

8、=1,2,…,n(3）i=1xij0(i=1,2,…,m;j=1,2,…,n)（4）我们可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况mn考虑ai>bj的运输问题，得到的数学模i=1j=1型为mnminf=cijxiji=1j=1ns.t.xijaii=1