数学规划建模.doc

一、基本知识
例1 要从甲城调出蔬菜2023吨，从乙城调出蔬菜1100吨，分别供应A地1700吨，B地1100吨，C地200吨，D地100吨。已知每吨运费如下表
每吨 供应单位
运费

调出单位

A地

B地

C地

D地

甲城
乙城

21
51

25
51

7
37

15
15
试问，该如何运送费用最小。
例2 某工厂又一批长度为5米的钢管（数量充足多），为制造零件的需要，要将它们截成长度分别为1400毫米，950毫米，650毫米的管料，并且这三种管料要按2：4：1的比例配套生产，就是说每制造一个成品分别需要2根1400毫米，4根950毫米，1根650毫米的管料。
把一根一定长度的钢管截成n段需要的管料时，一般要产生残料，例如，把5米的钢管截成1400毫米的3根和650毫米的1根，要剩残料150号毫米；假如截成1400毫米的2根和950毫米的两根，要剩残料300毫米。现在的问题是如何截分才干使截下来的三种管料，既能配套，又使残料最少。
下面，根据也许列出8种截法（残料明显很多的截法就不再列出来了）

截法
1 2 3 4 5 6 7 8
长度
1400毫米
3 2 2 1 1 0 0 0

950毫米
0 2 0 3 1 5 3 1

650毫米
1 0 3 1 4 0 3 6
残料（毫米）
150 300 250 100 50 250 200 150
挑选其中一种省料的截法（例如截法5），当然可以是残料最少，但是满足不了配套规定，所以我们必须同时采用若干种截法，配合起来，在完毕配套规定的条件下，使总的残料最少。
用xi(i=1,2,……，8)表达采用第i种截法所截钢管的数量，那么截出的1400豪米的管料数量是：
3x1+2x2+2x3+x4+x5
截出的900毫米的数量是：
2x2+3x4+x5+5x6+3x7+x8
截出的650毫米的数量是
x1+3x3+x4+4x5+3x7+6x8
根据配套规定，它们应分别等于2a,4a,a(a是套数)，我们先让a等于某一个正整数，例如a=1,求出xi以后，假如ai是分数，就乘以xi的分母的最小公倍数，这时候残料总长度
S=150x1+300x2+250x3+100x4+50x5+250x6+200x7+150x8

例3 设某公司有m种不同的资源（如原料、能源、资金等）用来生产n种产品，用aij表达生产一个单位第j种产品所消耗的第i种原料的数量，用cj（j=1,2,……，n）表达第j种产品的单位价值，而这个公司现存的第i种资源的数量是bi（i=1,2,……，m），现在要来做一个可以充足运用现有资源的生产计划，使每种产品在不超过现有资源的条件下总产值最大。
思考题 有甲、乙两种产品，都需要通过两道工序，甲产品每单位需第一道工序2小时，第二道工序3小时。而乙产品则分别是3小时和4小时。第一道工序可供运用的时间是16小时，第二道工序可供运用的时间是24小时。每生产一个单位的乙产品会产生2个单位的副产品丙，且不需外加任何费用。丙产品一部分可以出售赢利，其余的只能加以销毁。出售产品甲每单位能赢利4元，乙产品为10元。丙产品为3元，但是丙产品假如售不出去，那么每单位的销毁费用是2元。预测表白，最多可售出5个单位的丙产品。规定决定使利润最大的甲和乙的产量，试建立此问题的线性规划模型。
二、案例分析
回收固体废弃物问题
塞维特（Save－It）公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物解决，混合成为可销售的产品。根据混合是各种材料的比例，可将该产品提成不同的等级（参照表1）尽管在混合各种等级产品是允许一定的机动性，但每一等级产品中各种材料的最大最小值都必须符合下面质量标准的规定。（最大和最小值是根据该材料的重量在该等级产品总重量中的比例来拟定的。）在两种较高等级的产品中，有一种特定材料的比例是固定的。这些规定与混合的成本以及每一等级产品的售价都在表1中给出。
回收中心可以从一些渠道定期的收集到所需的固体废弃物，因此，可以获得维持稳定作业的解决量。表2给出了中心每周可以收集到每种材料的数量以及解决成本。
塞维特公司是绿地组织的全资公司，绿地组织是一个专门从事与环境有关业务的组织。塞维特公司的收益将所有用于支持绿地组织的其他活动，而绿地组织每周可获得$30,000的捐款，专门用于固体废弃物的解决。公司的董事会规定塞维特公司的管理层将这一捐款合理分派使用在各种材料上，务必将所收集到的固体废弃物中至少一半数量的废弃物加以解决。这些附加的约束如表2所示。
管理层决定在表1和表2所列的约束之内，有效地将各种材料分派到各等级的产品中去，以实现每周的总利润最大（总收入减总成本）。
表1 塞维特公司产品数据
等级
规格说明
每磅的混合成本
每磅的单价

A
材料1：不超过总量的30％
材料2：不少于总量的40％
材料3：不超过总量的50％
材料4：总量的20％

$3.00

$8.50

B
材料1：不超过总量的50％
材料2：不少于总量的10％
材料4：总量的10％

$2.5

$7.00
C
材料1：不超过总量的70％
$2.00
$5.50

表2塞维特公司固体废弃物的有关数据
材料
每周可获得的数量（磅）
每磅的解决成本
附加约束
1
2
3
4
3,000
2,000
4,000
1,000
$3.00
$6.00
$4.00
$5.00
1. 对于每种材料，每周必须至少收集并解决一半以上的数量
2. 每周有$30.000可用于解决这些材料。

这是一个线性规划问题，为了该问题建模，一方面要明确问题所涉及的活动，资源，收益以及拟定的需求。这一步的关键在于管理层的目的是将每种材料最优的分派给每一等级的产品。每一种材料与产品的组合都是一个决策：多少的材料用于这一等级的产品？
因此，要决策的是每周将多少磅的每一种材料加入到每一等级的产品中去。
由于资源有限，收益受到规定，以及拟定的需求，该问题就有了相称多的约束，归纳如下：
有限的资源：四种固体废弃物所能获得的数量如表2的第2栏所示，此外，表1的第2栏还表白材料1与材料3的用量有限，这些有限的资源都将形成资源的约束条件。
规定的受益：收益是指所收集和解决的每一种材料，表2的右边显示最低可接受的收益水平是可获得的材料的一半，而表1规定材料2的最低可接受的施用量，这些都是收益约束。
拟定需求的约束：1.表1第2栏所示的材料4的固定用量。2.表2右边所示的解决固体废弃物的固定开销。
管理层的目的是使得三种等级的产品所能实现的每周总利润最大，因此，这就是该问题的总绩效测度。这一测度可通过在销售总收入中减去混合解决的总成本计算出。$30,000的捐款所有用于解决固体废弃物，这一部份在计算利润时不能包含在成本里，因此，混合成本将是唯一的成本。这样，对于每一等级的产品，每磅的利润是将表1第四栏的销售价减去第3栏的混合成本计算出的。
建模：若用表达每周分派给x等产品的材料y的数量，则有如下数学模型：
目的函数：最大化利润
约束条件：
1． 混合的比例规定（表1的第2栏）

2． 可获得的材料（表2第2栏）：

3． 要解决的材料的约束（表2的右边）：

4． 解决成本的约束（表2的右边）：
5。非负约束：

德怀特公司的目的规划问题
德怀特公司的管理科学部在接下来的一个月中将要开展一项研究,研究的重点是拟定三种新产品的组合,以最佳的实现管理层的三个目的。三种新产品的产量就是要作出的决策。
管理层希望考虑三方面的影响因素：总利润，员工的稳定性以及产品开发的投资资金限制。这样管理层建立了如下的目的，
目的1：新产品产生的总利润（净现值）不得少于$125,000,000。
目的2：保持现有的4000人的员工水平。
目的3：将投资资金限制在$55，000，000以内。
但是，管理层意识到要同时实现三个目的是不大现实的，因此，他们对三个目的的相对重要性作出了评价，三个目的都是重要的，但是在重要性上还是有些先后的差别。
重要性排序目的1，目的2的前半部分（避免减少员工），目的3，目的2的后半部分（避免增长员工）。
为了进一步使这一排序量化，对每一目的都分派了表达偏离目的严重性的罚数权重。如下表3

表3 表达偏离目的相对严重性的罚数权重
目的
因素
偏离目的的罚数权重
1
总利润
5(低于目的的每$1,000,000)
2
员工水平
4(低于目的的每100名员工)
2(超过目的的每100名员工)
3
投资资金
3(超过目的的每$1,000,000)
各种产品对目的的单位奉献如下表4
表4 各种产品对目的的单位奉献
因素
产品的单位奉献
目的
1
2
3
总利润（百万美元）
员工水平（以百为单位）
投资资金（百万美元）
12
5
5

9
3
7
15
4
8

建模 若设Pi为产品I的天天产量，则三个目的分别为
目的1：（总利润目的）
目的2：（员工水平目的）
目的3：（投资资金目的）
这些数学表达式形式上很像线性规划的约束条件，但是，它们不能看作为是数学模型的约束，由于约束是必须满足的，而管理层已经意识到要同时实现所有的目的是不也许的。对于目的规划，问题的总目的就是要使所有的目的都尽也许实现。
对于每一个偏离的目的，其相应的罚数为罚数权重与偏离值的乘积，因此，问题的目的就是通过拟定决策变量的值以实现。
最小化W＝5（低于目的1的数量）＋2（超过目的2的数量）＋4（低于目的2的数量）＋3（高于目的3的数量）

炼油厂的生产优化问题
炼油厂购买两种原油（原油1和原油2），这些原油通过四道工序解决：分馏、重整、裂化和调合，最后得到油和煤油用于销售。
1） 分馏
分馏将每一种原油根据沸点不同分解为轻石脑油、中石脑油、重石脑油、轻油、重油和残油。轻、中、重石脑油的辛烷值分别是90、80、70，每桶原油可以产生的各种油分如表1所示，在分馏中有少量消耗。
表1 原油分馏得到的油分（桶/桶）

轻石脑油
中石脑油
重石脑油
轻油
重油
残油
原油1
原油2
0.10
0.25
0.20
0.25
0.20
0.18
0.12
0.08
0.20
0.19
0.13
0.12
2） 重整
石脑油可以直接用来调合成不同等级的汽油，也可以进入重整过程。重整过程产生辛烷值为115的重整汽油，1桶轻石脑油、中石脑油、重石脑油通过重整可以得到的重整汽油为0.6，0.52，0.45桶。
3） 裂化
轻油和重油可以直接经调合产生航空煤油，也可以通过催化裂化过程而产生裂化油和裂化汽油，裂化汽油的辛烷值为105，轻油和重油裂化产生的产品（单位：桶/桶）如表2所示。
表2轻油重油裂化产品

裂化油
裂化汽油
轻油
重油
0.68
0.75
0.28
0.20
裂化油可以用于调和成煤油和航空煤油，裂化汽油可用于调合成汽油。残油可以用来生产润滑油或者用于调合成航空煤油或煤油，一桶残油可以产生5.5桶润滑油。
4） 调合
（1）汽油（发动机燃料）。有两种类型的汽油，普通汽油和优质汽油，这两种汽油都可以用石脑油、重整汽油和裂化汽油调合得到。普通汽油的辛烷值必须不低于84，而优质汽油的辛烷值必须不低于94。这里假定，调合成的汽油的辛烷值与各成分的辛烷值及含量成线性关系。
（2）航空煤油。航空煤油可以用轻油、重油、裂化油和残油调合而成。航空煤油的蒸汽压必须不超过每平方厘米1公斤，而清幽、重油、裂化油和残油的蒸汽压（单位：公斤/平方厘米）分别为1.1，0.6，1.5，0.0 。可以认为，航空煤油的蒸汽压与各成分的蒸汽压及含量成线性关系。
（3）煤油。煤油由轻油、裂化油、重油和残油按10：4：3：1调合而成。
各种油品的数量及解决能力为：
（1）天天原油1的可供应量为20230桶。
（2）天天原油2的可供应量为30000桶。
（3）天天最多可分馏45000桶原油。
（4）天天最多可重整10000桶石脑油。
（5）天天最多可裂化解决8000桶。
（6）天天生产的润滑油必须在500桶到1000桶之间。
（7）优质汽油的产量必须是普通汽油产量的40%。
优质汽油、普通汽油、航空煤油、煤油、润滑油等各种产品的利润（元/桶）为0.7，0.6，0.4，0.35，0.15
图1表达炼油厂的整个炼油过程的工艺过程。

图1 炼油厂的生产流程

轻油
残油

分

馏

装

置
重整装置
裂化装置
汽

油

调

合
煤

油

调

合
润滑油装置
原油1
原油2
轻石脑油
中石脑油
润滑油
航空煤油
普通汽油
重石脑油
重油
煤油
优质汽油

现在的问题是制定炼油厂的生产计划，以得到最大利润。
货币危机条件下资金抽逃的最佳途径模型分析
假设，某投机商最初手中持有A1,A2,……,An等n种不同货币，在货币危机发生时，欲将所持货币兑换为一种硬通货C。但由于受危机发生国金融市场上货币汇率、交易成本、交易数额等条件限制，只能通过若干种中介货币B1,B2,……,Bm来兑换成这种硬通货C。在上述条件下，从数学意义上讲，投机者目前所面临的问题是寻找一条最佳途径，使其兑换时的总成本最低（收益最大）。
为讨论问题的方便起见，在上述若干种货币之间不存在套利机会时，其兑换网络如下图所示（该初始货币分别为A1，A2，A3，硬通货为C4，中介货币分别为B5，B6，B7，B8）：

B8
B7
B6
C4
B5
A3
A2
A1

由于各种货币之间不存在套汇机会，那么其兑换的最佳途径选择，可以通过修正的最小费用流方法加以解决。于是，我们可以建立如下的数学模型。
设某投机商在货币危机发生时，手中持有初始货币A1 ，A2 ，A3，其数量分别为a1，a2，a3，中介货币有四种B5，B6，B7，B8，欲兑换的硬通货为C4。第j种货币与第i种货币的汇率为（1单位j种货币= i种货币），交易成本比率（双向）为，第j种货币兑换为第i种货币的最大量（以第i种货币计量）为（j=1,2,3，i=1,2,3,4,5,6,7,8,ji）。那么，要拟定最佳兑换途径，若假设第j种货币兑换为第i种货币的数量为xji，则可以建立如下数学模型：
寻找最佳兑换途径，即规定各种交易的总成本最小，所以目的函数为：

需要满足的条件有下列五组：
1．每种初始货币兑换为其他货币的数量应等于其他初始货币兑换为该种初始货币的数量加上该种货币的原有量，即初始货币的守恒条件：

2．所有货币（涉及初始货币和中介货币）兑换为硬通货C4的数量等于初始货币直接兑换为硬通货C4的数量，即硬通货C4的守恒条件：

3．每种中介货币兑换为其他货币（涉及硬通货C4和其他中介货币）的数量等于其他货币（初始货币和其他中介货币）兑换为该种中介货币的数量，即中介货币守恒条件:

4. 交易额限制条件：

5．非负条件：

解上述线性规划，即可找到将所有的初始货币A1 ，A2 ，A3兑换为硬通货C4的费用最小的途径，从而达成资金抽逃的目的。
三、实例分析
为了进一步说明问题，下面我们用一个具体的实例来加以分析。
在货币危机条件下，设某投机商手中持有初始货币12亿日元，他需要将现有日元所有兑换为硬通货美元，以达成资金抽逃的目的。
他能找到世界上绝大多数货币的即时汇率见下表：

日元
美元
加拿大元
欧元
英镑
比索
日本日元
美元
加拿大元
欧元
英镑
墨西哥比索
1
0.008
1
0.01
1.25
1
0.0064
0.8
0.64
1
0.0048
0.6
0.48
0.75
1
0.0768
9.6
7.68
12
16
1
此外，他知道一种货币兑换成另一种货币的交易成本与逆向操作的交易成本是相等的。各种交易成本如下表：（比例）

日元
美元
加拿大元
欧元
英镑
比索
日本日元
美元
加拿大元
欧元
英镑
墨西哥比索
--
0.4
--
0.4
0.05
--
0.4
0.1
0.2
--
0.25
0.1
0.1
0.05
--
0.5
0.1
0.1
0.5
0.5
--
除此之外，在某国金融市场上，允许他把日元兑换成其他国家货币的最大量，即交易限制为：
单位：千元

日元
美元
加拿大元
欧元
英镑
比索
日元
--
2023
2023
2023
2023
4000
此问题的兑换网络如下图所示：

比
美
欧
加
日
英

在此问题中，日元为货币A1，美元为货币C4，加拿大元，欧元，英镑，比索分别为货币B5，B6，B7，B8，设为第j种货币兑换为第i种货币的数量（以第j种货币单位计量），则有如下数学模型：
目的函数（扩大10000倍）

约束条件：
1．
2．
3．

4．

5．
运用Excel电子表格求解上述线性规划，即可得到资金抽逃时的最佳途径是：先将12亿日元分为5个部分，即2.5亿、2亿、3.13亿、4.17亿、20833333日元；再分别将其兑换为美元、加拿大元、欧元、英镑、比索；最后再将所得到的2023000加拿大元、2023000欧元、2023000英镑、1600000比索才干所有兑换为9600000美元。所需费用约为40367美元，最终12亿日元在货币危机条件下能转换为美元的量是9559633美元。
公务员招聘问题（04D题）
我国公务员制度已实行数年，1993年10月1日颁布施行的《国家公务员暂行条例》规定：“国家行政机关录用担任主任科员以下的非领导职务的国家公务员，采用公开考试、严格考核的办法，按照德才兼备的标准择优录用”。目前, 我国招聘公务员的程序一般分三步进行：公开考试（笔试）、面试考核、择优录取。
现有某市直属单位因工作需要，拟向社会公开招聘8名公务员，具体的招聘办法和程序如下：
（一）公开考试：凡是年龄不超过30周岁，大学专科以上学历，身体健康者均可报名参与考试，考试科目有：综合基础知识、专业知识和“行政职业能力测验”三个部分，每科满分为100分。根据考试总分的高低排序按1:2的比例（共16人）选择进入第二阶段的面试考核。
（二）面试考核：面试考核重要考核应聘人员的知识面、对问题的理解能力、应变能力、表达能力等综合素质。按照一定的标准，面试专家组对每个应聘人员的各个方面都给出一个等级评分，从高到低提成A/B/C/D四个等级，具体结果见表１所示。
（三）由招聘领导小组综合专家组的意见、笔初试成绩以及各用人部门需求拟定录用名单,并分派到各用人部门。
该单位拟将录用的8名公务员安排到所属的7个部门，并且规定每个部门至少安排一名公务员。这7个部门按工作性质可分为四类：(1)行政管理、 (2)技术管理、(3)行政执法、(4)公共事业。见表2所示。
招聘领导小组在拟定录用名单的过程中，本着公平、公开的原则，同时考虑录用人员的合理分派和使用，有助于发挥个人的专长和能力。招聘领导小组将7个用人单位的基本情况（涉及福利待遇、工作条件、劳动强度、晋升机会和学习深造机会等）和四类工作对聘用公务员的具体条件的希望达成的规定都向所有应聘人员公布（见表2）。每一位参与面试人员都可以申报两个自己的工作类别志愿（见表1）。请研究下列问题：
（1）假如不考虑应聘人员的意愿，择优按需录用，试帮助招聘领导小组设计一种录用分派方案；
（2）在考虑应聘人员意愿和用人部门的希望规定的情况下，请你帮助招聘领导小组设计一种分派方案；
（3）你的方法对于一般情况，即N个应聘人员M个用人单位时，是否可行？
(4)你对上述招聘公务员过程认为尚有哪些地方值得改善，给出你的建议。

表１：招聘公务员笔试成绩，专家面试评分及个人志愿
应聘
人员
笔试
成绩
申报类别志愿
专家组相应聘者专长的等级评分
知识面
理解能力
应变能力
表达能力
人员1
290
（2）
（3）
A
A
B
B
人员2
288
（3）
（1）
A
B
A
C
人员3
288
（1）
（2）
B
A
D
C
人员4
285
（4）
（3）
A
B
B
B
人员5
283
（3）
（2）
B
A
B
C
人员6
283
（3）
（4）
B
D
A
B
人员7
280
（4）
（1）
A
B
C
B
人员8
280
（2）
（4）
B
A
A
C
人员9
280
（1）
（3）
B
B
A
B
人员10
280
（3）
（1）
D
B
A
C
人员11
278
（4）
（1）
D
C
B
A
人员12
277
（3）
（4）
A
B
C
A
人员13
275
（2）
（1）
B
C
D
A
人员14
275
（1）
（3）
D
B
A
B
人员15
274
（1）
（4）
A
B
C
B
人员16
273
（4）
（1）
B
A
B
C

表 2:　用人部门的基本情况及对公务员的盼望规定
用人
部门
工作
类别
各用人部门的基本情况
各部门对公务员专长的希望达成的规定
福利待遇
工作条件
劳动强度
晋升机会
深造机会
知识面
理解能力
应变能力
表达能力
部门1
（1）
优
优
中
多
少
B
A
C
A
部门2
（2）
中
优
大
多
少
A
B
B
C
部门3
（2）
中
优
中
少
多
部门4
（3）
优
差
大
多
多
C
C
A
A
部门5
（3）
优
中
中
中
中
部门6
（4）
中
中
中
中
多
C
B
B
A
部门7
（4）
优
中
大
少
多

三、思考题
教学组织问题
近年来，我国高等教育的规模迅速扩大，这对于普及高等教育，提高人民整体素质，加速培养人才等方面的确起到了积极的作用。然而事物总是一分为二的，各高校的教学质量普遍下降也是不争之事实，特别是普通院校，扩招后各专业，各班级学生的知识基础，接受能力参差不齐，使教师无所适从。更具体一点，扩招后的大学高等数学教育，已使数学教师头疼不已。按照以前的教学计划和教学规定实行教学，期末考试下来肯定是一半以上不及格；假如减少内容，减少规定，又会影响部分同学报考研究生；增长课时更是不行，由于学生早就抱怨不堪重负了（事实的确如此）。为此，各学校都在研究探讨，寻找新形势下高等数学教育的好办法。
我校今年计划在全校范围内对高等数学课采用分级教学（早在几年前，外语课已经先行），现正处在征求意见阶段。根据各专业门类教学计划、学生自身的规定和当前的就业特点，初步计划将高等数学课根据内容和规定划分为三类：第一类是理工类（约占28%），对高等数学规定较高，考研时要考高等数学一，这类学生数学基础较好，学数学的爱好也大；第二类为财经类（约占45%），专业上对数学也有较高规定，考研时要考数学四，和理工类比起来，内容和侧重点都有不同，这类学生数学基础和学习爱好一般；第三类为法学、外语、艺术、体育等（约占27%），这类学生（绝大部分是文科）数学基础和学习爱好都很差，有些甚至是由于数学的因素才报考这些专业，从专业的角度考虑，他们只需要掌握一些数学的基本知识和思维方法就行，考研时也不考高等数学。
鉴于各类学生对数学课的不同规定，现要将去年招收的2023名学生的高等数学课分为三种内容不同规定不同的教学方式。当然，我校现有的硬件和软件条件都需考虑。，要承担这2023名学生的高等数学教学任务，在进行分级教学时要考虑如下的一些因素：
1．我校高等数学教研室共有10名数学教师，要承担所有2023名学生的高等数学教学任务，且短期内人员不会有变动；
2．根据教学设备容量，大教室最多能容纳160名学生，同时为了合理使用教学资源，小教室至少为40人。
3．根据以往的教学经验，40人的小班高等数学及格率（合格率）约为90%，合班上课时（大班），由于课外作业、答疑和教学效果等因素，在40人的基础上每增长20人，及格率将下降约两个百分点。
4．考虑到教师的身体因素，每位教师上40人的小班课每周最多可以上四个班；而40~80人的中班课每周最多可以上三个；超过80人的班，则每周最多上两个。
5．每位教师由于种种因素，只愿上同一级别的课。
6．由于学生的因素，规定较低的一类学生也可以上较高规定一类的课，但幅度不超过10%。
7．每一级别至少开一个小班。
考虑下列问题：
1． 在不考虑分类的情况下，试建立分班教学的数学模型，使所有学生的及格率最高。
2． 在分类情况下，重新建立分班教学的数学模型，使所有学生的及格率最高。