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

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

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

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

3、据食物数量及价格可写出食谱费用为cxcxcx,1122nn其次食谱中第i种营养素的含量为axaxax.i11i22inn因此上述问题可表述为：mincxcxcx1122nnaxaxaxb1111221nn1axaxaxb2112222nn2s.t.axaxaxbm11m22mnnmx0,x0,x012n上述食谱问题就是一个典型的线性规划问题，它是指在一组线性的等式或不等式的约束条件下，寻求以线性函数的最大（小）值为目标的数学模型.目标函数Tc(c,

4、,c)价值向量1n线性规划模型的三种形式cj,j1,2,,n价值系数⑴一般形式xj,j1,2,,n决策变量Tmin(max)zc1x1cnxnAib1s.t.系axa1a1xa12aa1nxb,i1,,pi11i22inni数a21a22a2nbaiA1x1ai2x2ainxnbi,ip1,,s矩bmaxaxaxb,is1,,m阵i11i22inniam1am2amn右

5、端向量x0,j1,,qj非负约束Ajx0,jq1,n自由变量j⑵规范形式⑶标准形式TTmincxmincxAxbAxbs.t.s.t.x0x0三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.目标函数的转化maxzmin(z)zox-z约束条件和变量的转化①．为了把一般形式的LP问题变换为规范形式，我们必须消除等式约束和符号无限制变量.在一般形式的LP中，一个等式约束naijx

6、jbij1可用下述两个不等式约束去替代nnaijxjbi(aij)xj(bi)j1j1对于一个无符号限制变量xj，引进两个非负变量x0和x0，并设jjxxxjjj这样就把一般形式的LP变换为规范形式.②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量.对符号无限制变量的处理可按上述方法进行.对于一个不等式约束naijxjbij1可引入一个剩余变量si，用naijxjsibi,si0j1代替上述的不等式约束.对于不等式约束naijxjbi

7、j1可引入一个松弛变量ri，用naijxjribi,ri0j1代替上述的不等式约束这样就把一般形式的LP变换为标准形式.2.2线性规划模型的求解针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算法——单纯形方法及其相应的变化形式（两阶段法，对偶单纯形法等）.单纯形方法是线性规划问题的最为基础、也是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直

8、到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献[1].在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO和LINDO.运输问题例2.设要从甲地调出物资