《第一章-线性规划与单纯形法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第一章-线性规划与单纯形法ppt课件.ppt（253页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一章第一章 线性规划与单纯形法线性规划与单纯形法第一节第一节线性规划问题及其数学模型线性规划问题及其数学模型第二节第二节线性规划问题的几何意义线性规划问题的几何意义第三节第三节单纯形法单纯形法第四节第四节单纯形法的计算步骤单纯形法的计算步骤第五节第五节单纯形法的进一步讨论单纯形法的进一步讨论第六节第六节应用举例应用举例1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节线性
2、规划问题及其数学模型线性规划问题及其数学模型n一、一、问题的提出问题的提出n二、二、图解法图解法n三、三、线性规划问题的标准形式线性规划问题的标准形式n四、四、线性规划问题的解的概念线性规划问题的解的概念2经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n线性规划是运筹学的一个重要分支。线性规划是运筹学的一个重要分支。n线性规划在理论上比较成熟，在实用中的应用日益广泛与线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和深入。特别是在电子计算机能处理成千上万个约束条
3、件和决策变量的线性规划问题之后，线性规划的适用领域更为决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。广泛了。n从解决技术问题的最优化设计到工业、农业、商业、交通从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。用。它已是现代科学管理的重要手段之一。n解线性规划问题的方法有多种，以下仅介绍解线性规划问题的方法有多种，以下仅介绍单纯形法单纯形法 。3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购
4、买商品的价款或接受服务的费用一、问题的提出一、问题的提出例例1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。资源资源 产产 品品拥有量拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg 每生产一件产品每生产一件产品可获利可获利2 2元，每生产一件产品元，每生产一件产品可获利可获利3 3元，问应如何安排计划使该工厂获利最多元，问应如何安排计划使该工厂获利最多?4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用利润 z=2x1
5、+3x25经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用本问题的数学模型为本问题的数学模型为:这就是一个最简单的线性规划模型。这就是一个最简单的线性规划模型。6经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例2建立LP数学模型某家电厂家利用现有资源生产两种某家电厂家利用现有资源生产两种 产品，有关数据如下表：产品，有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时
6、产品产品产品产品D如何安排生如何安排生产产，使，使获获利最多？利最多？7经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量8经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的是非负且连续的；l都有关于各种资源和资源使用情况的技术数据，创造新
7、价值的数据；l存在可以量化的约束条件，这些约束条件可以用一组线线性性等式或线性等式或线性不等式来表示;l都有一个达到某一目标的要求，可用决策变量的线线性性函函数数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。上述两个问题具有的共同特征：上述两个问题具有的共同特征：9经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性规划模型的一般形式线性规划模型的一般形式目目标标函数函数满满足足约约束束条件条件价价值值系系数数技技术术（工（工艺艺）系数）系数限限额额系系数（数（资资源）源）非非负约负约
8、束条件束条件10经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二、图解法二、图解法例例1是一个二维线性规划问题，因而可用作图法直观地进行求是一个二维线性规划问题，因而可用作图法直观地进行求解。解。11经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4x1=164x2=12x1+2x2=8x1x24843012经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务
9、的费用4x1=164x2=12x1+2x2=8x1x248430Q1可行域可行域13经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用目标值在（目标值在（4，2）点，达到最大值）点，达到最大值144x1=164x2=12x1+2x2=8x1x248430Q2(4,2)Q1可行域可行域x1+2x2=84x1=1614经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图解法求解步骤图解法求解步骤n n由全部约束条件作图求出可行域；由全部约束
10、条件作图求出可行域；n n作目标函数等值线，确定使目标函数最作目标函数等值线，确定使目标函数最优的移动方向；优的移动方向；n n平移目标函数的等值线，找出最优点，平移目标函数的等值线，找出最优点，算出最优值。算出最优值。15经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用练习：用图解法求解练习：用图解法求解目标函数目标函数MaxZ=2x1+x2约束条件约束条件5x2 156x1+2x2 24x1+x2 5 x1、x2 0 016经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿
11、的金额为消费者购买商品的价款或接受服务的费用9876543210|123456789x1x2x1+x2=5目标函数目标函数目标函数目标函数MaxMaxZ Z=2=2x x1 1+x x2 2约束条件约束条件约束条件约束条件5 5x x2 2 151566x x11+2 2x x2 2 2424x x11+x x2 2 55 x x1 1、x x2 2 0 0 0 06x1+2x2=245x2=15v图解法图解法12111017经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9876543210|123456789
12、x1x2x1+x2=5目标函数目标函数MaxZ=2x1+x2约束条件约束条件约束条件约束条件5 5x x2 2 151566x x11+2 2x x2 2 2424x x11+x x2 2 55 x x1 1、x x2 2 0 0 0 06x1+2x2=245x2=15v图解法图解法121110可行域可行域18经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9876543210|123456789x1x2x1+x2=5目标函数目标函数目标函数目标函数MaxMaxZ Z=2=2x x1 1+x x2 2约束条件约束
13、条件约束条件约束条件5 5x x2 2 151566x x11+2 2x x2 2 2424x x11+x x2 2 55 x x1 1、x x2 2 0 0 0 06x1+2x2=245x2=15121110 x2=-2x16x1+2x2=24 x1+x2=5最优解最优解(3.5,1.5)目标值在（目标值在（3.5，1.5）点，达到最大值）点，达到最大值8.519经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（1）无穷多最优解无穷多最优解(多重最优解多重最优解)（2）无界解无界解（3）无可行解无可行解上例中求
14、解得到问题的最优解是惟一的通过图解法，可观察到一般线性规划的解还可能出现一下几种情况：20经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用无无穷穷多最多最优优解（多重最解（多重最优优解）解）4x1=164x2=12x1+2x2=8x1x248430可行域可行域Q2Q3MaxMaxZ Z=2=2x x1 1+4 4x x2 221经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4x1=16x1x240无界解（无界解（a）可行域22经营
15、者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用无界解（无界解（b）23经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 当存在相互矛盾的约束条件时，线性规划问题的可行域为空集，即无可行可行域为空集，即无可行解，也不存在最优解解，也不存在最优解。无可行解无可行解4x1=164x2=12x1+2x2=8x1x230原可行原可行域域8增加一个新的增加一个新的约约束条件束条件24经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿
16、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用可行域和解有以下几种情况可行域和解有以下几种情况(a)可行域可行域有界有界有唯一最优解有唯一最优解(b)可行域可行域有界有界有无穷多最优解有无穷多最优解25经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(c)可行域可行域无界无界有唯一最优解有唯一最优解(d)可行域可行域无界无界有无穷多最优解有无穷多最优解(e)可行域可行域无界无界无最优解无最优解(无界解无界解)26经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加
17、赔偿的金额为消费者购买商品的价款或接受服务的费用(f)可行域为可行域为空集空集无可行解无可行解27经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LPLP问题问题有可行解有可行解有最优解有最优解唯一解唯一解无穷多解无穷多解无最优解（可行域为无最优解（可行域为无界无界,无界解）无界解）无可行解（无解，可行域为空集）无可行解（无解，可行域为空集）若若LP问题问题有最有最优优解，解，则则要么最要么最优优解唯一，要么有无解唯一，要么有无穷穷多最多最优优解解28经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔
18、偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用可行域是有界或无界的凸多边形，凸多边形的顶点个数是可行域是有界或无界的凸多边形，凸多边形的顶点个数是可行域是有界或无界的凸多边形，凸多边形的顶点个数是可行域是有界或无界的凸多边形，凸多边形的顶点个数是有限的。有限的。有限的。有限的。若线性规划问题存在最优解，它一定可以在可行域的顶点若线性规划问题存在最优解，它一定可以在可行域的顶点若线性规划问题存在最优解，它一定可以在可行域的顶点若线性规划问题存在最优解，它一定可以在可行域的顶点得到。得到。得到。得到。若两个顶点同时得到最优解，则其连线上的所有点都是最若两个顶点同时得到最优解，
19、则其连线上的所有点都是最若两个顶点同时得到最优解，则其连线上的所有点都是最若两个顶点同时得到最优解，则其连线上的所有点都是最优解。优解。优解。优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即解题思路：找出凸集的顶点，计算其目标函数值，比较即解题思路：找出凸集的顶点，计算其目标函数值，比较即解题思路：找出凸集的顶点，计算其目标函数值，比较即得。得。得。得。29经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用三、线性规划问题的标准形式三、线性规划问题的标准形式在标准形式中规定约束条件的右端项bi030经营者提
20、供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用31经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用向量形式表示的标准形式线性规划用向量形式表示的标准形式线性规划线性规划问题的几种表示形式线性规划问题的几种表示形式32经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用矩阵形式表示的标准形式线性规划用矩阵形式表示的标准形式线性规划33经营者提供商品或者服务有欺
21、诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(1)若要求目若要求目标标函数函数实现实现最小化，最小化，即min z=CX，则只需将目标函数最小化变换求目标函数最大化，即令z=z，于是得到max z=CX。(2)约约束条件束条件为为不等式不等式。分两种情况讨论：l若约束条件为“”型不等式，则可在不等式左端加入非加入非负负松松弛弛变变量量，把原“”型不等式变为等式约束；l若约束条件为“”型不等式，则可在不等式左端减去一个非减去一个非负负剩余剩余变变量量(也称松弛也称松弛变变量量)，把不等式约束条件变为等式约束。(3)若存在取若存在取值值无
22、无约约束的束的变变量量xk,可令 如何将一般线性规划转化为标准形式的线性规划如何将一般线性规划转化为标准形式的线性规划34经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例3将例将例1的数学模型化为标准形式的线性规划。的数学模型化为标准形式的线性规划。例例1的数学模型在加入了松驰变量后变为的数学模型在加入了松驰变量后变为35经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例4将下述线性规划问题化为标准形式线性规划将下述线性规划问
23、题化为标准形式线性规划(1)用x4x5替换x3，其中x4，x50；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z=z，将求min z 改为求max z36经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例4的标准型的标准型37经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用补充补充：当某个变量xj0时,令xj=xj.当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再
24、化为等式，例如约束 将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。38经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用四、线性规划问题解的概念四、线性规划问题解的概念n1.可行解n2.基n3.基可行解n4.可行基39经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（1-4）（1-5）（1-6）一般线性规划问题的标准型：一般线性规划问题的标准型：40经营者提供商品或者服务有欺诈行为的，应当按照消
25、费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定定义义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解可行解；其中使目标函数（1-4）达到最大值的可行解可行解称为最最优优解解。1、可行解、可行解41经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2、基、基A是约束方程组的mn维系数矩阵，其秩为m42经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 B
26、是矩阵是矩阵A中中mm阶非奇异子矩阵（阶非奇异子矩阵（|B|0），则，则称称B是线性规划问题的一个是线性规划问题的一个基基。令令B=(P1,P2,Pm)Pj(j=1,2,m)为为基向量基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量记为记为XB=(x1,x2,xm )T，其余的变量称为其余的变量称为非基非基变量变量，记为，记为 XN=(xm+1,xm+2,xn )T。43经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基令非基变变量量xm+1=xm+2=xn=0线线性性规规划划问题变问
27、题变量的个数等于量的个数等于线线性方程性方程的个数（的个数（m个）个）利用高斯消去法，求出一个解利用高斯消去法，求出一个解X=(x1,x2,xm,0,0)T称称X为为基解（或称基解（或称为为基本解基本解）44经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4x1=164x2=12x1+2x2=8x1x2430Q1Q2Q3Q4Q6Q7Q845经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用满足非非负负条件条件（1-6）的基解，称为基可
28、行解基可行解(或称或称为为基本可基本可行解行解)。基可行解的非零分量的数目非零分量的数目不大于不大于m，并且都是非负的。3、基可行解、基可行解4x1=164x2=12x1+2x2=8x1x2430Q1Q2Q3Q4Q6Q7Q8基可行解基可行解为为可行域的可行域的顶顶点点46经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l对应于基可行解的基，称为可行基可行基。l约束方程组(1-5)具有的基解的数目最多是 个。l一般基可行解的数目要小于基解的数目。l以上提到了几种解的概念，它们之间的关系可用图1-6表明。l说明：当基
29、解中的非零分量的个数小于说明：当基解中的非零分量的个数小于m时，该时，该基解是基解是退化解退化解。在以下讨论时，假设不出现退化。在以下讨论时，假设不出现退化的情况。的情况。4、可行基、可行基47经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 非可行非可行非可行非可行解解解解可行解可行解 基可行解基可行解 基基基基解解解解图图1-6线性规划标准型问题不同解之间的关系线性规划标准型问题不同解之间的关系48经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价
30、款或接受服务的费用 例：求基解、基可行解、最优解。例：求基解、基可行解、最优解。49经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 系数矩阵列向量50经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1基：51经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X1 不是基可行解 52经营者提供商品或者服务有欺诈行为的，应当按照消费者的
31、要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2基：53经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X2 是基可行解 54经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3基：55经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X3 是基可行解 56经营者提供商品或者服务有欺诈
32、行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4基：57经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X4 是基可行解 58经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用5基：59经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X5 不是基可行解 60经
33、营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用6基：61经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X6 是基可行解 62经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7基：63经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解
34、X7 不是基可行解 64经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用8基：65经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用令非基变量 得基解 X8 是基可行解 66经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问1：是否是一个基?否,因为此矩阵不可逆,或者说列向量组线性相关67经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其
35、受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问2：是否是一个基?否,因为此矩阵不可逆,或者说列向量组线性相关68经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用143-200N22308013Y34200414Y44040128Y5800-1612N60321609Y704016-4N800816120Y是否基是否基可行解可行解最优解最优解全部基解：全部基解：69经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n
36、上例中指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基以及基解，如果是基可行解，则计算相应的解的目标函数值。由于基基的的个个数数是是有有限限的的（最多 个），因因此此必必定定可可以以从从有有限限个个基基本可行解中找到最优解。本可行解中找到最优解。70经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4x1=164x2=12x1+2x2=8x1x248430Q1约束直线的交点约束直线的交点基解基解 可行域的顶点可行域的顶点基可行解基可行解Q2Q3Q4Q5Q6Q7Q8143-200NQ7223080YQ
37、3342004YQ24404012YQ15800-1612NQ66032160YQ4704016-4NQ880081612YQ5是否基是否基可行解可行解对应的对应的点解点解71经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节线性规划问题的几何意义线性规划问题的几何意义n一、基本概念一、基本概念n二、几个定理二、几个定理72经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一、一、基本概念基本概念1.1.凸集凸集2.2.凸凸
38、组组合合3.3.顶顶点点73经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定定义义设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)，则称K为凸集。1.凸集凸集凸凸非凸非凸(a)(b)(d)(c)74经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。n从直观上讲，凸集没有凹入部分，其内部没有空洞。n任何两个凸集的交
39、集是凸集，见下图所示：75经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n设X(1)，X(2)，X(k)是n维欧氏空间En中的k个点。若存在1，2，k，且0i1,i=1,2,，k 使 X=1X(1)+2X(2)+kX(k)，成立 则称X为X(1)，X(2)，X(k)的一个凸组合（当0i1时，称为严格凸组合）。2.凸组合凸组合76经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n设K是凸集，XK；若X不能用不同的两点X(1)K和X(
40、2)K的线性组合表示为：X=X(1)+(1)X(2)，(01)则称X为K的一个顶点(或极点)。3.顶点顶点凸集凸集顶点77经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二、几个定理二、几个定理n定理定理1 若线性规划问题存在可行域，则其可行域 是凸集凸集。78经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定定理理1的的证证明明：只只需需证证明明D中中任任意意两两点点连连线线上上的的点点必必然然在在D内即可。内即可。设X(1)、
41、X(2)是D内的任意两点；且X(1)X(2)。AX(1)=A X(2)=bAX=AX(1)+(1-)X(2)AX=AX(1)+A X(2)-AX(2)AX=b+b-b=bXD令X为X(1),X(2)连线上的任意一点，即 X=X(1)+(1-)X(2)(01)将它代入约束条件，得到D是凸集79经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n引理引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。证证:(1)必要性必要性 由基可行解的定义可知。
42、(2)充分性充分性 若向量P1，P2，Pk线性独立，则必有km；当k=m时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的基可行解。当km时，则一定可以从其余的列向量中取出m-k个与P1，P2，Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解。80经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用定理定理2 线性规划的可行解X是基可行解的充分必要条件是X是可行域D的顶点。(1)充分性充分性：X是可行域D的顶点 X是基可行解。逆否命逆否命题题 若若X不是基可行解，不是基可行解，
43、则则它一定不是可行域它一定不是可行域D的的顶顶点点。81经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 根据引理1，若若X不是基可行解不是基可行解，则则其正分量所其正分量所对应对应的系数的系数列向量列向量P1，P2，Pm线线性相关性相关，即存在一组不全为零的数i,i=1,2,m，使得 1P1+2P2+mPm=0 (1-9)用一个数0乘(1-9)式再分别与(1-8)式相减和相加，得：(x11)P1+(x22)P2+(xm m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 不妨设不妨设X的前的
44、前m个分量为正个分量为正,则有则有P1 x1+Pm x m=b (1-8)82经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 现构造两个点现构造两个点X(1),X(2)如下如下:另一方面，当另一方面，当充分小时，可保证充分小时，可保证则则X(1),X(2)D,且且X1/2 X(1)+1/2 X(2)所以所以 X 不是不是D的顶点的顶点.X是是 X(1)，X(2)的中点的中点若若X不是基可行解，不是基可行解，则则它一定不是可行域它一定不是可行域D的的顶顶点点。83经营者提供商品或者服务有欺诈行为的，应当按照消费者
45、的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 因X不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1)X(2)，01 （2）必要性必要性：X是基可行解 X是可行域D的顶点。逆否命逆否命题题 若X不是可行域D的顶点，则它一定不是基可行解。84经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 假假设设X是是基基可可行行解解，X的前m个分量为正，对应的向向 量
46、量 组组 P1Pm线线 性性 独独 立立，故 当 j m时，有xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的两点，因而满足将两式相减，得 因X(1)X(2)，所以上式中的系数不全为零，故向量向量组组P1,P2,，Pm线线性相关性相关，与假与假设设矛盾，即矛盾，即X不是基不是基可行解。可行解。若若X不是可行域不是可行域D的的顶顶点，点，则则它一定不是基可行解。它一定不是基可行解。85经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n引理引理2 若K是有界凸集有界凸集，则任何一点XK可表示为K的顶
47、点的凸组合。本本引引理理的的证证明明从从略略，用用以以下下例例子子说说明明本本引引理的理的结论结论。n例例5 设X是三角形中任意一点，X(1)，X(2)和X(3)是三角形的三个顶点，试试用三个用三个顶顶点的坐点的坐标标表示表示X(见图1-8)图1-8x x1 1x x2 2X X(1)(1)X X(2)(2)X X(3)(3)X X86经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解：解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上一点X。因为X是X(1)、X(3)连线上一点，
48、故可用X(1)、X(3)线性组合表示为：X=X(1)+(1)X(3)01 又因X是X与X(2)连线上的一个点，故X=X+(1 )X(2)01 X X 图1-8x x1 1x x2 2X X(1)(1)X X(2)(2)X X(3)(3)X X87经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 将X的表达式X=X(1)+(1)X(3)代入式X=X+(1 )X(2)得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1 )X(3)+(1)X(2)令 1=,2=(1 ),3=(1 )，得到X=1X(1)+2
49、X(2)+3X(3)ii=1,0i1X X 图1-8x x1 1x x2 2X X(1)(1)X X(2)(2)X X(3)(3)X X88经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理定理 3 若可行域有界若可行域有界，则线则线性性规规划划问题问题的目的目标标函数一定可函数一定可以在其可行域的以在其可行域的顶顶点上达到最点上达到最优优。证证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优 z*=CX(0)(标准型是z*=max z)。因X(0)不是顶点，
50、所以它可以用D的顶点的凸组合表示。代入目标函数得:89经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替 中的所有X(i)，得到由此得到 CX(0)CX(m)n根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。90经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用定理定理4：目标函数可能