《运筹学(2).ppt》由会员分享，可在线阅读，更多相关《运筹学(2).ppt（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 3 章 线性规划模型的单纯形法3.1 线性规划数学模型的结构及特征3.2 线性规划模型的标准形式3.3 基、基本解、基本可行解3.4 单纯形表的数学原理3.5 从一个基本可行解转化为相邻的基本可行解3.6 最优性检验和解的判别3.7 单纯形表法3.8 人工变量法和两阶段法3.9 计算机软件QM求解线性规划模型的一般形式为线性规划模型的一般形式为3.1 3.1 线性规划数学模型的结构及特征线性规划数学模型的结构及特征 线性规划模型的特征：线性规划模型的特征：一组决策变量，一组一组决策变量，一组一组决策变量，一组一组决策变量，一组约束条件和一个目标函数，目标函数和约束条件约束条件和一个目标函数
2、，目标函数和约束条件约束条件和一个目标函数，目标函数和约束条件约束条件和一个目标函数，目标函数和约束条件都是线性的。都是线性的。都是线性的。都是线性的。3.2 3.2 线性规划模型的标准形式线性规划模型的标准形式3.2.1 3.2.1 标准形式标准形式标准形式定义为：标准形式定义为：标准形式模型的标准形式模型的标准形式模型的标准形式模型的特征：特征：特征：特征：1.1.1.1.约束条件为线约束条件为线约束条件为线约束条件为线性等式；性等式；性等式；性等式；2.2.2.2.所有变量全部所有变量全部所有变量全部所有变量全部大于等于大于等于大于等于大于等于0 0 0 0；3.3.3.3.右端常数项大
3、右端常数项大右端常数项大右端常数项大于等于于等于于等于于等于0 0 0 0；4.4.4.4.目标函数求最目标函数求最目标函数求最目标函数求最大值。大值。大值。大值。简写为简写为 用矩阵表示用矩阵表示用矩阵表示用矩阵表示CC价值向量价值向量bb资源向量资源向量XX决策向量决策向量 用向量表示用向量表示用向量表示用向量表示线性规划模型的一般形式为线性规划模型的一般形式为3.2.2 一般形式的线性规划模型变换为标准形式一般形式的线性规划模型变换为标准形式线性规划模型的标准形式为线性规划模型的标准形式为1.1.1.1.目标函数为求极小值，即为：因为求minz等价于求max(-z)，令z=-z，即转换为
4、：约束方程为约束方程为在在“”左端加入一个非负松弛变量，把原左端加入一个非负松弛变量，把原“”的不等式变为等式。的不等式变为等式。2.约束条件为不等式，约束方程为约束方程为在在“”左端减去一个非负剩余变量，把原左端减去一个非负剩余变量，把原“”的不等式变为等式。的不等式变为等式。.右端项右端项右端项右端项b b b bi i i i0000时，只需将等式两端同乘（时，只需将等式两端同乘（时，只需将等式两端同乘（时，只需将等式两端同乘（-1-1-1-1），则），则），则），则右端项必大于零右端项必大于零右端项必大于零右端项必大于零 4.4.决策变量无非负约束决策变量无非负约束,设设x xj j没
5、有非负约束，没有非负约束，若若x xj j00，可令可令x xj j=-=-x xj j，则，则x xj j00；若若x xj j为自由变量，即为自由变量，即x xj j可为任意实数，可为任意实数，可令可令x xj j=x xj j-x-xj j，且且x xj j,x,xj j005.5.决策变量决策变量x xj j有上界或者下界，即有上界或者下界，即x xj juu或者或者x xj jvv若若x xj juu，可令，可令x xj j=x xj j-u u，x xj j00；若若x xj jvv，可令可令x xj j=v-xv-xj j，x xj j00；【例例3-23-2】将下面的线性规划问
6、题化为标准型：将下面的线性规划问题化为标准型：将下面的线性规划问题化为标准型：将下面的线性规划问题化为标准型：（2）对于）对于“”约束约束 9x+3y 360，引入松引入松弛变量弛变量 x1，得到得到（3）对于）对于“”约束约束 3x+10y 300，引入引入剩余变量剩余变量 x2，得到得到解解（1）对目标函数，令）对目标函数，令则则（4）对于）对于 y 无非负约束，令无非负约束，令 yy(1)-y(2)，且，且y(1)0，y(2)0.（5）统一变量，）统一变量，令令 x=x3，y(1)=x4，y(2)=x5，得到该线性规划问题的标准形式：得到该线性规划问题的标准形式：3.3 3.3 基、基本
7、解、基本可行解基、基本解、基本可行解3.3.1 基、基本解、基本可行解的定义基：若基：若B B是矩阵是矩阵A A中中m mn n阶非奇阶非奇异子矩阵（），则异子矩阵（），则B B是线性规划问题的一个基。是线性规划问题的一个基。基向量：中的每一个列向量（基向量：中的每一个列向量（j=1，2，,m）基变量：与基向量对应的变量，用基变量：与基向量对应的变量，用X XB B表示。表示。非基变量：线性规划模型的决策变量中除基变量以外非基变量：线性规划模型的决策变量中除基变量以外的变量，用的变量，用X XN N表示。表示。基解：基解：设B为某一个基，A=（B,N),则有BXB+NXN=b 令XN=0，则得
8、一个满足AX=b式的解这个解称为基解。基可行解：若基可行解：若 为一个基解，且为一个基解，且则得到一个满足则得到一个满足AX=b、X0的的可行解，称为基可行解。可行解，称为基可行解。可行基：对应基可行解的基称为可行基可行基：对应基可行解的基称为可行基可行基：对应基可行解的基称为可行基可行基：对应基可行解的基称为可行基。注意两点：注意两点：1.1.B B在在A A中是任意取的。故中是任意取的。故A A中有很多基中有很多基B B。2.2.基变量是针对基变量是针对B B而言的，不同而言的，不同B B，其对应的基变量和其对应的基变量和非基变量是不同的。非基变量是不同的。3.3.2 3.3.2 基本解和
9、基本可行解的计算与几何解释基本解和基本可行解的计算与几何解释 通过通过【例例3-3】说明线性规划模型的基、对应的说明线性规划模型的基、对应的基本解、基本可行解。基本解、基本可行解。将模型化为标准型：将模型化为标准型：X2、X3、X5不能构成不能构成B的一组基变的一组基变量。量。X1、X3、X4不能构成不能构成B的的一组基变量。一组基变量。基基基变量基变量基解基解X=(x1,x2,x3,x4,x5)T是否可行是否可行 对应点对应点Z值值B1x1,x2,x3X=(4,3,-2,0,0)T不可行不可行DB2x1,x2,x4X=(2,3,0,8,0)T可行可行C13B3x1,x2,x5X=(4,2,0
10、,0,4)T可行可行E14B5x1,x3,x5X=(4,0,4,0,12)T可行可行G8B6x1,x4,x5X=(8,0,0,-16,12)T不可行不可行FB7x2,x3,x4X=(0,3,2,6,0)T可行可行A9B9x2,x4,x5X=(0,4,0,16,-4)T不可行不可行BB10 x3,x4,x5X=(0,0,8,16,12)T可行可行O0该模型所对应的基、基本解、基本可行解，如下表：该模型所对应的基、基本解、基本可行解，如下表：x1(0,0)(2,3)(0,3)(0,4)(4,3)(4,0)(4,2)(8,0)9 8 7 6 5 4 3 2 1 0|123456789x1x1+2x2
11、 84x1 16可行域可行域ABCDOEFG约束条件的交点有8个，基本解就有8个；可行域顶点有5个：基可行解就有5个：（0，0）、（0，3）、(2,3)、（4，2）和（4，0），其中E为最优解。该模型所对应的基、基本该模型所对应的基、基本解、基本可行解，如下图：解、基本可行解，如下图：可行解：可行解：可行解：可行解：满足约束条件满足约束条件满足约束条件满足约束条件AX=bAX=bAX=bAX=b与与与与X X X X 0 0 0 0的的的的解解解解X X X X基本解：基本解：基本解：基本解：对于某一特定的基对于某一特定的基对于某一特定的基对于某一特定的基B B B B，非基变量取，非基变量取
12、，非基变量取，非基变量取0 0 0 0值的值的值的值的 解，即解，即解，即解，即基本可行解：满足非负约束条件的基础解，即基本可行解：满足非负约束条件的基础解，即基本可行解：满足非负约束条件的基础解，即基本可行解：满足非负约束条件的基础解，即最优解：最优解：最优解：最优解：满足目标函数满足目标函数满足目标函数满足目标函数MaxZMaxZMaxZMaxZ=CX=CX=CX=CX的可行解的可行解的可行解的可行解X X X X基本最优解：满足目标函数基本最优解：满足目标函数基本最优解：满足目标函数基本最优解：满足目标函数MaxZMaxZMaxZMaxZ=CX=CX=CX=CX的基本可行解的基本可行解的
13、基本可行解的基本可行解X X X X3.3.3 3.3.3 线性规划模型解之间的关系线性规划模型解之间的关系基本解基本解基本解基本解可可可可行行行行解解解解最最最最优优优优解解解解基本最基本最基本最基本最优解优解优解优解基本基本基本基本可行可行可行可行解解解解基基基基最优基最优基最优基最优基可行基可行基可行基可行基 线性规划模型解、基的关系图定义定义定义定义1 1：如果集合如果集合C中任意两个点中任意两个点X1、X2，其连线上所其连线上所有点都是集合有点都是集合C中的点，那么称中的点，那么称C为为凸集。即凸集。即:则称为则称为C凸凸集。集。定义定义定义定义2 2：凸集凸集C中满足下述条件的点中
14、满足下述条件的点X称为顶点；如果称为顶点；如果C中不存在任何两个不同的点中不存在任何两个不同的点X1、X2，使使X成为这两成为这两个点连线上的一个点。即对于任何个点连线上的一个点。即对于任何 ，不存在不存在 ，则称，则称X是是凸集凸集C的顶点。的顶点。3.4 3.4 单纯形表的数学原理单纯形表的数学原理定理定理1：若线性规划问题存在可行解域，则其可行解域：若线性规划问题存在可行解域，则其可行解域是凸集。是凸集。定理定理2：线性规划问题的可行解：线性规划问题的可行解 为基可行解的充要条件是，为基可行解的充要条件是，X的正分量所对应的正分量所对应 的系数列向量是线性无关。的系数列向量是线性无关。定
15、理定理3：线性规划问题的基可行解：线性规划问题的基可行解X对应于可行域对应于可行域 D的顶点。的顶点。定理定理4 4：一个标准的线性规划模型，如果有可行解，：一个标准的线性规划模型，如果有可行解，则至少有一个基本可行解则至少有一个基本可行解定理定理5 5：一个标准的线性规划模型，如果有有限的最优：一个标准的线性规划模型，如果有有限的最优 值，则一定存在一个基本可行解是最优解值，则一定存在一个基本可行解是最优解由上述线性规划的基本定理，得以下结论：由上述线性规划的基本定理，得以下结论：1.线性规划问题的可行解域是凸集；线性规划问题的可行解域是凸集；2.基可行解是可行域的顶点，可行域的顶点即是基可
16、基可行解是可行域的顶点，可行域的顶点即是基可3.行解，因此，每个基可行解对应可行域的一个顶行解，因此，每个基可行解对应可行域的一个顶4.点；点；3.可行解域的顶点个数是有限的，不超过可行解域的顶点个数是有限的，不超过 个。个。4.若线性规划问题有最优解，则最优解必在某个顶点若线性规划问题有最优解，则最优解必在某个顶点 上得到。上得到。3.5 3.5 从一个基本可行解转化为相邻的从一个基本可行解转化为相邻的基本可行解基本可行解 定义定义3 3 两个基本可行解称为相邻的，如果两个基本可行解称为相邻的，如果 它们之间变换且仅变换一个基变量。它们之间变换且仅变换一个基变量。3.6.1 最优性判别准则最
17、优性判别准则 线性规划问题的标准型为：线性规划问题的标准型为：3.6 3.6 最优性检验和解的判别最优性检验和解的判别原线性规划可以化为：原线性规划可以化为：原线性规划问题等价于：原线性规划问题等价于：定理定理6 6（最优解判别定理）（最优解判别定理）(1)1)最优解判别定理：若：最优解判别定理：若：为基可行解，且全部为基可行解，且全部 则则 为最优解。为最优解。（2 2）唯一最优解判别定理：若所有）唯一最优解判别定理：若所有 则存在唯一最有解。则存在唯一最有解。3.6.2 3.6.2 无界解和无穷多最优解判别准则无界解和无穷多最优解判别准则（3 3）无穷多最优解判定定理：若：）无穷多最优解判
18、定定理：若：且存在某一个非基变量且存在某一个非基变量 ，则存在，则存在 无穷多最优解。无穷多最优解。（4 4）无界解判定定理：若）无界解判定定理：若 有某一个非基变量有某一个非基变量 并且对应的非基变量的系数并且对应的非基变量的系数 则具有无界解。则具有无界解。单纯形法的基本思想单纯形法的基本思想单纯形法的基本思想单纯形法的基本思想 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。3.7 3.7 单纯形表法单纯形表法 根据线性规划问题的可行域是凸多边形或凸多面体，
19、一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。【例例3-4】求解下列线性规划模型求解下列线性规划模型9 400 350 300 250 200 150 100 50 0|50100 150 200 250 300 350 400 x1OBCAD可行域可行域x29 400 350 300 250 200 150 100 50 0|50100 150 200 250 300 350 400 x1OBCAD可行域可行域可行域顶点有五
20、个可行域顶点有五个,有三个非角点可行有三个非角点可行解。两条边界线产生一个角点可行解，解。两条边界线产生一个角点可行解，每个角点可行解有两个相邻的角点可行每个角点可行解有两个相邻的角点可行解，如（解，如（0 0，0 0），相邻的角点可行解为），相邻的角点可行解为（0 0，250250）、和（）、和（200200，0 0）。）。x29 400 350 300 250 200 150 100 50 0|50100 150 200 250 300 350 400 x1OBCAD可行域可行域求解求解起始步骤：选择（起始步骤：选择（0 0，0 0）作为初始可行解）作为初始可行解最优性检验：（最优性检验：
21、（0 0，0 0）不是最优解：）不是最优解：z=0z=0迭代迭代1 1：由由(0,0)(0,0)沿沿x x2 2移动至移动至A A。解得可行解解得可行解（0 0，250250），最优性），最优性检验非最优值。检验非最优值。目标函数：目标函数：maxzmaxz=50 x=50 x1 1+100 x+100 x2 2x29 400 350 300 250 200 150 100 50 0 x1OBCAD可行域可行域迭代迭代2 2：由由(0,250)(0,250)沿沿x x2 2=250=250移移动至动至B B。解得可行解。解得可行解（5050，250250），最优性），最优性检验是最优值（无相检
22、验是最优值（无相邻的角点可行解优于邻的角点可行解优于它）。它）。x2|50100 150 200 250 300 350 400以以【例例3-4】来讨论它的求解过程，来讨论它的求解过程，其标准型为：其标准型为：转换一般的线性规划模型为标准型，并写出转换一般的线性规划模型为标准型，并写出A A，C C，b b （1）确定一个初始基可行解（顶点）。）确定一个初始基可行解（顶点）。取A中所含的单位矩阵作为一个基，即B=I，XB=(x3，x4，x5)T，XN=(x1,x2)T。则可得一初始基可行解X(0)=(0，0，300，400，250)T,其目标函数值 Z0=0。（2 2）最优解检验。）最优解检验
23、。最优解必在某一基可行解（顶点）上达到。最优解必在某一基可行解（顶点）上达到。考察目标函数考察目标函数Z=0+50 x1+100 x 2由于由于x1=x 2=0，所以所以 Z（0）=0。若将非基变量变换成基变量，目标函数的值就可若将非基变量变换成基变量，目标函数的值就可能增大，能增大，所以只要目标函数中存在正系数的非基变量，所以只要目标函数中存在正系数的非基变量，目标函数还有增大的可能。目标函数还有增大的可能。目标函数是以目标函数是以X（0）的非基变的非基变量表示的，量表示的，不会有不会有X（0）的的基变量。基变量。（3）确定入基（换入）变量）确定入基（换入）变量 任意选择任意选择x1,x2中
24、的一个作为入基变量都会使目标中的一个作为入基变量都会使目标值增加。一般选择最大正系数所对应的非基变量为入值增加。一般选择最大正系数所对应的非基变量为入基变量。基变量。由目标函数由目标函数Z=0+50 x1+100 x 2，故选择，故选择x2作为作为入入基变量。基变量。（4）确定出基（换出）变量）确定出基（换出）变量 当当x2定为入基变量后，必须从定为入基变量后，必须从X（0）的基变量的基变量x3，x4，x5 中换出一个，并保证它们都是非负的（可行中换出一个，并保证它们都是非负的（可行解所要求）。即解所要求）。即x3，x4，x5 0。当当 x1作为非作为非基变量等于基变量等于 0 时，得时，得只
25、有选择只有选择上式才能成立。上式才能成立。当当x2=250时，时，x5=0，决定用决定用x2替换替换x5，故基变量，故基变量x5出基出基这个规则称为这个规则称为 规则。规则。入基变量所能取入基变量所能取的最大值，由它们各的最大值，由它们各自的自的正系数正系数去除右边去除右边常数，然后取最小者。常数，然后取最小者。规则用来确定规则用来确定出基变量。出基变量。（5）确定一个新的基可行解）确定一个新的基可行解 当当x2替换替换x5（即（即 x2由非基变量由非基变量 基变量，基变量，x5由由基变量基变量 非基变量）后，则确定了以非基变量）后，则确定了以x2，x3，x4作作为基变量为基变量，以，以x1，
26、x5作为非基变量而组成的一个新的作为非基变量而组成的一个新的可行基，需求出新的基可行解。可行基，需求出新的基可行解。新的基可行解新的基可行解X（1）=（0，250，50，150，0）TZ（1）=25000目标函数目标函数Z=50 x1+100（250-x 5）=25000+50 x=25000+50 x1 1-100 x-100 x5 5 用用高斯消去高斯消去法将式中法将式中x2的系数列向量变换成单的系数列向量变换成单位向量。位向量。（6）重复上述的第）重复上述的第2步，对步，对X(1)进行最优化检验，进行最优化检验，由于由于X(1)的非基变量的非基变量x1 的系数为正数，故的系数为正数，故X
27、(1)不是最优不是最优解。确定解。确定x1 为入基为入基变量，变量，x5 仍为非基仍为非基变量，变量，求出新的求出新的基可行解。基可行解。x5=0，且且x2，x3，x40，则，则从从式上式可知，只有选择式上式可知，只有选择此式此式 才能成立。才能成立。当当x1=50时，基变量时，基变量x3=0，故基，故基变量变量x3为为出基出基变量。变量。故又得到一个以基变量为故又得到一个以基变量为x1，x2，x4，非基非基变量为变量为x3，x5而构成的一个新的可行基。而构成的一个新的可行基。用用高斯消去高斯消去法将式中法将式中x1的系数列向量变换成单的系数列向量变换成单位向量。位向量。这个新的可行基的基变量
28、为这个新的可行基的基变量为x1，x2，x4，非基非基变变量为量为x3，x5，故得此可行基的基可行解，故得此可行基的基可行解X（2）=（50，250，0，50，0）T，Z（2）=27500 重复第二步，重复第二步，X（2）进行最优化检验。进行最优化检验。X（2）的的非基变量非基变量x3，x5的系数均为负数，故的系数均为负数，故x3，x5均不能确均不能确定为入基变量（否则目标函数会变小），故定为入基变量（否则目标函数会变小），故X（2）为为最优解，此时，整个单纯形法过程结束。最优解，此时，整个单纯形法过程结束。以以X X（2 2）的非基变量表示的目标函数，不含有的非基变量表示的目标函数，不含有X
29、X（2 2）的基变量。的基变量。目标函数为：目标函数为：Z=25000+50(50-xZ=25000+50(50-x3 3+x+x5 5)x)x1 1-100 x-100 x5 5 =27500-50 x=27500-50 x3 3-50 x-50 x5 5 分析单纯形法过程，共获得了三个基可行解分析单纯形法过程，共获得了三个基可行解X（0）、X（1）、X（2），它们各自所对应的基变量和非它们各自所对应的基变量和非基变量是：（基变量是：（B1，B2，B3）出基出基 入基入基X（0）：基变量（基变量（x3，x4，x5）非基变量（非基变量（x1，x2）。）。出基出基 入基入基 X（1）：基变量（基
30、变量（x2，x3，x4）非基变量（非基变量（x1，x5）。）。X（2）：基变量（基变量（x1，x2，x4）非基变量（非基变量（x3，x5）。）。X（0）、X（1）、X（2）所所对对应应的的基基变变量量求求解解出出来来。只只要要令令它它们们各各自自的的非非基基变变量量等等于于0，即即可可求求出出各各自自的的基可行解。基可行解。X（0）、X（1）、X（2）各各自自的的非非基基变变量量表表示示的的目目标标函函数数（不不含含有有它它们们各各自自的的基基变变量量）这这些些目目标标函函数数的的系系数数称称为为检检验验数数。由由检检验验数数判判定定各各自自的的基基可可行行解解是是否否是是最优解最优解，并由检
31、验数，并由检验数确定入基变量确定入基变量。归纳单纯形法的性质：归纳单纯形法的性质：1.是从一个基可行解变换到另一个基可行解的过程，着是从一个基可行解变换到另一个基可行解的过程，着个过程实际上就是确定进基变量和出基变量的过程。个过程实际上就是确定进基变量和出基变量的过程。2.对每一个基可行解，均需解出其基变量。对每一个基可行解，均需解出其基变量。3.一个基可行解是否最优要由该基可行解的检验数来判一个基可行解是否最优要由该基可行解的检验数来判断。（检验数是该基可行解的非基变量所表示的目标断。（检验数是该基可行解的非基变量所表示的目标函数中的系数）。函数中的系数）。4.入基变量由检验数确定。入基变量
32、由检验数确定。5.出基变量由出基变量由 规则确定。规则确定。确定一初始基可行解确定一初始基可行解该基该基可行解可行解是否最优？是否最优？确定入基变量确定入基变量确定出基变量确定出基变量解出解出新的基可行解新的基可行解结束结束YN确定了一个新的可行基确定了一个新的可行基 求线性规划问题时，为了方便起见，可以求线性规划问题时，为了方便起见，可以设计一张表来代替所研究的线性规划问题表达设计一张表来代替所研究的线性规划问题表达式，其功能与解线性方程组的增广矩阵类似，式，其功能与解线性方程组的增广矩阵类似，称为单纯形表。开始建立的单纯形表称为初始称为单纯形表。开始建立的单纯形表称为初始单纯形表。单纯形法
33、的迭代运算可以在单纯形单纯形表。单纯形法的迭代运算可以在单纯形表上进行。表上进行。3.7.1 3.7.1 单纯形表的定义单纯形表的定义 设标准形为设标准形为表格表格设计设计依据：依据：将将将将-Z-Z-Z-Z看看看看作作作作不不不不参参参参与与与与基基基基变变变变换换换换的的的的基基基基变变变变量量量量，把把把把目目目目标标标标函函函函数数数数表表表表达达达达式式式式改改改改写写写写成成成成方方方方程程程程的的的的形形形形式式式式，和和和和原原原原有有有有的的的的m m m m个个个个约约约约束束束束方方方方程程程程组组组组成成成成一一一一个具有个具有个具有个具有n+m+1n+m+1n+m+1
34、n+m+1个个个个变变变变量、量、量、量、m+1m+1m+1m+1个方程的方程个方程的方程个方程的方程个方程的方程组组组组：取出系数写成增广矩取出系数写成增广矩阵的形式：的形式：-Z X1 X2 Xn Xn+1 Xn+2 Xn+m b -Z-Z，X Xn+1n+1，X Xn+mn+m所所对应对应的系数的系数列向量构成一列向量构成一个基个基 用矩用矩阵的初等行的初等行变换将将该基基变成成单位位阵,这时 变成成0，相相应的的增增广广矩矩阵变成如下形式：成如下形式：其中，其中，j=1j=1，2 2，n n，增广矩阵的最后一行就是用非基变量表示目标函数增广矩阵的最后一行就是用非基变量表示目标函数增广矩
35、阵的最后一行就是用非基变量表示目标函数增广矩阵的最后一行就是用非基变量表示目标函数的表达式的表达式的表达式的表达式,j j(j(j=1,2,n)=1,2,n)就是非基变量的检验就是非基变量的检验就是非基变量的检验就是非基变量的检验数。数。数。数。CBXBc1 x1cnxncn+1 xn+1 Cn+m xn+mbCn+1Xn+1a11a1n10b11Cn+2Xn+2a21a2n00b22.Cn+mXn+mam1amn01bmmj1n00-z0CBXBx1x2x3x4x5b501000000 x3111003000 x4210104000 x501001250j50100000初始可行基为初始可行
36、基为B，对应的基变量为，对应的基变量为XB，基变量对应的，基变量对应的目标函数系数为目标函数系数为CB。其中。其中j=cj-CBB-1PjCBXBc1 x1cnxncn+1 xn+1 Cn+m xn+mbCn+1Xn+1a11a1n10b11Cn+2Xn+2a21a2n00b22.Cn+mXn+mam1amn01bmmj1n00-z0单纯形表的特点：单纯形表的特点：基变量对应的约束方程系数矩阵为单位矩阵基变量对应的约束方程系数矩阵为单位矩阵I；基变量对应的检验数均等于基变量对应的检验数均等于0；基可行解不同，反映在原表中该基可行解对应的基基可行解不同，反映在原表中该基可行解对应的基B不同。不同
37、。对于某个基可行解，单纯形表可看成把原表中该对于某个基可行解，单纯形表可看成把原表中该基可行解对应的基基可行解对应的基B 经初等行变换化为单位矩阵得到。经初等行变换化为单位矩阵得到。初等行变换初等行变换XB XNXB XN-Z-ZCBXBx1x2x3x4x5b501000000 x31010-1500 x420010150100 x201001250j50000-100-25000CBXBx1x2x3x4x5b501000000 x11010-1500 x400-211500 x201001250j00-500-50-27500第三第三张单张单纯形纯形表表第二第二张单张单纯形纯形表表举例说明举
38、例说明CBXBx1x2x3x4x5b501000000 x3111003000 x4210104000 x501001250j501000000从最优表可知从最优表可知:该该LP的最优解是的最优解是X*=(0,0,300,400,250)T 相应的目标函数最优值是相应的目标函数最优值是Zmax=0CBXBx1x2x3x4x5b501000000 x3111003000 x4210104000 x501001250j5010000001.1.1.1.目标函数目标函数目标函数目标函数Z Z Z Z值的计算值的计算值的计算值的计算CBXBx1x2x3x4x5b501000000 x3111003000 x4210104000 x501001250j501000000CBXBx1x2x3x4x5b501000000 x31010-1500 x420010150100 x201001250j50000-100-250002.2.关于检验数的计算。关于检验数的计算。CBXBx1x2x3x4x5b501000000 x3111003000 x4210104000 x501001250j501000000CBXBx1x2x3x4x5b501000000 x31010-1500 x420010150100 x201001250j50000-100-25000