第二章图解法与单纯形法改

第二章图解法与单纯形法改第1页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法图解法是用作图的方法求解线性规划问题，一般只适用于具有两个决策变量的线性规划问题。步骤1画直角坐标系步骤2根据约束条件画出可行域步骤3画过坐标原点的目标函数线步骤4确定目标函数的增大方向步骤5让目标函数沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。第2页，共70页，2023年，2月20日，星期三x1x2O1020304010203040(15,10)最优解X=(15,10)最优值Z=85例题第3页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法

用图解法求解如下线性规划问题：

例1第4页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法求解Q3点为（3，3），此时z=15第5页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法本例中我们用图解法得到的问题的最优解是惟一的。但在线性规划问题的计算中,解的情况还可能出现下列几种:1无穷最优解。如将本例的目标函数改变为则目标函数的图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。第6页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法2.无界解(有可行解但无有界最优解)。如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。用图解法求解时,可以看到变量的取值可以无限增大,因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。第7页，共70页，2023年，2月20日，星期三2.1线性规划问题的图解法3.无可行解。如下述线性规划模型：用图解法求解时找不到满足所有约束条件的公共范围，这时问题无可行解。其原因是模型本身有错误,约束条件之间相互矛盾,应检查修正。

第8页，共70页，2023年，2月20日，星期三图解法虽然只能用来求解只具有两个变量的线性规划问题,但它的解题思路和几何上直观得到的一些概念判断,对下面要讲的求解一般线性规划问题的单纯形法有很大启示:线性规划问题求解的基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找，寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。线性规划问题求解时可能出现四种结局：唯一最优解无穷多个最优解无有界解无解或无可行解如果某一线性规划问题有最优解，可以按照以下思路求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其他顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。第9页，共70页，2023年，2月20日，星期三线性规划的基本性质凸集对集合C中任意两个点其连线上的所有点都是集合C中的点，则C为凸集。由于的连线可以表示为，因此凸集的数学表达为：对任意的，有则称C为凸集。第10页，共70页，2023年，2月20日，星期三

线性规划的基本性质定理1

若线性规划问题存在可行域，则其可行域一定是凸集。引理线性规划问题的可行解X=(x1,x2,…,xn)T为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。定理2线性规划问题的基可行解对应可行域的顶点。定理3

若线性规划问题有最优解，一定存在一个基可行解是最优解。第11页，共70页，2023年，2月20日，星期三从可行域中的一个基可行解出发，判别它是否已经是最优解，如果不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。基本思想：2.2线性规划单纯形法的原理与计算步骤3寻找改进的基可行解2最优性检验和解的判别1确定初始基可行解第12页，共70页，2023年，2月20日，星期三【例2】用单纯形法求下列线性规划的最优解第13页，共70页，2023年，2月20日，星期三单纯形法的计算步骤：步骤1：求初始基可行解，列出初始单纯形表。

对非标准形式的线性规划问题首先要化成标准形式。由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵[P1,P2,…,Pm]，以此作为基即可求得问题的一个初始基可行解。必须是标准形式第14页，共70页，2023年，2月20日，星期三【解】首先化为标准型，加入松驰变量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

第15页，共70页，2023年，2月20日，星期三单纯形法的计算步骤：步骤2最优性检验在单纯形表中，若所有的检验数表中的基可行解即为最优解。若存在并且有，则问题无有界解。计算结束。否则转入下一步。步骤3从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表。步骤4重复步骤2和3，一直到计算结束。第16页，共70页，2023年，2月20日，星期三进基列出基行bi/ai2，ai2>0θi表1-4(1)XBx1x2x3x4bx3211040x4130130σ

j3400

(2)x3x2σ

j

(3)x1

x2

σ

j

基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/5

2/5400-1-1将3化为1乘以1/3后得到3018第17页，共70页，2023年，2月20日，星期三单纯形算法的计算步骤①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数j，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个k所对应的系数列向量Pk≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi/aik|aik＞0}=bl/aik确定xl为换出变量。建立新的单纯形表，此时基变量中xk取代了xl的位置。⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第③步。

第18页，共70页，2023年，2月20日，星期三2.2线性规划单纯形法的原理与计算步骤单纯形法计算中可能出现以下两种情况：出现两个以上，原则上可任取一个对应的为换入基的变量；相持。即计算值出现两个以上相同的最小值。则可任选其中一个基变量作为换出变量。但是为防止出现循环现象，先后有人提出了一些方法。如：勃兰特法；字典序法；摄动法。（1选取检验数中下标最小的非基变量为换入变量（2按规则计算时，若出现两个和两个以上的最小比值时，选取下标最小的基变量为换出变量。第19页，共70页，2023年，2月20日，星期三单纯形法的计算

用单纯形法求解线性规划问题：

例3第20页，共70页，2023年，2月20日，星期三最优解的判别定理定理1最优解的判别定理

定理2有无穷多最优解的判别定理

第21页，共70页，2023年，2月20日，星期三单纯形法的计算

用单纯形法求解线性规划问题：

例4第22页，共70页，2023年，2月20日，星期三最优解的判别定理定理3有无界解的判别定理

第23页，共70页，2023年，2月20日，星期三单纯形法的计算

用单纯形法求解线性规划问题：

例题5第24页，共70页，2023年，2月20日，星期三XBx1x2x3x3401λj230第25页，共70页，2023年，2月20日，星期三唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线规划具有唯一最优解

。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:

某个且aij≤０（i=1，2,…,m）则线性规划具有无界解第26页，共70页，2023年，2月20日，星期三【练习1】用单纯形法求解第27页，共70页，2023年，2月20日，星期三Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表1－51/3150120301713751/30－90－2M2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最优解X=(25，35/3，0，0，0)T，最优值Z=145/3第28页，共70页，2023年，2月20日，星期三【练习2】求解线性规划【解】化为标准型第29页，共70页，2023年，2月20日，星期三初始单纯形表为XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2为换入变量，而第二列的数字均小于0，因此线性规划的最优解无有界解。由模型可以看出，当固定x1使x2→+∞且满足约束条件，还可以用图解法看出具有无界解。第30页，共70页，2023年，2月20日，星期三【练习3】求解线性规划【解】:化为标准型后用单纯形法计算如下表所示第31页，共70页，2023年，2月20日，星期三XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20第32页，共70页，2023年，2月20日，星期三表(3)中λj全部非正,则最优解为:表(3)表明,非基变量x3的检验数λ3=0,

使x3作为换入变量，

x5为换入变量继续迭代,得到表(4)的另一基本最优解

X(1),X(2)是线性规划的两个最优解，它的凸组合仍是最优解，从而原线性规划有多重最优解。第33页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第34页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第35页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第36页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第37页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第38页，共70页，2023年，2月20日，星期三单纯形法计算的矩阵描述第39页，共70页，2023年，2月20日，星期三人工变量法人工变量法的基本思路是：若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。

2.3线性规划单纯形法的进一步讨论第40页，共70页，2023年，2月20日，星期三线性规划求解的人工变量法第41页，共70页，2023年，2月20日，星期三线性规划求解的人工变量法第42页，共70页，2023年，2月20日，星期三由于单位阵作为基阵，因此，选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。大M法两阶段法第43页，共70页，2023年，2月20日，星期三第44页，共70页，2023年，2月20日，星期三

为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M(M为任意大的正数)。线性规划求解的大M法第45页，共70页，2023年，2月20日，星期三线性规划求解的大M法第46页，共70页，2023年，2月20日，星期三由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。这种方法我们通常称其为大M法。第47页，共70页，2023年，2月20日，星期三【例6】用大M法解下列线性规划线性规划求解的大M法举例第48页，共70页，2023年，2月20日，星期三【解】首先将数学模型化为标准形式式中x4为剩余变量，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。第49页，共70页，2023年，2月20日，星期三Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3第50页，共70页，2023年，2月20日，星期三最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3注意：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；第51页，共70页，2023年，2月20日，星期三【练习】第52页，共70页，2023年，2月20日，星期三线性规划求解的两阶段法第53页，共70页，2023年，2月20日，星期三线性规划求解的两阶段法第二阶段，单纯形法求解原问题第一阶段计算得到的最终单纯形表中除去人工变量，将目标函数行的系数，换成原问题的目标函数后，作为第二阶段计算的初始表，继续求解。

第54页，共70页，2023年，2月20日，星期三【例】用两阶段单纯形法求解例【6】的线性规划。第55页，共70页，2023年，2月20日，星期三【解】标准型为在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为用单纯形法求解，得到第一阶段问题的计算表如下：第56页，共70页，2023年，2月20日，星期三Cj00000-1-1

bCBXBx1x2x3x4x5x6x7-10-1x6x5x7－4123－1－212[1]－1000101000014101→λj-212↑-1000

-100x6x5x3－6－32[5]3－2001－100010100

3→81λj-65↑0-100

000x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/511/5λj00000

第57页，共70页，2023年，2月20日，星期三最优解为最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为第58页，共70页，2023年，2月20日，星期三Cj32-100bCBXBx1x2x3x4x5

2

0

－1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

－1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000－5

Cj32－100bCBXBx1x2x3x4x520－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/31331/319/3λj000－5－25/3

用单纯形法计算得到下表最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3第59页，共70页，2023年，2月20日，星期三【练习】用两阶段法求解线性规划。第60页，共70页，2023年，2月20日，星期三【解】第一阶段问题为用单纯形法计算如下表：第61页，共70页，2023年，2月20日，星期三Cj0000-1bCBXBx1x2x3x4x50-1x3x5[3]11－2100－1016→4λj

1↑-20-10

0-1x1x5101/3－7/31/3－1/30－10122λj

0-7/3-1/3-10

λj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值w=2≠0,x5仍在基变量中,从而原问题无可行解。第62页，共70页，2023年，2月20日，星期三解的判断唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线性规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:

某个λk>0且aik≤０（i=1，2,…,m）则线性规