Questions in category: 数学建模 (Mathematical Models)
应用数学 >> 数学建模

1. Fleury 算法

Posted by haifeng on 2018-04-17 16:57:51 last update 2018-04-17 17:00:23 | Answers (0) | 收藏


Fleury 算法用于求欧拉图的欧拉巡回.

 

设 $G=(V,E)$ 是一无向欧拉图, 我们要求 $G$ 中一条欧拉巡回.

算法:

(1) 任取 $G$ 中一顶点 $v_0$, 令道路 $w_0=v_0$.

(2) 假定道路 $w_i=v_0 e_1 v_1 e_2\cdots e_i v_i$ 已经选好, 则从剩余的边集 $E_{i}^{c}:=E(G)-\{e_1,e_2,\ldots,e_i\}$ 中选择 $e_{i+1}$, 使得:

    (a) $e_{i+1}$ 与 $v_i$ 相关联;
    (b) 除非不能选择, 否则一定要使 $e_{i+1}$ 不是 $G_i:=G[E_i^c]$ 的割边(或桥 bridge).

(3) 当第(2)步不能再进行时算法停止.

 

可以证明当算法停止时, 所得到的道路 $w_m=v_0 e_1 v_1 e_2 v_2\ldots e_m v_m$ (这里 $v_m=v_0$) 是 $G$ 中的一个欧拉巡回(或欧拉回路).

 

 

 


References:

赵静、但琦 等编《数学建模与数学实验》(第四版)5.5.2 中国邮递员问题.  Page 104.

http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

 

2. [Ex4.4.2]炼油厂问题

Posted by haifeng on 2018-04-09 20:00:02 last update 2018-04-09 20:00:42 | Answers (3) | 收藏


炼油厂将 $A,B,C$ 三种原油加工成甲、乙、丙三种汽油,一桶原油加工成一桶汽油的费用为4元,每天至多能加工汽油14000桶。原油的买入价、买入量、辛烷值、硫含量,及汽油的卖出价、需求量、辛烷值、硫含量由表4-15给出。

 

表 4-15
原油类别 买入价(元) 买入量(桶) 辛烷值(%) 硫含量(%)
A 45 $\leqslant 5000$ 12 0.5
B 35 $\leqslant 5000$ 6 2.0
C 25 $\leqslant 5000$ 8 3.0

 

汽油

汽油类别 卖出价(元) 需求量(桶) 辛烷值(%) 硫含量(%)
70 3000 $\geqslant 10$ $\leqslant 1.0$
60 2000 $\geqslant 8$ $\leqslant 2.0$
50 1000 $\geqslant 6$ $\leqslant 1.0$

 

问: 如何安排生产计划, 使利润最大?

一般来说,做广告可以增加销售,估计一天向一种汽油投入一元广告费,可使该汽油日销量增加10桶,且每天最多投入广告费800元。

问: 如何安排生产和广告计划使利润最大?

 

3. [Ex4.4.1]电路总功率问题

Posted by haifeng on 2018-04-09 19:28:01 last update 2018-04-09 19:28:01 | Answers (1) | 收藏


一电路由三个电阻 $R_1, R_2, R_3$ 并联,再与电阻 $R_4$ 串联而成,记 $R_k$ 上电流为 $I_k$,电压为 $V_k$, $k=1,2,3,4$。在下列情况下确定 $R_k$,使电路总功率最小:

(1)$I_1=4$, $I_2=6$, $I_3=8$, $2\leqslant V_k\leqslant 10$;

 

 


References:

《数学建模与数学实验》P. 83

4. 供应与选址

Posted by haifeng on 2018-03-25 10:14:44 last update 2018-03-25 10:29:59 | Answers (1) | 收藏


某公司有 6 个建筑工地要开工, 每个工地的位置(用平面坐标系 $a,b$ 表示, 距离单位: km) 以及水泥日用量 $d$ (单位: 吨 (t)) 由下表给出.

工地位置 $(a,b)$ 及水泥日用量 $d$
  1 2 3 4 5 6
横坐标位置 $a$ 1.25 8.75 0.5 5.75 3 7.25
纵坐标位置 $b$ 1.25 0.75 4.75 5 6.5 7.75
水泥日用量 $d$ (吨, t) 3 5 4 7 6 11

 

目前有两个临时料场位于 $A=(5,1)$, $B=(2,7)$, 日储量各为 20 吨.

假设从料场到工地之间均有直线道路相连.

(1) 试制定每天的供应计划, 即从 $A,B$ 两料场分别向各工地运送多少吨水泥, 使总的吨千米数最小.

(2) 为了进一步减少吨千米数, 打算舍弃这两个临时料场, 改建两个新的料场, 日储量仍都为 20 吨. 问应建在何处, 使得吨千米数最小? 节省的吨千米数为多少?

 

References:

赵静, 但琦 等编 《数学建模与数学实验》第四版, P56--61.

5. 某工厂生产甲、乙两种产品,生产每件产品需要原材料、能源消耗、劳动力及所获利润如下表所示:

Posted by haifeng on 2017-06-08 09:51:34 last update 2017-06-08 09:53:37 | Answers (1) | 收藏


某工厂生产甲、乙两种产品,生产每件产品需要原材料、能源消耗、劳动力及所获利润如下表所示:

品种 原材料(kg) 能源消耗(百元) 劳动力(人) 利润(千元)
2 1 4 4
3 6 2 5

现有库存原材料1400千克;
能源消耗总额不超过2400百元;
全厂劳动力满员为2000人。

试安排生产任务(生产甲、乙产品各多少件),使利润最大,并求出最大利润。

 

6. 确定最优定价问题

Posted by haifeng on 2017-06-08 00:26:29 last update 2017-06-08 00:26:29 | Answers (1) | 收藏


在考虑最优定价时设销售期为 $T$, 成本 $q$ 随时间增长, 不妨设单位商品的损耗成本是 $q(t)=q_0+\beta t$, 其中 $\beta$ 是增长率. 又设单位时间的销售量为 $x(p)=a-bp$ ($p$ 为价格).

今将销售期分为 $[0,\frac{T}{2}]$ 和 $[\frac{T}{2},T]$ 两个时间段, 每段的价格固定, 分别记作 $p_1, p_2$. 求 $p_1, p_2$ 的最优值, 使销售期内的总利润最大.

如果要求销售期 $T$ 内的总销售量为 $Q_0$, 求在此约束条件下的 $p_1, p_2$ 的最优值.

 

 


References:

姜启源、谢金星、叶俊 编 《数学建模》 P.82, Ex.6