第二讲线性规划基础课件.ppt

1、湖州师范学院商学院湖州师范学院商学院12022年12月16日第二讲第二讲 线性规划基础线性规划基础一一.线性规划的提出与模型线性规划的提出与模型 二二.线性规划的图解线性规划的图解 三三.线性规划标准型与解的概念线性规划标准型与解的概念四四.线性规划的基本理论线性规划的基本理论湖州师范学院商学院湖州师范学院商学院22022年12月16日一、线性规划的提出与模型一、线性规划的提出与模型1、问题的提出第二讲第二讲 线性规划基础线性规划基础 例1-1：某工厂在计划期内要安排生产甲、乙两种产品，按照工艺要求，产品甲、乙在设备A、B上所需的加工台时及原材料的消耗如表1-1所示。资源产品原材料/单位设备A

2、/h设备B/h单件利润/千元甲1403乙2044资源数量81612表1-1 例1-1数据资料湖州师范学院商学院湖州师范学院商学院32022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型1、问题的提出 续例1-1：问：应如何安排生产计划才能到最大利润？2x用数学关系式描述这个问题用数学关系式描述这个问题假设 ，分别表示在计划期内产品甲、乙的产量；生产 ，的数量多少，受到各种条件限制；1x2x124;164;822121xxxx生产的产品数量不能为负值生产的产品数量不能为负值，即 ；0,21xx问：如何安排生产，使利润最大？决策变量决策变量约束

3、条件约束条件目标函数目标函数1x 资源产品原材料/单位设备A/h设备B/h单件利润/千元甲1403乙2044资源数量81612湖州师范学院商学院湖州师范学院商学院42022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型1、问题的提出得到本问题的数学模型为:0124164823221212121x,xxxxx:xxzmax约束条件目标函数这就是一个最简单的线性规划模型。这就是一个最简单的线性规划模型。湖州师范学院商学院湖州师范学院商学院52022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模

4、型练习题 练习题练习题1 靠近某河流有两个化靠近某河流有两个化工厂工厂(见图见图1-1)，流经第一化工，流经第一化工厂的河流流量为每天厂的河流流量为每天500万立方万立方米，在两个工厂之间有一条流量米，在两个工厂之间有一条流量为每天为每天200万立方米的支流。万立方米的支流。化工厂化工厂1每天排放含有某种有害物质的工业污水每天排放含有某种有害物质的工业污水2万立方米，化工厂万立方米，化工厂2每天每天排放的工业污水为排放的工业污水为1.4万立方米。从化工厂万立方米。从化工厂1排出的污水流到化工厂排出的污水流到化工厂2前，前，有有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于可自然净

5、化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本处理污水的成本是是1000元元/万立方米万立方米,化工厂化工厂2处理污水的成本是处理污水的成本是800元元/万立方米万立方米。问。问:在满足环保要求的条件下，每厂各应处理多少工业污水，在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。使两个工厂处理工业污水的总费用最小。图1-1湖州师范学院商学院湖州师范学院商学院62022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线

6、性规划的提出与模型练习题1建模型之前的分析和计算设设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米100027004128021000250022211)x.()x(.)x(工厂后的水质要求：经第工厂前的水质要求：经第湖州师范学院商学院湖州师范学院商学院72022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型练习题1得到本问题的数学模型为：0,4.126.18.018001000min212121121xxxxxxxxxz约束条件目标函数湖州师范学院商学院湖州师范学院商学院82022年12月16日第二讲第二

7、讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型练习题2 练习题练习题2 某昼夜服务的公交线路每天各时间段内所需司机和某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表乘务人员数如表1-21-2所示。设司乘人员在各时间段一开始时上所示。设司乘人员在各时间段一开始时上班，并连续工作班，并连续工作8 8小时，问该公交线路怎样安排司乘人员，既小时，问该公交线路怎样安排司乘人员，既能满足工作需要，又配备最少的司机和乘务人员？试列出该能满足工作需要，又配备最少的司机和乘务人员？试列出该问题的线性规划模型。问题的线性规划模型。班次时间所需人数班次时间所需人数16：00-

8、10：0060418：00-22：0050210：00-14：0070522：00-2：0020314：00-18：006062：00-6：0030表1-2 练习题2数据资料湖州师范学院商学院湖州师范学院商学院92022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型2、线性规划的一般数学模型一般线性规划数学模型有三个要素：一般线性规划数学模型有三个要素：（1 1）决策变量集合：）决策变量集合：，通常要求非负；，通常要求非负；),(21nxxx（2 2）约束条件集合，决策变量集的一组线性等式或不等式；）约束条件集合，决策变量集的一组线性等式或

9、不等式；（3 3）目标函数：）目标函数：，通常求最大值或最小值。，通常求最大值或最小值。),(21nxxxfz湖州师范学院商学院湖州师范学院商学院102022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型2、线性规划的一般数学模型线性规划模型的一般形式为：线性规划模型的一般形式为：).(x,x,xb),(xaxaxa).(b),(xaxaxab),(xaxaxa).(xcxcxczmax(min)nmnmmmnnnnnn310211121221122222121112121112211约束条件目标函数湖州师范学院商学院湖州师范学院商学院11

10、2022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型2、线性规划的一般数学模型决策变量及各类系数之间的对应关系：决策变量及各类系数之间的对应关系：nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21价值系数动活资源决策变量湖州师范学院商学院湖州师范学院商学院122022年12月16日第二讲第二讲 线性规划基础线性规划基础一、线性规划的提出与模型一、线性规划的提出与模型总结：总结：线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。其组成部分：其组成部分：1、一个反映

11、决策目标的目标函数；2、一组线性等式或不等式的约束方程；3、限制决策变量取值范围的非负约束。湖州师范学院商学院湖州师范学院商学院132022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。0,1241648232max21212121xxxxxxxxz湖州师范学院商学院湖州师范学院商学院142022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法表示一簇平行线33212zxx2132xxzmax目标值在（目标值在（4 4，2 2）点，达到最大值）点，

12、达到最大值1414湖州师范学院商学院湖州师范学院商学院152022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法几种特殊情况：几种特殊情况：（1）无穷多最优解：）无穷多最优解：max z=2x1+4x2 将目标函数改为：将目标函数改为：max z=2xmax z=2x1 1+4x+4x2 2 当目标方程直线与某一约束直线平行时，最优值不唯一当目标方程直线与某一约束直线平行时，最优值不唯一！湖州师范学院商学院湖州师范学院商学院162022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法几种特殊情况：几种特殊

13、情况：（2）无界解：有可行域，但无最优解；）无界解：有可行域，但无最优解；ox,xxxxxxxzmax21211212424221xx221 xx湖州师范学院商学院湖州师范学院商学院172022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法几种特殊情况：几种特殊情况：（3）无可行解：无可行域；）无可行解：无可行域；当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例例如，如果在例1的数学模型中增加一个约束条件的数学模型中增加一个约束条件:思考：会出现什么结果？思考：会出现什么

14、结果？85.121xx湖州师范学院商学院湖州师范学院商学院182022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法（3）无可行解：无可行域；）无可行解：无可行域；85.121xx增加的约束条件结论：该问题的可行域为空集，即无可行解，结论：该问题的可行域为空集，即无可行解，湖州师范学院商学院湖州师范学院商学院192022年12月16日第二讲第二讲 线性规划基础线性规划基础二、线性规划的图解法二、线性规划的图解法结论：结论：1、当线性规划问题的可行域非空时，它是有界或无界凸多边形；2、若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到。推广：

15、无穷多最优解的情况？推广：无穷多最优解的情况？思考：图解法给人们的启示是什么？思考：图解法给人们的启示是什么？湖州师范学院商学院湖州师范学院商学院202022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念1、线性规划的标准型0,aczmax21221122222121112121112211nnnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxxcxcx约束条件：目标函数：湖州师范学院商学院湖州师范学院商学院212022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准

16、型与解的概念1、线性规划的标准型用向量形式表示的标准形式线性规划：用向量形式表示的标准形式线性规划：njbbbbaaaPxxxXcccCnjxbxPCXzmmjjjjnnjnjjj,2,1;,2,1,0max212121211约束条件：目标函数：湖州师范学院商学院湖州师范学院商学院222022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念1、线性规划的标准型用矩阵形式表示的标准形式线性规划：用矩阵形式表示的标准形式线性规划：TnnmnmnxxxXPPPaaaaAXbAXCXz,bbb000;,0max21m1211111决策变量向量

17、：；资源向量：零向量：系数矩阵：约束条件：目标函数：湖州师范学院商学院湖州师范学院商学院232022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念2、化一般模型为标准模型(1)若要求目标函数实现最小化，即min min z z=CXCX，则只需将目标函数最小化变换求目标函数最大化，即令z z=z z，于是得到max max z z=CXCX。kkkxxx0,kkxx(2)(2)约束条件为不等式。分两种情况讨论：约束条件为不等式。分两种情况讨论：若约束条件为若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，型不等式，则可在不

18、等式左端加入非负松弛变量，把原把原“”型不等式变为等式约束；型不等式变为等式约束；(3)(3)若存在取值无约束的变量若存在取值无约束的变量x xk k,可令可令:若约束条件为若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量也称松弛变量)，把不等式约束条件变为等式约束。，把不等式约束条件变为等式约束。湖州师范学院商学院湖州师范学院商学院242022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念2、化一般模型为标准模型练习题：练习题：例例3 将例将例1的数学模型化

19、为标准形式的线性规划。的数学模型化为标准形式的线性规划。0,1241648232max21212121xxxxxxxxz0,1241648243215241321xxxxxxxxxxxx5432100032maxxxxxxz湖州师范学院商学院湖州师范学院商学院252022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念2、化一般模型为标准模型练习题：练习题：为无约束3213213213213210533732x;x,xxxxxxxxxxxxxzmin(1)(1)用用x x4 4 x x5 5替换替换x x3 3，其中其中x x4 4，

20、x x5 500；(2)(2)在第一个约束不等式左端加入在第一个约束不等式左端加入松弛变量松弛变量x x6 6；(3)(3)在第二个约束不等式左端减去在第二个约束不等式左端减去剩余变量剩余变量x x7 7；(4)(4)令令z z=z z，将求，将求min min z z 改为求改为求max max z z湖州师范学院商学院湖州师范学院商学院262022年12月16日0,5)(232)(7)(00)(32max7654214217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型

21、与解的概念2、化一般模型为标准模型为无约束3213213213213210533732x;x,xxxxxxxxxxxxxzmin湖州师范学院商学院湖州师范学院商学院272022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念3、线性规划问题解的概念)(n,j,x)(m,i,bxa)(xczmaxjnjijijnjjj6121051214111 满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解可行解，其中使目标函数达到最大值的可可行解行解称为最优解。最优解。湖州师范学院商学院湖州师范学院商学院

22、282022年12月16日为基变量。为基向量，为线性规划问题的基。称阶非奇异子矩阵中的是系数矩阵),2,1(x),2,1(P,B0BAjj21212222111211mjmjPPPaaaaaaaaaBmmBmmmmmmm第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念3、线性规划问题解的概念湖州师范学院商学院湖州师范学院商学院292022年12月16日第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念3、线性规划问题解的概念mmmmmmmPPPaaaaaaaaaB,21212222111211nnmmmm

23、xpxpbxpxpxp112211则上式可以转化为：021nmmxxx若令：即为基本解。则Tmxx)0,0,(xX21湖州师范学院商学院湖州师范学院商学院302022年12月16日 满足非负条件的基解，称为基可行解满足非负条件的基解，称为基可行解.基可行解基可行解的非零分量的数目不大于的非零分量的数目不大于m m，并且都是非负的。，并且都是非负的。第二讲第二讲 线性规划基础线性规划基础三、线性规划标准型与解的概念三、线性规划标准型与解的概念3、线性规划问题解的概念对应于基可行解的基，称为可行基。对应于基可行解的基，称为可行基。mnC 约束方程组约束方程组(1-5)(1-5)具有的基解的数目最多

24、是具有的基解的数目最多是 个，个，一般基可行解的数目要小于基解的数目。一般基可行解的数目要小于基解的数目。思考：例中基解可以有多少个？思考：例中基解可以有多少个？湖州师范学院商学院湖州师范学院商学院312022年12月16日第二讲第二讲 线性规划基础线性规划基础线性规划问题各种解之间的关系线性规划问题各种解之间的关系三、线性规划标准型与解的概念三、线性规划标准型与解的概念湖州师范学院商学院湖州师范学院商学院322022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论1、凸集、凸组合与顶点 设设S是是n维欧氏空间的一点集，若任意两点维欧氏空间的一点

25、集，若任意两点X(1)S，X(2)S的连线上的所有点的连线上的所有点X(1)+(1)X(2)S，(01)，则称则称K为凸集。为凸集。湖州师范学院商学院湖州师范学院商学院332022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论1、凸集、凸组合与顶点是凸集。例：试证明点集,0,SnmnmRXRbMAXbAXX是凸集。即所以有：故：又则有：，记，又设证明SS,X0)1(;0)1(,0,0,0)1()1(A(AX,)1(10,X:212121212121XXXXXbAXAXXXXXXSX从直观上讲，凸集没有凹入部分，其内部没有空洞。从直观上讲，凸集没

26、有凹入部分，其内部没有空洞。任何两个凸集的交集是凸集。任何两个凸集的交集是凸集。湖州师范学院商学院湖州师范学院商学院342022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论1、凸集、凸组合与顶点 设设X X(1)1)，X X(2)(2)，X X(k k)是是n n维欧氏空间维欧氏空间R Rn n中的中的k k个点。若存个点。若存在在 1 1，2 2，k k，且，且00 i i1,1,（i i=1,2,=1,2,，k k）且）且 使使 X X=1 1X X(1)(1)+2 2X X(2)(2)+k kX X(k k)则称则称X X为为X X(1

27、)(1)，X X(2)(2)，X X(k(k)的一个凸组合（当的一个凸组合（当0 0 i i1 1时，时，称为严格凸组合）。称为严格凸组合）。kii11湖州师范学院商学院湖州师范学院商学院352022年12月16日 设设K K是凸集，是凸集，X XK K；若；若X X不能用不同的两点不能用不同的两点X X(1)(1)K K和和X X(2)(2)K K的线性组合表示为的线性组合表示为 X X=XX(1)(1)+(1+(1)X X(2)(2)，(0(0 1)1)则称则称X X为为K K的一个顶点的一个顶点(或极点或极点)。第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基

28、本理论1、凸集、凸组合与顶点思考：圆有没有顶点，如果有，有多少个？思考：圆有没有顶点，如果有，有多少个？湖州师范学院商学院湖州师范学院商学院362022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论2、线性规划基本定理 定理定理1 若线性规划问题存在可行域，则其可行域 是凸集。njjjjxbxPXD10,湖州师范学院商学院湖州师范学院商学院372022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论2、线性规划基本定理 引理引理 1 线性规划问题的可行解线性规划问题的可行解X X=(=(x x1

29、1,x x2 2,，x xn n)T T为基可行为基可行解的充要条件是：解的充要条件是：X X的正分量所对应的系数列向量是线的正分量所对应的系数列向量是线性独立的。性独立的。证证:(1)必要性由基可行解的定义可知。(2)充分性若向量P1，P2，Pk线性独立，则必有 km；当 k=m 时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的基可行解。当 km 时，则一定可以从其余的列向量中取出 m-k 个与 P1，P2，Pk 构成最大的线性独立向量组，其对应的解恰为 X，所以根据定义它是基可行解。湖州师范学院商学院湖州师范学院商学院382022年12月16日 定理定理2 2 线性规划问

30、题的基可行解线性规划问题的基可行解X X对应于可行域对应于可行域D D的顶的顶点。点。证：不失一般性，假设基可行解证：不失一般性，假设基可行解X X的前的前m m个分量为正。个分量为正。故故 现分两步来讨论，分别用反证法。现分两步来讨论，分别用反证法。mjjjbxP1第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论2、线性规划基本定理湖州师范学院商学院湖州师范学院商学院392022年12月16日 (1)(1)若若X X不是基可行解，则它一定不是可行域不是基可行解，则它一定不是可行域D D的顶点。的顶点。根据引理根据引理1 1，若，若X X不是基可行解，则其正分

31、量所对应的系数不是基可行解，则其正分量所对应的系数列向量列向量P P1 1，P P2 2，P Pm m线性相关，即存在一组不全为零的数线性相关，即存在一组不全为零的数 i i,i i=1,2,=1,2,m m，使得，使得 1 1P P1 1+2 2P P2 2+m mP Pm m=0 (1-9)=0 (1-9)用一个数用一个数 0 0乘乘(1-9)(1-9)式再分别与式再分别与(1-8)(1-8)式相加和相减，得式相加和相减，得 (x x1 1 1 1)P P1 1+(+(x x2 2 2 2)P P2 2+(+(x xm m m m)P Pm m=b b (x x1 1+1 1)P P1 1

32、+(+(x x2 2+2 2)P)P2 2+(+(x xm m+m m)P Pm m=b b 第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论 定理定理2 线性规划问题的基可行解线性规划问题的基可行解X对应于可行域对应于可行域D的顶点。的顶点。湖州师范学院商学院湖州师范学院商学院402022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论 定理定理2 线性规划问题的基可行解线性规划问题的基可行解X对应于可行域对应于可行域D的顶点。的顶点。RXX),2,1(0),(21X)0,0),(,),(),(;)0,0),(

33、,),(),(,XX(2)1(2)1()2()1(2211)2(2211)1(2)(1)的顶点。不是可行域义可知：是可行解。根据顶点定、也就是说充分小时，可以保证当连线的中点。、是即可以得到这里：、现在取点）（XmixXXXXXxxxXxxxXiiTmmTmm(1)若若X不是基可行解，则它一定不是可行域不是基可行解，则它一定不是可行域D的顶点。的顶点。湖州师范学院商学院湖州师范学院商学院412022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论 定理定理2 线性规划问题的基可行解线性规划问题的基可行解X对应于可行域对应于可行域D的顶点。的顶点。

34、（2 2）若）若X X不是可行域不是可行域D D的顶点，则它一定不是基可行解。的顶点，则它一定不是基可行解。因因X X 不是可行域不是可行域D D的顶点，故在可行域的顶点，故在可行域D D中可找到不同的两点中可找到不同的两点 X X(1)(1)=(=(x x1 1(1)(1),x x2 2(1)(1),x xn n(1)(1)T T X X(2)(2)=(=(x x1 1(2)(2),x x2 2(2)(2),x xn n(2)(2)T T 使得使得 X X=XX(1)(1)+(1+(1)X X(2)(2)，0 0 1 1 设设X X是基可行解，对应的向量组是基可行解，对应的向量组P P1 1

35、P Pm m线性独立，故当线性独立，故当j jm m时，时，有有x xj j=x xj j(1)(1)=x xj j(2)(2)=0=0。湖州师范学院商学院湖州师范学院商学院422022年12月16日由于由于X(1)，X(2)是可行域的两点，因而满足：是可行域的两点，因而满足：第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论 定理定理2 线性规划问题的基可行解线性规划问题的基可行解X对应于可行域对应于可行域D的顶点。的顶点。（2 2）若）若X X不是可行域不是可行域D D的顶点，则它一定不是基可行解。的顶点，则它一定不是基可行解。mjmjjjjjbxPbxP1

36、121与将两式相减，得：将两式相减，得：mjjjjxxP1210 因因X X(1)(1)X X(2)(2)，所以上式中的系数不全为零，故向量组，所以上式中的系数不全为零，故向量组P P1 1,P P2 2,，P Pm m线性相关，与假设矛盾，即线性相关，与假设矛盾，即X X不是基可行解。不是基可行解。湖州师范学院商学院湖州师范学院商学院432022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论 定理定理 3 3 若可行域有界，则线性规划问题的目标函数一定可若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。以在其可行域的顶

37、点上达到最优。证：证：设设X X(1),(1),X X(2)(2)，X X(k k)是可行域的顶点，若是可行域的顶点，若X X(0)(0)不是顶点，不是顶点，且目标函数在且目标函数在X X(0)(0)处达到最优处达到最优z z*=CXCX(0)(0)(标准型是标准型是z z=max=max z z)。因因X X(0)(0)不是顶点，所以它可以用不是顶点，所以它可以用D D的顶点线性表示为的顶点线性表示为 2、线性规划基本定理 kikiiiiiixX1101,0,湖州师范学院商学院湖州师范学院商学院442022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划

38、的基本理论2、线性规划基本定理 定理定理 3 3 若可行域有界，则线性规划问题的目标函数一定可若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。以在其可行域的顶点上达到最优。代入目标函数得：代入目标函数得：kikiiiiiCXXCCX110在所有的顶点中必然能找到某一个顶点在所有的顶点中必然能找到某一个顶点X X(m)(m)，使，使CXCX(m m)是所有是所有CXCX(i i)中最大者。并且将中最大者。并且将X X(m m)代替代替(1-10)(1-10)式中的所有式中的所有X X(i i)，得到：，得到：mkimikiiiCXCXCX11湖州师范学院商学院湖州师范学

39、院商学院452022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论2、线性规划基本定理 定理定理 3 3 若可行域有界，则线性规划问题的目标函数一定可若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。以在其可行域的顶点上达到最优。由此得到由此得到 CXCX(0)(0)CXCX(m m)根据假设根据假设CXCX(0)(0)是最大值，所以只能有是最大值，所以只能有 CXCX(0)(0)=CXCX(m m)即目标函数在顶点即目标函数在顶点X X(m m)处也达到最大值。处也达到最大值。结论：结论：有时，目标函数可能在多个顶点处

40、达到最大，这时有时，目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，这时线性规划问题有在这些顶点的凸组合上也达到最大值，这时线性规划问题有无限多个最优解。并且，线性规划不排斥在非顶点处取得最无限多个最优解。并且，线性规划不排斥在非顶点处取得最优解。优解。湖州师范学院商学院湖州师范学院商学院462022年12月16日精品课件精品课件！湖州师范学院商学院湖州师范学院商学院472022年12月16日精品课件精品课件！湖州师范学院商学院湖州师范学院商学院482022年12月16日第二讲第二讲 线性规划基础线性规划基础四、线性规划的基本理论四、线性规划的基本理论结论结论1 1、线性规划问题的可行域是凸集（定理、线性规划问题的可行域是凸集（定理1 1）；）；2 2、凸集的每个顶点对应一个基可行解（定理、凸集的每个顶点对应一个基可行解（定理2 2）；）；3 3、若线性规划问题有最优解，必在某顶点上得到。、若线性规划问题有最优解，必在某顶点上得到。