线 性 规 划

《线 性 规 划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划LinearPrograming运筹学基本内容线性规划的基本性质及其图解法单纯形法对偶问题灵敏度分析第一章线性规划的基本性质线性规划问题及模型二维线性规划的求解：图解法线性规划的标准形式线性规划问题解及其性质线性规划研究问题主要研究解决有限资源的最佳分配问题，即如何对有限资源作出最佳方式的调配和最有力地使用，以便最充分地发挥资源的效能，以获取最佳的经济效益。生产计划问题运输问题配料问题下料问题食谱问题产品配套问题(1)生产计划问题应如何安排生产这两种产品才能获利最多？产品车间单耗（工时/件）生产能力（工时/天）甲乙A108B0212C3436利润（百元/件）3

2、5问题分析数学模型为(2)运输问题设两个粮库供应三个粮店，供应量、需求量和运费如下表所示，问如何安排运输计划，可使总运费最少？建立数学模型粮店单价（百元）粮库B1B2B3供应量（吨）A118252028A221222429需求量（吨）121530问题分析数学模型(3)配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A、B、C三种化学成分，其含量以及产品中各成分含量的最低量如下表所示。甲、乙两种原料成本见下表。厂方希望总成本大到最小，则应如何配制该产品。原料成分成份含量（%）产品成分最低含量（%）甲乙A1234B2

3、32C3155成本(元/千克)32问题分析数学模型线性规划问题的特点1、（非负的）决策变量2、求极值的目标函数3、线性的约束条件一般模型线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优点（最优解）64-860x1x2图解法的步骤可行域图形地确定所有约束条件共同构成的图形成为可行域可行域所有点（包括边界）均是可行解目标函数的等值线与最优点的确定令Z取不同值，得到一组平行的等值线沿目标函数值增大的方向移动等值线，当韩淑芝最大时与可行域的交点即为最优点。最优点的求解在图上观测最优点的坐标通过解方程组得出最

4、优点坐标值可行域的几种情况无界域x1+2x24s.t.x1-2x25x1,x2014235123x1x2x1+2x24x1-2x25可行域的几种情况有界域2846102410x13x1+4x236x1≤812682x212可行域的几种情况空集s.t.x1+2x2≤4x1-2x2≥5x1,x2≥014235123x1x2x1+2x2≤4x1-2x2≥5最优点的几种情况唯一解多重解无界解无可行解线性规划的多重解maxz=x1+x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优点（最优解）64-860x1x2maxz=2x1

5、+x2s.t.x1+x22x1-2x20x1,x20线性规划无界解14235123x1x2x1+x22z=2x1+x2x1-2x20无可行解Maxz=x1+x2s.t.x1+2x2≤4x1-2x2≥5x1,x2≥014235123x1x2x1+2x2≤4x1-2x2≥5Z=x1+x2线性规划的标准形式线性规划标准型的简写形式求和符号形式线性规划标准型的简写形式向量形式线性规划标准型的简写形式矩阵形式线性规划标准型的简写形式集合形式线性规划的模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,unr,≤0线性规划的标准形式目标函

6、数：max约束条件：=变量符号：≥0非标准形LP问题的标准化例题非标准形LP问题的标准化目标函数最小化最大化：z’=-z不等式约束等式约束变量为负约束、无符号约束非负约束右端常数小于零非负等式两边均乘-1松弛变量剩余变量练习:将下列线性规划问题化成标准型1、minZ=5x1+x2+x33x1+x2-x3≤7-3x1+x2≤6s.tx1+2x2≤4x2≥-3,x1无限制,x3≤02、maxZ=-x1+4x2s.tx1-2x2+4x3≥-6x2+3x3=3x1,x2≥0,x3无限制线性规划问题的解及其性质1.线性规划的解2.线性规划的基与基本可行解3.线性规划的基本定理线

7、性规划解的定义(1)满足线性规划问题所有约束条件的解是该问题的可行解。X=(X1,X2,…,XN)T(2)线性规划问题全部可行解的集合构成线性规划问题的可行域（或称可行解集）。R={xAx=b,x0}(3)使目标函数达到极值的可行解称为线性规划问题的最优解。(4)若对任意大的M0，都存在可行解使得该线性规划的目标函数值z=cxM,则该线性规划问题无界。线性规划的基与基本可行解基的定义：给定线性规划问题P：max{cx

8、Ax=b,x0}A是mn满秩矩阵,n>m，如果B是其中任一个mm满秩子矩阵，则称B是P的一个基。基变量与非基变量