一、生产计划问题的Matlab求解
某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
如何安排生产使利润最大。
二、工厂-销售点配置问题
生产厂 顾客需求 销售点
4
5 D C B A
7 II
III 2 1
3 I 每件产品占用的
机时数（小时/件） 产品甲
产品乙
产品丙
产品丁
设备能力
（小时）
设备A
1.5
1.0
2.4
1.0
2000
设备B
1.0
5.0
1.0
3.5
8000
设备C
1.5
3.0
3.5
1.0
5000
利润（元/件）
5.24
7.30
8.34
4.18
问题: 为使经营成本最低,应开设那些工厂及销售点?
三、选址问题
某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）
假设：料场和工地之间有直线道路。现有2料场，位于A (5, 1), B (2, 7),记(xj,yj),j=1,2, 日储量ej各有20吨。
目标：制定每天的供应计划，即从A, B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。
四、最短路问题
求各点到T的最短路 IIIIII生产能力18001,0001,20030035,000240050070020045,000380060050030040,000450060070020042,000570060050040040,000ABCDI4080905040,000II7040608020,000III8030506060,000需求量200300150250运输成本: 工厂-销售点开设的固定成本开设的固定成本运输成本: 销售点-客户i １ ２ ３ ４ ５ ６
a 1.25 8.75 0.5 5.75 3 7.25
数学建模中国邮递员问题求解算法
1 / 21 邮递员问题求解算法
若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求；关于非Euler图，1973年，Edmonds和Johnson给出下边的解法：
设G是连通赋权图，则
（i）求V0 {v|v
V(G),d(v)
1(mod2)}；
（ii）对每对极点
u,v
V0，求d(u,v)（
d(u,v)
是u
与v的距离，可用
Floyd
算法求得）；
iii）结构完整赋权图K|V0|，以V0为极点集，以d(u,v)为边uv的权；
iv）求K|V0|中权之和最小的完满对集M；
v）求M中边的端点之间的在G中的最短轨；
vi）在（v）中求得的每条最短轨上每条边增添一条等权的所谓“倍边”（即共端点共权的边）；
vii）在（vi）中得的图G'上求Euler回路即为中国邮递员问题的解。
多邮递员问题求解
邮局有k(k2)位送达员，同时送达信函，全城街道都要送达，达成任务返回邮局，怎样分派送达路线，使得达成送达任务的时间最早？我们把这一问题记
成kPP。
KPP的数学模型以下：
G(V,E)是连通图，v0 V(G)，求G的回路C1, ,Ck，使得
（i）v0 V(Ci)，i 1,2,,k，
（ii）max () min，
we 数学建模中国邮递员问题求解算法
2 / 22 ikeE(C )
（iii） k
E(Ci) E(G)
1
运筹学重要考点
第一部分：线性规划
1、线性规划与单纯形法
（1）线性规划问题的数学模型
（2）线性规划问题解的概念
（3）线性规划问题的图解法
（4）单纯形法
①将所给问题标准化
②计算、迭代步骤
③最优性的判定（解的判定定理）
④人工变量法：大M法和两阶段法
2、对偶问题
⑴原问题转化为对应的对偶问题
⑵对偶问题的基本性质
⑶对偶单纯形法的计算
⑷影子价格
3、灵敏度分析
⑴价值系数灵敏度分析
⑵约束条件灵敏度分析
⑶技术系数灵敏度分析
4、运输问题
⑴表上作业法
①初始基的确定：最小元素法、伏格尔法
②最优解的判别：闭回路法、位势法
③改进方法：闭环回路调整法
⑵产销不平衡运输问题的求解
第二部分：整数规划
⑴分支定界法
⑵割平面法
⑶0-1规划建模及解法（隐枚举法）
⑷指派问题
①解法：匈牙利法
②非标准指派问题
第三部分：动态规划
1、动态规划的基本思想
2、动态规划的解题步骤
⑴建立动态规划模型
⑵采用逆序法求解
3、动态规划的应用
⑴最短路问题（一维资源分配问题）
⑵生产经营问题
①生产——库存问题
②库存——销售问题
③限期采购问题
⑶可靠性问题
⑷背包问题
⑸设备更新问题
第四部分：图与网路计划
1、图的基本概念和性质
2、最小树（Kruskal算法）
3、最短路问题及算法
⑴Dijcskra算法
⑵Ford算法
4、网路最大流问题
5、最小费用最大流问题
6、中国邮递员问题（奇偶图上作业法）
7、网络计划
⑴绘制网络图
⑵计算时间参数和确定关键路径
⑶网络计划的调整和优化
单纯型 对偶单纯型（改进单纯计算及参数灵敏度不考） 运输 整数规划（分支定界和割平面计算不考）动态规划（会计算即可）动态规划应用（只考一维资源费配 背包 可靠度 排序）图论 网络计划（知道关键路线特征及虚工作意义即可
不考计算）
最短路线
姓名
邮递员叔叔每天都要送信，而且要穿过数以百计的大街小巷。怎样设计一种科学的走法，使他完成送信任务后回到邮局所走的路最短？这个问题叫做最短邮递路线问题。
最短的邮递路线当然是从邮局出发，走遍每条街巷而且只走一次，最后回到邮局。这样的路线由于没有重复，是最短的。实际生活中是不是有这样的理想路线呢？当然没有。那么， 在什么情况下才能达到这样理想的路线呢？这还得从一种有名的数学游戏“一笔画”谈起。
如果在画图形时，笔不离纸而且每条线都不许重复，这种画法称为“一笔画”。
下面三个图形，请你试一试能不能将它们一笔画成？
任何图形都是由点和线组成的，图形中的点可以分为两大类：
（1）凡是从这点出发的线的数目是偶数的，称为偶点。
（2）凡是从这点出发的线的数目是奇数的，称为奇点。
一个图形能否一笔画成，关键在于图中奇点的个数的多少。它的规律是：
（1）凡是图形中没有奇点的，一定可以一笔画成。画时，可以从任意一个偶点为起点，最后仍回到这点。
（2）凡是图形中只有两个奇点，一定可以一笔画成。画时，必须以一个奇点为起点，另一个奇点为终点。
（3）当一个图形中奇点的个数多于两个时，此图形不能一笔画成。
例1、下图是国际奥委会的会徽，你能一笔把它画出来吗？
及时练：
1、下面图形可以一笔画成吗？如果可以，请你用一笔画成。
（1） （2）
（3）
（4） （5）
例2、试判断下图中，哪一幅能一笔画？为什么？？
及时练：
1、请将下列图形一笔画成，如果不行，请说明理由。
（1） （2）
（3）
（4） （5）
