《[数学]Chapter-2--线性规划.ppt》由会员分享，可在线阅读，更多相关《[数学]Chapter-2--线性规划.ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学数学Chapter-2-线性性规划划一、问题的提出和数学模型例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 2021/5/2222021/5/2231.1数学模型数学模型MathematicalModel线性规划线性规划（Linear Programming,缩写为LP
2、）是运筹学的重是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行等问题。线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源用最少的资源（如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，去完成确定的任
3、务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。利润最大）。2021/5/224应用模型举例应用模型举例【例例1.11.1】最最优优生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙、丙丙三三种种产产品品。这这些些产产品品分分别别需需要要要要在在设设备备A A、B B上上加加工工，需需要要消消耗耗材材料料C C、D D，按按工工艺艺资资料料规规定定，单单件件产产品品在在不不同同设设备备上上加加工工及及所所需需要要的的资资源源如如表表1.11.1所所示示。已已知知
4、在在计计划划期期内内设设备备的的加加工工能能力力各各为为200200台台时时，可可供供材材料料分分别别为为360360、300300公公斤斤；每每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为4040、3030、5050元元，假假定定市市场场需需求求无无限限制制。企企业业决决策策者者应应如如何何安安排排生生产产计计划划，使使企企业业在在计计划划期期内内总总的的利利润润收收入最大入最大？2021/5/225表表1.1产品资源消耗产品资源消耗产品产品资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料
5、材料D235300利润（元利润（元/件）件）4030502021/5/226分析：设变量xi为第i种（甲、乙、丙）产品的生产件数（i1，2，3）。根据题意，我们知道三种产品的生产受到设备能力（机时数）的限制。对设备A，三种产品生产所占用的机时数不能超过200，于是我们可以得到不等式：3x1+x2+2x3 200；对设备B，三种产品生产所占用的机时数不能超过200，于是我们可以得到不等式：2x1+2x2+4x3 200；2021/5/227对材料C，三种产品生产所消耗的材料数不能超过360公斤，于是我们可以得到不等式：4x1+5x2+x3 360；对材料D，三种产品生产所消耗的材料数不能超过30
6、0，于是我们可以得到不等式：2x1+3x2+5x3 300；2021/5/228同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=40 x1+30 x2+50 x32021/5/229【解】设【解】设x1、x2、x3分别为甲、乙、丙三种产品的分别为甲、乙、丙三种产品的产量数学模型为：产量数学模型为：最优解最优解X=(50,30,10);Z=3400产产品品资源资源甲甲乙乙丙丙现有资现有资源源设备设备A312200设备设备B224200材料材料C451360材料材料D235300利润（元利润（元/件）件）4030502021/5/2210这是一个
7、典型的利润最大化的生产计划问题。其标这是一个典型的利润最大化的生产计划问题。其标中，中，“Max”“Max”是英文单词是英文单词“Maximize”“Maximize”的缩写，含义的缩写，含义为为“最大化最大化”；例题中例题中x1、x2、x3称为决策变量称为决策变量;不等式组称为约束条件不等式组称为约束条件,(有时在它前面加有时在它前面加“s.t.”“s.t.”表示表示“subject to”“subject to”的意思，意思是的意思，意思是“满足于满足于”);”);函数函数Z Z称为目标函数称为目标函数,随讨论问题的不同随讨论问题的不同,Z,Z也可以求最小值也可以求最小值.线性规划的数学模
8、型由线性规划的数学模型由 决策变量决策变量 Decision Decision variables;variables;目标函数目标函数Objective functionObjective function及约束及约束条件条件ConstraintsConstraints构成。称为三个要素。构成。称为三个要素。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？其特征是：其特征是：1 1解决问题的目标函数是多个决策变量的线性函解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或数，通常是求最大值或 最小值；最小值；2 2解决问题的约束条件是一组多个决策变量解决问题的约束条件
9、是一组多个决策变量 的线的线性不等式或等式。性不等式或等式。2021/5/2211书本还例举了诸如合理用料问题书本还例举了诸如合理用料问题;配料问题配料问题;投资问题投资问题;均衡配均衡配套生产问题等套生产问题等.线性规划的一般模型线性规划的一般模型一般地，假设线性规划数学模一般地，假设线性规划数学模型中，有型中，有m个约束，有个约束，有n个决策个决策变量变量xj,j=1,2,n，目标函数的，目标函数的变量系数用变量系数用cj表示表示,cj称为称为价值价值系数系数。约束条件的变量系数用。约束条件的变量系数用aij表示，表示，aij称为称为工艺系数工艺系数。约。约束条件右端的常数用束条件右端的常
10、数用bi表示，表示，bi称为称为资源限量资源限量。则线性规划数。则线性规划数学模型的一般表达式可写成学模型的一般表达式可写成在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。2021/5/22121.2线性规划的标准型线性规划的标准型StandardformofLPMax（或Min）z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 0注：本教材默认目标函数是注：本教材默认目标函数是max2021/5/2213可以看出，线性规划的标准形
11、式有如下四个特点：目标最大化、约束为等式、决策变量xjxj均非负、右端常数常数bibi项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式2021/5/2214如果目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z -f，该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z2021/5/2215线性规划的标准形式也写成下列形式线性规划的标准形式也写成下列形式：或用矩阵形式或用矩阵形式2021/5/2
12、216如何将非标准形式的线性规划问题转化为标准形式当约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi2021/5/2217当约束条件为 ai1x1+ai2x2+ainxn bi 时，类似地令 s=(ai1x1+ai2x2+ainxn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1x1+ai2x2+ainxn-s=bi 为了使约束由不等式成为等式而引进的
13、变量s称为“松弛变量”（slack variableslack variable）。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。2021/5/2218【例【例1.12】将下列线性规划化为标准型】将下列线性规划化为标准型【解】（）因为【解】（）因为x x3 3无符号要求无符号要求 ，即，即x x3 3取正值取正值也可取负值，标准型中要求变量非负，所以令也可取负值，标准型中要求变量非负，所以令2021/5/2219(2)(2)第一个约束条件是第一个约束条件是号，在号，在左端加入松左端加入松驰变量驰变量x x4 4，x x40,40,化为等式化为等式(3
14、)(3)第二个约束条件是第二个约束条件是号，在号，在号号 左端减去左端减去剩余变量剩余变量x5x5，x5x500。也称松驰变量。也称松驰变量4)4)第三个约束条件是第三个约束条件是号且常数项为负数，因此号且常数项为负数，因此在在左边加入松驰变量左边加入松驰变量x x6 6，x x6060，同时两边乘，同时两边乘以以1 1。（5 5）目标函数是最小值，为了化为求最大值，）目标函数是最小值，为了化为求最大值，令令Z=Z=Z,Z,得到得到max Z=max Z=Z Z，即当，即当Z Z达到最小值达到最小值时时ZZ达到最大值，反之亦然。达到最大值，反之亦然。2021/5/2220综合起来得到下列标准型
15、综合起来得到下列标准型2021/5/2221当某个变量当某个变量x xj j00时时,令令x/j=xj 。当某个约束是绝当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束化为等式，例如约束将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。2021/5/2222【例例1.13】将下例线性规划化为标准型】将下例线性规划化为标准型【解】解】此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 则有则有2021/5/2223得到线性规划的标准形式得到线性规划的标准形式对
16、于对于axb(a、b均大于零均大于零)的有界变量化为标准形式的有界变量化为标准形式有两种方法，一种方法是增加两个约束有两种方法，一种方法是增加两个约束xa及及xb，另一种方法是令另一种方法是令=xa，则，则axb等价于等价于0ba，增加一个约束，增加一个约束ba并且将原问题所有并且将原问题所有x用用a替换。替换。2021/5/22241.1.如何化标准形式？如何化标准形式？可以对照四条标准逐一判断可以对照四条标准逐一判断标准形式是人为定义的，目标函数可以标准形式是人为定义的，目标函数可以是求最小值是求最小值2.2.用用WinQSBWinQSB软件求解时，不必化成标准软件求解时，不必化成标准型型
17、图解法时不必化为标准型。图解法时不必化为标准型。3.3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材作业：教材P34 TP34 T 82021/5/22251.3图解法图解法 GraphicalMethod线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：(1)分别取决策变量x1,x2 为坐标向量建立直角坐标系。（2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过2021/5/2226判断确定不等式所决定的半平面。各约束半判断确定不等式
18、所决定的半平面。各约束半平面交出来的区域平面交出来的区域(存在或不存在），若存在，存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或这些符合约束限制的点集合，称为可行集或可行域可行域。3.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量先过原点作一条矢量指向点（指向点（c1,c2)，矢量的方向就是目标函数增，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；垂直的直线，这条直线就是目标函数图形；4.求最优解求最
19、优解依据目标函数求最大或最小移动目依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标函数直线，直线与可行域相交的点对应的坐标就是标就是最优解最优解。2021/5/2227x1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85例例1.72021/5/2228246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例1.82021/5/2229246x1246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例1.9有无穷多个最优解有无穷多个最优解
20、即具有多重解即具有多重解,通解为通解为 01 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)x22021/5/2230246x1x2246无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.102021/5/2231由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1.7例例1.8)2.有多重解有多重解(例例1.9)3.有无界解有无界解(例例1.10)4.无可行解无可行解(例例1.11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解2021/5/22321.通过图解法
21、了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材作业：教材P34 T7 学习要点2021/5/22331.4线性规划的有关概念线性规划的有关概念BasicConceptsofLP 设线性规划的标准型设线性规划的标准型max Z=CX（1.1）AX=b（1.2）X 0（1.3）式中式中A 是是mn矩阵，矩阵，mn并且并且r（A）=m，显然，显然A中至少中至少有一个有一个mm子
22、矩阵子矩阵B，使得，使得r（B）=m。基基 (basis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称，则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basis matrix）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过2021/5/2234【例【例1.14】线性规划】线性规划 求所有基矩阵求所有基矩阵。【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵 容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵有有C52=10个，其中第个，其中第1列与第列与第3列构列构成的成的2
23、阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即2021/5/2235由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩阵。当矩阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量(basis vector)，其余列向量称为，其余列向量称为非基向量非基向量 基向量对应的变量称为基向量对应的变量称为基变量基变量(basis variable)，非基向量，非基向量对应的变量称为对应的变量称为非基变量非基变量
24、在在上上例例中中B2的的基基向向量量是是A中中的的第第一一列列和和第第四四列列，其其余余列列向向量量是是非非基基向向量量，x1、x4是是基基变变量量，x2、x3、x5是是非非基基变变量量。基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不不同同的的基基对对应应的的基基变变量量和非基变量也不同。和非基变量也不同。2021/5/2236可行解可行解(feasible solution)满足式（满足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T称为可行解称为可行解。基基本本可可行行解解(basis feasible solution)若若基基本本解解是
25、是可可行行解解则则称称为为是基本可行解（也称基可行解）。是基本可行解（也称基可行解）。例如，例如，与与X=（0，0，0，3，2，）都是例，）都是例1 的可行解。的可行解。基本解基本解(basis solution)对某一确定的基对某一确定的基B，令非基变量等于零，令非基变量等于零，利用式（利用式（1.）解出基变量，则这组解称为基解出基变量，则这组解称为基的基的基本解。本解。最最优优解解(optimal solution)满满足足式式 （1.1）的的可可行行解解称称为为最最优优解解，即即是是使使得得目目标标函函数数达达到到最最大大值值的的可可行行解解就就是是最最优优解解，例例如可行解如可行解 是
26、例是例2的最优解。的最优解。非可行解非可行解(Infeasible solution)无界解无界解(unbound solution)2021/5/2237显然，只要基本解中的基变量的解满足式（显然，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在在例例1.13中中，对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变变量量，令令x3=x4=x5=0，则式（，则式（1.）为）为对对B2来说，来说，x1,x4,为基变量，令非变量为基变量，令非变量x2,x3,x5为零，由式为零，由式（1.2）得到）得
27、到，x4=4，因因|B1|，由克莱姆法，由克莱姆法则则知，知，x1、x2有唯一解有唯一解x12/5,x2=1则则 基基本解为本解为2021/5/2238由于由于 是基本解，从而它是基本可行解，在是基本解，从而它是基本可行解，在 中中x10,因此不是可行解，也就不是基本可行解。因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解反之，可行解不一定是基本可行解例如例如 满足式（满足式（1.2）（）（1.3），但不是），但不是任何基矩阵的基本解。任何基矩阵的基本解。基本解为基本解为2021/5/2239可行基可行基 基可行解对应的基称为可行基；基可行解对应的基称为可行基；最优基最优基基
28、本最优解对应的基称为最优基；基本最优解对应的基称为最优基；如上述如上述B3就是最优基，最优基也是可行基。就是最优基，最优基也是可行基。当最优解唯一时，最优解亦当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例则最优解不一定是基本最优解。例如右图中线段如右图中线段 的点为最优的点为最优 解解时，时，Q1点及点及Q2点是基本最优解点是基本最优解,线线段段 的内点是最优解而不是基的内点是最优解而不是基本最优解。本最优解。基本最优解基本最优解 最优解是基本解称为基本最优解。例如，满足式最优解是基本解称为基本最优解。例如，满足式（1.1
29、）(1.3)是最优解是最优解,又是又是B3的基本解的基本解,因此它是基本最优解。因此它是基本最优解。2021/5/2240基基本本最最优优解解、最最优优解解、基基本本可可行行解解、基基本本解解、可可行行解解的关系如下所示：的关系如下所示：基本最优解基本最优解基本可行解基本可行解可行解可行解最最 优优 解解基本解基本解例如例如,B点和点和D点是可点是可行解行解,不是基本解不是基本解;C点点是基本可行解是基本可行解;A点是点是基本最优解基本最优解,同时也是同时也是最优解、基本可行解、最优解、基本可行解、基本解和可行解。基本解和可行解。2021/5/2241凸集凸集(Convex set)设设K是是
30、n维空间的一个点集，对任意两点维空间的一个点集，对任意两点 时，则称时，则称K为凸集。为凸集。凸凸组组合合(Convex combination)设设 是是Rn中的点若存在中的点若存在 使使得得 成成立立，则则称称X为为 的的凸组合。凸组合。就就是是以以X（1）、X（2）为为端端点点的的线线段段方方程程，点点X的的位位置置由由的的值值确确定定，当当=0时时，X=X（2），当当=1时时X=X（1）2021/5/2242极极点点(Extreme point)设设K是是凸凸集集，若若X不不能能用用K中两个不同的中两个不同的 点点 的凸组合表示为的凸组合表示为)10()1()2()1(0表表1-4(1
31、)XBx1x2x3x4bx3211040 x4130130j3400(2)x3x2j(3)x1x2j基变量基变量将将3化为化为1乘乘以以1/3后后得得到到1001/301/3105/31-1/35/30-4/330103/5-1/51801-1/5 2/5400-1-13018i10402021/5/2250最优解最优解X=(18，4，0，0)T，最优值，最优值Z=70O20301040(3,4)X(3)=(18,4)最优解最优解X=(18,4)最优值最优值Z=70X(1)=(0,0)10 x2x130X(2)=(0,10)2021/5/2251单单纯纯形形法法全全过过程程的的计计算算，可可以
32、以用用列列表表的的方方法法计计算算更更为为简简洁洁，这种表格称为单纯形表（表这种表格称为单纯形表（表1.4）。）。计算步骤：计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；基变量的检验数必为零；2.判断：判断：（a）若）若j（j，n）得到最解；）得到最解；（b）某某个个k0且且aik（i=1，2,m）则则线线性性规规划划具具有有无无界解界解(见例见例1.18)。（c）若存在）若存在k0且且aik(i=1,m)不全非正，则进行换基；不全非正，则进行换基；2021/5/2252第第个个比比值值最最小小，选选最最
33、小小比比值值对对应应行行的的基基变变量量为为出出基基变变量量，若若有相同最小比值，则任选一个。有相同最小比值，则任选一个。aLk为主元素；为主元素；(c）求求新新的的基基可可行行解解：用用初初等等行行变变换换方方法法将将aLk 化化为为,k列列其其它它元元素素化化为为零零（包包括括检检验验数数行行）得得到到新新的的可可行行基基及及基基本本可可行解，再判断是否得到最优解。行解，再判断是否得到最优解。（b）选出基变量）选出基变量，求最小比值：，求最小比值：3.换基：换基：（a）选进基变量）选进基变量设设k=max j|j 0,xk为进基变量为进基变量2021/5/2253【例【例1.16】用单纯形
34、法求解用单纯形法求解【解】将数学模型化为标准形式：【解】将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，单纯法计算结果如表可作为初始基变量，单纯法计算结果如表 1.所示所示。2021/5/2254Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j表表151/3150120301713751/30M2025601017/31/31250128/91/92/335/3001/97/3最优解最优解X=(25，35/3，0，0，0)T，最优值，最优值Z=145/398/99022021/5/2255
35、【例【例1.17】用单纯形法求解】用单纯形法求解 【解】【解】这是一个极小化的线性规划问题这是一个极小化的线性规划问题,可以将其化为极大化问题可以将其化为极大化问题求解求解,也可以直接求解也可以直接求解,这时判断标准是：这时判断标准是：j0(j=1，n)时得到时得到最优解最优解。容易观察到容易观察到,系数矩阵中有一个系数矩阵中有一个3阶单位矩阵阶单位矩阵,x3、x4、x5为基变量。为基变量。目标函数中含有基变量目标函数中含有基变量x4,由第二个约束得到由第二个约束得到x4=6+x1x2，并代入，并代入目标函数消去目标函数消去x4得得2021/5/2256XBx1x2x3x4x5bx3x4x51
36、-1611210001000156215621/2j1-1000 x2x4x51-241001-1-20100015111j20100表中表中j0,j=1,2,5所以最优解为所以最优解为X=(0,5,0,1,11,)最优值最优值 Z=2x12x2x4=251=11极小值问题极小值问题,注意判断标准注意判断标准,选进基变量时选进基变量时,应选应选j0,x2进进基基，而而a120，a220且且aik（i=1，2,m）则线）则线性规划具有无界解性规划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可存在某个基变量为零的基本可行解。行解。2021/5/2263在在实实际际问
37、问题题中中有有些些模模型型并并不不含含有有单单位位矩矩阵阵，为为了了得得到到一一组组基基向向量量和和初初基基可可行行解解，在在约约束束条条件件的的等等式式左左端端加加一一组组虚虚拟拟变变量量，得得到到一一组组基基变变量量。这这种种人人为为加加的的变变量量称称为为人人工工变变量量，构构成成的的可可行行基基称称为为人人工工基基，用用大大M法法或或两两阶阶段段法法求求解解，这这种种用用人人工工变变量量作作桥梁的求解方法称为人工变量法。桥梁的求解方法称为人工变量法。【例【例1.20】用大】用大M法解法解 下列线性规划下列线性规划1.大大M 单纯形法单纯形法1.5.2大大M和两阶段单纯形法和两阶段单纯形
38、法2021/5/2264【解】首先将数学模型化为标准形式【解】首先将数学模型化为标准形式式式中中x4，x5为为松松弛弛变变量量，x5可可作作为为一一个个基基变变量量，第第一一、三三约约束束中中分分别别加加入入人人工工变变量量x6、x7，目目标标函函数数中中加加入入Mx6Mx7一一项项，得得到到人人工变量单纯形法数学模型工变量单纯形法数学模型用前面介绍的单纯形法求用前面介绍的单纯形法求解，见下表。解，见下表。2021/5/2265Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6
39、x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/32021/5/2266（1）初初始始表表中中的的检检验验数数有有两两种种算算法法，第第一一种种算算法法是是利利用用第第一一、三三约约束束将将x6、x7的的表表达达式式代代入入目目标标涵涵数数消消去去x6和和x7，得得到到用用非非基基变变量量表表达达的的目目标标函函数数，其其系系数数就就是是检检验验数数；第第二二种种算算法法是
40、是利利用用公式计算，如公式计算，如（2）M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理解为它能大于给定的任何一个确定数值；理解为它能大于给定的任何一个确定数值；最优解最优解X（31/3，13，19/3，0，0)T；最优值；最优值Z152/3注意：注意：2021/5/2267【例【例1.21】求解线性规划】求解线性规划【解】加入松驰变量【解】加入松驰变量x3、x4化为标准型化为标准型在第二个方程中加入人工变量在第二个方程中加入人工变量x5，目标函数中加上，目标函数中加上Mx5一项，一项，得到得到 2021/5/2268用单纯形法计算如下表所示。用
41、单纯形法计算如下表所示。Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM02021/5/2269表表中中j0，j=1，2，5，从从而而得得到到最最优优解解X=（2，0，0，0，2），Z=10+2M。但但最最优优解解中中含含有有人人工工变变量量x50说说明明这这个个解解是伪最优解，是不可行的，因此原问题无可行解。是伪最优解，是不可行的，因此原问题无可行解。两阶段单纯形法与大两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基单纯形法的目的类似，将人工变
42、量从基变量中换出，以求出原问题的初始基本可行解。将问题分成两变量中换出，以求出原问题的初始基本可行解。将问题分成两个阶段求解，第一阶段的目标函数个阶段求解，第一阶段的目标函数是是约束条件是加入人工变量后的约束方程，当第一阶段的最优解约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解。解，第二阶段就以此为基础对原目标函数求最优解。当第一阶当第一阶段的最优解段的最优解w0时，说明还有不为零的人工变量是基变量，则原时，说明还有不为零的人工变量是基
43、变量，则原问题无可行解。问题无可行解。2.两阶段单纯形法两阶段单纯形法2021/5/2270【例【例1.22】用两阶段单纯形法求解例】用两阶段单纯形法求解例19的线性规划。的线性规划。【解】标准型为【解】标准型为在第一、三约束方程中加入人工变量在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为后，第一阶段问题为用单纯形法求解，得到第一阶段问题的计算表如下：用单纯形法求解，得到第一阶段问题的计算表如下：2021/5/2271Cj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100 x6x5x36
44、32532001100010100381j650100000 x2x5x36/53/52/51000011/53/52/50103/531/511/5j000002021/5/2272最最优优解解为为 最最优优值值w=0。第第一一阶阶段段最最后后一一张张最最优优表表说说明明找找到到了了原原问问题题的的一一组组基基可可行行解解，将将它它作作为为初初始始基基可可行行解解，求求原问题的最优解，即第二阶段问题为原问题的最优解，即第二阶段问题为2021/5/2273【例【例1.23】用两阶段法求解例】用两阶段法求解例1.21的线性规划。的线性规划。【解】例【解】例1.21的第一阶段问题为的第一阶段问题为
45、用单纯形法计算如下表：用单纯形法计算如下表：2021/5/2274Cj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一阶段的最优解得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值最优目标值w=20,x5仍在基变量中仍在基变量中,从而原问题无可行解。从而原问题无可行解。2021/5/2275解的判断解的判断唯一最优解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解规划具有唯一最优解 多重最
46、优解的判断多重最优解的判断:最优表中存在非基变量的检验数为零最优表中存在非基变量的检验数为零,则则线则性规划具有多重最优解。线则性规划具有多重最优解。无无界界解解的的判判断断:某某个个k0且且aik（i=1，2,m）则则线线性性规规划具有无界解划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。无无可可行行解解的的判判断断：(1)当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且且存在存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。(2)当第一阶段的最优值当第一阶段的最优值w0时，则原问题无可
47、行解时，则原问题无可行解。2021/5/2276设有线性规划设有线性规划其中其中Amn且且r(A)=m,X0应理解为应理解为X大于等于零向量，即大于等于零向量，即xj0,j=1,2,n。1.5.3 计算公式计算公式2021/5/2277不不妨妨假假设设A（P1，P2，Pn）中中前前m个个列列向向量量构构成成一一个个可可行行基基，记记为为B=(P1，P2，Pm)。矩矩阵阵A中中后后nm列列构构成成的的矩矩阵阵记记为为N（Pm+1,Pn）,则则A可可以以写写成成分分块块矩矩阵阵A=（B，N）。对对应应于于 基基 B，基基 变变 量量 为为 XB=（x1,x2，xm）T,非非 基基 变变 量量 为为
48、XN=(xm+1,xm+2,xn)T。则则X可表示成可表示成 同理将同理将C写成分块矩阵写成分块矩阵C=（CB，CN），），CB=(C1,C2,Cm),CN=(Cm+1Cm+2，cn)则则AX=b可写成可写成2021/5/2278因为因为r（B）=m（或（或|B|0）所以）所以B1存在，因此可有存在，因此可有 令令非非基基变变量量XN=0，XB=B1b，由由 B是是 可可行行基基的的假假设设，则则得得到到基本可行解基本可行解将目标函数写成将目标函数写成 X=(B1b，0)T2021/5/2279得到下列五个计算公式：得到下列五个计算公式：(令令XN=0)2021/5/2280上上述述公公式式可
49、可用用下下面面较较简简单单的的矩矩阵阵表表格格运运算算得得到到，设设初初始始矩矩阵阵单纯形表单纯形表1-15 将将B化化为为I（I为为m阶阶单单位位矩矩阵阵）,CB化化为为零零,即即求求基基本本可可行行解解和和检检验数。用验数。用B1左乘表中第二行左乘表中第二行,得到表得到表1-16XBXNbXBIB-1NB-1bCj-ZjCBCN0XBXNbXBBNbCj-ZjCBCN0表表115表表1162021/5/2281再将第二行左乘再将第二行左乘CB后加到第三行后加到第三行,得到得到XBZ0XBXNbXBIB-1NB-1 1bCj-Zj0CN-CBB1NCBB1b表表1172021/5/2282五
50、个公式的应用五个公式的应用【例【例1.24】线性规划】线性规划已知可行基已知可行基 求求(1)单纯形乘子单纯形乘子;(2)基可行解及目标值基可行解及目标值;(3)求求3;(4)B1是否是最优基是否是最优基,为什么为什么;(5)当可行基为当可行基为 时求时求1及及3。2021/5/2283【解解】(1)因因为为B1由由A中中第第一一列列、第第二二列列组组成成,故故x1、x2为为基基变变量量，x3、x4、x5为非基变量为非基变量,有关矩阵为有关矩阵为CB=(c1,c2)=(1,2)CN=(c3,c4,c5)=(1,0,0)故单纯形乘子故单纯形乘子 2021/5/2284(2)基变量的解为基变量的解