第1章 运筹学基础及应用-第六版

2020/2/21管理运筹学OPERATIONSRESEARCHFORMANAGEMENTSCIENCE2020/2/22第一章线性规划及单纯形法(LinearProgramming&SimplexMethod)§1一般线性规划问题的数学模型§2图解法§3单纯形法原理§4单纯形法的计算步骤§5单纯形法的进一步讨论§6数据包络分析(DEA)§7应用举例例2(教材第9页)生产计划问题常山机器加工厂，利用A、B、C三种不同设备加工生产Ⅰ、Ⅱ两种产品。按工艺要求，每生产一个单位的Ⅰ产品，需要占用三种设备2、4、0小时；每生产一个单位的Ⅱ产品，需要占用三种设备2、0、5小时。已知三种设备加工能力分别为12、16、15小时。且每生产一个单位的Ⅰ产品可获取2单位的利润；每生产一个单位的Ⅱ产品可获取2单位的利润。问应当如何安排加工，可使获取的总利润最大？2020/2/232020/2/24§1一般线性规划问题的数学模型1.1引例例1、生产计划问题ⅠⅡ设备能力（小时）设备A2212设备B4016设备C0515利润（元）23问：Ⅰ，Ⅱ两种产品各加工多少单位,可获最大利润?2020/2/252x1+2x212s.t.4x1165x215x1，x20注意模型特点maxZ=2x1+3x2解:设产品Ⅰ,Ⅱ产量分别为变量x1，x2防灾科技学院附例营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？序号食品名称热量（千卡）蛋白质（克）钙（毫克）价格(元/kg）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002各种食物的营养成分表每天需要300055800x1x2x3x4解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：1234123412341234min14632100080090020030005060201055..4002003005008000(j1,...,4)jzxxxxxxxxxxxxstxxxxx12121212max2322124162.t.515,0zxxxxxsxxx例2020/2/210线性规划模型的特点决策变量：向量X=(x1…xn)T决策人要考虑和控制的因素，非负约束条件：关于X的线性等式或不等式目标函数：Z=ƒ(x1…xn)为关于X的线性函数，求Z极大或极小防灾科技学院11LP问题一般可整理为：111212112122211222c12nnmnmmnmnaaaxxxccbbbmaaaaaa决策变量价值资源系数活动决策变量及各类系数之间的对应关系防灾科技学院12上述模型的共同特征：每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。nx,x,x21;;(1,;1,)ijjiacbimjn2020/2/2131.2线性规划问题的数学模型三个组成要素：1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？2020/2/215一般线性规划问题的数学模型：1111221121122222112212,,..,,,,0nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx（或）（或）（或）目标函数：约束条件：nn2211xcxcxczminmax）（或线性规划模型的简写形式(求和符号)11max(min)Z()(i12)0(j12)njjjnijjijjcxaxbmxn一般线性规划(LP)问题模型向量形式)(21ncccCnxxX1mjjjaaP11mbbbmax(min)()b..0jjzCXpxstX其中：一般线性规划(LP)问题模型矩阵形式mnmnaaaaA1111max(min)()b0ZCXAXX其中：)(21ncccCnxxX11mbbb2020/2/2191.3线性规划问题的标准形式标准形式：），，（），，（n1j0xm1ibxaxczmaxjin1jjijn1jjj标准形式特点：4.决策变量取值非负。1.目标函数为求极大值；2.约束条件全为等式；3.约束条件右端常数项全为非负；2020/2/220一般线性规划问题如何化为标准型：1.目标函数求极小值：njjjxcz1min令：，即化为：zz'njjjnjjjxcxczzz11min)max(max2020/2/2212.约束条件为不等式：（1）当约束条件为“≤”时如：122221xx可令：，显然1222321xxx03x（2）当约束条件为“≥”时如：18121021xx可令：，显然04x181210421xxx称为松弛变量。3x称为剩余变量。4x2020/2/222松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。2020/2/2233.取值无约束的变量如果变量xj代表某产品当年计划数与上一年计划数之差，显然xj的取值可能是正也可能是负，这时可令：jjjxxx其中：00xx，令4.变量xj≤0jjxx，显然0jx2020/2/224例3(教材15页)将下述LP模型化为标准型123123123123123min2329324..32360,0,zxxxxxxxxxstxxxxxx取值无约束2020/2/225解：令，，11xxzz0033333xxxxx，，得标准形式为：06332342239200332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxz，，，，，线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”,又称多项式时间算法线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simplex）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。2020/2/233求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。），，（），，（njxmibxaxczjinjjijnjjj101max111.4线性规划问题的解的概念2020/2/234可行解：满足所有约束条件的解称为可行解，所有可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解。基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。基可行解：满足变量非负的基解称为基可行解可行基：对应于基可行解的基称为可行基2020/2/235例：考察下述线性规划问题：5,...2,1,01551641222..00032max524132154321ixxxxxxxxtsxxxxxzi2020/2/236（1）可行解，如)15,16,12,0,0()0,4,0,3,3(或满足约束条件，所以是可行解。（2）基系数矩阵A：100500100400122A54321PPPPP其中100010001),,(5431PPPB或150004022),,(5212PPPB都构成基。而)(431PPP不构成基。2020/2/237（3）基向量、基变量521,,PPP是对应于基的三个基向量，而2B521,,xxx是对应于这三个基向量的基变量。（4）基解、基可行解、可行基)1516,12,0,0(是对应于基1B的一个基解、基可行解。)5,0,0,2,4(是对应于基2B的一个基解、基可行解。21,BB均是可行基。练习：P14，例42020/2/238为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。求解下述线性规划问题：0,151641222212121xxxxxx52132maxxxz§2线性规划问题的图解法2020/2/239画出线性规划问题的可行域：122221xx1641x1552x2x1xO1Q2Q3Q4Q342132xxZ目标函数等值线33212zxx2020/2/2401、可行域：约束条件所围成的区域。2、基可行解：对应可行域的顶点。3、目标函数等值线：332321