《管理运筹学》演示(线性规划与单纯形）.ppt

*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-100