第二章线性规划的标准型与单纯形法.ppt

第二章线性规划的标准型与单纯形法现在学习的是第1页，共122页|运筹学的概况运筹学的概况|最优化模型|教学计划与方法|考试与要求|参考文献 绪 论现在学习的是第2页，共122页运筹学的由来与发展运筹学的性质与特点 运筹学的主要内容运筹学的发展趋势运筹学的学科地位运 筹 学 概 况现在学习的是第3页，共122页名称的由来名称的由来OperationResearch运筹帷幄运筹帷幄“史记史记”运作研究运作研究发展历程发展历程运筹学的由来与发展二战以前萌萌芽芽二战期间产产生生五六十年代发发展展七八十年代成成熟熟现在学习的是第4页，共122页引入数学方法解决实际问题引入数学方法解决实际问题-定性与定量方法结合定性与定量方法结合系统与整体性系统与整体性-从全局考察问题从全局考察问题应用性应用性-源于实践、为了实践、服务于实践源于实践、为了实践、服务于实践交叉学科交叉学科-涉及经济、管理、数学、工程和系统等涉及经济、管理、数学、工程和系统等多学科多学科开放性开放性-不断产生新的问题和学科分支不断产生新的问题和学科分支多分支多分支-问题的复杂和多样性问题的复杂和多样性运筹学的性质与特点现在学习的是第5页，共122页线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析运筹学的主要内容现在学习的是第6页，共122页成熟的学科分支向纵深发展成熟的学科分支向纵深发展新的研究领域产生新的研究领域产生与新的技术结合与新的技术结合与其他学科的结合加强与其他学科的结合加强传统优化观念不断变化传统优化观念不断变化运筹学的发展趋势现在学习的是第7页，共122页1在数学学科中的地位在数学学科中的地位运筹数学1在系统科学中的地位在系统科学中的地位系统工程1在管理科学中的地位在管理科学中的地位管理与运筹学1与经济学的关系与经济学的关系问题与方法1与工程科学的关系与工程科学的关系方法与应用1 与计算机科学的关系与计算机科学的关系核心算法与工具基础理论基础理论应用理论应用理论应用技术应用技术运筹学运筹学运筹学的学科地位现在学习的是第8页，共122页教学计划教学计划数学规划以线性规划和整数规划数学规划以线性规划和整数规划及动态规划及动态规划为为讲讲授重点，组合授重点，组合优化部分主要讲优化部分主要讲图与图与网络优化，而随机优化讲授排队论部分作为选网络优化，而随机优化讲授排队论部分作为选讲内容。讲内容。教学方法教学方法以授课为主，讲课中主要培养用最优化方法解决实际问题的能力。以授课为主，讲课中主要培养用最优化方法解决实际问题的能力。教学计划与方法现在学习的是第9页，共122页考核内容考核内容及方式及方式理论方法理论方法期末考期末考试试 6 60%0%理论方法理论方法期中考期中考试试 2 20%0%平时成绩平时成绩 20%20%考试与要求现在学习的是第10页，共122页韩伯棠，管理运筹学，高等教育出版社，北京，2000年徐光辉等，运筹学手册，科学出版社，北京，1999年胡运权等，运筹学教程，清华出版社，北京，1998年刘家壮，王建方，网络最优化，华中工学院出版社，武汉，1987年管梅谷，郑汉鼎，线性规划，山东科学技术出版社，济南，1983年参 考 资 料现在学习的是第11页，共122页运筹学运筹学Operations ResearchChapter 2 线性规划线性规划Linear Programming2.1 LP的数学模型的数学模型 Mathematical Model of LP2.2 图解法图解法 Graphical Method2.3 标准型标准型 Standard form of LP2.4 基本概念基本概念 Basic Concepts2.5 单纯形法单纯形法 Simplex Method现在学习的是第12页，共122页2.1 数学模型数学模型 Mathematical Model 现在学习的是第13页，共122页n 问题的提出问题的提出：在在生生产产管管理理的的经经营营活活动动中中，通通常常需需要要对对“有有限限的的资资源源”寻寻求求“最最佳佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题：有限资源的合理配置有两类问题：l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。所消耗的资源数最少。现在学习的是第14页，共122页 与规划问题有关的数学模型总有两部分组成与规划问题有关的数学模型总有两部分组成：l l约束条件：约束条件：约束条件：约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；l l目标函数目标函数目标函数目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。反映生产经营者在有限资源条件下希望达到的生产或经营的目标。现在学习的是第15页，共122页例例 某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万元。但根据市场万元。但根据市场需求调查的结果，甲药品每周的产量不应超过需求调查的结果，甲药品每周的产量不应超过4 4吨。问该厂应如何安排两种吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？药品的产量才能使每周获得的利润最大？现在学习的是第16页，共122页 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标：使总利润使总利润 Z=5xZ=5x1 1+2x+2x2 2 极大化极大化 约束：约束：每周资源总量的限制，每周资源总量的限制，30 x30 x1 1+20 x+20 x2 2160160 5x5x1 1+x+x2 2 1515甲种药品每周产量不应超过甲种药品每周产量不应超过4 4吨的限制吨的限制 x x1 144计划生产数不可能是负数，计划生产数不可能是负数，x x1 10 x0 x2 200每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 5现在学习的是第17页，共122页 数学模型为数学模型为 s.t.s.t.（subject to)subject to)(such that)(such that)这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。学规划问题。在满足一组约束条件的限制下，寻求决策变量在满足一组约束条件的限制下，寻求决策变量x x1 1，x x2 2的决策值，使目标函数的决策值，使目标函数达到最大值。达到最大值。每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 5现在学习的是第18页，共122页例例 某某化化工工厂厂根根据据一一项项合合同同要要求求为为用用户户生生产产一一种种用用甲甲、乙乙两两种种原原料料混混合合配配制制而而成成的的特特种种产产品品。已已知知甲甲、乙乙两两种种原原料料都都含含有有A A、B B、C C三三种种化化学学成成分分，两两种种原原料料分分别别所所含含三三种种化化学学成成分分的的百百分分比比含含量量，以以及及按按合合同同规规定定的的产产品品中中三三种种化化学成分的最低含量如下表所示：学成分的最低含量如下表所示：已已知知甲甲、乙乙两两种种原原料料的的成成本本分分别别是是每每公公斤斤3 3元元和和2 2元元，厂厂方方希希望望总总成成本达到最小，问如何配置该产品？本达到最小，问如何配置该产品？原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分现在学习的是第19页，共122页定义定义x x1 1，x x2 2分别为每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本目标：使总成本 Z=3xZ=3x1 1+2x+2x2 2 极小化极小化 约束：配料平衡条件，约束：配料平衡条件，x x1 1+x+x2 2=1=1产品中产品中A A、B B、C C三种化学成分的最低含量三种化学成分的最低含量 12x12x1 1+3x+3x2 244 2x2x1 1+3x+3x2 222 3x3x1 1+15x+15x2 255非负性条件非负性条件 x x1 10,x0,x2 200原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分现在学习的是第20页，共122页 数学模型：数学模型：s.t.s.t.这是一个原料配制问题，是在生产任务确定的条件下，合理的组织这是一个原料配制问题，是在生产任务确定的条件下，合理的组织 生产，使所消耗的资源数最少的数学规划问题。生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1和和x x2 2的值使目标函数取得最小的值使目标函数取得最小 值。值。原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量（产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分现在学习的是第21页，共122页1 1解决问题的目标函数是多个决策变量的线性函数，通常是解决问题的目标函数是多个决策变量的线性函数，通常是 求最大值或最小值求最大值或最小值；2 2解决问题的解决问题的约束条件约束条件约束条件约束条件是一组多个决策变量的线性不等式或等式是一组多个决策变量的线性不等式或等式。线性规划数学模型的线性规划数学模型的特征：特征：线性规划数学模型的线性规划数学模型的三要素：三要素：决策变量决策变量(Decision variables);目标函数目标函数(Objective function);约束条件约束条件(Constraints);建立一个问题的线性规划模型的建立一个问题的线性规划模型的一般步骤：一般步骤：(1)(1)确定决策变量；确定决策变量；(2)(2)确定目标函数；确定目标函数；(3)(3)确定约束条件；确定约束条件；(4)(4)确定变量是否有非负约束。确定变量是否有非负约束。2.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP现在学习的是第22页，共122页2.1.2 线性规划的一般模型线性规划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中,有有m个个约约束束,有有n个个决决策策变变量量xj(j=1,2,n)，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束束条条件件右右端端的的常常数数用用bi 表示表示，bi 称为称为资源限量资源限量。则线性规划数学模型的一般表达式可写成则线性规划数学模型的一般表达式可写成2.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP现在学习的是第23页，共122页在实际中一般在实际中一般xj0,但有时但有时 xj0或或 xj 无符号限制。无符号限制。为了书写方便，上式也可写成：为了书写方便，上式也可写成：2.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP现在学习的是第24页，共122页2.2 图解法图解法 Graphical Method现在学习的是第25页，共122页图解法的步骤：图解法的步骤：1.在直角坐标系中画出可行解集：在直角坐标系中画出可行解集：分别画出满足每个约束包括变量分别画出满足每个约束包括变量非负要求的区域，其交集就是可行解集，或称非负要求的区域，其交集就是可行解集，或称可行域；可行域；2.绘制目标函数图形：绘制目标函数图形：先过原点作一条矢量指向点先过原点作一条矢量指向点(c c1,c c2 )，矢量的方向，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；这条直线就是目标函数图形；3.求最优解：求最优解：依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，先将目标函数直线放在可行域中：一般地，先将目标函数直线放在可行域中：若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最小值，则将目标函数直线沿着矢量的反方向移动。若要求最小值，则将目标函数直线沿着矢量的反方向移动。2.2 图解法图解法The Graphical Method现在学习的是第26页，共122页x1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85例例1.42.2 图解法图解法The Graphical Method现在学习的是第27页，共122页246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例2.5 (1,2)2.2 图解法图解法The Graphical Method现在学习的是第28页，共122页246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例2.6有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)2.2 图解法图解法The Graphical Method现在学习的是第29页，共122页246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.72.2 图解法图解法The Graphical Method现在学习的是第30页，共122页x1x2O10203040102030405050无可行解，从无可行解，从而无最优解。而无最优解。max Z=10 x1+x2例例2.82.2 图解法图解法The Graphical Method现在学习的是第31页，共122页由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有惟一最优解有惟一最优解(例例1.4、例、例1.5)2.有多重解有多重解(例例1.6)3.有无界解有无界解(例例1.7)4.无可行解无可行解(例例1.8)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解2.2 图解法图解法The Graphical Method现在学习的是第32页，共122页4.通过图解法了解线性规划有几种解的形式；通过图解法了解线性规划有几种解的形式；5.作图的关键有三点：作图的关键有三点：(1)可行解区域要画正确；可行解区域要画正确；(2)目标函数增加的方向不能画错；目标函数增加的方向不能画错；(3)目标函数的直线怎样平行移动。目标函数的直线怎样平行移动。下一节：线性规划的标准型下一节：线性规划的标准型2.2 图解法图解法The Graphical Method1.什么是线性规划，掌握线性规划在管理中的几个应用例子；什么是线性规划，掌握线性规划在管理中的几个应用例子；2.线性规划数学模型的组成及其特征；线性规划数学模型的组成及其特征；3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。现在学习的是第33页，共122页2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第34页，共122页 在用单纯法求解线性规划问题时，为了讨论问题方在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。便，需将线性规划模型化为统一的标准形式。2.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负现在学习的是第35页，共122页max(或min)Z=c1x1+c2x2+cnxn2.3 线性规划的标准型线性规划的标准型Standard form of LP注：本教材默认标准型中目标函数是注：本教材默认标准型中目标函数是 max现在学习的是第36页，共122页或写成下列形式或写成下列形式：或用矩阵形式或用矩阵形式2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第37页，共122页通常通常X记为：记为：,称称为约束方程为约束方程的系数矩阵，的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，一般是决策变量的个数，一般情况情况mn，且，且r()m。其中其中:2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第38页，共122页一般形式线性规划模型的标准化准则一般形式线性规划模型的标准化准则:（前提（前提 b bi 0）5.xj0令令xj=xj ,xj 0 现在学习的是第39页，共122页【例例1】将下列线性规划化为标准型将下列线性规划化为标准型【分析分析】()因为因为x3无符号要求无符号要求，即，即x3 可取正值也可取负可取正值也可取负值，标准型中要求变量非负，所以令值，标准型中要求变量非负，所以令 2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第40页，共122页(3)第二个约束条件是第二个约束条件是“”号，在号，在“”号左端减去剩余号左端减去剩余变量变量(surplus variable)x5，x50，也称松驰变量；，也称松驰变量；2.3 线性规划的标准型线性规划的标准型Standard form of LP(2)第一个约束条件是第一个约束条件是“”号，号，在在“”号左端加入松驰变量号左端加入松驰变量(slack variable)x4，x40,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是“”号且常数项为负数，因此在号且常数项为负数，因此在“”左左边加入松驰变量边加入松驰变量x6，x60，同时两边乘以，同时两边乘以1。(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令Z=Z,得到得到 max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值。达到最大值。现在学习的是第41页，共122页综合起来得到下列标准型综合起来得到下列标准型 2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第42页，共122页当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束再化为等式，例如约束 将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。2.3 线性规划的标准型线性规划的标准型Standard form of LP现在学习的是第43页，共122页2.4 线性规划的有关概念线性规划的有关概念Basic Concepts of LP现在学习的是第44页，共122页 设线性规划的标准型设线性规划的标准型 max Z=CX (2.1)AX=b (2.2)X 0 (2.3)式式中中A 是是mn矩矩阵阵，mn并并且且r(A)=m，显显然然A中中至至少少有有一一个个mm子矩阵子矩阵B，使得，使得r(B)=m。2.4 基本概念基本概念Basic Concepts 基基 (basis)：A中中 mm子矩阵子矩阵 B 并且有并且有r(B)=m，则称，则称B是线性是线性规划的一个规划的一个基基(或或基矩阵基矩阵basis matrix)。注：注：基矩阵基矩阵B必为非奇异矩阵即必为非奇异矩阵即|B|0。当当m=n时，基矩阵惟一，当时，基矩阵惟一，当mn时，基矩阵就可能有多个，但数时，基矩阵就可能有多个，但数目不超过目不超过现在学习的是第45页，共122页【例例2】线性规划线性规划 求所有基矩阵求所有基矩阵。【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 2.4 基本概念基本概念Basic Concepts 现在学习的是第46页，共122页容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵有有C52=10个，其中第个，其中第1列与第列与第3列列构成的构成的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即现在学习的是第47页，共122页当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为为基向量基向量(basic vector)，其余列向量称为，其余列向量称为非基向量非基向量;基向量对应的变量称为基向量对应的变量称为基变量基变量(basic variable)，非基向量对应的变量称为非基向量对应的变量称为非基变量非基变量；在在上上例例中中B2的的基基向向量量是是A中中的的第第一一列列和和第第四四列列，其其余余列列向向量量是是非非基基向向量量，x1、x4是是基基变变量量，x2、x3、x5是是非非基基变变量量。基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不不同同的的基基对对应的基变量和非基变量也不同。应的基变量和非基变量也不同。2.4 基本概念基本概念Basic Concepts 现在学习的是第48页，共122页 可行解可行解(feasible solution):满足式满足式(2.2)及及(2.3)的解的解X=（x1,x2,xn)T 称为可行解；称为可行解；基本可行解基本可行解(basic feasible solution):若基本解是可行解若基本解是可行解 则称为是基本可行解（也称基可行解）。则称为是基本可行解（也称基可行解）。基本解基本解(basic solution):对某一确定的基对某一确定的基B，令，令非基变量非基变量 等于零等于零，利用式，利用式(2.2)解出基变量，则这组解称为基解出基变量，则这组解称为基 的的基本解。基本解。最优解最优解(optimal solution):满足式满足式(1.1)的可行解称为最优的可行解称为最优 解，即使得目标函数达到解，即使得目标函数达到最大值最大值的的可行解可行解就是最优解；就是最优解；非可行解非可行解(infeasible solution)无界解无界解(unbounded solution)2.4 基本概念基本概念Basic Concepts 现在学习的是第49页，共122页显然，只要基本解中的基变量的解满足式显然，只要基本解中的基变量的解满足式(2.3)的非负要求，的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在在上上例例中中，对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变变量，令量，令x3=x4=x5=0，则式，则式(2.2)为为 因因|B1|，由克莱姆法，由克莱姆法则则知，知，x1、x2有有惟一惟一解解x12/5,x2=1,从而基本解为从而基本解为2.4 基本概念基本概念Basic Concepts 现在学习的是第50页，共122页对对B2来来说说，x1,x4,为为基基变变量量，令令非非变变量量x2,x3,x5为为零零，由由式式(2.2)得得 ，x4=4，则基本解为，则基本解为反之，反之，可行解不一定是基本可行解可行解不一定是基本可行解，如，如满足式满足式(2.2)(2.3)，但不是任何基矩阵的基本解。，但不是任何基矩阵的基本解。在在 中中x10,不是可行解，因此也不是基本可行解。不是可行解，因此也不是基本可行解。现在学习的是第51页，共122页可行基可行基:基可行解对应的基称为可行基；基可行解对应的基称为可行基；最优基最优基:基本最优解对应的基称为最优基；基本最优解对应的基称为最优基；如上述如上述B3就是最优基，最优基肯定是可行基。就是最优基，最优基肯定是可行基。2.4 基本概念基本概念Basic Concepts 基本最优解基本最优解:最优解是基本解称为基本最优解。例如最优解是基本解称为基本最优解。例如 满足式满足式(2.1)(2.3)是最优解是最优解,又是又是B3的的基本解基本解,因此它是基本最优解。因此它是基本最优解。注：注：当最优解惟一时，最优解亦是基本最优解，当最优解惟一时，最优解亦是基本最优解，当最优解不惟一时，则最优解不一定是基本最优解。当最优解不惟一时，则最优解不一定是基本最优解。现在学习的是第52页，共122页基基本本最最优优解解、最最优优解解、基基本本可可行行解解、基基本本解解、可可行行解解的的关系关系:基本最优解基本最优解基本可行解基本可行解可行解可行解最最 优优 解解基本解基本解2.4 基本概念基本概念Basic Concepts 现在学习的是第53页，共122页凸集凸集(Convex set):设设 K 是是 n 维空间维空间 Rn 的一个点集，对的一个点集，对任意两点任意两点 时，则称时，则称K为凸集。为凸集。就就是是以以X(1)、X(2)为为端端点点的的线线段段方方程程,点点X的的位位置置由由的的值值确确定定,当当=0时时,X=X(2),当当=1时时X=X(1)。凸组合凸组合(Convex combination):设设是是Rn中的点，若存在中的点，若存在 使得使得 成立，成立，称称X为为 的凸组合。的凸组合。2.4 基本概念基本概念Basic Concepts 现在学习的是第54页，共122页极极点点(Extreme point):设设K是是凸凸集集，若若X不不能能用用K中中两两个个不同的点不同的点 的凸组合表示为的凸组合表示为 )10()1()2()1(-+=a aa aa aXXX则称则称X是是K的一个极点或顶点。的一个极点或顶点。X是凸集是凸集K的极点，即的极点，即X不可能是不可能是K中某一线段的内点，只能是中某一线段的内点，只能是K中某中某一线段的端点。一线段的端点。O2.4 基本概念基本概念Basic Concepts 现在学习的是第55页，共122页【定理定理2.1】若线性规划可行解集若线性规划可行解集 K 非空非空,则则 K 是凸集。是凸集。【定定理理2.2】线线性性规规划划的的可可行行解解集集合合 K 的的点点 X 是是极极点点的的充充要条件为要条件为 X 是基本可行解。是基本可行解。【定定理理2.3】若若线线性性规规划划有有最最优优解解,则则最最优优值值一一定定可可以以在在可可行行解集合的某个极点上达到解集合的某个极点上达到,最优解就是极点的坐标向量。最优解就是极点的坐标向量。注注：定定理理2.22.2刻刻划划了了可可行行解解集集的的极极点点与与基基本本可可行行解解的的对对应应关关系系，极极点点是是基基本本可可行行解解，反反之之，基基本本可可行行解解一一定定是是极极点点，但但它它们们并并非非一一一一对对应应，有有可可能能两两个个或或几几个个基基本本可可行行解解对对应应于于同同一一极极点点(退退化化基基本本可行解时可行解时)。线性规划的基本定理线性规划的基本定理2.4 基本概念基本概念Basic Concepts 现在学习的是第56页，共122页 定定理理2.32.3描描述述了了最最优优解解在在可可行行解解集集中中的的位位置置，它它也也表表明明若若线线性性规规划划问问题题有有最最优优解解，则则必必有有基基本本最最优优解解，且且若若最最优优解解惟惟一一，则则最最优优解解只只能能在在某某一一极极点点上上达达到到；若若具具有有多多重重最最优优解解，则则最最优优解解是是某某些些极极点点的的凸凸组组合合，从从而而最最优优解解是是可可行行解解集集的的极极点点或或界界点点，不不可可能能是是可行解集的内点。可行解集的内点。若若线线性性规规划划的的可可行行解解集集非非空空且且有有界界，则则一一定定有有最最优优解解；若若可可行行解解集集无无界界，则则线线性性规规划划可可能能有有最最优优解解，也也可可能能没没有有最最优优解解；若若线线性性规规划划具具有无界解，则可行域一定无界。有无界解，则可行域一定无界。定定理理2.22.2及及2.32.3还还给给了了我我们们一一个个启启示示，寻寻求求最最优优解解可可不不在在无无限限个个可可行行解解中中去去找找，而而是是去去有有限限个个基基本本可可行行解解中中去去找找。下下一一节节将将介介绍绍一一种种有有效效地地寻寻找找最最优优解的方法。解的方法。2.4 基本概念基本概念Basic Concepts 现在学习的是第57页，共122页2.5 单纯形法单纯形法Simplex Method现在学习的是第58页，共122页考虑到如下线性规划问题考虑到如下线性规划问题 其其中中一一个个mnmn矩矩阵阵，且且秩秩为为m m，总总可可以以被被调调整整为为一一个个m m维维非非负负列列向向量量，为为n n维行向量，为维行向量，为n n维列向量。维列向量。根据线性规划基本定理：根据线性规划基本定理：如果可行域如果可行域=n n/=，00非空有界，非空有界，则上的最优目标函数值则上的最优目标函数值=一定可以在的一个顶点上达到。一定可以在的一个顶点上达到。这个重要的定理启发了这个重要的定理启发了DantzigDantzig的单纯形法，的单纯形法，即将寻优的目标集中在即将寻优的目标集中在D D的各个顶点上。的各个顶点上。p单纯形法的一般原理单纯形法的一般原理现在学习的是第59页，共122页DantzigDantzig的单纯形法把寻优的目标集中在所有基本可行解的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。最优基本可行解的最佳途径。单纯形法的一般步骤如下：单纯形法的一般步骤如下：（1 1）寻找一个初始的基本可行解。）寻找一个初始的基本可行解。（2 2）检查现行的基本可行解是否最优，如果为最优，）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。则停止迭代，已找到最优解，否则转一步。（3 3）移至目标函数值有所改善的另一个基本可行解，）移至目标函数值有所改善的另一个基本可行解，然后转到步骤（然后转到步骤（2 2）。）。现在学习的是第60页，共122页n 确定初始的基本可行解确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初始的可确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵中前为了讨论方便，不妨假设在标准型线性规划中，系数矩阵中前m m个系数列向个系数列向量恰好构成一个可行基，即量恰好构成一个可行基，即 =（），其中（），其中 =（1 1，2 2，m m）为基变量）为基变量x x1 1，x x2 2，xxm m的系数列向量的系数列向量 构成的可行基，构成的可行基，=(=(m+1m+1，P Pm+2m+2,P Pn n)为非基变量为非基变量x xm+1 m+1,x,xm+2,m+2,x,xn n的的 系数列向量构成的矩阵。系数列向量构成的矩阵。现在学习的是第61页，共122页所以约束方程所以约束方程 就可以表示为就可以表示为 用可行基的逆阵用可行基的逆阵-1-1左乘等式两端，再通过移项可推得：左乘等式两端，再通过移项可推得：若令所有非基变量若令所有非基变量,则基变量则基变量由此可得初始的基本可行解由此可得初始的基本可行解现在学习的是第62页，共122页l问题：问题：要判断要判断m m个系数列向量是否恰好构成一个基并不是一件容易的事。个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵中基由系数矩阵中m m个线性无关的系数列向量构成。个线性无关的系数列向量构成。但是要判断但是要判断m m个系数列向量是否线性无关并非易事。个系数列向量是否线性无关并非易事。即使系数矩阵中找到了一个基即使系数矩阵中找到了一个基B B，也不能保证该基恰好是可行基。，也不能保证该基恰好是可行基。因为不能保证基变量因为不能保证基变量B B=-1-1b0b0。为了求得基本可行解为了求得基本可行解 ，必须求基的逆阵，必须求基的逆阵-1-1。但是求逆阵但是求逆阵-1-1也是一件麻烦的事。也是一件麻烦的事。l结论：在线性规划标准化过程中应设法得到一个结论：在线性规划标准化过程中应设法得到一个m m阶单位矩阵阶单位矩阵I I作为初始可行基，作为初始可行基，现在学习的是第63页，共122页若在化标准形式前，约束方程中有若在化标准形式前，约束方程中有“”“”不等式，不等式，那么在化标准型时除了在方程式左端减去剩余变量使不等式变那么在化标准型时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为成等式以外，还必须在左端再加上一个非负新变量，称为人工变量人工变量若在化标准形式前，约束方程中有等式方程，那么可以直接在若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。等式左端添加人工变量。为了设法得到一个为了设法得到一个m m阶单位矩阵阶单位矩阵I I作为初始可行基，可在性规作为初始可行基，可在性规划标准化过程中作如下处理：划标准化过程中作如下处理：若在化标准型前，若在化标准型前，m m个约束方程都是个约束方程都是“”“”的形式，的形式，那么在化标准型时只需在一个约束不等式左端都加上一个松弛变那么在化标准型时只需在一个约束不等式左端都加上一个松弛变量量x xn+in+i(i=1,2,m)(i=1,2,m)。现在学习的是第64页，共122页n判断现行的基本可行解是否最优判断现行的基本可行解是否最优假如已求得一个基本可行解假如已求得一个基本可行解将这一基本可行解代入