ch1 数学模型及单纯形法.ppt

Chapter1 线性规划及单纯形法 v 1.1 线性规划问题及数学模型 v 1.2 图解法 v 1.3 单纯形法 v 1.4 单纯形法的进一步讨论 本章主要内容：本章主要内容： page1 1.1 线性规划问题及数学模型 1.1.1 问题的提出 v规划问题Program 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益，这就是 规划问题。 v线性linear 量与量之间按比例、成直线的关系，在数学上可以理 解为一阶导数为常数的函数。 page2 1.1 线性规划问题及数学模型 v线性规划 Linear Programming 求线性目标函数在线性约束条件下的最大值或最小值 的问题，统称为线性规划问题。通常解决下列两类问题： （1）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益 （如产品量最多 、利润最大。） （2）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、材料、人工、时间等）去完成确定的任务或目标。 page3 1.1 线性规划问题及数学模型 例1 美佳公司计划制造、两种家电产品。已知各制造1 件时分别占用的设备A，B的台时、调试工序时间及每天 可用于这两种家电的能力、各售出1件时的获利情况，如 下表所示。问该公司应制造两种家电各多少件，使获取的 利润为最大。 page4 1.1 线性规划问题及数学模型 例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知 各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越 长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理， 每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个 月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积 和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的 是使所付租借费用最小。 表1-2 单位：100m2 表1-3 单位：元/100m2 page5 1.1 线性规划问题及数学模型 1.1.2 线性规划问题的数学模型 1）线性规划问题的数学定义： 求取一组变量xj (j=1,2,n)，使之既满足线性约束条 件，又使具有线性的目标函数取得极值的一类最优化问题称 为线性规划问题。 怎样辨别一个模型是线性规划模型？ （1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最 小值； （2）问题的约束条件是一组多个决策变量的线性不等式或等式。 page6 1.1 线性规划问题及数学模型 1.1.2 线性规划问题的数学模型 2 2） 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成 例例1 1 例例2 2 决策变量决策变量 Decision variables Decision variables 目标函数目标函数 Objective functionObjective function 约束条件约束条件 ConstraintsConstraints page7 例1 page8 (1.1c) 目标函数 约束条件 (1.1a) (1.1b) (1.1d) max: maximize的缩写， “最大化”， s.t. subject to的缩写， “受限制于” 例1 page9 目标函数 约束条件 s.t. min：minimize ， “最小化” 1.1.2 线性规划问题的数学模型 目标函数：目标函数： 约束条件：约束条件： 3 3）线性规划数学模型的一般形式）线性规划数学模型的一般形式 简写为： page10 1.1.2 线性规划问题的数学模型 向量形式：向量形式： 其中： page11 1.1.2 线性规划问题的数学模型 矩阵形式：矩阵形式： 其中： page12 1.1 线性规划问题及数学模型 v 课堂练习 某企业有三个工厂甲、乙、丙生产某种产品销往四个销售点A、B 、C、D。每个计划期内甲乙丙的供应量分别为150、200和250件， 销售点A、B、C、D的需求量分别是120、140、160和180件。各 工厂运送至各销售点 的运价如表所示，试制定总运价最小的调运方案 （建立该问题的线性规划模型）。 销售点 运价（元/件） 工厂 A B C D 甲 4 6 8 10 乙 6 410 4 丙8 2 4 6 page13 1.1 线性规划问题及数学模型 vv1.1.3 1.1.3 线性规划问题的标准形式线性规划问题的标准形式 特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负。 page14 1.1.3 线性规划问题的标准形式 如何化标准形式？如何化标准形式？ 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1) ，可化为求极大值问题。 也就是：令 ，可得到上式。 即 若存在取值无约束的变量 ，可令 其中： 变量的变换 page15 1.1.3 线性规划问题的标准形式 约束方程的转换：由不等式转换为等式。 称为松弛变量 称为剩余变量 变量 的变换 可令 ，显然 page16 例3 将下述线性规划化为标准形式 page17 1.1.3 线性规划问题的标准形式 课堂练习 将下列线性规划问题化为标准形式 用 替换 ，且 解:（）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以 page18 1.1.3 线性规划问题的标准形式 (2) 第一个约束条件是“”号，在“”左端加入松驰变量x4， x40,化为等式； (3) 第二个约束条件是“”号，在“”左端减去剩余变量x5， x50； (4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右 端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然; page19 1.1.3 线性规划问题的标准形式 标准形式如下： page20 作业 v 某药厂生产A、B、C三种药品，有甲乙丙丁四种原料可供选择（原材 料供应不限），四种原料成本分别为每公斤4、7、9、5元。每公斤不 同原料提取的各种药品数量g如下表所示： v 该厂要求每天生产药品A恰好115g，B至少260g，C不超过130g。使确 定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数 学模型，并将模型化成标准型。 原料 每公斤提取药 量（g） 药品 甲乙丙丁 A2132 B6625 C3223 page21 1.2 图解法 v 线性规划问题的求解方法 一 般 有 两种方法 图 解 法 单纯形法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但必需将 一般形式变成标准形式 可行解：满足所有约束条件的解。 可行域：所有可行解的集合。 最优解：使目标函数达到最大值的可行解。 page22 1.2 图解法 v 只有两个决策变量的线性规划问题，这时可以通过图解的方法 来求解。 v 图解法具有简单、直观、便于初学者窥探线性规划基本原理和 几何意义等优点。其目的表现为： 判别线性规划问题的求解结局； 若存在最优解，将其找出。 page23 1.2 图解法 v图解法的步骤： 1）建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单 位长度。 2）对约束条件加以图解，找出可行域。 3）画出目标函数等值线。 4）结合目标函数的要求求出最优解。 page24 1.2 图解法 (1.5c) (1.5a) (1.5b) (1.5d) 例1 用图解法求解线性规划问题 page25 1.2 图解法 page26 1.2 图解法 max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0 例 用图解法求解线性规划问题 page27 1.2 图解法 x1 x2 o X1 - 1.9X2 = 3.8() X1 + 1.9X2 = 3.8() X1 - 1.9X2 = -3.8 () X1 + 1.9X2 = 10.2() 4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）D max Z min Z 此点是唯一最优解， 且最优目标函数值 max Z=17.2 可行域 max Z = 2X1 + X2 page28 1.2 图解法 max Z=3X1+5.7X2 x1 x2 o X1 - 1.9X2 = 3.8 () X1 + 1.9X2 = 3.8() X1 - 1.9X2 = -3.8() X1 + 1.9X2 = 10.2 () （7.6，2）D L0： 0=3X1+5.7X2 max Z （3.8，4） 34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最 优解这种情形为有无穷多最 优解，但是最优目标函数值 max Z=34.2是唯一的。 可行域 page29 1.2 图解法 v min Z=5X1+4X2 x1 x2 o X1 - 1.9X2 = 3.8 () X1 + 1.9X2 = 3.8() X1 + 1.9X2 = 10.2 () D L0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2） 可行域 此点是唯一最优解 page30 1.2 图解法 246 x1 x2 2 4 6 无界解(无最优解) max Z=x1+2x2例1.6 x1+x2=4() x1+3x2=6() 3x1+x2=6() max Z min Z page31 x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解(即无最优解) max Z=3x1+4x2例1.7 page32 1.2 图解法 (a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解多个最优解 唯一最优解 (d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解 page33 1.2 图解法 学习要点： 1. 通过图解法了解线性规划有几种解的形式 （唯一最优解；无穷多最优解；无界解；无可行解） 2. 若线性规划问题的可行域存在，则可行域是一个 凸集； 3. 若线性规划问题的最优解存在，则最优解一定是 可行域凸集的某个顶点； 4.解题思路：先找凸集的任意顶点，计算在顶点处的 目标函数值。 page34 1.3 单纯形法 vv1.3.1 1.3.1 线性规划问题的解线性规划问题的解 线性规划问题 求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。 page35 1.3.1 线性规划问题的解 可行解：满足约束条件、的解为可行解。所有可行解 的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(m0 40 10 换 出 行 将3化为1 5/3 1 180 1/301/310 11/330 30 05/304/3 乘 以 1/3 后 得 到 103/5 1/5 18 011/52/54 00 11 page49 CB 基 cj21000 b x1x2x3x4x5 0x31505100 0x42462010 0x5511001 cj-zj21000 解： 表1-7 page50 01/602/614x12 0-1/301/30cj-zj 1-1/604/601x50 0015015x30 x5x4x3x2x1b 00012 cj 基 CB 表1-8 -1/21/40017/2x12 -1/2-1/4000cj-zj 3/2-1/40103/2x21 -15/25/410015/2x30 x5x4x3x2x1 b 00012 cj 基CB 表1-9 page51 表1-9中所有j0且aik（i=1，2,m）则线性 规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并 且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 page67 无可行解 0 1 0 x5 -M -1-40-54x5-M -M-2-4M0-1-5M cj-zj 01122x22 x4x3x2x1 b 0023 cj XB CB page68 有可行解，但无最优解 101-34x23 -30011 cj-zj 110-26x30 x4x3x2x1 b 0032 cj XB CB page69 退化解 -3/4 3/4 -1/4 -1/2 x5 0 001-1/25/2x20 000-9/2cj-zj 0103/23/2x31 10000x40 x4x3x2x1 b 0000 cj XB CB page70 无穷多个最优解 7/45-2/45017/3x14 0-200 cj-zj -2/457/45107/3x214 x4x3x2x1 b 00144 cj XB CB page71 单纯形法的进一步讨论人工变量法 v 单纯性法小结: 建 立 模 型 个 数取 值右 端 项 等式或 不等式 极大或极小 新加变 量系数 两 个 三个 以上 xj0xj无 约束 xj 0 bi 0 bi 0 =max Z minZx s x a 求 解 图 解 法 、 单 纯 形 法 单纯 形法 不 处 理 令xj = xj - xj xj 0 xj 0 令 xj = - xj 不 处 理 约束 条件 两端 同乘 以-1 加 松 弛 变 量 x s 加 入 人 工 变 量 x a 减 去 x s 加 入 x a 不 处 理 令 z=- Z minZ = max z 0-M page72 A page73 线性规划模型的应用 v 一般而言，一个经济、管理问题凡是满足以下条 件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且 为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约 束可用线性等式或不等式描述 page74 线性规划在管理中的应用 1. 人力资源分配问题 例1.11 某昼夜服务的公交线路每天各时间段内 所需司机和乘务人员人数如下表所示： 班次时间所需人员 16:0010:0060 210:0014:0070 314:0018:0060 418:0022:0050 522:002:0020 62:006:0030 设司机和乘务人员分别在各时间段开始时上班，并连续工作 8小时，问该公交线路应怎样安排司机和乘务人员，即能满 足工作需要，又使配备司机和乘务人员的人数减少? page75 线性规划在管理中的应用 v 解：设xi表示第i班次时开始上班的司机和乘务人员人数。 此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员150人。 page76 线性规划在管理中的应用 v 2. 生产计划问题 某厂生产、三种产品，都分别经A、B 两道工序加工。设A工序可分别在设备A1和A2上完 成，有B1、B2、B3三种设备可用于完成B工序。已 知产品可在A、B任何一种设备上加工；产品可 在任何规格的A设备上加工，但完成B工序时，只能 在B1设备上加工；产品只能在A2与B2设备上加工 。加工单位产品所需工序时间及其他各项数据如下 表，试安排最优生产计划，使该厂获利最大。 page77 线性规划在管理中的应用 设备 产品 设备有效 台时 设备加工费 （单位小时） A27910 000321 B168124