第七章 线性规划问题与网络流 225

单位生产费用要增加6元,加工后单位售价增加9元。产品B可以按单位售价7元出售,也可以在第三车间继续加工,单位生产费用要增加4元,加工后单位费用可增加6元。原料N的单位购入价为2元,上述生产费用不包括工资在内。3个车间每月最多有20万工时,每工时工资0.5元,每加工1单位N需1.5个工时,如A继续加工,每单位需3工时,如B继续加工,每单位需2工时。原料N每月最多能得到10万单位。问如何安排生产,使工资获利最大。
7-5 设计在7.3节图7-25所示的残余网络中寻找负费用圈1-2-5-3-1的过程。
7-6 餐巾计划问题。一个餐厅在相继的N 天里,每天需用的餐巾数不尽相同。假设第i天
需要ri块餐巾(i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为p分;或者把 旧餐巾送到快洗部,洗一块需m天,其费用为f 分;或者送到慢洗部,洗一块需n天(n>m),其费用为s(s<f)分。每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划,使总的花费最小。
7-7 试题库问题。假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可
能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。
7-8 深海机器人。深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多
个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人
完成采集。每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。
用一个 P×Q 网格表示深海机器人的可移动位置。西南角的坐标为(0,0),东北角的坐标为 (Q,P)。 给定每个深海机器人的出发位置,以及每条网格边上生物标本的价值。计算深海机器人的最优移动方案,使深海机器人到达目的地后,采集到的生物标本的总价值最高。
7-9 太空机器人问题。W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行
可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…,In }。实验Ej需要用到的仪器是I的子集Rj。运送仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
7-10 圆桌问题。假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分
别为Ri ( i=1,2,3...,n)。会议餐厅共有m张餐桌,每张餐桌可容纳Ci (i=1,2, 3...m) 个代表就餐。 为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试对下述实例设计一个算法,给出满足要求的代表就餐方案。
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档