单纯形法解线性规划问题

《单纯形法解线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题minf=5x1+x2s.t.2x1+x2≥2-x1+x2≤1x1+2x2≥2x1,x2≫0解：1)、将该线性问题转为标准线性问题2x1+x2-x3=2-x1+x2+x4=1x1+2x2-x5=2x1,x2,x3,x4,x5≫0一、第一阶段求解初始可行点2)、引入人工变量修改约束集合2x1+x2-x3+x6'=2-x1+x2+x4+x7'=1x1+2x2-x5+x8'=2xi≥0,i=1,2,…,8取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。x1x2x

2、3x4x5x6'2-2-112x7'11-1-11x8'2-1-212f'5-2-41-115000003)、对上述单纯形表进行计算，是目标函数f'进一步减小，选x2为要改变的决策变量，计算改变的限值。x1x2x3x4x5x6'2-2-1121x7'11-1-110x8'2-1-2120f'5-2-41-115100000010004)、由于x7'，x8'为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加x1的值使目标函数值更小。x1x3x4x5x6'1-31110x211-1143f'1-3111000001

3、30005）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为x1=13，x2=43二、第二阶段用单纯形法求解最优解6）由1）中的标准线性问题方程式组得到单纯形表如下表，采用5）中的初始可行点计算。x1x2x3-2210x411-10x5-2121f5131343要使目标函数继续减小，需要减小x1或x2的值，由以上计算，已经有两个松弛变量为零，因此x1或x2不能再减小了，故该初始可行点即为最优解。minf=5x1+x2=32、求解问题maxf=2x1+x2+x3s.t.x1+x2+x3≤10x1+5x2+x3≥20x1,x2,x3≥0如果目标函数

4、变成f=cx1+x2+x3，确定使原解仍保持最优的c值范围，并把目标函数最大值变达成c的函数。解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。1）将问题华为标准线性问题minf'=-2x1-x2-x3s.t.x1+x2+x3+x4=10x1+5x2+x3-x5=20x1,x2,x3,x4,x5≥02）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解x1x2x3x410-1-1-110x5-20151-20f'-2-1-10000要使目标函数minf'=-2x1-x2-x3继续减小，可以增大x1，增

5、大的限值是10。x1x2x3x410-1-1-1100x5-20151-20-10f'-2-1-10-2000010003）转轴。将为零的松弛变量x4和决策变量x1交换进行转轴x2x3x4x110-1-1-110152x5-1040-1-100f'-20112-20-3520005200由目标函数minf'=-2x1-x2-x3，x2增加时f会继续减小。4）由上图可得x4和x5都为0，问题变量不能继续减小，所以已到达最优解。x1=152，x2=52，x3=0时，目标函数maxf=2x1+x2+x3=352。5）如果目标函数为maxf=cx1+x2+x3，由最后一次

6、变形得x1=10-x2-x3-x4，x2=x5+x4+10/4，得minf'=-cx1-x2-x3=-152c-5/2+5c-14x4+c-14x5+（c-1）x3x3x4x5f'-152c-5/2(c-1)5c-1/4(c-1)4-152c-5/2决策变量x3，x4，x5都为零，要使最优解保持不变，则系数为正：5c-1>0c-1>0解得c>1