单纯形法求解全过程详解共9页

第1页共9页单纯形法例题：某工厂生产I、II两种商品,已知生产单位商品所需的设备台时、A、B两种原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品I可获利3元，每生产一件商品II可获利4元。写出使该工厂所获利润最大的线性规划模型,并用单纯形法求解。产品I产品II限额设备2140台时原材料1330KG解：设生产产品I的数量为1x，生产产品II的数量为2x，所获利润为z，相应的模型为：⎪⎩⎪⎨⎧≥≤+≤++=0,30340243max21212121xxxxxxxxz标准型⎪⎩⎪⎨⎧≥=++=+++=0,,,30340243max432142132121xxxxxxxxxxxxz用单纯形法求解。（1）建立初始单纯形表，即将目标函数和约束条件填入表格中。3400b1x2x3x4x402110301301（2）挑选单位阵为初始基。在本题中初始基],[431PPB=，相应的，基变矢TBxxX],[431=。（3）将初始基],[431PPB=对应的基变量按顺序填入单纯形表中的BX一列。3400BXb1x2x3x4x3x4021104x301301这时，我们可以得到初始基],[431PPB=对应的基可行解。即令非基变量0,021==xx，根据表中的约束条件可得30,4043==xx（这两个值正好是表中基变量对应的资源向量b对应的分量，为什么？）第一个基可行解为TX]30,40,0,0[1=。（4）找到了第一个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准是：非基变量jx对应的检验数jBjjPBCc⋅⋅−=−1σ是否0≤。如果所有第2页共9页非基变量的检验数jσ均0≤，那么该基可行解为最优解，如果有一个或若干个非基变量的检验数jσ0，那么该基可行解不是最优解，需要继续找另一个基可行解。因为我们选择的初始基IB=1，所以其逆矩阵IB=−11。相应的，检验数jBjjPBCc⋅⋅−=−1σ，⇒jBjjPCc⋅−=σ。在计算检验数时需用到BC（基变量在目标函数中的系数向量），将BC填入表格最左一列中。3400BCBXb1x2x3x4x03x40211004x301301接下来就是计算非基变量的检验数（基变量的检验数均等于0，为什么?）3400BCBXb1x2x3x4x03x40211004x301301jBjjPCc⋅−=)1(σ00这时，非基变量的检验数：()3120,03111=⎟⎟⎠⎞⎜⎜⎝⎛⋅−=⋅−=PCcBσ，()4310,04222=⎟⎟⎠⎞⎜⎜⎝⎛⋅−=⋅−=PCcBσ；均0，所以该基可行解还不是最优解。接下来，我们的任务就是找另一个基可行解。当然，我们希望接下来的这第二个基可行解2X对应的目标函数值比第一个基可行解1X对应的目标函数值更接近max值。（5）找另一个基可行解。由非基变量→基变量的决策变量，我们称之为进基变量，挑选原则：{}0maxjjσσkσ=，那么kx进基（即由非基变量变为基变量）。由基变量→非基变量的决策变量，我们称之为出基变量，挑选原则：⎭⎬⎫⎩⎨⎧0minikikiaablklab=，那么原来的第l个基变量出基（即由基变量变为非基变量）。第3页共9页我们称lka为主元素，简称主元，在单纯形表中用[]表示。题中，进基变量：{}2214,3maxσσσσ====k，即2x进基成为基变量。出基变量：=⎭⎬⎫⎩⎨⎧0minikikiaab⎭⎬⎫⎩⎨⎧222121,minabab⎭⎬⎫⎩⎨⎧===10330,40140min222ab=，即第2个基变量出基，第2个基变量是4x，所以是4x出基成为非基变量。主元为22a。总结：2x进基成为基变量，4x出基成为非基变量。也就是说2x代替4x成为基变量，即：3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x42x这时的基变矢TBxxX],[232=。这两个基变量对应的系数列向量组成的矩阵即为2B。因为在计算非基变量的检验数的计算过程中会用到12−B,计算逆矩阵是一件麻烦事，我们当然不想干，怎么办呢？为了计算简便，我们期待IPPB==],[232，目前我们只是期待而已。下面先把我们的“期待”填入单纯形表中。第4页共9页3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x0142x10jBjjPCc⋅−=)2(σ先来看1X对应的主元22a所在的行。行的系数表示的是约束条件：421330xxx++=②。对应于2X，我们期待的是：在这个约束条件中，2x的系数＝1，3x的系数＝0。要做到这一点，只需在等式左右同除以3（主元22a本身），得421313110xxx++=②’，式②’与式②等价。接着看另一行。即第一行，该行的系数表示的是约束条件：321240xxx++=①。对应于2X，我们期待的是：在这个约束条件中，2x的系数＝0，3x的系数＝1。要做到这一点，需要将①－×1②’431313530xxx−+=⇒①’，式①’与式①等价。为实现我们的期待，将约束条件⎩⎨⎧++=++=421321330240xxxxxx就等价的代换成⎪⎩⎪⎨⎧++=−+=421431313110313530xxxxxx将这两个与原约束条件等价的约束条件填入表格中。第5页共9页3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30350131−42x10311031jBjjPCc⋅−=)2(σ这时，我们可以得到基],[232PPB=对应的基可行解。即令非基变量0,041==xx，根据表中的约束条件可得10,3023==xx（这两个值正好是表中基变量对应的资源向量b对应的分量）那么，第2个基可行解为TX]0,30,10,0[2=。（6）找到了第2个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4）。3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30350131−第6页共9页42x10311031jBjjPCc⋅−=)2(σ350034−这时，非基变量的检验数34,3541−==σσ，其中01σ，所以该基可行解不是最优解。（7）接下来，我们的任务就是找另一个基可行解。即转回到步骤（5）。选择进基变量：1135maxσσσ==⎭⎬⎫⎩⎨⎧=k，即1x进基成为基变量。出基变量：⎭⎬⎫⎩⎨⎧212111,minabab⎭⎬⎫⎩⎨⎧=×=×=30310,185330min111ab=，即第1个基变量出基，第1个基变量是3x，所以是3x出基成为非基变量。主元为11a。总结：1x进基成为基变量，3x出基成为非基变量。也就是说1x代替3x成为基变量，即：3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30[35]0131−185330=×42x1031103130310=×jBjjPCc⋅−=)2(σ350034−31x42xjBjjPCc⋅−=)3(σ这时的基变矢TBxxX],[213=。这两个基变量对应的系数列向量组成的矩阵即为3B。第7页共9页同样的，我们期待IPPB==],[213。3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30[35]0131−185330=×42x1031103130310=×jBjjPCc⋅−=)2(σ350034−31x1042x01jBjjPCc⋅−=)3(σ先来看主元11a所在的行。行的系数表示的是约束条件：431313530xxx−+=①’。我们期待的是：在约束条件中，1x的系数＝1，2x的系数＝0。要做到这一点，只需在等式左右同除以35（主元11a本身），得431315318xxx−+=①’’，式①’’与式①’等价。接着看另一行。即第二行，该行的系数表示的是约束条件：421313110xxx++=②’。我们期待的是：在约束条件中，1x的系数＝0，2x的系数＝1。要做到这一点，需要将②’－×31①’’43252514xxx+−=⇒②’’，式②’’与式②’第8页共9页等价。约束条件⎪⎩⎪⎨⎧++=−+=421431313110313530xxxxxx就等价的代换成⎪⎩⎪⎨⎧+−=−+=43243152514515318xxxxxx将这些系数填入表格中。3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30[35]0131−185330=×42x1031103130310=×jBjjPCc⋅−=)2(σ350034−31x18105351−42x40151−52jBjjPCc⋅−=)3(σ这时，我们可以得到基],[213PPB=对应的基可行解。即令非基变量0,043==xx，根据表中的约束条件可得4,1821==xx（这两个值正好是表中基变量对应的资源向量b对应的分量）那么，第3个基可行解为TX]0,0,4,18[3=。（8）找到了第3个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4）。第9页共9页3400BCBXb1x2x3x4xikiab03x40211040140=04x301[3]0110330=jBjjPCc⋅−=)1(σ340003x30[35]0131−185330=×42x1031103130310=×jBjjPCc⋅−=)2(σ350034−31x18105351−42x40151−52jBjjPCc⋅−=)3(σ001−1−这时，非基变量的检验数1,143−=−=σσ，均0，所以该基可行解就是最优解。即TX]0,0,4,18[=∗，7044183=×+×=⋅=∗bCzB。