资源描述：
《线性规划及单纯形法(II)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章线性规划及单纯形法LinearProgrammingandSimplexMethod北京物资学院运筹学教学课件北京物资学院信息学院李珍萍2013年9月第一节线性规划问题的数学模型第二节两变量线性规划问题的图解法第三节线性规划问题的基本定理第四节单纯形法第五节单纯形法的进一步讨论第六节线性规划应用案例分析本章内容第一节线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。线性规划研究的问题：极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。极小化问
2、题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务。一、引例：生产安排问题原料配比问题运输问题二、线性规划问题的结构特征三、线性规划问题的数学模型线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化本节内容安排一、引例例1[生产安排问题]某企业使用A、B、C三台机器生产甲、乙两种产品。已知未来两周内A、B、C三台机器的使用时间分别不得超过80，60，45小时，生产每单位产品所需要各台机器的加工时间及每单位产品的利润如下表所示，问企业如何安排未来两周的生产，才能使总利润达到最大？产品机器甲乙可利用的机时
3、（小时）A2480B3260C3045单位产品的利润（元）5060可控因素：生产两种产品的数量，设分别为x1,x2，目标是生产利润最大，设生产利润为z.利润函数为：限制条件：三台设备的使用时间不超过可利用机时设备A:2x1+4x2≤80设备B:3x1+2x2≤60设备C:3x1≤45蕴涵约束：产量为非负x10,x20目标函数约束条件设生产甲乙两种产品的数量分别为x1,x2单位，总利润为z.例2[原料配比问题]某企业使用三种原料B1,B2,B3配置某种食品，要求食品中蛋白质、脂肪、糖、维生素的含量分别不低于15、20、25、30单位。以上三
4、种原料的单价以及每单位原料所含各种成分的数量如下表所示，问应如何配置食品，才能使成本最低？原料营养成分B1B2B3食品中营养成分的需要量蛋白质56815脂肪34620糖85425维生素1012830原料单价（元）202530设x1,x2,x3分别表示原料B1,B2,B3的用量，z表示食品成本。该问题的数学模型为：例3[运输问题]设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。假定运费与运量成正比例，问怎样才能找到一个总运
5、费最省的调拨计划？丙1726384315375151乙1572521甲DCBA销地产地单位：元/吨x22x11x12x13x21x23x31x32x33x14x24x34用（i=1,2,3;j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。则该问题的数学模型为简化表达式二、线性规划问题的结构特征：（1）都有一组决策变量。（2）都有一组线性的约束条件，它们是线性等式或不等式。（3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。线性规划问题的本质：研
6、究在一组线性约束下，一个线性函数的极值问题。所以称为线性规划linearprogramming(LP)1.线性规划问题的一般形式s.t（1）（2）（3）一般形式的简化表达三、线性规划问题的数学模型：规范形式极大化问题极小化问题2.线性规划的标准形式s.t.s.t（1）（2）（3）标准形式的简化表达标准形式的矩阵表达标准形式的向量表达标准形式的特点：(1).目标函数极大化(2).约束条件全部是等式(3).所有的变量都是非负的(4).约束条件右端常数为非负的3.一般形式向标准形式的转化：(1)目标函数极大化对于极小化的目标函数可以等价地转化成求的
7、极大化。(2)不等式约束化等式约束对于形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。例如：(3)自由变量化非负变量的差自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量，可以引进两个非负变量并设(4)约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘以-1。取值小于等于0的变量，可以用一个非负变量的相反数表示。例将下列LP问题化成标准形式s.t.s.t.课堂练习：将下列LP问题化成标准形式作业：P46页 习题1-4题第二节两变量线性规划问题的图解法
8、一、几个概念二、两变量线性规划问题的图解法三、两变量线性规划问题解的性质可行解：任何一组满足所有约束条件的决策变量值称为LP问题的一个可行解。最优解：使目标函数达到
