管理运筹学I本科.ppt

目 录 第1章 线性规划 第2章 对偶理论 第3章 运输问题 第4章 整数规划与分配问题 第5章 图与网络分析 第6章 计划评审法和关键路线法 第7章 目标规划 第1章 线性规划 1.1 线性规划的数学模型 1.2 图解法 1.3 单纯形法原理与计算步骤 1.4 单纯形法进一步讨论 1.5 线性规划建模 1.1 线性规划数学模型 ex1.1:甲企业计划生产两种产品Ⅰ、Ⅱ，这两种产品都要分别在A、B、C、D四种不同设备上加工，已知每生产一件产品的设备加工工时、设备生产能力、产品单位利润如下表，问Ⅰ、Ⅱ各生产多少使利润达到最大？ 1.2 图解法 优点：直观性强，便于了解线性规划问题解的情况 线性规划问题解的情况 1.3 单纯形法 1.4 单纯形法进一步讨论 1.5 线性规划建模 变换效率矩阵 确定独立零元素 是否有m个 独立零元素 N Y 未划去零元素 是否构成闭回路 每行减去本行最小元素 每列减去本列最小元素 从“行”找，“列”画线 从“列”找，“行”画线 Y 最优解 间隔指派 沿闭回路 N 找到未被直线覆盖最小元素k，画线的行Ui=0，否则Ui=k,画线的列vj=-k，否则vj=0 匈牙利法计算步骤 : 每一元素分别减去Ui和vj ex4.2 有一份说明书要分别翻译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完成不同文字的翻译所需的时间如表4-1所示，应如何分配翻译任务，使这四个人分别完成四项任务总的时间为最小。 7 8 11 9 丁 9 14 16 13 丙 10 4 14 15 乙 2 15 13 4 译成英文 译成日文 译成德文 译成俄文 甲 表4 - 1 人 工作 一般的分配问题 （1） 人数和事数不等的问题 人少事多，一人只做一件事：添上一些虚拟的人，这些虚拟人完成各事的费用系数为0，即这些费用不会发生的。 人少事多，事情必须全部完成：意味着某些人要完成若干件事情，则可将该人化作相同的几个人来接受指派，这几个“相同的人”做同一件事的费用系数当然也相同。 人多事少：添上一些虚拟的事，当然完成虚拟事的费用为0。 （2） 某事不能由某人做的分配问题 若某件事一定不能由某个人来做，则可将相应的费用系数取任意大的系数 M 即可。 （3） 最大化分配问题 目标函数是求最大值，按照下列方法转化为最小分配问题:找出效率矩阵B中最大的元素 m，用m 分别减去原效率矩阵 B 的每一个元素，得出新的效率矩阵 C,则以C为效率矩阵的最小化分配问题和以B为效率矩阵的最大化分配问题最优解相同，求解C 。 ex4.3 某商业公司计划开办5家新商店，为了尽早建成营业，商业公司决定由5家建筑公司分别承建，已知建筑公司Ai（i=1…5）对新商店Bi（i=1…5）的建造费用的报价是cij，见表4-3，商业公司如何来分配建造任务，才能使总的建造费用最少？ 12 10 7 10 6 B5 15 14 8 6 10 B4 7 17 12 14 12 B3 8 9 9 7 9 B2 4 7 6 6 6 A1 A2 A3 A4 A5 B1 表4 - 3 建筑商 商店 报价 ex4.4 对于ex4.2中的分配问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量相对较强的建筑公司A1 、A2 和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。 12 10 7 B5 15 14 8 B4 7 17 12 B3 8 9 9 B2 4 7 6 A1 A2 A3 B1 建筑商 商店 4.3 分枝定界法（Branch and Bound method） 分枝定界法的思路和步骤 （1）求解整数规划的松弛问题 设整数规划问题为A，它的松弛问题为B，则A的可行域是B 的可行域的子集 。若B无可行解则A无可行解；若B的最优解是A的可行解（满足A整数要求），则也是A的最优解；否则B的最优解（不满足A的整数要求）就是A最优解的上界（求极大时）或下界值（求极小时），转（2）。 （2）分枝 对问题B，任选一个不符合整数要求的变量进行分枝。 （3）定界 对B的子问题求最优解，若该解满足A的约束，即找到了A的一个可行解，否则该解为所属分枝的边界值（求极大化时为上界，求极小化时为下界）。 若所有的子问题的最优解均非A的可行解，则选取其边界值最大（求极大值时）或最小（求极小值时）的子问题进一步细分子问题求解 分枝过程一直进行下去，直到找到A的一个可行解为止。若计算时同时出现两个以