null一、求解LP问题的单纯形法
1.单纯形法的求解原理 一、求解LP问题的单纯形法
1.单纯形法的求解原理 单纯形法引例null
Step2. 确定换入换出变量,进行第一次迭代 Step1. 确定初始基可行解。 初始基可行解为:X1=(0 0 360 200 300)Tf1=0*null
f2 =360 Step3.确定新的换入换出变量,进行第二次迭代*null目标函数值 f 3 = 428。即当A产品生产20kg,B产品生产24kg,工厂才能获得最大利润428百元。x3=84代表煤的剩余量为84t,x4 = x5 = 0表示电力和劳动日完全利用,没有剩余。X3为最优解2.单纯形法的主要步骤2.单纯形法的主要步骤Step1.
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
化,找初始基可行解,建立初始的单纯形表;
对于(max , ),松弛变量对应的列构成一个单位阵
Step2.检验当前基可行解是否为最优解
所有检验数 λj 0,则得到最优解(若存在λk >0,且pk 0,则该问题无最优解,停止计算) 否则进行下一步。
Step3.换基迭代(改进基可行解)
从 λj > 0 中找最大者λ k ,其对应变量xk称为换入变量(若最大判别数有同样大的,选对应下标小的变量为换入变量)
xk所在列称为主元列
确定换入变量的最大值和换出变量
最小比值原则null设第 l 行使 最小,则第 l 行对应的基变量x l称为换出变量,第 l 行称为主元行,alk 称为主元。
Step4.迭代过程
迭代过程以主元alk为中心进行,即要将主元 alk变为1,主列上其它元素变为0,得到一个新的单纯形表,同时得到一个新的基可行解。
转回Step2。3. 单纯形表及其格式3. 单纯形表及其格式例1 用单纯形法求解下列LP问题例1 用单纯形法求解下列LP问题 max f =40x1+ 50x2标准化标准化 max f =40x1+ 50x2+0·x3 +0·x4+0·x5建立初始单纯形表建立初始单纯形表基变量*30/2=1560/2=3024/2=1240 50 0 0 00
0
0第一步迭代第一步迭代基变量6/1=636/3=12__40 50 0 0 00
0
50第二步迭代第二步迭代基变量18/2=912/0.5=24__40 50 0 0 040
0
50第三步迭代第三步迭代基变量该问题的最优解为:X=(15, 7.5, 0, 0, 9)T40 50 0 0 040
0
50例2 用单纯形法求解下列LP问题例2 用单纯形法求解下列LP问题null基变量 1 1 0 0 00
0
00-12893-2002-1-2x11该问题具有无界解例2 用单纯形法求解下列LP问题例2 用单纯形法求解下列LP问题max f =x1+ x2+2x3 -x4 x1 +x3 - x4 =1
-x1 +x2 +2x4 =0
x1 , …, x4 0
max f =x1+ x2+2x3 -x4=2 -x4max f =x1+ x2+2x3 -x4=2 -x4基变量null此问题具有无穷多最优解 max f =2
总结:解的判别总结:解的判别1、最优解的判别:
若X=(x1x2….xn)T为对应于基B的一个基可行解,且所有λj 0,则X为最优解。
2、无穷多最优解的判别:
若X=(x1x2….xn)T为一个基可行解,存在所有λj 0,又存在某一非基变量xk对应的判别数λk = 0,则此LP问题有无穷多解。
3、无界解的判别:
若X=(x1x2….xn)T为一个基可行解,其中某个非基变量xk对应的判别数λk > 0,且对应的系数矩阵aik 0,则此LP问题具有无界解。(或称无最优解,最优解 无穷)4 .人工变量的引入及其解法
当约束条件为“”型,引入剩余变量和人工变量4 .人工变量的引入及其解法
当约束条件为“”型,引入剩余变量和人工变量由于所添加的剩余变量的系数为1,不能构成初始基变量,为此引入一个人为的变量(注意,此时约束条件已为“=”型),以便取得初始基变量,故称为人工变量
由于人工变量在原问题的解中是不能存在的,应尽快被迭代出去,因此人工变量在目标函数中对应的系数应具有惩罚性,称为罚系数。罚系数的取值视解法而定
两种方法
大M法
两阶段法(1)两阶段法:(1)两阶段法:null作辅助问题解题过程:max = -y1 - y2- … -ymnull 从第一阶段得到的基本可行解开始,继续用单纯形法进行迭代,直到找出原问题的最优解或判断具有无界解。第二阶段:例3 用两阶段法求解下列LP问题例3 用两阶段法求解下列LP问题null引入人工变量x6 , x7构造下列辅助问题:nullx300-2130-11000-311011nullx300-2112-1x20-2-50000-11-12-12nullx11/3-2/34102/3-4/30-1/3-1/3-29得到原问题的最优解为:X*=(4 1 9 0 0)T
f * =2(2) 大M法:(2) 大M法:–Mx6 – Mx7(M为任意大的正数)null3 -1 -1 0 0 -M -M0
-M
-Mnull3 -1 -1 0 0 -M -M0
-M
-1null3 -1 -1 0 0 -M -M0
-1
-1null3 -1 -1 0 0 3
-1
-1得到原问题的最优解为:X*=(4 1 9 0 0)T
f * =2练习:练习:标准化:大M法的一些说明大M法的一些说明 大M法实质上与原单纯形法一样,M可看成一个很大的常数
人工变量被迭代出去后就不会再成为基变量
当检验数都满足最优条件,但基变量中仍有人工变量,说明原线性规划问题无可行解
大M法手算很不方便
因此提出了两阶段法
计算机中常用大M法
两阶段法手算可能容易
单纯型法的一些具体问题
a.关于无界解问题单纯型法的一些具体问题
a.关于无界解问题可行区域不闭合(缺约束条件)
单纯型表中入变量 x j* 对应的列中所有 b.关于多重解问题 b.关于多重解问题多个基可行解都是最优解,这些解在同一个超平面上,且该平面与目标函数等值面平行
最优单纯形表中有非基变量的检验数为0
最优解的线性组合仍是最优解,即
X=k1X1+k2X2,k1+k2=1 c.关于无可行解问题 c.关于无可行解问题约束条件互相矛盾,无可行域
单纯形表迭代到最优解时,人工变量仍在基变量中
d.关于退化问题 d.关于退化问题退化问题的原因很复杂
当单纯形表中同时有多个基变量可选作出变量时
退化的严重性在于可能导致死循环,克服死循环的方法有“字典序”法
一、判断题
一、判断题
1、线性规划问题的每一个基解对应可行域的一个顶点。
2、图解法与单纯形法,虽然求解的形式不同,但从几何上理解,两者是一致的。
3、线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点。
4、若x1、x2分别是某一线性规划问题的最优解,则
x=λ1 x1+λ2x2也是该线性规划问题的最优解,其中λ1
λ2为正的实数。
5、对一个有n个变量、m个约束的标准形的线性规划问题,其可行域
的顶点恰好为Cnmnull6、单纯形法迭代的过程就是从一个基可行解(顶点)到另一个基可行解(顶点)的过程。
7、用单纯形方法,正的判别数对应的变量都可以作为换入变量。
8、线性规划问题的数学模型增加约束条件,可行域范围一般缩小,减少约束条件,可行域范围一般扩大。2、计算题2、计算题 下表是求极大化线性规划问题的单纯形表,表中无人工变量,a1 ,a2,a3,d,c1,c2为待定常数,试说明这些常数满足什么条件,能使以下结论成立:nullnull (1)表中解为唯一最优解;
(2)表中解为最优解,但存在无穷多最优解;
(3)该线性规划问题无最优解;
(4)现行解不可行(说出哪一个变量);
(5)现行解是退化的基可行解(哪个变量造成了退化);
(6)表中解非最优,为改进解,选换入变量x1,换出变量x6.3、maxf=5x1+3x2,求abcdefg的值3、maxf=5x1+3x2,求abcdefg的值