单纯形法解线性规划问题培训资料

1、单纯形法解线性规划问题、用单纯形第I阶段和第U阶段解下列问题mins.t申+尢宀 -裔m Q xi 2x2>2 xlx2 » 0解：1）、将该线性问题转为标准线性问题+ x2 - x3 = 2-Xi + X2 + X4= 1X1 + 2龙 2 - xs = 2所七也耳心» 0、第一阶段求解初始可行点2）、引入人工变量修改约束集合f注;+ x2 -叼+人=2-X, 1 x2 4-+ x7 = 1丹+ 2七-心+ %二2x（ > O.i = 1,28取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值5

2、2-2-11211-1-112-1-212f5-2-41-115000003）、对上述单纯形表进行计算，是目标函数f进一步减小，选"为要改变的 决策变量，计算改变的限值。阿网2-2-112111-1-1102-1-21205-2-41-1151000004）、由于对，九为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加可的值使目标函数值更小i-3iii0i1-ii恻i-3iii00000卩归0005）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为工】='R， x2 =二、第二阶段用单纯形法求解最优解6

3、）由1）中的标准线性问题方程式组得到单纯形表如下表，采用5）中的初始可行点计算F3r-2210i1-10-2121i513】/3|*/3|要使目标函数继续减小，需要减小 可或*的值，由以上计算，已经有两个松弛变量为零，因此或 不能再减小了，故该初始可行点即为最优解。2、求解问题max /= 2xr + x2 + xAst片+也+乃“。阿! 5七+帀 20 卜丿说3王0如果目标函数变成+叱+乃,确定使原解仍保持最优的c值范围，并把目标函数最大值变达成c的函数。解：先采用单纯形法求解最优解，再对保持最优解时 C值的范围进行讨论1)将问题华为标准线性问题min/ =2x1x2-xj!st心+勺+叼十

4、心=104 5x2 + x3-x5 = 20xpx2lx3,x/lx5 > 02）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解10-1-1-110-20151-201-2-1-10000要使目标函数 聞八-"Us继续减小，可以增大心，增大的限值是10。V|10-1-1-1100-20151-20-101-2-1-10-2000010003）转轴。将为零的松弛变量心和决策变量心交换进行转轴X2£戶110-1-1-11012-1040-1-100ki-20112-200005/200由目标函数皿耐 2衍-七-巧，5增加时会继续减小4）由上图可得 和都为0,问题变量不能继续减小，所以已到达最优巧=15化，七=»2,网=0时，目标函数5）如果目标函数为=纹】+竝+ %，由最后一次变形得衍= 10-孔一力-奋七=（与+引+ 1°）”得min f' = -cx -x2-x= '15/2c-5/2 + 竺f 斗+ 呼2心+（c-1）心/lb-5/22