第二章线性规划 第一讲 数学模型与图解法

运筹学OperationsResearchChapter2线性规划LinearProgramming2.1LP的数学模型MathematicalModelofLP2.2图解法GraphicalMethod2.3标准型StandardformofLP2.4基本概念BasicConcepts2.5单纯形法SimplexMethod2.1数学模型MathematicalModelChapter2线性规划LinearProgramming某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表2.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？案例分析2.1线性规划的数学模型MathematicalModelofLPChapter2线性规划LinearProgramming产品资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)403050表2.1产品资源消耗2.1线性规划的数学模型MathematicalModelofLPChapter2线性规划LinearProgramming321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，，【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量,则数学模型为：产品资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)403050最优解X=(50,30,10);Z=34002.1线性规划的数学模型MathematicalModelofLPChapter2线性规划LinearProgramming结论•如何求解，难点是什么？关键在那里？线性规划模型的建立、模型的特征、模型的求解思路和过程。Chapter2线性规划LinearProgramming线性规划问题的概念•1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）Chapter2线性规划LinearProgramming•例2.1如图所示，如何截取x使铁皮所围成的容积最大？xaxxav220dxdv0)2()2()2(22xaxxa6axChapter2线性规划LinearProgramming【例2.2】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表2.2所示。表2.2营业员需要量统计表问：商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少？星期需要人数星期需要人数一300五480二300六600三350日550四400【解】设(j=1，2，…，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为jx2.1线性规划的数学模型MathematicalModelofLPChapter2线性规划LinearProgramming7,,2,1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj2.1线性规划的数学模型MathematicalModelofLP星期需要人数星期需要人数一300五480二300六600三350日550四400Chapter2线性规划LinearProgramming2.1.2线性规划的一般模型一般地，假设线性规划数学模型中,有m个约束,有n个决策变量xj(j=1,2…,n)，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成112211112211211222221122max(min)(,)(,)..(,)0,1,2,,nnnnnnmmmnnmjZcxcxcxaxaxaxbaxaxaxbSTaxaxaxbxjn或或或LLLLLLLLLLLLLLLLLLLL2.1线性规划的数学模型MathematicalModelofLP目标函数：约束条件：Chapter2线性规划LinearProgramming11max(min)(,)1,2,,..0,1,2,,njjjnijjijjZcxaxbimSTxjn或LL在实际中一般xj≥0,但有时xj≤0或xj无符号限制。为了书写方便，上式也可写成：2.1线性规划的数学模型MathematicalModelofLPChapter2线性规划LinearProgramming2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？建立一个问题的线性规划模型的一般步骤：(1)确定决策变量；(2)确定目标函数；(3)确定约束条件；(4)确定变量是否有非负约束。Chapter2线性规划LinearProgramming向量形式：)(21ncccCnxxX1mjjjaaP1mbbB10)((min)maxXBxpCXzjj其中：Chapter2线性规划LinearProgramming矩阵形式：mnmnaaaaA11110)((min)maxXBAXCXZ其中：)(21ncccCnxxX1mbbB1Chapter2线性规划LinearProgramming例2.3某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时1281612Chapter2线性规划LinearProgramming•解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12Chapter2线性规划LinearProgramming练习1运输问题设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们的砖供应3个工地。其需要量分别为17万块、18万块、和15万块。而自各产地到各工地的运价列表如下（运价元/万块)：工地砖厂B1B2B3A1506070A260110160问如何调运，才使总运费最省？Chapter2线性规划LinearProgramming解：设xij表示由砖厂Ai运往工地Bj的砖的数量（单位：万块）（i=1,2;j=1,2,3),现列表如下：工地砖厂B1B2B3发量（万块）A1x11x12x1323A2x21x22x2327收量(万块)17181550因为由砖厂A1运往三个工地砖的总数应为A1的产量23万块,即:x11+x12+x13=23。同理由砖厂A2运往三个工地砖的总数应为A2的产量27万块,即:x21+x22+x23=27。Chapter2线性规划LinearProgramming另一方面，两个砖厂运往B1工地的砖的数量应等于B1的需要量17万块，即：x11+x21=17；同理可得：x12+x22=18；x13+x23=15。因此调运方案就是求满足前面所有约束条件的x11、x12、x13、x21、x22、x23一组变量的非负值。显然，可行的调运方案有很多，我们就是在这很多个调运方案中，找一个运费最少的方案，所求数学模型为：Chapter2线性规划LinearProgrammingMinz=50x11+60x12+70x13+60x21+110x22+160x23s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15x11、x12、x13、x21、x22、x230Chapter2线性规划LinearProgramming练习2：营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？Chapter2线性规划LinearProgramming序号食品名称热量（千卡）蛋白质（克）钙（毫克）价格(元/kg）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002各种食物的营养成分表每天需要300055800Chapter2线性规划LinearProgramming解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40Chapter2线性规划LinearProgramming例：新星炼油厂生产的70,80,85号三种汽油由三种原料调和而成，且有不同的质量要求。每种原料每日可用数量、质量指标、成本以及每种汽油的质量要求和价格见表。该炼油厂如何调和才能使利润最大？假定调和中的质量指标都符合线性相加关系。例2.汽油调和问题Chapter2线性规划LinearProgramming汽油原料数据原料辛烷值含硫量%成本(元/吨)可用量(吨/日)直馏汽油621.56002000催化汽油780.89001000重整汽油900.21400500Chapter2线性规划LinearProgramming产品汽油数据产品%辛烷值含硫量销售价格(元/吨)70#汽油701.090080#汽油801.0120085#汽油850.61500Chapter2线性规划LinearProgramming问题分析•问题类型：最优调和方案什么原料调入什么产品，调入的数量是多少•目标：调和方案的利润最大利润=销售收入-调和成本=产品价格*销售数量-原料成本*用量•变量：产品数量？原料数量？其他物理量？j产品生产数量=各原料调入j产品数量和i原料使用数量=i原料调入各产品的数量和Chapter2线性规划LinearProgramming汽油调和模型决策变量xij=i种原料调入j种汽油的数量；参数pj=第j种产品的销售价格;ci=第i种原料的生产成本;ei=原料的辛烷值,ej=产品的辛烷值