1、线性规划(续1.3)两阶段法例 第一阶段(LP-1) CR X X 15 0 2 4 0 (7/5) X 0653403 2/5 5480100010 001000100 0001000 0 6.5 15/7 20 00000 -3/5 6/5 4/5 25/3 7/5 8/5 15/7 17 5/7 -3/7 7 3/7 0 -1/7 2/7 25/3 52/7 3/7 0 -6/7 2/7 0 0 得到原问题的基本可行解:(0,15/7,25/7,52/7)
26 1、 线 性 规 划 （续1.3）两阶段法例 0 0 0 0 -1 -1 CB XB x1 x2 x3 x4 x5 x6 θi -1 x5 15 1 2 3 0 1 0 5 -1 x6 20 2 1 (5) 0 0 1 4 0 x4 26 1 2 4 1 0 0 6.5 -z 35 3 3 8 0 0 0 -1 x5 3 -1/5 (7/5) 0 0 1 -3/5 15/7 0 x3 4 2/5 1/5 1 0 0 1/5 20 0 x4 10 -3/5 6/5 0 1 0 -4/5 25/3 -z 3 -1/5 7/5 0 0 0 -8/5 0 x2 15/7 -1/7 1 0 0 5/7 -3/7 0 x3 25/7 3/7 0 1 0 -1/7 2/7 25/3 0 x4 52/7 -3/7 0 0 1 -6/7 -2/7 -z 0 0 0 0 0 -1 -1 •第一阶段 （LP - 1） • 得到原问题的基本可行解：(0，15/7，25/7，52/7)T
1、线性规划(续1.3)两阶段法例 第二阶段把基本可行解填入表中 C23 15/7 -17 0 25/7 (3/7) 25/3 52/7 0 53/7 25/7 2 10/3 1/3 Xxx 25/3 11 0001000 7/3 x00100010 112/30 25/3 得到原问题的最优解:(25/3,103,0,11)T 最优目标值:112/3 27
27 1、 线 性 规 划 （续1.3）两阶段法例 5 2 3 -1 CB XB x1 x2 x3 x4 θi 2 x2 15/7 -1/7 1 0 0 3 x3 25/7 (3/7) 0 1 0 25/3 -1 x4 52/7 -3/7 0 0 1 -z -53/7 25/7 0 0 0 2 x2 10/3 0 1 1/3 0 5 x1 25/3 1 0 7/3 0 -1 x4 11 0 0 1 1 -z -112/3 0 0 -25/3 0 •第二阶段 把基本可行解填入表中 • 得到原问题的最优解：(25/3，10/3，0，11)T •最优目标值：112/3
1、线性规划(续1.3) 13.5矩阵描述此段为选读,有困 难者可不看。 13.6段单纯形迭代过程中的几点注意 事项是对有关内容的强调和补充,要认 真学习、理解。 习题:p70-71习题11-5,1-6 28
28 1、 线 性 规 划 （续1.3） 1.3.5 矩阵描述—— 此段为选读，有困 难者可不看。 1.3.6 段单纯形迭代过程中的几点注意 事项是对有关内容的强调和补充，要认 真学习、理解。 **习题：p70--71 习题1 1-5，1-6
1、线性规划(续1.4) 1.4线性规划应用—建模(p55-68) 本节介绍了些线性规划应用的例子,这些例子从多个方面介绍建模对未来 是很有用的,应认真对待。 除了教材上的例子之外,还有许多其它应用 合理利用线材问题:如何下料使用材最少 *配料问题:在原料供应量的限制下如何获取最大利润 *投资问题:从投资项目中选取方案,使投资回报最大 *产品生产计划:合理利用人力、物力、财力等,使获利最大 *劳动力安排:用最少的劳动力来满足工作的需要 *运输问题:如何制定调运方案,使总运费最小 读下面是一些建模的例子,有兴趣者,可作为练习。这些例子有一定的难度,做 起来会有一些困难。 *习题:p72-73习题11-7,1-8,1-9,1-10 返回
29 1. 4 线性规划应用——建模（p55--68） 本节介绍了些线性规划应用的例子，这些例子从多个方面介绍建模对未来 是很有用的，应认真对待。 除了教材上的例子之外，还有许多其它应用： * 合理利用线材问题：如何下料使用材最少 * 配料问题：在原料供应量的限制下如何获取最大利润 * 投资问题：从投资项目中选取方案，使投资回报最大 * 产品生产计划：合理利用人力、物力、财力等，使获利最大 * 劳动力安排：用最少的劳动力来满足工作的需要 * 运输问题：如何制定调运方案，使总运费最小 **下面是一些建模的例子，有兴趣者，可作为练习。这些例子有一定的难度，做 起来会有一些困难。 **习题：p72--73 习题1 1-7，1-8，1-9，1-10 1、 线 性 规 划 （续1.4） 返回目录
例:人力资源分配的问题 例.某昼夜服务的公交线路每天各时间段内所需司机和乘务人 员数如下: 班次 时间 所需人数 6:00 10:00 60 10:00 14:00 70 23456 14:00 18:00 60 18:00 22:00 50 22: 2:00 20 2:00 6:00 30 设司机和乘务人员分别在各时间段一开始时上班,并连续 工作八小时,问该公交线路怎样安排司机和乘务人员,既能 满足工作需要,又配备最少司机和乘务人员?
30 例．某昼夜服务的公交线路每天各时间段内所需司机和乘务人 员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续 工作八小时，问该公交线路怎样安排司机和乘务人员，既能 满足工作需要，又配备最少司机和乘务人员? 班次 时间 所需人数 1 6：00 —— 10：00 60 2 10：00 —— 14：00 70 3 14：00 —— 18：00 60 4 18：00 —— 22：00 50 5 22： —— 2：00 20 6 2：00 —— 6：00 30 例：人力资源分配的问题