《单纯形法解线性规划问题》由会员分享，可在线阅读，更多相关《单纯形法解线性规划问题（4页珍藏版）》请在装配图网上搜索。
1、一、用单纯形第I阶段和第I【阶段解下列问题min f = 5%! + x2S.t.2 %! + %2 2X1 + x2 1+ 2%2 2 %2 0解：1）、将该线性问题转为标准线性问题2%i + x2-x3-%i +x2+x4 = 1+ 2%2 %5 = 2一.第一阶段求解初始可行点2）、引入人工变量修改约束集合2%1 + %2 %3 + %$ = 2%1 + %2 + %4 + 坊=1%! + 2%2 %5 + %8 = 22 0* i = 1,2,. ,8取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。X1兀2X4221
2、211121212f52-4115000003）、对上述单纯形表进行计算，是目标函数广进一步减小，选恋为要改变的决策变量, 计算改变的限值。X2X3兀4兀522-1121x711-1110X82-12120f5241115100000010004）、由于坊，对为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。 同时将以改变的决策变量转换为状态变量。增加心的值使目标函数值更小。X3X4兀5X6131110X211114/3f13111000001/30005）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为勺=1/3, x2 =4/3二、第二阶段用单纯形法求解最优
3、解6）由1）中的标准线性问题方程式组得到单纯形表如下表，采用5）中的初始可行点计算。X1七2210X411J0兀52121f5131/34/3要使目标函数继续减小，需要减小衍或%2的值，由以上计算，已经有两个松弛变量为零，因 此帀或%2不能再减小了，故该初始可行点即为最优解。min / = 5%! + 恋=32、求解问题max / = 2 %! + x2 + x3S.t. + %2 + %3 S 10.%! + 5%2 + %3 20二 0如果目标曲数变成f= CXx + %2+%3，确定使原解仍保持最优的C值范围，并把目标函数最 大值变达成C的函数。解：先采用单纯形法求解最优解，再对保持最优
4、解时C值的范闱进行讨论。1）将问题华为标准线性问题minfr = 2x1 x2 x2St r %! +%2 + x3 +x4 = 1.+ 5%2 + 兀3 %5 = 20XlfX2fX2t X4/%5 02）用量纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值 为零值，求解初始解和最优解XlX2x3X4101-1-110X5-20151-20f2-1-10000要使目标函数min厂=2帀七一七继续减小,可以增大%增大的限值是10。XlX2X3x410-1-11100X5-20151-20-10f-2-110-2000010003）转轴。将为零的松弛变量兀4和决策变量%1交换
5、进行转轴X2兀3x4X110-1J1015/2X5-1040-100f-20112-20-35/20005/200由目标函数min广=2%i %2 %3，兀2增加时f会继续减小。4）由上图可得%4和心都为0，问题变量不能继续减小，所以已到达最优解。%1 = 15/2, %2 = 5/2, %3 = 0时,目标函数 max/* = 2xx + x2 + x3 = 35/2。5)如果目标函数为max f = cxx + x2 + x3,由最后一次变形得= 10 -x2 -x3 - x4, %2 =(兀5 + 兀4 + 10)/4,得min 厂 = c%! x2 x3 = 15/2 c 5/2 + 5打1*4 + %5+ (c-1) x3X5f-15/2C-5/2(c-1)(5c 1)/4(C - 1)/4-15/2C-5/2决策变量乃，%4,心都为零，要使报优解保持不变，则系数为正:5c-l 0_ c- 1 0 解得cl
单纯形法解线性规划问题
