运筹学运筹演示2

《运筹学运筹演示2》由会员分享，可在线阅读，更多相关《运筹学运筹演示2（68页珍藏版）》请在金锄头文库上搜索。

1、复习第一章、第二章内容 例1：某工厂生产、两种型号计算机， 为了生产一台型和型计算机，所需要原 料分别为2个单位和3个单位，需要的工时分 别为4个单位和2个单位，在计划期内可以使 用的原料为100个单位，工时为120个单位。 已知生产每台、型计算机可获利6个单 位和4个单位，试确定获利最大的生产方案 。原料工时时利润润 型246 型324 资资源限制100120求解线性规划的方法： 1.图解法 2.单纯形法 3.大M法 4.对偶单纯形法 例2. minZ=15x1+24x2 +5x36x2+x3 25x1+2x2+x3 1x1， x2 ，x3 0 第三章 运输问题 第一节 平衡运输问题的数学模

2、型 运输问题的提出 例：某公司经销甲产品，该产品有三个加工厂，产量分别 为7、4、9吨，该产品有四个销售地点，销售量为3、6、 5、6吨，已知单位定价，问如何在满足各销售点的需求量 的前提下，使花费最小？销销 地 产产 地B1B2B3B4产产量A1 A2 A33 1 711 9 43 2 1010 8 57 4 9销销 量3656一般运输问题的提出: 某种物资有m个产地A1、A2Am，其产量 分别为a1、a2am，有n个销地B1、B2Bn ，其销量分别为b1、b2bm，现需要把这种 物资从各个产地运往各个销地，假设产销平 衡ai= bj，且每个产地到每个销地的单位 货物运价为Cij，问如何调运

3、，才能使总的运 费最省。 已知有m个生产地点Ai（i=1，2m），其 产量分别为ai；有n个销售地点Bj（j= 1， 2n），其销量分别为bj，假设产销平衡 ，且从Ai到Bj运输单位物资运价为Cij，可以 汇总数据得到产销平衡表：销销地 产产地B1B2 Bn产产量A1 A2 AmC11 C21 Cm1C12 C22 Cm2 C1n C2n Cmna1 a2 am 销销量b1b2bn 第二节 表上作业法 一、基本概念 1.闭回路：从起点出发经过另外几个点回到 始点的变量集合。 2.数字格（基格）：在调运方案中，分配运 输量的基变量的格。 3.空格：在调运方案中，没分配运输量的非 基变量的格。 4

4、.性质：运输问题的基变量的个数是约束条 件的个数减一，即m+n-1个。 二、表上作业法的基本步骤 1.编制初始方案，确定初始可行解。 使用方法：最小元素法、伏格尔法。 2.最优性检验 使用方法：闭回路法、位势法。 3.方案的调整 使用方法：闭回路法 例：某公司经销甲产品，该产品有三个加 工厂，产量分别为7、4、9吨，该产品有四 个销售地点，销售量为3、6、5、6吨，已 知单位定价，问如何在满足各销售点的需 求量的前提下，使花费最小？销地 产地B1B2B3B4产量A1 A2 A33 1 711 9 43 2 1010 8 57 4 9销量3656 最小元素法销销 量 产产量B1B2B3B4销销

5、量A1100201115A212792025A301416185产产量5151510 第二节 产销不平衡的运输问题 1.产量销量，虚设一个销地Bn+1，其销地 的销量为bn+1=a- b，在令各产地到虚拟 销地的单位运价为Cin+1=0（i=1，2m） 。 2.产量销量，虚设一个产地Am+1，其产地 的产量为am+1=b- a，在令虚拟产地到各 销地的单位运价为Cm+1j=0（j=1，2n） 。 例：销销地 产产地B1B2B3B4产产量A1324520A2752110A3963615销销量510155 例：已知某运输问题，要求B地区的115个 单位必须满足，试求最优的调运方案。销销地 产产地A

6、BCDE产产量11015202040502204015303010033035405525130销销量25115603070 例：某化学公司有4个化工厂生产某种产品，产量分别为 200、300、400、100吨，供应6个地区的需要，需求量分 别为200、150、400、100、150、150吨，由于工艺技术 条件的差别有关数据如表所示，要求第三个地区至少供应 300单位，第四个地区需要必须满足，试确定该公司获利 最大的产品调运方案。销销地 产产地123456单单位 成本154343112238956214377374411464265815单单位售价202418221620 运输问题应用： 一

7、、生产计划问题 某拖拉机厂与某单位签订了生产70台某种型号拖拉机的合 同，按合同规定明年每个季度末分别提供10、15、25、 20台拖拉机，已知该厂各季度的生产能力及生产每台拖拉 机的成本如表所示，如生产出来的拖拉机当季度不交货， 每台每积压一个季度需要储存维护费用0.15万元，问该厂 怎样安排各季度生产计划，既完成合同又使得总费用最少 。季节节 生产产能力单单位成本（万元）1 2 3 425 35 30 1010.8 11.1 11 11.3 二、资源短缺问题销销地 产产地B1B2B3B4产产量A11613221750A21413191560A3192023-50最低需求 最高需求 30 5

8、070 700 3010 不限 第四节 指派问题 一、问题的提出 有n个人去完成n项任务，每个人只能完成 一项任务，且每项任务只能由一个人来完 成，每人完成各项任务的效率不同如表,问 如何分派任务，才能使总时间最少?任务 人12n1C11C12C1n2C21C22C2n:nCn1Cn2Cnn 二、匈牙利法的基本思想 对于同一个人来说，所有的任务的完成效 率都提高或降低同一个常数ti，不会影响最 优分配，同样对同一个任务来说，让所有 人去完成的效率都提高或降低同一常数dj也 不会影响其最优分配，从而得到新的效率 矩阵为bij=cij+ti+dj。 例1.有一份中文说明书，需要翻译成英日德 三种文

9、字，记作E、J、G，有甲、乙、丙 三个人他们将中文说明书翻译成不同语种 的说明书所需要的时间如表所示，问应指 派何人去完成何工作，使所需总时间最短 ？任务 人EJG甲 乙 丙25 15 2231 20 1935 24 17 1.对指派问题的系数矩阵进行变换，使每行 每列都出现0元素 2.进行试指派。找出独立的0元素。 行搜索：从只有一个0元素的行开始，给这 个0划圈，并划去该元素所在列的其他0元 素。 列搜索：从只有一个0元素的列开始，给这 个0划圈，并划去该元素所在行的其他0元 素。 反复行列搜索，直到所有的0元素圈上和划 去为止。 3.若独立0元素个数=方阵的阶数，则已经 找到最优方案，反

10、之，转下步。 4.求覆盖0元素的最小直线集合。 （1）对没有圈0的行的右边打 （2）对打的行上所有0元素的下方打 （3）对打的列上有圈0的行的右边打 （4）对没有打的行划横线，对打的列划 垂线。 5.确定调整量，在没有被直线覆盖的部分中 找到最小元素Q， 没有被直线覆盖的元素-Q。 一次被直线覆盖的元素不变。 二次被直线覆盖的元素+Q。 例2施工队工时 工程12345升板74568滑板121013159模板10981113多层板1517201411厂房1614131815 例3.矿区开采量 机器12341101512521217121316206244631 例4.任 务利润 人甲乙丙丁A32

11、-21B2-20-C-110 例5.某公司计划开5家商店，为了尽早完成建设，决定由3 家建筑公司分别承建，已知建筑公司Ai(i=1,2,3)对新商 店Bj(j=1,2,3,4,5)的建造费用的报价。商业公司应对3家 建筑公司怎样分配建造任务，才能使总的建筑费用最少？ （允许每家建筑公司承建1-2家商店的建设） 新商店建筑公司B 1B2B3B4B5A14871512A279171410A3691287 0-1整数规划问题 1.投资问题，设有n个投资项目，其中第j个项目需要资金 aj万元，将来可获得利润cj万元，若现在资金总额为b万 元，则应选择哪些投资项目才能获得利润最大？ 2.背包问题，一个旅

12、行者要在其背包里装一些最有用的旅 行物品，背包容积为a,携带物品总重量最多为b,现有物品 m件，第i件物品体积为ai，重量为bi（i=1，2，m),为 了比较物品的有用程度，假设第i件物品的价值为ci，若 每件物品只能整件携带，每件物品都能放入背包中，并且 不考虑物品放入背包的相互间隙，问旅行者应带携带哪些 物品，才能使携带物品的总价值最大？ 第五章 动态规划 多阶段决策问题：指这样一类决策过程，它可以 把复杂问题按照时间或空间分成若干阶段，每个 阶段都需要进行决策，以便得到过程的最优结局 。 动态规划的基本概念： 1.阶段：一个问题需要进行决策的步数。K=1，2 ，n 2.状态：是各个阶段之

13、间信息的传递点和结合点 。第k阶段的状态xk表示。 3.决策：决策者面临不同选择而作出最后的选择 。第k阶段xk 状态下的决策用uk（ xk ）表示。 允许决策集合：决策变量的取值往往限制 在某一范围内，此范围称为允许决策集合 。 4.状态转移方程：由一个状态到另一个状态 的演变过程。 5.全过程：由第一阶段开始到终点为止。 子过程：由第k阶段开始到终点为止。 6.指标函数：用来衡量过程优劣的效益值。 阶段指标函数：对应某一阶段的效益值vk。 过程指标函数：子过程的效益值vk，n。 7.最优解：第k子过程指标函数在xk 状态下 的最优值。用fk（ xk ）表示。 最优化原理：作为整个的最优策略

14、具有这 样的性质，无论过去的状态和决策如何， 对前面形成的状态而言，余下的诸决策必 构成最优策略。 动态规划的运算步骤： 1.将问题按时间和空间的顺序划分若干阶段 。 2.正确选择状态变量。 3.确定决策变量和允许决策集合。 4.写出状态转移方程。 5.建立指标函数。 6.建立基本方程。 例：（追加投资问题）某公司有四百万元 ，可以向ABC三个项目追加投资，不同投 资额的相应效益如表，问怎样分配资金使 总效益值最大？投资 项目0（百万）1234A3841486066B4042506066C4864687879 例：某警卫部门共有12只巡逻队负责4个要害部 位的巡逻，对每个部位可分派2-4个巡逻

15、队，并且 巡逻队数不同，各部位预期在一段时间内可能造 成的损失有差别，问该警卫部门应往各部位分派 多少巡逻队，使总预期损失最小？部位预期损 失 巡逻队 数ABCD218382434314352231410312125 例：（生产计划问题）某厂与一用户签定合同， 在4个月内出售一定数量的某种产品，工厂每月最 多生产100个单位，产品可以存储，存储费为每 月每单位2元，要求四个月末存储量为0，每月需 要量与单位产品成本如表，现确定每月的生产量 ，要求既满足每月的合同要求又使费用最少。月份单位产品成本（元）需求量170602727038012047660 K=1,2,3,4 Xk-第k阶段拥有的产品数（存货） Uk-第k阶段的产量 Ck-第k阶段的单位成本 dk-第k阶段的需求量 状态转移方程Xk+1=Xk+Uk-dk 例：某系统有3个工作部件，ABC串联而成 ，3个部件的工作是相互独立，据统计资料 ，各部件的故障率A为0.3，B为0.2，C为 0.4，如果三个环节各自配备一个部件，则 系统正常工作概率： P=（1-0.3）（1-0.2）（1-0.4）=0.336 现管理部门决定各环节除工作部件外，可 增设备用部件，以提高系统的可靠性，用 语购买部件的金额