胡运权运筹学第五版第一章习题讲解.ppt

1、习题讲解,课程：运筹学 内容：第一章课后习题解,作业分类汇总,1、LP问题解四种情况的判别 习题： 1.1(a)、1.1(b)、1.7(b) 2、LP问题解的基本概念 习题：1.2(b)、1.3(a) 3、LP问题的标准形式转化 习题：1.6(a) 4、单纯形法的计算 (标准型的系数矩阵中不包含单位矩阵的情况） 习题：1.7(b) 5、单纯形法计算的向量矩阵描述及特征应用 习题：1.8、1.12 6、现实问题应用 习题：1.13、1.14 7、证明题 习题：1.16、1.17,END,线性规划数学模型的标准形式,即：1.目标函数求极大值max z；2.全部是等式约束；3.常数项非负 （b 0

2、）；4.变量非负 （X 0 ) ；5.nm。,一般形式的线性规划数学模型转化为标准形式,1.目标函数为求最小值： 作变换，令z=(-z),化为求： max z = -( c1x1 +c2x2 + cnxn ) 2.约束条件为不等式：当约束条件为时，加一非负的松弛变量。 当约束条件为时，减一非负的剩余变量。 注：松弛变量在目标函数中的系数为0 3.取值无约束的变量：作变换，令xj=xj-xj(xj,xj0),即将其化为两个非负变量之差。 4.负变量 (xj0): 作变换,令xj= - xj ,0 5.常数项为负： 约束两端同乘（-1）即可。,几种解的基本概念,1.可行解： 满足系统约束条件和非负

3、性约束的解X=(x1 ,x2 , xn )T,称为LP问题的可行解。 2.最优解：满足目标函数值最大的可行解称为LP的最优解。 3.基（本）解：设B为LP问题的一个基，在系统约束方程组中，令非基变量xm+1= xm+2 =xn =0, 而B是满秩的，由克莱姆法则，可解出由m个基变量表示的唯一解XB= (x1 ,x2 , xm)T 或X= (x1 ,x2 , xm，0，0)T ，称X为LP问题的一个基解。 4.基（本）可行解：满足变量非负性约束的基解称为基可行解。,LP问题解四种情况的判别,1、LP问题的解总有四种情况： 唯一最优解 无穷多最优解 无界解 无可行解 2、判别方式： 图解法：直观性

4、强，但有其局限性，只适用于问题中有两个变量的情况。 单纯形法。,图解法,唯一最优解 无穷多最优解,无界解 无可行解,单纯形法,单纯形法计算的矩阵描述,均左乘矩阵B-1,课后题答案,课后题答案,1.2（b）答案：,课后题答案,1.3 答案： 单纯形法：图解法：,课后题答案,1.6（a）答案： 标准形式： 初始单纯形表：,课后题答案,1.7（b）答案： 大M法： 两阶段法： 最优解为： 因为：30，有非基变量检验数为0，所以该问题有无穷多最优解。 且，目标函数最优值为Z*=7.,课后题答案,1.8 答案： 最后结果：a3，b=2, c=4, d=-2, e=2, f=3, g=1, h=0, i=

5、5, j=5, k=-3/2, L=0.,课后题答案,1.12 答案 最后结果：b=5, c1= 3/2, c2=2, c3 =3,课后题答案,1.13 答案： 解：设该厂第i个月办理租借合同，租借j个月，租借面积为xij，则该问题的线性规划模型为：,课后题答案,1.14 答案： 解：设产品在A1B1上生产的数量记为x111，A1B2 、A1B3 、A2B1 、A2B2 、A2B3依次记为x112，x113，x121，x122，x123，产品在A1B1、A2B1上生产的数量记作x211，x221，III产品在A2B2上生产的数量记作x322，建立模型如下：,A1,A2,B1,B3,B2,III （一种方式）,A工序,B工序,I （2*3=6种方式）,II （2种方式）,课后题答案,课后题答案,1.16 答案： 由X*为最优解，可得此时：=C-CBB-1A0 (a) X*仍为最优解,max z=CX；=C-CBB-1A=(C-CBB-1A)0 (b)一般X*不再是问题的最优解。 =(C+)-(CB+B)B-1A=(C-CBB-1A)+(-BB-1A )(c)最优解变为X*，最优值不变。令X*=X/,课后题答案,1.17 答案：