单纯形法-人工变量法VIP专享VIP免费

人工变量的引入及其解法当约束条件为“”型，引入剩余变量和人工变量•由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量•由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定•两种方法–大M法–二阶段法minz=-3x1+x2+x3s.t.01232411232131321321x,x,xxxxxxxxx标准型：maxz’=3x1-x2-x3s.t.012324112513153214321x,,xxxxxxxxxxx其中第2、3个约束方程中无明显基变量，分别加上人工变量x6,x7,约束方程为“>=”或“=”的情形（加人工变量）01232411271731653214321x,,xxxxxxxxxxxxx这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：01232411271731653214321x,,xxxxxxxxxxxxx反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例的单纯形表格为：只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。大M法在目标函数中加上惩罚项。max=3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x7111311-4-2-2101211000-10010001j3-6MM-13M-10-M000x4103-20100-1-Mx610[1]00-11-21-1x31-20100011-1+M00-M0-3M+10x412[3]001-2-1x210100-14-1x31-201001000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3-2000-1/3-1/3X*=(4，1，9，0，0)T,z*=2113/21〔〕只要原问题有可行解，该最小化问题的最优目标函数值就是0，解得的最优解x6=0，x7=0，对应原问题一个基可行解。反之若该问题的最优解目标函数值大于零，则说明原问题无可行解。两阶段法第一阶段：以人工变量之和最小化为目标函数。min=x6+x7第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。例8试用两阶段法求解线性规划问题minz=-3x1+x2+x3s.t.0123241123211321321x,x,xxxxxxxxx3解：先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：min=x6+x7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，…，x70第一阶段的单纯形表如下：cj0000011CBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-21012[1]1000-10010001113/216-1-30100010x4x6x3101130-2-2[1]00011000-10010-1-21—1—0-100103000x4x2x3121130-2010001100-2-10210-5-204——00000111第一阶段求得的结果是=0,最优解是（0,1,1,12,0,0,0）T因人工变量x6=x7=0，所以(0,1,1,12,0)T是原线性规划问题的基可行解。第二阶段运算:cj-31100CBXBbx1x2x3x4x5011x4x2x31211[3]0-2010001100-2-104——σj-10001-311x1x2x34191000100011/302/3-2/3-1-4/3σj20001/31/3约束方程为“>=”或“=”的情形（加人工变量）人工变量法（确定初始可行基）：0,,,0,,1111222121111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。MaxZ=2x1+x2+x3s.t.4x1+2x2+2x3≥42x1+4x2≤204x1+8x2+2x3≤16x1，x2，x3≥0用两阶段法求下面线性规划问题的解线性规划问题解的讨论一、无可行解maxz=2x1+4x2x1+x2102x1+x240x1,x20人工变量不能从基底人工变量不能从基底换出，此时原线性规换出，此时原线性规划问题无可行解。划问题...