《图解法与单纯形法改.ppt》由会员分享，可在线阅读，更多相关《图解法与单纯形法改.ppt（70页珍藏版）》请在金锄头文库上搜索。
1、 第二章第二章 线性规划的图解法与单纯形线性规划的图解法与单纯形解法解法1 1 线性规划问题的图解法线性规划问题的图解法2 2线性规划的基本性质线性规划的基本性质3 3线性规划单纯形法的原理线性规划单纯形法的原理与计算步骤与计算步骤4 4线性规划单纯形法的进一线性规划单纯形法的进一步讨论步讨论5 5线性规划特例线性规划特例运输问题运输问题6 6 2.1 线性规划问题的图解法线性规划问题的图解法v图解法是用作图的方法求解线性规划问题，一般只适用于具有两个决策变量的线性规划问题。v步骤1 画直角坐标系v步骤2 根据约束条件画出可行域v步骤3 画过坐标原点的目标函数线v步骤4 确定目标函数的增大方向
2、v步骤5 让目标函数沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。x1x2O1020304010203040(15,10)最优解最优解X=(15,10)最优值最优值Z=85例题例题2.1 线性规划问题的图解法线性规划问题的图解法 用图解法求解如下线性规划问题： 例12.1 线性规划问题的图解法线性规划问题的图解法v求解Q3点为（3，3），此时z=152.1 线性规划问题的图解法线性规划问题的图解法v本例中我们用图解法得到的问题的最优解是惟一的。 但在线性规划问题的计算中,解的情况还可能出现下列几种:v1 无穷最优解。如将本例的目标函数改变为 则目标函数的
3、图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。2.1 线性规划问题的图解法线性规划问题的图解法v2. 无界解 (有可行解但无有界最优解)。 如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。 用图解法求解时, 可以看到变量的取值可以无限增大, 因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。 其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。2.1 线性规划问题的图解法线性规划问题的图解法v3. 无可行解。如下述线性规划模型：v用图解法求解时找不到满足所有约束条件的公共范围，这时问题无可行解。其原因
4、是模型本身有错误, 约束条件之间相互矛盾, 应检查修正。 图解法虽然只能用来求解只具有两个变量的线性规划问题图解法虽然只能用来求解只具有两个变量的线性规划问题, , 但它的解题思路和几何上直观得到的一些概念判断但它的解题思路和几何上直观得到的一些概念判断, , 对下面对下面要讲的求解一般线性规划问题的单纯形法有很大启示要讲的求解一般线性规划问题的单纯形法有很大启示: :线性规划问题求解的基本线性规划问题求解的基本依据是：线性规划问题的依据是：线性规划问题的最优解总可在可行域的顶最优解总可在可行域的顶点中寻找，寻找线性规划点中寻找，寻找线性规划问题的最优解只需比较有问题的最优解只需比较有限个顶点
5、处的目标函数值。限个顶点处的目标函数值。线性规划问题求解时可能线性规划问题求解时可能出现四种结局：出现四种结局：唯一最优解唯一最优解无穷多个最优解无穷多个最优解无有界解无有界解无解或无可行解无解或无可行解如果某一线性规划问题有如果某一线性规划问题有最优解，可以按照以下思最优解，可以按照以下思路求解：先找可行域中的路求解：先找可行域中的一个顶点，计算顶点处的一个顶点，计算顶点处的目标函数值，然后判别是目标函数值，然后判别是否有其他顶点处的目标函否有其他顶点处的目标函数值比这个顶点处的目标数值比这个顶点处的目标函数值更大，如有，转到函数值更大，如有，转到新的顶点，重复上述过程，新的顶点，重复上述过
6、程，直到找不到使目标函数值直到找不到使目标函数值更大的新顶点为止。更大的新顶点为止。线性规划的基本性质v凸集v对集合C中任意两个点 其连线上的所有点都是集合C中的点，则C为凸集。v由于 的连线可以表示为 ，因此凸集的数学表达为：对任意的 ，有 则称C为凸集。 线性规划的基本性质线性规划的基本性质v定定理理1 若若线线性性规规划划问问题题存存在在可可行行域域，则则其其可可行行域一定是凸集。域一定是凸集。v引引理理 线线性性规规划划问问题题的的可可行行解解X=(x1,x2,xn)T为为基基可可行行解解的的充充要要条条件件是是X的的正正分分量量对对应应的的系系数列向量是线性独立的。数列向量是线性独立
7、的。v定定理理2 线线性性规规划划问问题题的的基基可可行行解解对对应应可可行行域域的的顶点。顶点。v定定理理3 若若线线性性规规划划问问题题有有最最优优解解，一一定定存存在在一一个基可行解是最优解。个基可行解是最优解。 从可行域中的一个基可行解出发，判别它是否已经是最优解，如果从可行域中的一个基可行解出发，判别它是否已经是最优解，如果不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。如此迭代下去，直到找到最优解或判定问题无解为止。基本思想：基本思想：2.2 2.2 线性规划单纯形法
8、的原理与计算步骤线性规划单纯形法的原理与计算步骤3 3 寻找改进寻找改进的基可行解的基可行解2 2 最优性检最优性检验和解的判验和解的判别别1 1 确定初始确定初始基可行解基可行解【例例2】用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解单纯形法的计算步骤：单纯形法的计算步骤：v步骤1：求初始基可行解，列出初始单纯形表。v 对非标准形式的线性规划问题首先要化成标准形式。 由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵P1,P2,Pm ，以此作为基即可求得问题的一个初始基可行解。必须是标准形式必须是标准形式【解解】首先化为标准型，加入松驰变量首先化为标准型，加入松驰变量
9、x3、x4则标准型为则标准型为系数矩阵系数矩阵A及可行基及可行基B1r(B1)=2，B1是是单单位位矩矩阵阵作作为为初初始始基基,x3、x4为为基基变变量量，x1、x2为为非非基基变变量量，令令x1=0、x2=0由由约约束束方方程程知知x3=40、x4=30得到初始基可行解得到初始基可行解X(1)=(0,0,40,30)T单纯形法的计算步骤：单纯形法的计算步骤：v步骤2 最优性检验v在单纯形表中，若所有的检验数 表中的基可行解即为最优解。若存在 并且有 ，则问题无有界解。计算结束。否则转入下一步。v步骤3 从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表。v步骤4 重复步骤2
10、和3，一直到计算结束。进基列进基列出出基基行行bi/ai2，ai20i表表1-4(1)XBx1x2x3x4bx3211040x4130130j3400(2)x3x2j(3)x1x2j基变量基变量110001/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/52/5400- -1- -1将将3化为化为1乘乘以以1/3后后得得到到3018单纯形算法的计算步骤单纯形算法的计算步骤 将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯阶单位矩阵作为初始可行基，建立初始单纯形表。形表
11、。计算各非基变量计算各非基变量xj的检验数的检验数 j，若所有，若所有 j0，则问题已得到最则问题已得到最优解，停止计算，否则转入下步。优解，停止计算，否则转入下步。在大于在大于0的检验数中，若某个的检验数中，若某个 k所对应的系数列向量所对应的系数列向量Pk0，则则此问题是无界解，停止计算，否则转入下步。此问题是无界解，停止计算，否则转入下步。根据根据max j j0= k原则，确定原则，确定xk为换入变量为换入变量(进基变量进基变量)，再按再按 规则计算：规则计算： =minbi/aik|aik0=bl/aik确定确定xl为换出变为换出变量。建立新的单纯形表，此时基变量中量。建立新的单纯形
12、表，此时基变量中xk取代了取代了xl的的位置。位置。以以aik为主元素进行迭代，把为主元素进行迭代，把xk所所对应的列向量变为单位列向量，对应的列向量变为单位列向量，即即aik变为变为1，同列中其它元素为，同列中其它元素为0，转第，转第步。步。 2.2 线性规划单纯形法的原理与计算步骤线性规划单纯形法的原理与计算步骤v单纯形法计算中可能出现以下两种情况：v出现两个以上 ，原则上可任取一个 对应的为换入基的变量；v相持。 即计算值出现两个以上相同 的最小值。则可任选其中一个基变量作为换出变量。 v但是为防止出现循环现象，先后有人提出了一些方法。如：勃兰特法；字典序法；摄动法。v（1选取检验数中下
13、标最小的非基变量为换入变量v（2按 规则计算时，若出现两个和两个以上的最小比值时，选取下标最小的基变量为换出变量。单纯形法的计算单纯形法的计算 用单纯形法求解线性规划问题： 例3最优解的判别定理最优解的判别定理v定理定理1 最优解的判别定理最优解的判别定理 v定理定理2 有无穷多最优解的判别定理有无穷多最优解的判别定理单纯形法的计算单纯形法的计算 用单纯形法求解线性规划问题： 例4最优解的判别定理最优解的判别定理v定理定理3有无界解的判别定理有无界解的判别定理单纯形法的计算单纯形法的计算 用单纯形法求解线性规划问题： 例题5XBx1x2x3x3401j230唯一最优解的判断：唯一最优解的判断：
14、最优表中所有非基变量的检验数最优表中所有非基变量的检验数小于零小于零,则线规划具有唯一最优解则线规划具有唯一最优解。多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为最优表中存在非基变量的检验数为零零,则线则性规划具有多重最优解。则线则性规划具有多重最优解。无界解的判断无界解的判断:某个某个且且aij（i=1，2,m）则则线性规划具有无界解线性规划具有无界解【练习练习1】用单纯形法求解用单纯形法求解Cj12100bCBXBx1x2x3x4x50x423210150x51/3150120j121000x42x2j1x12x2j表表151/3150120301713751/30902
15、M2025601017/31/31250128/91/92/335/30098/91/97/3最优解最优解X=(25，35/3，0，0，0)T，最优值最优值Z=145/3【练习练习2】求解线性规划求解线性规划【解解】化为标准型化为标准型初始单纯形表为初始单纯形表为XBx1x2x3x4bx3x43221100114j11002=10,x2为为换换入入变变量量，而而第第二二列列的的数数字字均均小小于于0，因因此此线线性性规规划划的的最最优优解解无无有有界界解解。由由模模型型可可以以看看出出，当当固固定定x1使使x2+且且满足约束条件，还可以用图解法看出具有无界解。满足约束条件，还可以用图解法看出具
16、有无界解。【练习练习3】求解线性规划求解线性规划【解解】:化为标准型后用单纯形法计算如下表所示化为标准型后用单纯形法计算如下表所示XBx1x2x3x4x5b(1)x3x4x5111221100010001410225j24000(2)x2x4x51/221/21001/211/201000126438j40200(3)x2x1x50101001/41/23/41/41/21/40017/235/21410/3j00020(4)x2x1x30101000011/31/31/31/32/34/38/314/310/3j00020表表(3)中中j全部非正全部非正,则最优解为则最优解为:表表(3)表表
17、明明,非非基基变变量量x3的的检检验验数数3=0,使使x3作作为为换换入入变变量量，x5为为换入变量继续迭代换入变量继续迭代,得到表得到表(4)的另一的另一基本最优解基本最优解X(1),X(2)是线性规划的两个最优解，它的凸组合是线性规划的两个最优解，它的凸组合仍是最优解，从而原线性规划仍是最优解，从而原线性规划有多重最优解。有多重最优解。单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述 单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的
18、矩阵描述v人工变量法人工变量法v人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 2.3线性规划单纯形法的进一步讨论线性规划单纯形法的进一步讨论线性规划求解的人工变量法线性规划求解的人工变量法线性规划求解的人工变量法线性规划求解的人工变量法由于单位阵作为基阵，因此，选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。 大大M M法法两阶段法两阶段法v为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一
19、个很大的负价值系数-M (M为任意大的正数)。线性规划求解的大M法线性线性规划求解的大规划求解的大M法法v由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。v这种方法我们通常称其为大M法。【例例6】用大用大M法解法解下列线性规划下列线性规划线性规划求解的大线性规划求解的大M法举例法举例【解解】首先将数学模型化为标准形式首先将数学模型化为标准形式式式中中x4为为剩剩余余变变量量，x5为为松松弛弛变变量量，x5可可作作为为一一个个基基变变量量，第第一一、三三约约束束中中分分别别加加入入人人工工变变量量x6、x7，目目标标函函数数中中加加入
20、入Mx6Mx7一一项项，得得到到人人工工变变量量单单纯纯形形法法数数学学模型模型用前面介绍的单纯形法求用前面介绍的单纯形法求解，见下表。解，见下表。Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3最优解最优
21、解X（31/3，13，19/3，0，0)T；最优值最优值Z152/3注意：注意：vM是一个很大的抽象的数，不需要给是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大出具体的数值，可以理解为它能大于给定的任何一个确定数值；于给定的任何一个确定数值；【练习练习】线性线性规划求解的两阶段法规划求解的两阶段法线性规划求解的两阶段法线性规划求解的两阶段法第二阶段第二阶段，单纯形法求解原问题，单纯形法求解原问题第一阶段计算得到的最终单纯形表中除去人工变第一阶段计算得到的最终单纯形表中除去人工变量，将目标函数行的系数，换成原问题的目标函量，将目标函数行的系数，换成原问题的目标函数后，作为第二阶段计
22、算的初始表，继续求解。数后，作为第二阶段计算的初始表，继续求解。【例例】用两阶段单纯形法求解例用两阶段单纯形法求解例【6】的线性规划。的线性规划。【解解】标准型为标准型为在第一、三约束方程中加入人工变量在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为后，第一阶段问题为用单纯形法求解，得到第一阶段问题的计算表如下：用单纯形法求解，得到第一阶段问题的计算表如下：Cj00000-1-1bCBXBx1x2x3x4x5x6x7-10-1x6x5x74123121211000101000014101j-212-1000-100x6x5x3632532001100010100381j-650-1
23、00000x2x5x36/53/52/51000011/53/52/50103/531/511/5j00000最最优优解解为为最最优优值值w=0。第第一一阶阶段段最最后后一一张张最最优优表表说说明明找找到到了了原原问问题题的的一一组组基基可可行行解解，将将它它作作为为初初始始基基可可行行解解，求求原问题的最优解，即第二阶段问题为原问题的最优解，即第二阶段问题为Cj32-100bCBXBx1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/5100
24、0011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j000525/3用单纯形法计算得到下表用单纯形法计算得到下表最优解最优解X（31/3，13，19/3，0，0)T；最优值最优值Z152/3【练习练习】用两阶段法求解线性规划。用两阶段法求解线性规划。【解解】第一阶段问题为第一阶段问题为用单纯形法计算如下表：用单纯形法计算如下表：Cj0000-1bCBXBx1x2x3x4x50-1x3x5311210010164j1-20-100-1x1x5101/37/31/31/3010122j0-7/3-1/3-10
25、j0,得到第一阶段的最优解得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值最优目标值w=20,x5仍在基变量中仍在基变量中,从而原问题无可行解。从而原问题无可行解。解的解的判断判断唯一最优解的判断：唯一最优解的判断：最优表中所有非基变量的检验数小于零最优表中所有非基变量的检验数小于零,则则线性规划具有唯一最优解线性规划具有唯一最优解多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为零最优表中存在非基变量的检验数为零,则则线则性规划具有多重最优解。线则性规划具有多重最优解。无无界界解解的的判判断断:某某个个k0且且aik（i=1，2,m）则则线线性性规规划具有无界解划具
26、有无界解无无可可行行解解的的判判断断：(1)当当用用大大M单单纯纯形形法法计计算算得得到到最最终终单单纯纯形形表中存在非零的人工变量，则表明原线性规划问题无可行解。表中存在非零的人工变量，则表明原线性规划问题无可行解。(2)当第一阶段的最优值当第一阶段的最优值w0时，则原问题无可行解。时，则原问题无可行解。【习习题题1】配配料料问问题题。某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他成成分分。钢钢铁铁公公司司拟拟从从五五种种不不同同
27、级级别别的的矿矿石石中中进进行行冶冶炼炼，每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1.4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最最低低的的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。表表1.4矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍% 杂质杂质%费用（元费用（元/t ）125101025303402400030302603015520601804202004020230585151755190习题习题解解:设设xj（j=1,2，5
28、）是第是第j种矿石数量，得到下列线性规划模型种矿石数量，得到下列线性规划模型注注意意，矿矿石石在在实实际际冶冶炼炼时时金金属属含含量量会会发发生生变变化化，建建模模时时应应将将这这种种变变化化考考虑虑进进去去，有有可可能能是是非非线线性性关关系系。配配料料问问题题也也称称配配方方问问题题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。v习题2 找出下面线性规划问题的基解，基可行解以及最优解。v习题3v下表是求极大化线性规划问题计算得到的单纯形表，表中无人工变量，a1，a2，a3，d，c1，c2为待定常数，试说明这些常数分别取何值时，以下结论成立v1、表中解为唯一最优解v2、表中解为最优解，但存在无穷多最优解。v3、该线性规划问题具有无界解。v4、表中解非最优，为对解进行改进，换入变量为x1，换出变量为x6.v习题4分别用单纯形法中的大M法和两阶段法求解下述线性规划问题，并指出属于哪一类解。
