运筹学习题课课件.ppt

《运筹学习题课课件.ppt》由会员分享，可在线阅读，更多相关《运筹学习题课课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学第一次习题课运筹学第一次习题课1.1用用图解法求解下列解法求解下列线性性规划划问题，并指出，并指出问题具有最具有最优解、无解、无穷解无界解解无界解还是无可行解。是无可行解。v（a）v S.T解：解：该问题有无穷最优解，即满足 且 的所有（），此时目标函数值为3 v（c）v由图可知在点（10，6）处目标函数取得最大值16。线性规划有唯一最优解。（补充）充）v（b）解：解：v用图解法找不到满足所有约束条件的公共范围，则该问题无解。1.2对下述下述线性性规划找出所有基解，指出划找出所有基解，指出哪些是基可行解，并确定最哪些是基可行解，并确定最优解解。v（a）v v s.t v .v解:写出约束

2、方程的系数矩阵 vA=1 4-2 8v -1 2 3 4R(A)=2，所以只要找出2个列向量组成矩阵满秩，这两个向量就是线性规划问题的一个基，由于 与 线性相关不能构成基，构建表格列出全部基，基解，指出基可行解，*标注的为最优解：基基 是基可行解？是基可行解？目目标函数函数值 0 0 0是-2 8 0 3 0是31*0 0 0 1/4是-3/20 0 0是-20 0 0 1/4是-3/2 基解基解 (补充充)v（b）1.3 分分别用用图解法和解法和单纯形法求解下述形法求解下述线性性规划划问题，并，并对照指出照指出单纯形表中的各基行解分形表中的各基行解分别v对应图解法中可行域的哪一个定点.(b)

3、S.t.v由图可知最优解为v的解x=(7/2,3/2),最大值z=17/2(2)单纯形法形法v首先在各约束条件上添加松弛变脸，将问题转化为标准形式vS.t.v则 组成一个基，令v得基可行解 ，由此列出初始单纯形表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-45 2 1 0 0 0 初始表初始表对应定点（定点（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 13123/20 1/3 0 -1/3 0v表明已经找到问题的最优

4、解v 对应点 ，最大值为17/22 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(补充充)v（a）st（图解法）解法）（单纯形法）形法）1.6将下列将下列线性性规划划问题化化为标准形式，准形式，并列出初始并列出初始单纯形表。形表。v（a）vst解：解：v在约束条件中添加松弛变量或剩余变量，且令 ，v该问题转化为其约束系数矩阵为 2 3 -3 4 1 0A=4 1 -1-2 0-1 3 -1 1-3 0 0在A中人为的添加两列单位向量v 2 3 -3 4 1

5、0 0 0vA=4 1 -1 -2 0-1 1 0v 3 -1 1 -3 0 0 0 1v令v得到初始单纯形表-3-11-200-M-M基b01223-341000-M841-1-20-110-M63-11-300017M-3-11-2-M0-M001.7分分别用用单纯形法中的大形法中的大M法和两法和两阶段法求段法求解下列解下列线性性规划划问题,并指出属那里并指出属那里类解解v(a)vst(1)大大M法法v将上述线性规划问题中分别减去剩余变量 再加上人工变量 ，得vstv其中M是一个任意大的正数。据此列出单纯形表2-120-M0-M0-M基b-M6111-1100006-M2-20100-11

6、00-M002-10000-1102-M3M-12+M-M0-M0-M02-120-M0-M0-M基b-M6103/2-11001/204-M2-20100-11002-1001-1/20000-1/21-2-M0-M0-M02-120-M0-M0-M基b-M3400-113/2-3/21/2-1/23/422-20100-1100-11-11000-1/21/2-1/2-1/2-4M+500-M0v由于 0且 ，则该线性规划问题有无界解2-120-M0-M0-M基b23/4100-1/43/8-3/81/8-1/83/427/2001-1/2-1/41/41/4-1/4-17/4010-1/

7、41/4-1/81/8-3/8-5/8-0005/4-3/8（2）两）两阶段法段法v现在上述线性规划问题的约束条件中分别减去剩余变量 ，再加上人工变量 ，得第一阶段的数学模型v由此可列出单纯形表000010101基b16111-110000612-20100-1100-1002-10000-1-01-3-111000010101基b16103/2-11001/2-1/2412-20100-110020001-1/20000-1/21/2-10-5/211-000010101基b13400-113/2-3/21/2-1/23/402-20100-1100-01-11000-1/21/2-1/21

8、/2-4001-3/23/2-1/2v第一阶段求得最优解目标函数的最优值为0。000010101基b03/4100-1/41/43/8-3/81/8-1/807/2001-1/2-1/2-1/41/41/4-/407/4010-1/41/4-1/81/8-3/83/8000010101v因为人工变量全部为0，则X是线性规划问题的基可行解，于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量表取消，并填入原问题的目标函数的系数，进行第二阶段的运算，其表如下：vYouv有表知道 0,而 所以线性规划问题有无界解2-12000基b23/4100-1/43/81/827/2001-1/2-1/41

9、/4-17/4010-1/4-1/8-3/80005/4-3/8-9/8(补充充)v（b）vst（大（大M法）法）v化成标准形-2-3-100-M-M基b-M8142-10102-M62300-10134M-26M-32M-1-M-M00-2-3-100-M-M基b-321/411/2-1/401/408-M25/20-11/2-1-1/214/50-M0-2-3-100-M-M基b-39/5013/5-3/101/103/10-1/10-24/510-2/51/5-2/5-1/52/5000-1/2-1/2（二（二阶段法）段法）1.10判断并判断并说明理由明理由v（a）对取值无约束的变量 通

10、常令v ，其中 ，在单纯形法求得的最优解中，有可能同时出现 v（b）若X1,X2分别是某一线性规划的最优解，则X=aX1+(1-a)X2也该是线性规划问题的最优解，其中0 a 1。v（c）单纯形法计算中选取最大正校验数v 对应的变量 作为换入基的变量，将使得迭代后的目标函数值得到最快增长。v（d）含有n个变量m个约束的标准型的线性规划问题，基解数恰好为 。v（e）如线性规划问题存在可行域，则可行域一定包含坐标的原点。1.12已知已知线性性规划划问题St用单纯形法求解最终单纯形表如下，表中 为松弛变量1/5103/5-1/53/501-1/52/5-7/1000-3/5-4/5解：解：由表可知

11、为此线性规划问题最优解，必在可行域顶点上，此顶点为带入解得v由表可知解得1.19已知已知线性性规划划问题迭代某步的迭代某步的单纯形表如下：形表如下：b41002-1-501-103-300-410000问在什么条件下：（a）表中解为唯一最优解；（b）表中解最优，但具有无穷多最优解；（c）现有基解为退化解；（d）问题具有无界解；（e）现有基解中，用 替换 后目标函数进一步优化。1.21北海北海银行一个分理行一个分理处每天个每天个时间段段对职员的需求如下表：的需求如下表：该分理处分别聘用部分全日制职员和部分非全日制职员。全日制职员每天从9：00工作到17：00，中间安排一小时午餐休时段段91010

12、11111212131314141515161617所需人数45665688v息（分两批，一批为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元。问该分理处聘用全日制和各批此的非全日制职员各多少人，能满足需求又使薪金支出最少。解：解：v令两种全日制的员工人数为 和 ，个时段非全日的人数为v ，则v以vst1.22工工业原材料合理利用原材料合理利用v要制作100套架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原材料长7.4m，应如何切割，使用原材料最节省，试建立线性规划模型并求解。