管理运筹学演示线性与单纯形

34x1=16484Q4Q1Q2(4,2)x1x24x2

=12x1+2x2=8o.建立坐标系,绘制约束条件.

确定可行域.

绘制和平移目标函数等值线,确定最优解、最优值Q3可行域C步骤:线性规划图解法X*=(4,2)TZ*=144o34x1=164Q4Q1Q2(4,2)x1x24x2

=12x1+2x2=8Q3(2,3)可行域82x1+4x2=zC线性规划求解的几种结果

(无穷多解或多重解)－2x1+x2=44ox2x1x1－x2=22可行域无界x1+x2=zc目标值

z趋于无穷大线性规划求解的几种结果(无界解或无有限最优解)目标值

z趋于无穷大目标值

z趋于无穷大目标值

z趋于无穷大目标值

z趋于无穷大1466ox2线性规划求解的几种结果(无可行解)x1x1+2x2=142x1+2x2=12可行域是空集7可行域是空集可行域是空集可行域是空集可行域是空集可行域是空集单纯形表结构例1：用单纯形法求线性规划问题：解：引人松弛变量、和，将上述线性规划模型化为标准形式。

松弛变量、和前的系数列向量构成单位阵，作为初始可行基。43000000000040032320000121008161240010000140031601001/44001011010-1/231010-1/201001/4800-41222230004322412-92000-3/4200-201/4111-130233000最优解:最优值:2最优解:最优值:最优解:最优值:最优解:最优值:最优解:最优值:2300041001/40400-21/21011/2-1/8020300-1.5-1/80-14例2:用大M法求线性规划模型:解：为构造一个初始可行基，引入松弛变量、剩余变量和人工变量和，并在目标函数中给人工变量加上“＋M”，变量、、和前的单位向量构成单位阵，可作为初始可行基。由于目标函数为求最小化，最优判别条件为。-31100M0MMM111-2110003-4120-1101-2010001-3+6M1-3M0M001-M0113/21100[

]01M10113-20100-10100-11-2-2010001-11-M00M03-M001100[

]01112113001-22-5000-11-2-2010001-10001M-1M+10140[

]-311419001/3-2/32/3-5/3000-11-20012/3-4/34/3-7/31100001/3M-1/3M-2/32最优解:最优值:-31100MM最优解:最优值:最优解:最优值:最优解:最优值:最优解:最优值:最优解:最优值:例3:用两阶段法求线性规划模型:解:

两阶段是将整个问题的求解过程分为两个阶段来处理：第一阶段：构造一个仅含有人工变量的辅助线性规划问题，并求解和判断原线性规划是否存在基可行解。如果w=0，原问题存在基可行解，可以进行第二阶段计算；否则，应停止计算。辅助线性规划的构成：目标函数取所有的人工变量之和，并求最小化；约束条件仍为原问题的约束条件，并以人工变量形成的单位阵作为可行基。0000010111111-2110003-4120-1101-20100016-30100-10113/21100[

]00110113-20100-10100-11-2-20100010-100103001100[

]01112113001-22-5000-11-2-2010001000001114-31100011001-100-31112113001-2000-1-2010001401/31/304191001/3-2/3000-10012/3-4/3010[

]第二阶段：在第一阶段的最终表中，去掉人工变量，并将目标函数系数换成原问题的目标函数系数，继续迭代。在第一阶段最优表中，w=0，人工变量从基变量中换出，得到原问题的一个可行基和基可行解X（0〕=(0,1,1,12,0)T，可转入第二阶段：434x2

=12Q2(4,2)84x1=164Q1(4,0)x1+2x2=8图解法与单纯形法的联系可行域可行域666x1x2o6666666单纯形法C对偶单纯形法例：用对偶单纯形法求解解：建立该问题的初始单纯形表，先将其化为标准形式，并找出对偶问题的初始可行基；-2-3-4-3-40000-1-2-110-21-301cj-2-3-400-4-2-21-3-3-4[]解：建立该问题的初始单纯形表，先将其化为标准形式，并找出对偶问题的初始可行基；解：建立该问题的初始单纯形表，先将其化为标准形式，并找出对偶问题的初始可行基；0-20-1/21-1/23/221-1/20-5/21/2-10-10-4-1-1-4-5/2-11/2-1-1/2-5/2[-5/2]-3-22/501-1/5-2/51/511/5107/5-1/5-2/5-8/5-1/500-3/52/511/5原问题的最优解