广工管理运筹学运筹学-绪论及第2章.ppt

运筹学运筹学钟映竑1 1广东工业大学管理学院广东工业大学管理学院绪论n n什么是运筹学n n运筹学研究的基本特征和基本方法n n运筹学的主要分支n n运筹学与管理科学2 2广东工业大学管理学院广东工业大学管理学院什么是运筹学（不同的定义）n n大英百科全书大英百科全书n n中国大百科全书中国大百科全书n n辞海辞海n n中国企业管理百科全书中国企业管理百科全书3 3广东工业大学管理学院广东工业大学管理学院大英百科全书的定义大英百科全书的定义n n运筹学是一门应用于管理有组织系统的科学。n n运筹学为掌管这类系统的人提供决策目标和数量分析的工具。4 4广东工业大学管理学院广东工业大学管理学院中国大百科全书的定义中国大百科全书的定义n n运筹学用数学方法研究经济、民政和国防等部门在内外的约束条件下合理分配人力、物力、财力等资源，是实际系统有效运行的技术科学，它可以用来预测发展趋势，制订行动规划或优选可行方案。5 5广东工业大学管理学院广东工业大学管理学院辞海的定义辞海的定义n n运筹学主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到经济有效地使用人力物力。6 6广东工业大学管理学院广东工业大学管理学院中国企业管理百科全书的定义中国企业管理百科全书的定义n n运筹学应用分析、实验、量化的方法，对经济管理系统中人财物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。7 7广东工业大学管理学院广东工业大学管理学院n n英国英国Operational researchn n美国美国Operations researchn n夫夫运筹运筹帷幄之中，决胜千里之外。帷幄之中，决胜千里之外。史史记记n n齐王赛马齐王赛马n n丁渭修宫丁渭修宫n n二战时英国的防空雷达系统二战时英国的防空雷达系统8 8广东工业大学管理学院广东工业大学管理学院运筹学的发展大致可分三个阶段:运筹学诞生的三个来源：军事、管理和经济1945-1950年代,创建时期;1950年代,成长时期;1960年代至今,普及和发展时期.9 9广东工业大学管理学院广东工业大学管理学院运筹学的基本特征n n系统的整体观念系统的整体观念n n多学科的综合多学科的综合n n应用模型技术应用模型技术1010广东工业大学管理学院广东工业大学管理学院n n运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开最劣的方案。1111广东工业大学管理学院广东工业大学管理学院运筹学的基本方法 模型化的方法应用步骤：应用步骤：分析与表述问题分析与表述问题分析与表述问题分析与表述问题建立模型建立模型建立模型建立模型求解模型与优化方案求解模型与优化方案求解模型与优化方案求解模型与优化方案测试模型及对模型进行必要的修正测试模型及对模型进行必要的修正测试模型及对模型进行必要的修正测试模型及对模型进行必要的修正建立对解的有效控制建立对解的有效控制建立对解的有效控制建立对解的有效控制方案的实施方案的实施方案的实施方案的实施1212广东工业大学管理学院广东工业大学管理学院决策过程（问题解决的过程）：决策过程（问题解决的过程）：决策过程（问题解决的过程）：决策过程（问题解决的过程）：1 1 1 1）认清问题；）认清问题；）认清问题；）认清问题；2 2 2 2）找出一些可供选择的方案；）找出一些可供选择的方案；）找出一些可供选择的方案；）找出一些可供选择的方案；3 3 3 3）确定目标或评估方案的标准；）确定目标或评估方案的标准；）确定目标或评估方案的标准；）确定目标或评估方案的标准；4 4 4 4）评估各个方案：解的检验、灵敏性分析等；）评估各个方案：解的检验、灵敏性分析等；）评估各个方案：解的检验、灵敏性分析等；）评估各个方案：解的检验、灵敏性分析等；5 5 5 5）选出一个最优的方案：决策；）选出一个最优的方案：决策；）选出一个最优的方案：决策；）选出一个最优的方案：决策；6 6 6 6）执行此方案：回到实践中；）执行此方案：回到实践中；）执行此方案：回到实践中；）执行此方案：回到实践中；7 7 7 7）进行后评估：考察问题是否得到完满解决；）进行后评估：考察问题是否得到完满解决；）进行后评估：考察问题是否得到完满解决；）进行后评估：考察问题是否得到完满解决；1 1 1 1）2 2 2 2）3 3 3 3）：形成问题；）：形成问题；）：形成问题；）：形成问题；4 4 4 4）5 5 5 5）：分析问题：定性分析与定量分析。构成决策。）：分析问题：定性分析与定量分析。构成决策。）：分析问题：定性分析与定量分析。构成决策。）：分析问题：定性分析与定量分析。构成决策。1313广东工业大学管理学院广东工业大学管理学院运筹学的主要分支n n线性规划线性规划(linear programming)n n非线性规划非线性规划(nonlinear programming)n n动态规划动态规划(dynamic programming)n n图与网络分析图与网络分析(graph theory and network analysis)n n存贮论存贮论(inventory theory)n n排队论排队论(queueing theory)n n对策论对策论(game theory)n n决策论决策论(decision theory)1414广东工业大学管理学院广东工业大学管理学院第四节 运筹学与管理科学n n国际上目前通行的说法：“运筹学”与“管理科学(management sciences)”在许多场合实际是指同一学科，不过前者强调方法而后者强调应用。n n因此运筹学是现代科学管理的基础，从而在管理中有非常广泛的应用。1515广东工业大学管理学院广东工业大学管理学院n n生产计划：生产作业的计划、日程表的编排、合理下料、生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和配料问题、物料管理等，追求利润最大化和成本最小化成本最小化n n库存管理：多种物资库存量的管理，库存方式、库存量等库存管理：多种物资库存量的管理，库存方式、库存量等n n运输问题：确定最小成本的运输线路、物资的调拨、运输运输问题：确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等工具的调度以及建厂地址的选择等n n人事管理：对人员的需求和使用的预测，确定人员编制、人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等人员合理分配，建立人才评价体系等n n市场营销：广告预算、媒介选择、定价、产品开发与销售市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等计划制定等n n财务和会计：预测、贷款、成本分析、定价、证券管理、财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等现金管理等*设备维修、更新，项目选择、评价，工程优化设计与管理等设备维修、更新，项目选择、评价，工程优化设计与管理等1616广东工业大学管理学院广东工业大学管理学院运筹学方法使用情况运筹学方法使用情况(美美1983)1717广东工业大学管理学院广东工业大学管理学院 运筹学方法在中国使用情况运筹学方法在中国使用情况 (随机抽样随机抽样)1818广东工业大学管理学院广东工业大学管理学院n n运筹学在国内或国外的推广应用前景是非常广阔的。n n工商企业对运筹学应用的需求是很大的。n n在工商企业推广运筹学方面有大量的工作要做。1919广东工业大学管理学院广东工业大学管理学院n n由国际运筹与管理科学协会（由国际运筹与管理科学协会（INFORMSINFORMS）和它的）和它的管理科学实践学会（管理科学实践学会（College for the Practice of College for the Practice of the Management Sciencesthe Management Sciences）主持评奖的负有盛名）主持评奖的负有盛名的弗兰茨的弗兰茨 厄德曼（厄德曼（Frany EdlmanFrany Edlman）奖，就是为奖）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入围者进奖每年举行一次，在对大量富有竞争力的入围者进行艰苦的评审后，一般有六位优胜者获奖。关于这行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物些获奖项目的文章都在第二年发表在著名刊物InterfaceInterface的第一期上，下面列表就是发表在的第一期上，下面列表就是发表在InterfaceInterface期刊的一些获奖项目。期刊的一些获奖项目。2020广东工业大学管理学院广东工业大学管理学院组织组织应用应用InterfaceInterface期刊号期刊号 每年节支每年节支（美元）（美元）联合航空公司联合航空公司满足乘客需求前提下满足乘客需求前提下,以最低成本进行订票及安排以最低成本进行订票及安排机场工作班次机场工作班次1-2/19861-2/1986600600万万CitgoCitgo石油石油优化炼油程序及产品供应、配送及营销优化炼油程序及产品供应、配送及营销1-2/19871-2/198770007000万万荷马特发展公司荷马特发展公司（Homart Development Homart Development Co.Co.）优化商业区和办公楼销售程序优化商业区和办公楼销售程序1-2/19871-2/198740004000万万AT&T AT&T 优化商业用户的电话销售中心选址优化商业用户的电话销售中心选址1-2/19901-2/19904.064.06亿亿 ，更多销，更多销售售标准品牌公司标准品牌公司控制成品库存（制定最优再订购点和订购量，确保控制成品库存（制定最优再订购点和订购量，确保安全库存）安全库存）12/198112/1981380380万万施乐公司施乐公司通过战略调整，缩短维修机器的反应时间和改进维通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率修人员的生产率11/197511/1975第二部分第二部分生产率提高生产率提高50%50%以上以上宝洁公司宝洁公司重新设计北美生产和分销系统以降低成本并加快了重新设计北美生产和分销系统以降低成本并加快了市场进入速度市场进入速度1-2/19971-2/19972 2亿亿法国国家铁路法国国家铁路制定最优铁路时刻表并调整铁路日运营量制定最优铁路时刻表并调整铁路日运营量1-2/19981-2/199815001500万更多年收万更多年收入入DeltaDelta航空公司航空公司进行上千个国内航线的飞机优化配置来最大化利润进行上千个国内航线的飞机优化配置来最大化利润1-2/19941-2/19941 1亿亿IBMIBM重组全球供应链，保持最小库存的同时满足客户需重组全球供应链，保持最小库存的同时满足客户需求求1-2/20001-2/2000第一年第一年7.57.5亿亿MeritMerit青铜制品公司青铜制品公司安装统计销售预测和成品库存管理系统，改进客户安装统计销售预测和成品库存管理系统，改进客户服务服务1-2/19931-2/1993更优的服务更优的服务2121广东工业大学管理学院广东工业大学管理学院第二章 线性规划n n线性规划问题及其数学模型n n图解法n n单纯形法原理n n单纯形法计算步骤n n单纯形法的进一步讨论n n应用举例2222广东工业大学管理学院广东工业大学管理学院第一节 线性规划及其数学模型n n问题的提出n n线性规划的数学模型n n线性规划的标准形式2323广东工业大学管理学院广东工业大学管理学院例1 美佳公司计划制造I、II两种家电产品，已知各制造一件分别占用的设备A、B的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一件的获利情况如下表所示。I III II每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 1问该公司应每天制造两种家电各多少件，使获取的利润最大。2424广东工业大学管理学院广东工业大学管理学院例2 捷运公司租借仓库的问题捷运公司在下一年度的捷运公司在下一年度的1-41-4月的月的4 4个月内拟租用仓库堆放物个月内拟租用仓库堆放物资。已知各月份所需仓库面积如下表所示。仓库租借费资。已知各月份所需仓库面积如下表所示。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表。用随合同期而定，期限越长，折扣越大，具体数字见表。租借仓库的合同每月初都可办理，每份合同具体规定租租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租期不同的合同。试确定该公司签订租干份租用面积和租期不同的合同。试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。借合同的最优决策，目的是使所付租借费用最小。2525广东工业大学管理学院广东工业大学管理学院月份月份1 12 23 34 4所需仓库面积所需仓库面积(100m(100m2 2)1515101020201212合同租借期限合同租借期限1 1个月个月 2 2个月个月 3 3个月个月4 4个月个月合同期内的租合同期内的租费费(元元/100m/100m2 2)280028004500450060006000730073002626广东工业大学管理学院广东工业大学管理学院例1、例2的共同点 在现有各项资源条件的限制或约束下，如何确定方案，使预期目标达到最优。例1的资源限制：设备A、B与调试工序每天可用时数。目标：总利润最大例2的资源约束：租期内每月所需的仓库面积数。目标：总租金最小2727广东工业大学管理学院广东工业大学管理学院线性规划研究的问题大体上可归为两类：1、给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务；2、对于给定的任务，如何运筹规划，合理安排，以最少资源来完成它。2828广东工业大学管理学院广东工业大学管理学院n n线性规划要研究的两类问题中都包含有限制或约束条线性规划要研究的两类问题中都包含有限制或约束条件：第一类问题的约束条件是件：第一类问题的约束条件是“给出一定量的人力、给出一定量的人力、物力和财务等资源物力和财务等资源”；第二类问题是；第二类问题是“给定的任务给定的任务”。在线性规划中，我们常要求这种约束条件可以用一组在线性规划中，我们常要求这种约束条件可以用一组线性方程或线性不等式来描述。在约束满足的条件下，线性方程或线性不等式来描述。在约束满足的条件下，所要达到的结果称所要达到的结果称“目标目标”，第一类问题的目标是利，第一类问题的目标是利用有限资源完成最大任务，第二类问题的目标是要用用有限资源完成最大任务，第二类问题的目标是要用最少资源完成给定任务。在线性规划中，要求可以用最少资源完成给定任务。在线性规划中，要求可以用一个线性函数来描述这种目标，并称这个线性函数为一个线性函数来描述这种目标，并称这个线性函数为目标函数目标函数目标函数目标函数。n n线性规划研究的各种实际问题尽管约束条件与目标不线性规划研究的各种实际问题尽管约束条件与目标不相同，但规划的目的就是使这些资源发挥最大限度的相同，但规划的目的就是使这些资源发挥最大限度的作用，从而完成最多最大的任务。换句话说，也就是作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用数学的方式描述，规划的目资源的最优利用问题。用数学的方式描述，规划的目的就是在给定的限制条件（或称的就是在给定的限制条件（或称约束条件约束条件约束条件约束条件）下，求目）下，求目标函数的极值问题（包括极小值和极大值）。标函数的极值问题（包括极小值和极大值）。2929广东工业大学管理学院广东工业大学管理学院模型数学规划问题3030广东工业大学管理学院广东工业大学管理学院例1的数学模型3131广东工业大学管理学院广东工业大学管理学院3232广东工业大学管理学院广东工业大学管理学院例2的数学模型3333广东工业大学管理学院广东工业大学管理学院例例1 穗羊公司要加工两种产品I、II，需要使用两种原材料及某专用生产设备等三种资源，分别记为A、B、C。生产这两种产品的单位资源消耗、这些资源的每周可使用量及每单位产品可获利润见下表：I III II每周可使用量每周可使用量A A（千克）（千克）1 12 25 5B B（吨）（吨）2 21 14 4C C（百工（百工时时）4 43 39 9单单位位产产品利品利润润（万元）（万元）3 32 2问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？3434广东工业大学管理学院广东工业大学管理学院根据问题所给数据，当产品I、II每周的产量分别是x1和x2时，总利润为因此我们的目标就是 再考虑资源的限制:因此关于A原材料，我们有约束条件：关于B原材料，有约束条件：关于设备，有约束条件：此外产品I和II每周的产量不可能是负数，因此关于这两个变量，还有约束：3535广东工业大学管理学院广东工业大学管理学院将上述数学表达式合起来，就得到这个问题的数学模型为：其中s.t.是英文词组subject to的缩写，表示“受限制于”的意思，有时也约去不写出来。例1中的问题常称为生产计划问题生产计划问题或产品组合产品组合（product mix）问题。3636广东工业大学管理学院广东工业大学管理学院例例2 设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料。因为，10米长的钢筋截为3米或4米长，共有三种截法：截法：3 3 3 1 米截法：3 3 4 0 米截法：4 4 0 2 米假设按截法，各截取10米长的钢筋分别为x1,x2,x3根 则可以获得3米长的短钢筋的根数是 4米长短钢筋的根数是 按问题要求它们应该不小于100根。总共用料是 要达到最省料的目的，就必须使总用料最小。3737广东工业大学管理学院广东工业大学管理学院例2的模型就是例2 中的问题常称为下料问题下料问题。3838广东工业大学管理学院广东工业大学管理学院模型的特征n n模型的三个要素（1）决策变量（2）目标函数（3）约束条件n n线性规划模型的特征（1）目标函数是决策变量的线性函数（2）约束条件是含决策变量的线性等式或不等式3939广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式4040广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式（续1）n n决策变量：n n价值系数：n n资源常数：n n技术（工艺）系数：4141广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式（续2）利用和号简化模型的表示4242广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式（续3）向量形式：向量形式：式中4343广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式（续4）矩阵形式：其中4444广东工业大学管理学院广东工业大学管理学院线性规划模型的一般形式（续5）注：决策变量通常是非负的，但从数学意义上决策变量可以取非正的值，或取任何实数。4545广东工业大学管理学院广东工业大学管理学院线性规划问题的（模型）的标准形式4646广东工业大学管理学院广东工业大学管理学院标准形式的特征n n目标函数为求最大值目标函数为求最大值n n约束条件均为等式约束条件均为等式n n资源常数非负资源常数非负n n决策变量只能取非负值决策变量只能取非负值不具备上述所有特征的线性规划问题称为不具备上述所有特征的线性规划问题称为非标准形式的线性规划问题非标准形式的线性规划问题4747广东工业大学管理学院广东工业大学管理学院化线性规划问题为标准形式的方法（1）目标函数为求最小值的，即）目标函数为求最小值的，即将目标函数用其相反数代替，得到新的目将目标函数用其相反数代替，得到新的目标函数标函数，即令，即令则则求原目标函数的最小值问题等价于求新求原目标函数的最小值问题等价于求新目标函数的最大值问题目标函数的最大值问题4848广东工业大学管理学院广东工业大学管理学院化线性规划问题为标准形式的方法（续1）（2）右端常数小于零，即）右端常数小于零，即 将将该约束条件两端同乘（该约束条件两端同乘（-1）（3）约束条件为不等式）约束条件为不等式“”型，左端加上一个非负的松弛变量型，左端加上一个非负的松弛变量“”型，左端减去一个非负的剩余变量型，左端减去一个非负的剩余变量松弛变量和剩余变量在目标函数中的系数松弛变量和剩余变量在目标函数中的系数为零为零4949广东工业大学管理学院广东工业大学管理学院化线性规划问题为标准形式的方法（续2）（4）取值无约束的变量。）取值无约束的变量。用两个非负变用两个非负变量的差表示该变量。量的差表示该变量。（5）取非正值的变量。）取非正值的变量。用其相反数代替用其相反数代替该变量该变量P15 例例35050广东工业大学管理学院广东工业大学管理学院线性规划问题线性规划问题要处理的内容要处理的内容x1,x3右端常数右端常数不等式不等式不等式不等式最小化目标最小化目标处处理理后后5151广东工业大学管理学院广东工业大学管理学院第二节 图解法有关概念有关概念n n满足所有约束条件的一组决策变量满足所有约束条件的一组决策变量x1,x2,xn称为称为LP问题的问题的可行解可行解n n所有可行解的集合称为所有可行解的集合称为可行域可行域n n使得目标函数值达到最大的可行解称为使得目标函数值达到最大的可行解称为LP问题的问题的最优解最优解（对最大化问题而言）（对最大化问题而言）n n求解求解LP问题问题就是求出其最优解就是求出其最优解5252广东工业大学管理学院广东工业大学管理学院 图解法及其目的n n图解法即通过平面作图的方法求解线性规图解法即通过平面作图的方法求解线性规划，适用于只含两个决策变量的简单划，适用于只含两个决策变量的简单LP问问题。题。n n图解法的目的有二，一是利用它来说明图解法的目的有二，一是利用它来说明LP问题求解的可能结局。二是在问题求解的可能结局。二是在LP问题最优问题最优解存在时，求出最优解。解存在时，求出最优解。采用图解法时通常无须将采用图解法时通常无须将采用图解法时通常无须将采用图解法时通常无须将LPLPLPLP问题化为标准形式问题化为标准形式问题化为标准形式问题化为标准形式5353广东工业大学管理学院广东工业大学管理学院图解法步骤：在平面上建立直角坐标系在平面上建立直角坐标系图示约束条件，找出可行域图示约束条件，找出可行域图示目标函数图示目标函数寻找最优解寻找最优解5454广东工业大学管理学院广东工业大学管理学院例1Max z=2x1+x2s.t.5x215 6x1+2x2 24 x1+x2 5 x1,x20 x2=33x1+x2=12x1+x2=5最优解可行域x1x25555广东工业大学管理学院广东工业大学管理学院线性规划问题几种可能的结局1.1.有有唯一的最优解唯一的最优解2.2.有无穷多个最优解有无穷多个最优解3.3.无界解无界解4.无解（无可行解）无解（无可行解）5656广东工业大学管理学院广东工业大学管理学院由图解法得到的启示1.1.揭示了求揭示了求LP问题的解的可能情况问题的解的可能情况2.2.若可行域非空，则必为凸集若可行域非空，则必为凸集3.3.若若LP问题的最优解存在，则最优解或问题的最优解存在，则最优解或最优解之一是可行域的顶点最优解之一是可行域的顶点4.4.LP问题的求解思路（单纯形法）问题的求解思路（单纯形法）先找出可行域的任一顶点，计算该顶点处的目标先找出可行域的任一顶点，计算该顶点处的目标先找出可行域的任一顶点，计算该顶点处的目标先找出可行域的任一顶点，计算该顶点处的目标函数值；比较周围相邻顶点的目标函数值是否比函数值；比较周围相邻顶点的目标函数值是否比函数值；比较周围相邻顶点的目标函数值是否比函数值；比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点为最优解（或最这个值大，如果为否，则该顶点为最优解（或最这个值大，如果为否，则该顶点为最优解（或最这个值大，如果为否，则该顶点为最优解（或最优解之一）对应的点，否则转到比这个点目标函优解之一）对应的点，否则转到比这个点目标函优解之一）对应的点，否则转到比这个点目标函优解之一）对应的点，否则转到比这个点目标函数值更大的顶点，重复上述过程，直到找出目标数值更大的顶点，重复上述过程，直到找出目标数值更大的顶点，重复上述过程，直到找出目标数值更大的顶点，重复上述过程，直到找出目标函数值最大的顶点为止。函数值最大的顶点为止。函数值最大的顶点为止。函数值最大的顶点为止。5757广东工业大学管理学院广东工业大学管理学院第三节 单纯形法原理n n线性规划解的基本概念线性规划解的基本概念考虑考虑标准形式的线性规划问题标准形式的线性规划问题可行解可行解满足所有约束条件的解满足所有约束条件的解X=(x1,x2,xn)T,称为称为LP问题的可行解。问题的可行解。所有可行解的集合称为可行域。所有可行解的集合称为可行域。最优解最优解使得目标函数达到最大值的使得目标函数达到最大值的可行解称为最优解。可行解称为最优解。LP问题的可行域是一个凸集。问题的可行域是一个凸集。5858广东工业大学管理学院广东工业大学管理学院基基设设A为约束方程组的为约束方程组的m n阶阶系数矩系数矩阵阵（通常总假定（通常总假定nm，且，且A的秩的秩=m），若），若B是是A的一个的一个m m阶的阶的满秩子矩阵满秩子矩阵，则称，则称B是是LP问题的一个问题的一个基基。若。若B是是LP问题的一个问题的一个基，则它的每一个列向量称为基，则它的每一个列向量称为基向量基向量，与，与基向量对应的变量称为基向量对应的变量称为基变量基变量LPLP问题的基本概念（续问题的基本概念（续1 1）5959广东工业大学管理学院广东工业大学管理学院秩的概念秩的概念如果矩阵A中有一个r阶子式Dr不等于零，而所有r+1阶子式（如果存在的话）的值全等于零，则称Dr为矩阵A的一个最高阶非零子式，其阶数r称为矩阵A的秩。注：Dr为行列式r的值。6060广东工业大学管理学院广东工业大学管理学院LPLP问题的基本概念（续问题的基本概念（续2 2）基解基解在约束方程组在约束方程组 中令中令所有的非基变量所有的非基变量xm+1=xm+2=xn=0,则由于剩则由于剩下的变量（基变量）构成的方程组的系数行下的变量（基变量）构成的方程组的系数行列式列式|B|0，因此约束方程组此时有唯一的解，因此约束方程组此时有唯一的解XB=（x1,x2,xm,0,0)T这个解称为这个解称为LP问题的（对应基问题的（对应基B的）的）基解基解。很明显，对应着不同的基，很明显，对应着不同的基，LP问题有不同问题有不同的基解。因此的基解。因此LP问题的基解不是唯一的，问题的基解不是唯一的，但总数不超过但总数不超过 此外基解不一定是可行此外基解不一定是可行解解。6161广东工业大学管理学院广东工业大学管理学院LPLP问题的基本概念（续问题的基本概念（续3 3）基可行解基可行解满足非负约束条件的基解称为满足非负约束条件的基解称为基可行解基可行解可行基可行基对应着基可行解的基称为对应着基可行解的基称为可行基可行基很明显很明显LPLP问题的基可行解是有限的。并且每问题的基可行解是有限的。并且每一个基可行解对应着可行域的一个顶点。一个基可行解对应着可行域的一个顶点。6262广东工业大学管理学院广东工业大学管理学院找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。6363广东工业大学管理学院广东工业大学管理学院序号序号x x1 1x x2 2x x3 3x x4 4x x5 5z z是否基可行解是否基可行解1 10 00 05 510104 45 5是是2 20 04 45 52 20 01717是是3 35 50 00 05 54 41010是是4 40 05 55 50 0-1-12020否否5 510100 0-5-50 04 41515否否6 65 52.52.50 00 01.51.517.517.5是是7 75 54 40 0-3-30 02222否否8 82 24 43 30 00 01919*是是6464广东工业大学管理学院广东工业大学管理学院凸集及其顶点凸集及其顶点凸集凸集如果一个非空集合中任意两点的连线段如果一个非空集合中任意两点的连线段上所有点仍属于该集合，则称该集合为上所有点仍属于该集合，则称该集合为凸集凸集。凸集的顶点凸集的顶点若凸集中的一个点不是任何另外若凸集中的一个点不是任何另外两点连线段上的点，则称该点为这个凸集的两点连线段上的点，则称该点为这个凸集的顶点顶点。凸集凸集凸集凸集不是凸集不是凸集顶点顶点6565广东工业大学管理学院广东工业大学管理学院几个基本定理几个基本定理定理定理1 若若LP问题存在可行解，则问题的可问题存在可行解，则问题的可行域为凸集行域为凸集定理定理2 LP问题的基可行解对应着问题的基可行解对应着LP问题可问题可行域的顶点行域的顶点定理定理3 若若LP问题有最优解，一定存在一问题有最优解，一定存在一个基可行解是最优解个基可行解是最优解6666广东工业大学管理学院广东工业大学管理学院单纯形法迭代原理单纯形法迭代原理单纯形法迭代步骤：单纯形法迭代步骤：找出一个找出一个基可行解基可行解是否为最优解是否为最优解停止停止（依据：（依据：LP问题的最优解若问题的最优解若存在，则一定有一个基可行存在，则一定有一个基可行解为最优解。）解为最优解。）转换到相邻的基可行解，转换到相邻的基可行解，并使目标函数增大并使目标函数增大开始开始Y YN N6767广东工业大学管理学院广东工业大学管理学院1.1.求初始基可行解求初始基可行解基可行解基可行解求基解求基解求解线性求解线性方程组方程组求基求基求基求基B B或或或或基变量基变量基变量基变量6868广东工业大学管理学院广东工业大学管理学院求基可行解需要考虑的问题求基可行解需要考虑的问题n n是否便于计算目标函数值是否便于计算目标函数值n n是否便于判断其目标函数值是否为最大是否便于判断其目标函数值是否为最大n n是否便于转换到目标函数值更大的相邻基是否便于转换到目标函数值更大的相邻基可行解可行解6969广东工业大学管理学院广东工业大学管理学院初始基可行解通常都是从一种特殊的基可行解出发求解通常都是从一种特殊的基可行解出发求解LP问题，这一特殊的基可行解称为问题，这一特殊的基可行解称为初始基可行初始基可行解解。初始基可行解对应的基，也称。初始基可行解对应的基，也称初始可行初始可行基基，它具有特定的形式，它是，它具有特定的形式，它是单位矩阵或者单位矩阵或者由单位矩阵经过交换列以后得到的矩阵由单位矩阵经过交换列以后得到的矩阵。相。相应的基变量称为应的基变量称为初始基变量初始基变量，它是一组变量，它是一组变量，具有特点：具有特点：共有共有m m个变量，恰好每个约束方程个变量，恰好每个约束方程包含一个变量，且该变量的系数为包含一个变量，且该变量的系数为1 1。7070广东工业大学管理学院广东工业大学管理学院已知初始基变量，求初始基可行解以例以例1为例说明求法。添加松弛变量后例为例说明求法。添加松弛变量后例1可标准化为可标准化为其中其中x3,x4,x5为初始基变量，初始基可行解为为初始基变量，初始基可行解为7171广东工业大学管理学院广东工业大学管理学院2.判别最优性判别最优性不难发现这时每个初始不难发现这时每个初始基变量取的值恰好就基变量取的值恰好就是包含这个变量的约束方程的右端常数值，是包含这个变量的约束方程的右端常数值，非基变量取的值为零非基变量取的值为零。将这个解代入到目标。将这个解代入到目标函数，就可得到这个解对应的目标函数值。函数，就可得到这个解对应的目标函数值。目标函数目前的值为零，很明显如果能使的目标函数目前的值为零，很明显如果能使的变量变量x1或或x2取正值的话，目标函数的值还可以取正值的话，目标函数的值还可以增加。所以目标函数还未达到其最大值。增加。所以目标函数还未达到其最大值。一般地，一般地，若目标函数已经表示成了非基变量若目标函数已经表示成了非基变量的函数，且其中非基变量的系数中还有正数，的函数，且其中非基变量的系数中还有正数，则目标函数还可能增大则目标函数还可能增大。这时目标函数中各。这时目标函数中各变量的系数称为变量的系数称为检验数检验数。这时目标函数的表达式为这时目标函数的表达式为7272广东工业大学管理学院广东工业大学管理学院3.旋转若基可行解不是最优解，则需要转到一个相邻若基可行解不是最优解，则需要转到一个相邻的基可行解，并使得目标函数值增加。的基可行解，并使得目标函数值增加。所谓所谓相邻相邻的基可行解是指两个基可行解只有一的基可行解是指两个基可行解只有一个基变量不同而其它的基变量都相同。个基变量不同而其它的基变量都相同。要从一个基可行解转到与它相邻的基可行解，要从一个基可行解转到与它相邻的基可行解，意味着需要将一个非基变量变成基变量，而且意味着需要将一个非基变量变成基变量，而且将一个原来的基变量变为非基变量，前者称为将一个原来的基变量变为非基变量，前者称为换入变量换入变量，后者称为，后者称为换出变量换出变量。7373广东工业大学管理学院广东工业大学管理学院确定换入变量目的：目的：新的基变量换入后，会使目标函数新的基变量换入后，会使目标函数值增大（通常还希望增加的越大越好）值增大（通常还希望增加的越大越好）因此选择在目标函数中系数为正值的非基因此选择在目标函数中系数为正值的非基变量作为换入变量，通常取在目标函数中变量作为换入变量，通常取在目标函数中最大的正系数对应的非基变量为换入变量，最大的正系数对应的非基变量为换入变量，即即取最大的正检验数对应的非基变量为换取最大的正检验数对应的非基变量为换入变量入变量。换入变量为换入变量为 x1对例对例1，这时目标函数为，这时目标函数为7474广东工业大学管理学院广东工业大学管理学院确定换出变量由于基变量只有由于基变量只有m个，因此将一个非基变量变个，因此将一个非基变量变为基变量后，必须将一个原来的基变量变为非为基变量后，必须将一个原来的基变量变为非基变量，这个变量就是所谓的基变量，这个变量就是所谓的换出变量换出变量。换出变量与换出变量与换入变量换入变量是密切相关的。设是密切相关的。设xk是换是换入变量。若入变量。若xk0，则第，则第i个约束条件可以写成个约束条件可以写成并且由于其余的非基变量保持零值，因此并且由于其余的非基变量保持零值，因此7575广东工业大学管理学院广东工业大学管理学院由此可见为保证由此可见为保证xi0，就必须，就必须 从而对所有的从而对所有的i，若，若aik0，则，则7676广东工业大学管理学院广东工业大学管理学院若确定若确定xk为换入变量，则可估计为换入变量，则可估计xk的取值，使的取值，使得：得：其余的决策变量都取非负值；并且目标其余的决策变量都取非负值；并且目标函数得到尽可能的增加函数得到尽可能的增加。对前者，只须。对前者，只须 对所有的对所有的i成立，即成立，即为了使目标函数尽可能增加，显然应该有为了使目标函数尽可能增加，显然应该有设设i=l(1 l n)时，上式右端达到最小值。由时，上式右端达到最小值。由于于因此因此xl=0。7777广东工业大学管理学院广东工业大学管理学院这意味着这意味着xl可以是非基变量。因此取可以是非基变量。因此取xl为换出为换出变量。也就是取变量。也就是取使得使得成立的成立的