1、第第1页页第第2页页在生产管理和经营活动中经常提出以下两类问在生产管理和经营活动中经常提出以下两类问题：题：1.如何利用有限的人力、物力、财力等资源安如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。排生产，使产值最大或利润最高。2.对给定的任务，如何统筹安排，以便用最少对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。的人力、物力、财力等资源消耗去完成任务。第第3页页对于这种从生产的计划与组织中提出的达到最对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支运
2、筹学的一个重要分支数学规划论。数学规划论。第第4页页第第5页页例例1 某工厂在计划内要生产某工厂在计划内要生产I、II两种产品，已知生产两种产品，已知生产单位产品所需的设备台时数、原材料单位产品所需的设备台时数、原材料A的消耗量、原的消耗量、原材料材料B的消耗量，具体数据如表所示。的消耗量，具体数据如表所示。设设 备备原材料原材料A原材料原材料BI140II2048台时台时16kg12kg第第6页页又知道，每生产一件产品又知道，每生产一件产品 I 可获利可获利2元，每生产一件元，每生产一件产品产品 II 可获得可获得3元，问应如何安排生产计划才能够使元，问应如何安排生产计划才能够使得工厂获利最
3、多？得工厂获利最多？解：生产计划就是要确定生产产品解：生产计划就是要确定生产产品 I 和和 II 各多少件。各多少件。故问题的决策变量为需要生产产品故问题的决策变量为需要生产产品I的数量、生产产的数量、生产产品品II的数量。的数量。设需要生产产品设需要生产产品I的数量：的数量：x1设需要生产产品设需要生产产品II的数量：的数量：x2第第7页页对生产计划（即产品对生产计划（即产品 I 和和 II 的生产数量）造成影响的的生产数量）造成影响的制约因素有三个，分别为：制约因素有三个，分别为：（1）设备台时数限制：）设备台时数限制：x1+2x2 8（2）原材料）原材料A的数量限制：的数量限制：4x1
4、16（3）原材料）原材料B的数量限制：的数量限制：4x2 12问题的目标是使得创造的利润达到最大，用问题的目标是使得创造的利润达到最大，用 z 表示所表示所创造的利润值，则可表示为：创造的利润值，则可表示为：max z=2x1+3x2 第第8页页综上所述，建立问题的数学模型为：综上所述，建立问题的数学模型为：目标函数：目标函数：max z=2x1+3x2 0,12416482212121xxxxxx约束条件：约束条件：第第9页页例例2 河流旁建有两个化工厂，两条河流的流量分别为河流旁建有两个化工厂，两条河流的流量分别为500万立方米万立方米/天、天、200万立方米万立方米/天。天。500 万立
5、方米万立方米/天天200 万立方米万立方米/天天 工厂工厂 I 工 厂工 厂 II工厂工厂 I 排污：排污：2 万立方米万立方米/天。天。工厂工厂 II 排污：排污：1.4万立方米万立方米/天。天。第第10页页根据环保要求，河流中污水含量不应大于根据环保要求，河流中污水含量不应大于0.2%。为了达到环保要求，需要进行污水处理。处理方式有为了达到环保要求，需要进行污水处理。处理方式有两种：两种：（1）河流自然净化：工厂）河流自然净化：工厂1排出的污水流到工厂排出的污水流到工厂2时时，20%得到自然净化。得到自然净化。（2）工厂自己进行污水处理：）工厂自己进行污水处理：工厂工厂I 污水处理成本：污
6、水处理成本：1000 元元/万立方米万立方米 工厂工厂II 污水处理成本：污水处理成本：800 元元/万立方米万立方米问如何制定污水处理计划才能使工厂总污水处理成本问如何制定污水处理计划才能使工厂总污水处理成本最小。最小。第第11页页解：污水处理计划就是要确定工厂解：污水处理计划就是要确定工厂 I 和工厂和工厂 II 各处各处理污水多少。理污水多少。故问题的决策变量为工厂故问题的决策变量为工厂 I 处理的污水、工厂处理的污水、工厂 II 处处理的污水。理的污水。设工厂设工厂I 需处理的污水：需处理的污水：x1 万立方米万立方米设工厂设工厂II 需处理的污水：需处理的污水：x2 万立方米万立方米
7、第第12页页对污水处理计划（即工厂对污水处理计划（即工厂I和和II的污水处理量）造成影的污水处理量）造成影响的制约因素有四个，分别为：响的制约因素有四个，分别为：（1）工厂）工厂I 污水处理量的上限：污水处理量的上限：x1 2（2）工厂）工厂II 污水处理量的上限：污水处理量的上限：x2 1.4（3）工厂）工厂I和和II之间河流污水含量的之间河流污水含量的0.2%限制：限制：（2-x1）/500 0.002x1 1 第第13页页问题的目标是使得污水处理成本最小，用问题的目标是使得污水处理成本最小，用 z 表示污水表示污水处理成本，则可表示为：处理成本，则可表示为：min z=1000 x1+8
8、00 x2（4）工厂）工厂II之后河流污水含量的之后河流污水含量的0.2%限制：限制：0.8（2-x1）+（1.4-x2）/700 0.0020.8x1+x2 1.6 第第14页页综上所述，建立问题的数学模型为：综上所述，建立问题的数学模型为：目标函数：目标函数：min z=1000 x1+800 x2 0,4.1 2 6.1 8.01 2121211xxxxxxx约束条件：约束条件：第第15页页从以上两个例子可以看出，它们都属于一类优化问题从以上两个例子可以看出，它们都属于一类优化问题，它们的共同特征为：，它们的共同特征为：每个问题都用一组决策变量（每个问题都用一组决策变量（x1,x2,xn
9、）表示某一）表示某一方案。这组决策变量的值代表一个具体方案，这些变方案。这组决策变量的值代表一个具体方案，这些变量一般取值都是非负的。量一般取值都是非负的。第第16页页存在一定的约束条件，这些约束条件可以用一组线存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。性等式或线性不等式来表示。都有一个要求表达的目标，它可用决策变量的线性都有一个要求表达的目标，它可用决策变量的线性函数来表示（称为目标函数），按问题的不同，要求函数来表示（称为目标函数），按问题的不同，要求目标函数实现最大化或最小化。目标函数实现最大化或最小化。第第17页页满足以上三个条件的数学模型称为线性规划的数学
10、满足以上三个条件的数学模型称为线性规划的数学模型：模型：目标函数目标函数 max(min)z=c1x1+c2x2+cnxn约束条件约束条件 a11x1+a12x2+a1nxn (=,)b1 a21x1+a22x2 +a2nxn (=,)b2 am1x1+am2x2+amnxn (=,)bm x1,x2,xn 0第第18页页1.决策变量正负不限。决策变量正负不限。2.约束条件可以为约束条件可以为=，即约束条件为决策变，即约束条件为决策变量的线性等式或不等式。量的线性等式或不等式。3.每一约束条件右端的常数可为正、负。每一约束条件右端的常数可为正、负。4.目标函数可以要求极大，也可以极小。目标函数
11、可以要求极大，也可以极小。5.目标函数为决策变量的线性函数。目标函数为决策变量的线性函数。第第19页页对于两个或三个变量的线性规划问题可以用图解法对于两个或三个变量的线性规划问题可以用图解法来求解。来求解。1.在直角坐标系中画出由所有约束条件不等式所组成在直角坐标系中画出由所有约束条件不等式所组成的公共取值范围。的公共取值范围。第第20页页该公共取值范围中的每一点都满足所有约束条件，该公共取值范围中的每一点都满足所有约束条件，称为线性规划的可行域。称为线性规划的可行域。可行域边界上改变方向的点称为可行域的顶点。可行域边界上改变方向的点称为可行域的顶点。可行域中的每一点都满足所有约束条件，称可行
12、可行域中的每一点都满足所有约束条件，称可行域中的每一点为线性规划的可行解。域中的每一点为线性规划的可行解。可行域中使目标函数极大或极小的那个可行解称可行域中使目标函数极大或极小的那个可行解称为最优解。为最优解。最优解必然在可行域的顶点上取得。最优解必然在可行域的顶点上取得。定定 义义第第21页页2.如目标函数为最大化：则把目标函数在直角坐标如目标函数为最大化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右上方或左上方平系中所代表的直线沿法线方向向右上方或左上方平移，直到同图中可行域（公共取值范围）的边界点移，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移；相交为止，停止平移；
13、第第22页页3.如目标函数为最小化：则把目标函数在直角坐标如目标函数为最小化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右下方或左下方，系中所代表的直线沿法线方向向右下方或左下方，直到同图中可行域（公共取值范围）的边界点相交直到同图中可行域（公共取值范围）的边界点相交为止，停止平移。为止，停止平移。定义：位于同一条目标函数所代表的直线上的点具定义：位于同一条目标函数所代表的直线上的点具有相同的目标函数值，因而称它为有相同的目标函数值，因而称它为“等值线等值线”。第第23页页4.求出目标函数直线同可行域相交的边界点坐标值。求出目标函数直线同可行域相交的边界点坐标值。5.该边界值即为问题的
14、最优解，并代入目标函数，该边界值即为问题的最优解，并代入目标函数，求出问题的最优解。求出问题的最优解。第第24页页例：目标函数：例：目标函数：max z=2x1+3x2 0,12 4 16 48 2212121xxxxxx约束条件：约束条件：第第25页页解：解：（1）绘制公共取值范围：）绘制公共取值范围：x1+2x2 8：直线：直线 x1+2x2=8 的左下方的左下方 4x1 16：直线：直线 4x1 =16 的左方的左方 4x2 12：直线：直线 4x2 =12 的下方的下方 x10、x20：第：第1象限象限x1x24x2=12x1+2x2=84x1=16第第26页页（2）绘制等值线、并向右
15、上方平移。）绘制等值线、并向右上方平移。x1x24x2=12x1+2x2=84x1=162x1+3x2=zQ第第27页页（3）求出交点坐标）求出交点坐标 Q（4,2）。）。（4）最优解为：）最优解为：x1=4，x2=2。最优值为：最优值为：z=14第第28页页1.确定约束条件围成的区域；确定约束条件围成的区域；2.求出该区域边界点，列表求出目标函数的最优值。求出该区域边界点，列表求出目标函数的最优值。依据依据线性规划问题的最优解在其可行域的顶点上线性规划问题的最优解在其可行域的顶点上取得。取得。第第29页页x1x24x2=12x1+2x2=84x1=162x1+3x2=z0Q1Q2Q3Q4解：
16、解：0=(0,0)；Q1=(4,0)；Q2=(4,2)；Q3=(2,3)；Q4=(0,3)边界点坐标边界点坐标0=(0,0)Q1=(4,0)Q2*=(4,2)Q3=(2,3)Q4=(0,3)目标函数值目标函数值z0814*139第第30页页1.最优解是唯一的。最优解是唯一的。2.无穷多最优解：目标函数直线同某一约束条件直无穷多最优解：目标函数直线同某一约束条件直线平行。线平行。3.无界解：可行域无界。无界解：可行域无界。4.无可行解：无可行域。无可行解：无可行域。第第31页页1.最优解是唯一的。最优解是唯一的。目标函数：目标函数：max z=2x1+3x2 0,12416482212121xx
17、xxxx约束条件：约束条件：第第32页页目标函数：目标函数：max z=2x1+4x2 0,12416482212121xxxxxx约束条件：约束条件：2.无穷多最优解：目标函数直线同某一约束条件直无穷多最优解：目标函数直线同某一约束条件直线平行。线平行。第第33页页x1x24x2=12x1+2x2=84x1=162x1+4x2=zQ3Q2位于线段位于线段 Q2Q3 上任意一点都使目标函数上任意一点都使目标函数 z 取得相取得相同的最大值。同的最大值。分析：目标函数直线和约束条件分析：目标函数直线和约束条件x1+2x28的边界线平的边界线平行。行。第第34页页目标函数：目标函数：max z=2
18、x1+3x2 0,12 416 482212121xxxxxx约束条件：约束条件：3.无界解：可行域无界。无界解：可行域无界。第第35页页x1x24x2=124x1=16x1+2x2=8可行域无界，故最优解无界。可行域无界，故最优解无界。注：可行域无界，可能无最优解，也可能存在最优解，但此时最注：可行域无界，可能无最优解，也可能存在最优解，但此时最优解一定在顶点上取得。优解一定在顶点上取得。第第36页页4.无可行解：无可行域。无可行解：无可行域。目标函数：目标函数：max z=2x1+3x2 0,12 416 4162212121xxxxxx约束条件：约束条件：第第37页页x1x24x2=12
19、x1+2x2164x1=16(4,3)无可行域，所以无可行解。无可行域，所以无可行解。第第38页页分分 析：析：当求解结果出现当求解结果出现3、4两种情况时，一般说明线性规两种情况时，一般说明线性规划问题的数学模型有错误。划问题的数学模型有错误。情况情况 3 可能是因为建模时缺少了某些必要的约束条可能是因为建模时缺少了某些必要的约束条件。件。情况情况 4 可能是因为建模时出现了矛盾的约束条件。可能是因为建模时出现了矛盾的约束条件。图解法虽然直观、简便，但当变量数多于图解法虽然直观、简便，但当变量数多于 3 个以上个以上时，它就无能为力了。需要借助于后面章节所介绍的时，它就无能为力了。需要借助于
20、后面章节所介绍的一种代数法一种代数法单纯形法。单纯形法。第第39页页鉴于线性规划问题模型形式的多样性，为了便于求鉴于线性规划问题模型形式的多样性，为了便于求解和讨论，对于一般线性规划问题总是先将它化为解和讨论，对于一般线性规划问题总是先将它化为标准形式的线性规划问题，然后再予以分析或求解。标准形式的线性规划问题，然后再予以分析或求解。第第40页页具有具有 m 个约束条件和个约束条件和 n 个决策变量的线性规划问题个决策变量的线性规划问题的标准型定义为：的标准型定义为：max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn =b1 a21x1+a22x2 +a2nxn
21、 =b2 am1x1+am2x2+amnxn =bm其中：其中：x1,x2,xn 0，b1,b2,bm0形式一（完整形式）形式一（完整形式）第第41页页形式二（简化形式）形式二（简化形式）njjjxczMax1 mibxatsinjjij,.,1,.1 njxj,.,1,0 第第42页页形式三（向量形式）形式三（向量形式）Max z=CXs.t.AX=b X0其中：其中：C=(c1,cn)A=(aij)m n,，i=1,m，j=1,n X=(x1,xn)T b=(b1,bm)T第第43页页1.目标函数为极大化。目标函数为极大化。2.所有约束条件为等式。所有约束条件为等式。3.所有决策变量限于非
22、负值。所有决策变量限于非负值。4.每一约束条件右端的常数为非负值。每一约束条件右端的常数为非负值。实际碰到的各种线性规划问题的数学模型都应变实际碰到的各种线性规划问题的数学模型都应变换为标准型后才求解。换为标准型后才求解。第第44页页1、目标函数为极小化：将目标函数乘以、目标函数为极小化：将目标函数乘以-1 即可化即可化为等价的极大化问题。为等价的极大化问题。Min z=c x Max z=-c x 第第45页页min z=-2x1-3x2 0,12 4 16 48 2 .212121xxxxxxtsmax z=2x1+3x2解：线性规划模型的标准型为：解：线性规划模型的标准型为：0,12 4
23、 16 48 2 .212121xxxxxxts第第46页页2、约束条件为不等式：、约束条件为不等式：（1）约束条件为）约束条件为：在不等式左端加上一个非负的：在不等式左端加上一个非负的新变量即可化为等式。新增的非负变量称为松弛变新变量即可化为等式。新增的非负变量称为松弛变量。量。（2）约束条件为）约束条件为：在不等式左端减去一个非负的：在不等式左端减去一个非负的新变量即可化为等式。新增的非负变量称为剩余变新变量即可化为等式。新增的非负变量称为剩余变量。量。第第47页页max z=2x1+3x2 0,12 4 16 48 2 .212121xxxxxxtsmax z=2x1+3x2解：引入松弛
24、变量解：引入松弛变量 x3和和 x4，剩余变量，剩余变量 x5。0,12 -4 16 48 2 .543215241321xxxxxxxxxxxxts从而线性规划模型的标准型为：从而线性规划模型的标准型为：第第48页页3、决策变量不是非负值：、决策变量不是非负值：（1）决策变量有非正约束：用一新变量（该变量为）决策变量有非正约束：用一新变量（该变量为决策变量的相反数）来代替。决策变量的相反数）来代替。xj 0引入新变量引入新变量 xj 0，令，令 xj=-xj；将将 xj 表达式代入线性规划模型，用表达式代入线性规划模型，用 xj 替代替代 xj。第第49页页max z=2x1+3x2 0,0
25、12 4 16 482 .212121xxxxxxtsmax z=2x1-3x2解：引入新变量解：引入新变量 x2 0，令，令 x2=-x2。0,12 4-16 48 2 .212121xxxxxxts从而线性规划模型的标准型为：从而线性规划模型的标准型为：第第50页页（2）决策变量符号不受限制（为自由变量）：用两）决策变量符号不受限制（为自由变量）：用两个非负新变量来代替。个非负新变量来代替。xj 正负不限正负不限引入新变量引入新变量 xj 0 和和 xj 0，令，令 xj=xj-xj；将将 xj 表达式代入线性规划模型，用表达式代入线性规划模型，用 xj、xj替代替代 xj。第第51页页m
26、ax z=2x1+3x2 符符号号不不限限212121,012 4 16 482 .xxxxxxtsmax z=2x1+3x2 3x2”解：引入新变量解：引入新变量 x2 0，x2”0，令，令 x2=x2 x2”。0,12 4-4 16 48 2-2 .221221221xxxxxxxxxts从而线性规划模型的标准型为：从而线性规划模型的标准型为：第第52页页（3）决策变量有上、下界：）决策变量有上、下界：引进新变量使其等于原变量减去下限值，并用新引进新变量使其等于原变量减去下限值，并用新变量替换模型中原变量；变量替换模型中原变量；将新变量的上限约束转化为新的约束条件，并化将新变量的上限约束转
27、化为新的约束条件，并化为等式。为等式。a xj b引入新变量引入新变量xj，令，令 xj=xj-a，0 xj b-a；将将 xj 表达式（表达式（xj=xj+a）代入线性规划模型，用）代入线性规划模型，用 xj 替换替换 xj；将将 xj b-a 转为约束，再化为等式。转为约束，再化为等式。第第53页页max z=2x1+3x2 42,013 4 16 482 .212121xxxxxxts解：引入新变量解：引入新变量 x2，令，令 x2=x2 2，x2 2将将 x2=x2+2代入模型，用代入模型，用 x2 替代替代 x2 ：将将 x2 2 转化为约束转化为约束第第54页页max z=2x1
28、3(x2+2)0,2 13 )2(4 16 48 2)(2 .2122121xxxxxxxts第第55页页max z=2x1 3 x2+9 0,2 13 )2(4 16 48 2)(2 .321322121xxxxxxxxxts第第56页页max z=2x1 3 x2+9 0,2 5 4 16 44 2 .321322121xxxxxxxxxts第第57页页4、约束条件右端的常数为负：约束两端乘以、约束条件右端的常数为负：约束两端乘以-1。max z=2x1+3x2 0,012 4 16 482 .212121xxxxxxts解：将第三个约束两端分别乘以解：将第三个约束两端分别乘以-1。从而线
29、性规划模型的标准型为：从而线性规划模型的标准型为：max z=2x1+3x2 0,12 4-16 48 2 .212121xxxxxxts第第58页页在讨论线性规划问题的求解之前，先要了解线性在讨论线性规划问题的求解之前，先要了解线性规划问题的解的概念。规划问题的解的概念。njjjxczMax1 mibxatsinjjij,.,1,.1 njxj,.,1,0 （1）（2）（3）第第59页页1.可行解可行解满足约束条件（满足约束条件（2）和（）和（3）的解）的解X=(x1,xn)T 称为线性规划问题的可行解。称为线性规划问题的可行解。2.可行域可行域所有可行解的集合称为可行域。所有可行解的集合称
30、为可行域。3.最优解最优解使目标函数（使目标函数（1）达到最优（最大化问题）达到最优（最大化问题是使目标函数值最大，最小化问题是使目标函数最是使目标函数值最大，最小化问题是使目标函数最小）的可行解称为最优解。小）的可行解称为最优解。第第60页页Max z=C Xs.t.A X=b X 0其中：其中：C=(c1,cn)A=(aij)m n,，i=1,m，j=1,n X=(x1,xn)T b=(b1,bm)T第第61页页1.几个概念几个概念 （1）向量）向量 由数由数 a1,a2,an 组成的有序数组，称为组成的有序数组，称为 n 维向量。维向量。a=(a1,a2,an )n 维行向量维行向量 n
31、 维列向量维列向量 Tnnaaaaaaa.2121 第第62页页 （2）矩阵的列向量）矩阵的列向量 (m,n)矩阵矩阵 A 的每一列由竖直排列的的每一列由竖直排列的 m 个变量组个变量组成，把它叫做矩阵成，把它叫做矩阵 A 的一个列向量。的一个列向量。),.,(.21212222111211nmnmmnnPPPaaaaaaaaaA TmjjjmjjjjaaaaaaP.2121 第第63页页（3）线性相关）线性相关 给定向量组给定向量组 A=(P1,P2,Pn)则称向量组则称向量组 A 是线性相关的。是线性相关的。使使 k1P1+k2P2+knPn=0如果存在如果存在 n 个不全为零的数个不全为
32、零的数 k1,k2,kn第第64页页（4）线性无关）线性无关 给定向量组给定向量组 A=(P1,P2,Pn)则称向量组则称向量组 A 是线性无关的。是线性无关的。使使 k1P1+k2P2+knPn=0如果不存在如果不存在 n 个不全为零的数个不全为零的数 k1,k2,kn第第65页页 设向量设向量(,P1,P2,Pn)则称则称可由向量可由向量(P1,P2,Pn)线性表示。线性表示。如果存在如果存在 一组数一组数 k1,k2,kn使使=k1P1+k2P2+knPn（5）向量的线性表示）向量的线性表示第第66页页定定 理：理：设向量组设向量组(P1,P2,Pn)线性无关线性无关 设向量组设向量组(
33、,P1,P2,Pn)线性相关线性相关 则则可由可由(P1,P2,Pn)线性表示且表达式唯一。线性表示且表达式唯一。第第67页页（6）矩阵的秩）矩阵的秩从从(m,n)矩阵矩阵 A 中选取中选取 r 个行个行 r 个列，这个列，这 r 个行个行 r 个个列相关处的元素构成一个列相关处的元素构成一个 r 阶方阵，它的行列式叫做阶方阵，它的行列式叫做A 的的 r 阶子式。阶子式。当当 A 的各的各 r 阶子式中至少有一个不为阶子式中至少有一个不为 0，而，而 r+1 阶子阶子式全为式全为0，就说矩阵，就说矩阵 A 的秩为的秩为 r，记为，记为 r(A)。显然显然 r(A)min m,n。第第68页页（
34、7）矩阵秩和向量线性无关）矩阵秩和向量线性无关若矩阵若矩阵 A 的秩等于的秩等于 r，则在列向量（或行向量）中必，则在列向量（或行向量）中必然有然有 r 个列向量（或行向量）构成线性无关组，而任个列向量（或行向量）构成线性无关组，而任意意 r+1 个列向量（或行向量）都是线性相关的。个列向量（或行向量）都是线性相关的。r(A)=A 中最大线性无关列数中最大线性无关列数 =A 中最大线性无关行数中最大线性无关行数第第69页页2.约束条件方程组系数矩阵约束条件方程组系数矩阵 A 的讨论的讨论 njjjxczMax1 mibxatsinjjij,.,1,.1 njxj,.,1,0 第第70页页 mn
35、mnaaaaA1111约定：约定：(1)m n，即约束条件数少于决策变量数。，即约束条件数少于决策变量数。(2)r(A)=m，约束条件系数矩阵的秩等于约束方程数。，约束条件系数矩阵的秩等于约束方程数。第第71页页下面来论证上述两条约定：下面来论证上述两条约定：(1)m n，即约束条件数少于决策变量数。，即约束条件数少于决策变量数。(2)r(A)=m，约束条件系数矩阵的秩等于约束方程数。，约束条件系数矩阵的秩等于约束方程数。第第72页页m n 的论证的论证如果如果m n，约束条件变为了由，约束条件变为了由 m 个相互独立的方程个相互独立的方程组成的线性方程组，从而可直接求出。故在线性规组成的线性
36、方程组，从而可直接求出。故在线性规划问题模型中，约定划问题模型中，约定 m n。第第73页页r(A)=m 的论证的论证因为因为r(A)minm,n=m，所以存在两种情况：，所以存在两种情况：r(A)m r(A)=m 第第74页页下面来论证下面来论证 r(A)m 是不正确的。是不正确的。若若 r(A)m，则线性无关的约束条件只有，则线性无关的约束条件只有 r(A)个，其个，其余的余的 m-r(A)个约束必然可以由这个约束必然可以由这 r(A)个线性无关的个线性无关的约束线性表示，所以这约束线性表示，所以这 m-r(A)个约束方程为多余的个约束方程为多余的，它们根本起不到约束作用，不应当作为问题的
37、约束，它们根本起不到约束作用，不应当作为问题的约束条件而存在于模型中，故应将其删去。条件而存在于模型中，故应将其删去。第第75页页综上所述，对于线性规划问题，均约定：综上所述，对于线性规划问题，均约定：约束条件数约束条件数 决策变量数（决策变量数（m n）所有约束条件之间必须线性无关，即约束条件所有约束条件之间必须线性无关，即约束条件系数矩阵的秩系数矩阵的秩=约束条件数（约束条件数（r(A)=m）第第76页页设设(A)m n 是线性规划问题的约束条件系数矩阵，是线性规划问题的约束条件系数矩阵，r(A)=m。将。将 A 表示成列向量的形式，即表示成列向量的形式，即 A=(P1,P2,Pn)，则约
38、束方程可写成：，则约束方程可写成：mnnbbbxxxPPP.212121第第77页页又因为又因为 r(A)=m，故，故(P1,P2,Pn)中有中有 m 个列向个列向量线性无关，设量线性无关，设 B=(P1,P2,Pm)为为 A 中中 m 个线性个线性无关的列向量。无关的列向量。1、基、基由由(P1,P2,Pm)此此 m 个线性无关的列向量所构成个线性无关的列向量所构成的矩阵称为线性规划问题的一个基。的矩阵称为线性规划问题的一个基。基的个数最多为基的个数最多为 Cnm 个个第第78页页例：例：max z=x1+x2 s.t.2x1+6x2 +2x3+x4 =10 3x1+x2 +2x3+x4 =
39、8 x1,x2,x3,x4 0 1362 2322 1312 2126 1116 1212、解：系统矩阵中存在的基有：解：系统矩阵中存在的基有：不构成基不构成基第第79页页2.基变量基变量 基基(P1,P2,Pm)所对应的所对应的 m 个变量个变量(x1,x2,xm)称为基变量。称为基变量。3.非基变量非基变量 其余其余 n-m 个变量称为非基变量。个变量称为非基变量。第第80页页例：例：max z=x1+x2 s.t.2x1+6x2 +2x3+x4 =10 3x1+x2 +2x3+x4 =8 x1,x2,x3,x4 0 1362解：解：x1 和和 x2x3 和和 x4选择基选择基基变量基变量
40、非基变量非基变量第第81页页x1 和和 x3x2 和和 x4选择基选择基基变量基变量非基变量非基变量 2322x3 和和 x4x1 和和 x2不构成基不构成基不是基变量不是基变量不是非基变量不是非基变量 1212第第82页页由此可知由此可知基变量所对应的系数列向量必须线性无关基变量所对应的系数列向量必须线性无关第第83页页4.基解基解 令令(n-m)个非基变量等于个非基变量等于0，并对余下的，并对余下的 m 个基变个基变量求解，所得的解称为基解。量求解，所得的解称为基解。基解中非零分量的数目基解中非零分量的数目 m 基解的个数最多为基解的个数最多为 Cnm 个个第第84页页例：例：max z=
41、x1+x2 s.t.2x1+6x2 +2x3+x4 =10 3x1+x2 +2x3+x4 =8 x1,x2,x3,x4 0 1362、解：解：基变量：基变量：x1 和和 x2非基变量：非基变量：x3 和和 x4令令 x3=x4=0（非基变量），求得：（非基变量），求得：x=（19/8，7/8，0，0）为基解。）为基解。第第85页页 2322基变量：基变量：x1 和和 x3非基变量：非基变量：x2 和和 x4令令 x2=x4=0（非基变量），求得：（非基变量），求得：x=（-2，0，7，0）为基解，但不是）为基解，但不是一个可行解。一个可行解。第第86页页令令 x3=x4=1（非基变量），求得：
42、（非基变量），求得：x=（23/16，11/16，1，1）不为基解，但）不为基解，但它是一个可行解。它是一个可行解。1362基变量：基变量：x1 和和 x2非基变量：非基变量：x3 和和 x4第第87页页令令 x3=-1，x4=0（非基变量），求得：（非基变量），求得：x=（3，1，-1，0）不为基解，它也不是）不为基解，它也不是一个可行解。一个可行解。1362基变量：基变量：x1 和和 x2非基变量：非基变量：x3 和和 x4第第88页页5.基可行解基可行解 若基解满足非负约束，称其为基可行解。若基解满足非负约束，称其为基可行解。6.可行基可行基 对应于基可行解的基。对应于基可行解的基。第第
43、89页页例：例：max z=x1+x2 s.t.2x1+6x2 +2x3+x4 =10 3x1+x2 +2x3+x4 =8 x1,x2,x3,x4 0、解：解：选择选择 x1 和和 x2 为基变量为基变量令令 x3=x4=0（非基变量），求得：（非基变量），求得：x=（19/8，7/8，0，0）为基解，同时也是可）为基解，同时也是可行解，所以是基可行解。行解，所以是基可行解。可行基可行基 1362第第90页页选择选择 x1 和和 x3为基变量为基变量令令 x2=x4=0（非基变量），求得：（非基变量），求得：x=（-2，0，7，0）为基解，但不是可行解，所）为基解，但不是可行解，所以不是基可行
44、解。以不是基可行解。不是可行基不是可行基 2322第第91页页7.退化解退化解 若基可行解中有基变量等于若基可行解中有基变量等于0，则该基可行解称为，则该基可行解称为退化解。退化解。第第92页页例：例：max z=x1+x2 s.t.2x1+6x2 +2x3+x4 =16/3 3x1+x2 +2x3+x4 =8 x1,x2,x3,x4 0、1362基变量：基变量：x1 和和 x2非基变量：非基变量：x3 和和 x4令令 x3=x4=0（非基变量），求得：（非基变量），求得：x=(8/3，0，0，0)为基可行解，同时也是一为基可行解，同时也是一个退化解。个退化解。解：解：第第93页页可行解可行解非可行解非可行解基解基解基解中的可行解基解中的可行解基解中的不可行解基解中的不可行解（基可行解）（基可行解）第第94页页不可行解不可行解可行解可行解第第95页页不可行解不可行解可行解可行解基解基解第第96页页不可行解不可行解可行解可行解基基解解中中的的不不可可行行解解基基可可行行解解
