运筹学习题课PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,运筹学第一次习题课,1,1.1,用图解法求解下列线性规划问题，并指出问题具有最优解、无穷解无界解还是无可行解。,（,a,）,S.T,2,2025/5/22 周四,解：,该问题有无穷最优解，即满足 且,的所有（），此时目标函数值为,3,3,2025/5/22 周四,（,c,）,由图可知在点（,10,，,6,）处目标函数取得最大值,16,。线性规划有唯一最优解。,4,2025/5/22 周四,（补充）,（,b,）,5,2025/5/22 周四,解：,用图解法找不到满足所有约束条件的公共范围，则该问题无解。,6,2025/5/22 周四,1.2,对下述线性规划找出所有基解，指出哪些是基可行解，并确定最优解,。,（,a,）,s.t,.,7,2025/5/22 周四,解,:,写出约束方程的系数矩阵,A=1 4-2 8,-1 2 3 4,R(A)=2,，所以只要找出,2,个列向量组成矩阵满秩，这两个向量就是线性规划问题的一个基，,由于 与 线性相关不能构成基，构建表格列出全部基，基解，指出基可行解，*标注的为最优解：,8,2025/5/22 周四,基,是基可行解？,目标函数值,0 0 0,是,-2,8 0 3 0,是,31*,0 0 0 1/4,是,-3/2,0 0 0,是,-2,0 0 0 1/4,是,-3/2,基解,9,2025/5/22 周四,(,补充,),（,b,）,10,2025/5/22 周四,11,2025/5/22 周四,12,2025/5/22 周四,1.3,分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基行解分别,对应图解法中可行域的哪一个定点,.,(b),S.t.,13,2025/5/22 周四,由图可知最优解为,的解,x=(7/2,3/2),最大值,z=17/2,14,2025/5/22 周四,(2),单纯形法,首先在各约束条件上添加松弛变脸，将问题转化为标准形式,S.t.,15,2025/5/22 周四,则 组成一个基，令,得基可行解 ，由此列出初始单纯形表,2 1 0 0 0,基,b,0 15,0 24,0 5,0 5 1 0 0,6,2,0 1 0,1,1 0 0 1,-,4,5,2 1 0 0 0,16,2025/5/22 周四,初始表对应定点（,0,，,0,）,对应点（,4,，,0,）,2 1 0 0 0,基,b,0 15,2 4,0 1,0 5 1 0 0,1,1/3,0 1/6 0,0,2/3,0 -1/6 1,3,12,3/2,0 1/3 0,-1/3 0,17,2025/5/22 周四,表明已经找到问题的最优解,对应点 ，最大值为,17/2,2 1 0 0 0,基,b,0 15/2,2 7/2,1 3/2,0 0 1 5/4,-,15/2,1,0 0,1/4 -1/2,0 1 0-1/4 3/2,0 0 0 -1/4 -1/2,18,2025/5/22 周四,(,补充,),（,a,）,st,19,2025/5/22 周四,（图解法）,20,2025/5/22 周四,（单纯形法）,21,2025/5/22 周四,22,2025/5/22 周四,23,2025/5/22 周四,24,2025/5/22 周四,1.6,将下列线性规划问题化为标准形式，并列出初始单纯形表。,（,a,）,st,25,2025/5/22 周四,解：,在约束条件中添加松弛变量或剩余变量，且令 ，,该问题转化为,26,2025/5/22 周四,其约束系数矩阵为,2 3 -3 4 1 0,A=4 1 -1-2 0-1,3 -1 1-3 0 0,在,A,中人为的添加两列单位向量,27,2025/5/22 周四,2 3 -3 4 1 0 0 0,A=4 1 -1 -2 0-1 1 0,3 -1 1 -3 0 0 0 1,令,得到初始单纯形表,28,2025/5/22 周四,-3,-1,1,-2,0,0,-M,-M,基,b,0,12,2,3,-3,4,1,0,0,0,-M,8,4,1,-1,-2,0,-1,1,0,-M,6,3,-1,1,-3,0,0,0,1,7M-3,-1,1,-2-M,0,-M,0,0,29,2025/5/22 周四,1.7,分别用单纯形法中的大,M,法和两阶段法求解下列线性规划问题,并指出属那里类解,(a),st,30,2025/5/22 周四,(1),大,M,法,将上述线性规划问题中分别减去剩余变量 再加上人工变量 ，得,st,31,2025/5/22 周四,其中,M,是一个任意大的正数。据此列出单纯形表,2,-1,2,0,-M,0,-M,0,-M,基,b,-M,6,1,1,1,-1,1,0,0,0,0,6,-M,2,-2,0,1,0,0,-1,1,0,0,-,-M,0,0,2,-1,0,0,0,0,-1,1,0,2-M,3M-1,2+M,-M,0,-M,0,-M,0,32,2025/5/22 周四,2,-1,2,0,-M,0,-M,0,-M,基,b,-M,6,1,0,3/2,-1,1,0,0,1/2,0,4,-M,2,-2,0,1,0,0,-1,1,0,0,2,-1,0,0,1,-1/2,0,0,0,0,-1/2,1,-,2-M,0,-M,0,-M,0,33,2025/5/22 周四,2,-1,2,0,-M,0,-M,0,-M,基,b,-M,3,4,0,0,-1,1,3/2,-3/2,1/2,-1/2,3/4,2,2,-2,0,1,0,0,-1,1,0,0,-,-1,1,-1,1,0,0,0,-1/2,1/2,-1/2,-1/2,-,4M+5,0,0,-M,0,34,2025/5/22 周四,由于,0,且 ，则该线性规划问题有无界解,2,-1,2,0,-M,0,-M,0,-M,基,b,2,3/4,1,0,0,-1/4,3/8,-3/8,1/8,-1/8,3/4,2,7/2,0,0,1,-1/2,-1/4,1/4,1/4,-1/4,-,-1,7/4,0,1,0,-1/4,1/4,-1/8,1/8,-3/8,-5/8,-,0,0,0,5/4,-3/8,35,2025/5/22 周四,（,2,）两阶段法,现在上述线性规划问题的约束条件中分别减去剩余变量 ，再加上人工变量 ，得第一阶段的数学模型,由此可列出单纯形表,36,2025/5/22 周四,0,0,0,0,1,0,1,0,1,基,b,1,6,1,1,1,-1,1,0,0,0,0,6,1,2,-2,0,1,0,0,-1,1,0,0,-,1,0,0,2,-1,0,0,0,0,-1,-,0,1,-3,-1,1,1,37,2025/5/22 周四,0,0,0,0,1,0,1,0,1,基,b,1,6,1,0,3/2,-1,1,0,0,1/2,-1/2,4,1,2,-2,0,1,0,0,-1,1,0,0,2,0,0,0,1,-1/2,0,0,0,0,-1/2,1/2,-,1,0,-5/2,1,1,38,2025/5/22 周四,-,0,0,0,0,1,0,1,0,1,基,b,1,3,4,0,0,-1,1,3/2,-3/2,1/2,-1/2,3/4,0,2,-2,0,1,0,0,-1,1,0,0,-,0,1,-1,1,0,0,0,-1/2,1/2,-1/2,1/2,-,-4,0,0,1,-3/2,3/2,-1/2,39,2025/5/22 周四,第一阶段求得最优解,目标函数的最优值为,0,。,0,0,0,0,1,0,1,0,1,基,b,0,3/4,1,0,0,-1/4,1/4,3/8,-3/8,1/8,-1/8,0,7/2,0,0,1,-1/2,-1/2,-1/4,1/4,1/4,-/4,0,7/4,0,1,0,-1/4,1/4,-1/8,1/8,-3/8,3/8,0,0,0,0,1,0,1,0,1,40,2025/5/22 周四,因为人工变量全部为,0,，则,X,是线性规划问题的基可行解，于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量表取消，并填入原问题的目标函数的系数，进行第二阶段的运算，其表如下：,41,2025/5/22 周四,You,有表知道,0,而 所以线性规划问题有无界解,2,-1,2,0,0,0,基,b,2,3/4,1,0,0,-1/4,3/8,1/8,2,7/2,0,0,1,-1/2,-1/4,1/4,-1,7/4,0,1,0,-1/4,-1/8,-3/8,0,0,0,5/4,-3/8,-9/8,42,2025/5/22 周四,(,补充,),（,b,）,st,43,2025/5/22 周四,（大,M,法）,化成标准形,44,2025/5/22 周四,-2,-3,-1,0,0,-M,-M,基,b,-M,8,1,4,2,-1,0,1,0,2,-M,6,2,3,0,0,-1,0,1,3,4M-2,6M-3,2M-1,-M,-M,0,0,45,2025/5/22 周四,-2,-3,-1,0,0,-M,-M,基,b,-3,2,1/4,1,1/2,-1/4,0,1/4,0,8,-M,2,5/2,0,-1,1/2,-1,-1/2,1,4/5,0,-M,0,46,2025/5/22 周四,-2,-3,-1,0,0,-M,-M,基,b,-3,9/5,0,1,3/5,-3/10,1/10,3/10,-1/10,-2,4/5,1,0,-2/5,1/5,-2/5,-1/5,2/5,0,0,0,-1/2,-1/2,47,2025/5/22 周四,48,2025/5/22 周四,（二阶段法）,49,2025/5/22 周四,50,2025/5/22 周四,51,2025/5/22 周四,52,2025/5/22 周四,1.10,判断并说明理由,（,a,）对取值无约束的变量 通常令,，其中 ，在单纯形法求得的最优解中，有可能同时出现,（,b,）若,X1,X2,分别是某一线性规划的最优解，则,X=aX1+(1-a)X2,也该是线性规划问题的最优解，其中,0 a 1,。,53,2025/5/22 周四,（,c,）单纯形法计算中选取最大正校验数,对应的变量 作为换入基的变量，将使得迭代后的目标函数值得到最快增长。,（,d,）含有,n,个变量,m,个约束的标准型的线性规划问题，基解数恰好为 。,（,e,）如线性规划问题存在可行域，则可行域一定包含坐标的原点。,54,2025/5/22 周四,1.12,已知线性规划问题,St,用单纯形法求解最终单纯形表如下，表中,为松弛变量,55,2025/5/22 周四,1/5,1,0,3/5,-1/5,3/5,0,1,-1/5,2/5,-7/10,0,0,-3/5,-4/5,56,2025/5/22 周四,解：,由表可知 为此线性规划问题最优解，必在可行域顶点上，此顶点为,带入解得,57,2025/5/22 周四,由表可知,解得,58,2025/5/22 周四,1.19,已知线性规划问题迭代某步的单纯形表如下：,b,4,1,0,0,2,-1,-5,0,1,-1,0,3,-3,0,0,-4,1,0,0,0,0,59,2025/5/22 周四,问在什么条件下：,（,a,）表中解为唯一最优解；,（,b,）表中解最优，但具有无穷多最优解；,（,c,）现有基解为退化解；,（,d,）问题具有无界解；,（,e,）现有基解中，用 替换 后目标函数进一步优化。,60,2025/5/22 周四,61,2025/5/22 周四,62,2025/5/22 周四,1.21,北海银行一个分理处每天个时间段对职员的需求如下表：,该分理处分别聘用部分全日制职员和部分非全日制职员。全日制职员每天从,9,：,00,工作到,17,：,00,，中间安排一小时午餐休,时段,910,1011,1112,1213,1314,1415,1516,1617,所需人数,4,5,6,6,5,6,8,8,63,2025/5/22 周四,息（分两批，一批为,12,：,0013,：,00,，另一批为,13,：,0014:00,）每天薪金,240,元。非全日制职员分留批次上班，时间分别为,9,：,0012,：,00,，,10,：,0013:00,，,11,：,0014,：,00,，,12,：,0015,：,00,，,13,：,0016,：,00,，,14,：,0017:00,。每人每天薪金,80,元。问该分理处聘用全日制和各批此的非全日制职员各多少人，能满足需求又使薪金支出最少。,64,2025/5/22 周四,解：,令两种全日制的员工人数为 和 ，个时段非全日的人数为,，则,65,2025/5/22 周四,以,st,66,2025/5/22 周四,1.22,工业原材料合理利用,要制作,100,套架子，每套有长,2.9m,、,2.1m,和,1.5m,的钢筋各一根。已知原材料长,7.4m,，应如何切割，使用原材料最节省，试建立线性规划模型并求解。,67,2025/5/22 周四,68,2025/5/22 周四,69,2025/5/22 周四,