[工学]线性规划网络流二分图匹配.pptVIP

线性规划简介 2018-3-2 2 of 158 线 性 规 划(Linear Programming) 线性规划问题 线性规划的图解法 2018-3-2 3 of 158 一、线性规划问题 设备 产 品 A B C D 利润（万元） Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有 效 台 时 12 8 16 12 例、已知资料如右表所示，问如何安排生产才能使利润最大？ 模 型 max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0 s.t. 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 此为带约束的极值问题 2018-3-2 4 of 158 目标函数： 约束条件： ① ② ③ 2、线性规划数学模型的一般形式 2018-3-2 5 of 158 一 般 有 两种方法 图 解 法 单纯形法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但需将 一般形式变成标准形式 二、线性规划问题的求解方法 （一）、求解方法 2018-3-2 6 of 158 1、解的概念 ⑴ 可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。 ⑵ 最优解：使目标函数达到最大值的可行解。 （二）、线性规划问题的解 2018-3-2 7 of 158 2、解的基本定理 ⑴ 线性规划问题的可行域是凸集（凸多边形）。 凸集 凸集 不是凸集 ⑵ 最优解一定是在凸集的某一顶点实现。 2018-3-2 8 of 158 ⑶ 先找一个可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。 3、解的情况 唯 一 解 无 穷多 解 无 界 解 无可行解 有最优解 无最优解 2018-3-2 9 of 158 建立直角坐标 ，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。 例一、 ⑴ ⑵ ⑶ ⑷ 三、图 解 法 2018-3-2 10 of 158 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴ ⑵ ⑶ ⑷ 作 图 ∴ 最 优 解：x1 = 4 x2 = 2 有唯一最优解，Z = 14 x2 x1 (4, 2) 2018-3-2 11 of 158 例二、 例三、 ⑴ ⑵ ⑶ 无穷多最优解 ⑴ ⑵ 无界解 x1 x1 x2 x2 2018-3-2 12 of 158 ⑴ ⑵ x1 x2 无可行解 例四、 2018-3-2 13 of 158 每个线性规划问题需要在有限个线性约束条件下，求解线性目标函数 F 何处能达到极值。有限个线性约束条件所形成的区域（可行解区域），由于其边界比较简单（逐片平直），人们常称其为单纯形区域。单纯形区域 D 可能有界，也可能无界，但必是凸集（该区域中任取两点，则连接这两点的线段全在该区域内），必有有限个顶点。以下关于线性规划问题的叙述中，不正确的是（）　。 A. 若 D 有界，则 F 必能在 D 的某个顶点上达到极值 B. 若 F 在 D 中 A、B 点上都达到极值，则在 AB 线段上也都能达到极值 C. 若 D 有界，则该线性规划问题一定有一个或无穷多个最优解 D. 若 D 无界，则该线性规划问题没有最优解 2018-3-2 14 of 158 例： 某IT企业计划对一批新招聘的技术人员进行岗前脱产培训，培训内容包括编程和测试两个专业，每个专业要求在基础知识、应用技术和实际训练三个方面都得到提高。根据培训大纲，每周的编程培训可同时获得基础知识3学分、应用技术7学分以及实际训练 10 学分；每周的测试培训可同时获得基础知识 5 学分、应用技术 2 学分以及实际训练7学分。企业要求这次岗前培训至少能完成基础知识70学分，应用技术86学分，实际训练185学分。以上说明如下表所示： 编程（学分/周） 测试（学分/周） 学分最低要求 基础知识 3 5 70 应用技术 7 2 86 实际训练 10 7 185 2018-3-2 15 of 158 例： 那么这样的岗前培训至少需要 （ ） 周时间才能满足企业的要求。    编程（学分/周） 测