运筹学习题课课件.ppt

1、运筹学第一次习题课运筹学第一次习题课1.1用图解法求解下列线性规划问题，并指出用图解法求解下列线性规划问题，并指出问题具有最优解、无穷解无界解还是无可行解问题具有最优解、无穷解无界解还是无可行解。v（a）v S.T2132minxxz66421 xx42421 xx0,21xx解：解：该问题有无穷最优解，即满足 且 的所有（），此时目标函数值为3 06421 xx102 x21,xxv（c）v由图可知在点（10，6）处目标函数取得最大值16。线性规划有唯一最优解。21maxxxz12010621xx1051 x832 x（补充）（补充）v（b）21maxxxz2221 xx124321 xx0

2、,21xx解：解：v用图解法找不到满足所有约束条件的公共范围，则该问题无解。1.2对下述线性规划找出所有基解，指出对下述线性规划找出所有基解，指出哪些是基可行解，并确定最优解哪些是基可行解，并确定最优解。v（a）v v s.t v .43216542maxxxxxz28244321xxxx14324321xxxx)4,.,1(0jxjv解:写出约束方程的系数矩阵 vA=1 4-2 8v -1 2 3 4R(A)=2，所以只要找出2个列向量组成矩阵满秩，这两个向量就是线性规划问题的一个基，由于 与 线性相关不能构成基，构建表格列出全部基，基解，指出基可行解，*标注的为最优解：1p2P3P4P2P

3、4P 基基 是基可行解？是基可行解？目标函数值目标函数值 0 0 0是-2 8 0 3 0是31*0 0 0 1/4是-3/20 0 0是-20 0 0 1/4是-3/21P2P1P3P1P4P2P3P3P4P 基解基解 1x2x3x4x(补充补充)v（b）43212325minxxxxz74324321xxxx32224321xxxx)4,.,1(0jxj1.3 分别用图解法和单纯形法求解下述线性规分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基行解分别划问题，并对照指出单纯形表中的各基行解分别v对应图解法中可行域的哪一个定点.(b)S.t.212maxxxz1552x

4、242621 xx521 xx0,21xxv由图可知最优解为v的解x=(7/2,3/2),最大值z=17/2242621 xx521 xx(2)单纯形法单纯形法v首先在各约束条件上添加松弛变脸，将问题转化为标准形式vS.t.543210002maxxxxxxz15532 xx2426421xxx5521xxxv则 组成一个基，令v得基可行解 ，由此列出初始单纯形表3P4P5P021 xxTx)5,24,15,0,0(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 jcBc3x4x5x1x2x3x4x5

5、xijjzc 初始表对应定点（初始表对应定点（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 0jcBc3x1x5x1x2x3x4x5xijjzc v表明已经找到问题的最优解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/2jcBc3x1x2x1x2x3x4x5xijjzc T)0,0,2

6、15,23,27()23,27(补充补充)v（a）st21510maxxxz94321 xx82521 xx0,21xx（图解法）（图解法）（单纯形法）（单纯形法）1.6将下列线性规划问题化为标准形式，将下列线性规划问题化为标准形式，并列出初始单纯形表。并列出初始单纯形表。v（a）vst32123minxxxz12432321xxx824321xxx633321xxx解：解：v在约束条件中添加松弛变量或剩余变量，且令 ，v该问题转化为)0,0(22 222xxxxx33xxzz543 2210023maxxxxxxxz12433243 221xxxxx82453 221xxxxx6333 22

7、1xxxx其约束系数矩阵为 2 3 -3 4 1 0A=4 1 -1-2 0-1 3 -1 1-3 0 0在A中人为的添加两列单位向量0,543 221xxxxxxv 2 3 -3 4 1 0 0 0vA=4 1 -1 -2 0-1 1 0v 3 -1 1 -3 0 0 0 1v令v得到初始单纯形表76543 2210023maxMxMxxxxxxxz-3-11-200-M-M基b01223-341000-M841-1-20-110-M63-11-300017M-3-11-2-M0-M00jcBcjjzc 4x6x7x1x2x 2x3x4x5x6x7x1.7分别用单纯形法中的大分别用单纯形法中

8、的大M法和两阶段法求法和两阶段法求解下列线性规划问题解下列线性规划问题,并指出属那里类解并指出属那里类解v(a)vst32122maxxxxz6321xxx2231xx0232 xx0,321xxx(1)大大M法法v将上述线性规划问题中分别减去剩余变量 再加上人工变量 ，得vst4x8x6x5x9x7x98765432100022maxMxxMxxMxxxxxz654321xxxxx227631xxxx029832xxxx0,987654321xxxxxxxxxv其中M是一个任意大的正数。据此列出单纯形表2-120-M0-M0-M基b-M6111-1100006-M2-20100-1100-M

9、002-10000-1102-M3M-12+M-M0-M0-M0jcBcjjzc 5x7x9x1x2x3x4x5x6x7x8x9xi2-120-M0-M0-M基b-M6103/2-11001/204-M2-20100-11002-1001-1/20000-1/21-2-M0-M0-M0jcBcjjzc 5x7x2x1x2x3x4x5x6x7x8x9xi235M21M231M2-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-M0jcBcjjzc 5x3x2x1x2x3x4x5

10、x6x7x8x9xi21M231M233M235Mv由于 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/41/4-1/81/8-3/8-5/8-0005/4-3/8jcBcjjzc 1x3x2x1x2x3x4x5x6x7x8x9xi8981M45M83M404ia（2）两阶段法）两阶段法v现在上述线性规划问题的约束条件中分别减去剩余变量 ，再加上人工变量 ，得第一阶段的数学模型v由此可列出单纯形表8x6x4x5x7x9x000010101基b16111

11、-110000612-20100-1100-1002-10000-1-01-3-111jcBcjjzc 5x7x9x1x2x3x4x5x6x7x8x9xi1000000010101基b16103/2-11001/2-1/2412-20100-110020001-1/20000-1/21/2-10-5/211jcBcjjzc 5x7x2x1x2x3x4x5x6x7x8x9xi212300-000010101基b13400-113/2-3/21/2-1/23/402-20100-1100-01-11000-1/21/2-1/21/2-4001-3/23/2-1/2jcBcjjzc 5x3x2x1x

12、2x3x4x5x6x7x8x9xi230v第一阶段求得最优解目标函数的最优值为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/8000010101jcBcjjzc 1x3x2x1x2x3x4x5x6x7x8x9xTX)0,0,0,0,0,0,027,47,43(v因为人工变量全部为0，则X是线性规划问题的基可行解，于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量表取消，并填入原问题的目标函数的系数，进行第二阶段的运算，其表如下：vYouv有表知

13、道 0,而 所以线性规划问题有无界解2-12000基b23/4100-1/43/81/827/2001-1/2-1/41/4-17/4010-1/4-1/8-3/80005/4-3/8-9/8jcBcjjzc 1x3x2x1x2x3x4x6x8xi404ia(补充补充)v（b）vst32132minxxxz824321xxx62321 xx0,321xxx（大（大M法）法）v化成标准形76543210032maxMxMxxxxxxz82464321xxxxx6237521xxxx7654321,xxxxxxx-2-3-100-M-M基b-M8142-10102-M62300-10134M-26

14、M-32M-1-M-M00jcBcjjzc 6x7x2x1x2x3x4x5x6x7xi-2-3-100-M-M基b-321/411/2-1/401/408-M25/20-11/2-1-1/214/50-M0jcBcjjzc 2x7x2x1x2x3x4x5x6x7xi4525MM21432M2343M-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/2jcBcjjzc 2x1x2x1x2x3x4x5x6x7xM21M21M21（二阶段法）（二阶段法）1.10判断并说明理由判断并说明理由v（a）

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

16、11maxxcxcxcz13212bxxx232132bxxx)3,2,1(0jxj4x5x和试计算并确定321,ccc的值。21,bb1/5103/5-1/53/501-1/52/5-7/1000-3/5-4/51x3x5x4x3x2x2xjjzc 解：解：由表可知 为此线性规划问题最优解，必在可行域顶点上，此顶点为带入解得T)3,1,0(13212bxxx232132bxxx521 bbv由表可知解得1075351321ccc53515332cc54525132cc3,2,2/3321ccc1.19已知线性规划问题迭代某步的单纯已知线性规划问题迭代某步的单纯形表如下：形表如下：b41002

17、-1-501-103-300-410000jjzc 3x4x6x1x2x3x4x5x6x1a2a3a1c2c问在什么条件下：（a）表中解为唯一最优解；（b）表中解最优，但具有无穷多最优解；（c）现有基解为退化解；（d）问题具有无界解；（e）现有基解中，用 替换 后目标函数进一步优化。1x6x1.21北海银行一个分理处每天个时间段对职北海银行一个分理处每天个时间段对职员的需求如下表：员的需求如下表：该分理处分别聘用部分全日制职员和部分非全日制职员。全日制职员每天从9：00工作到17：00，中间安排一小时午餐休时段时段9101011111212131314141515161617所需人数45665

18、688v息（分两批，一批为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 ，则1y2y5x2x1x3x6x4xv以vst)(80)(240min65432121xxxxxxyyz4121xyy52121xxyy632121xxxyy64322xxxy55431xxxy665421xxxyy86521xxyy8721xyy)6,5,4,3,2,1(0,0,21jxyyj1.22工业原材料合理利用工业原材料合理利用v要制作100套架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原材料长7.4m，应如何切割，使用原材料最节省，试建立线性规划模型并求解。