5.2初始基本可行解 本节来介绍求(TP)的一个初始基本可行解的两种方法:西北角法和最小元素法 如§5.1所言,运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表,而是借助于运输表来实现:但其算法在理论基础、基本思想、算法步骤(包括初始基本可行解的选取、最优性的验证、转轴)等各方面都和单纯形法是一致的供需平衡型运输问题的运输表:∑a=∑b

5.1运输问题 运输问题(p, Transportation Problem):从m个发点A1,A2,,A往n个收点B1,B2,…,Bn运输货物,有关数据如下图所示:

12.2统筹图中有关参数的计算 关键路线(critical path):统筹图中从总开工事项顶点到总完工事项顶点的最长的有向路 华罗庚先生称关键路线为主要矛盾线 关键路线的长度:关键路线上各工序时间之和 关键工序:关键路线上的工序

12.1统筹图 统筹方法是利用数学方法和网络图来研究、分析工程项目的合理组织、协调管理的一种科学管 理方法 这一方法于20世纪50年代产生于美国.956年,美国杜邦公司为协调公司不同业务部门的系 统规划,利用网络方法制订了第一套网络计划,称为关键路线法(CPM, Critical Path Method).1958年,美国海军武器局在制订“北极星”导弹研制计划时,同样利用了网络方法,但 更注重于对各项任务安排的评价和审查,称为计划评审技术(pr, Program Evaluation and Review Technique)

2.2.2最小树与森林 支撑(生成)树(spanning tree): spanning subgraph of graph which is itself 支撑树T 例1画出下列各图的所有不同构的支撑树:

2.2.1树 1847年,克希霍夫在研究电网络方程时首次提出了树的概念 树(tree): connected(连通的) and acyclic(无圈的) graph. 平凡树(trivial tree):v=1的树,即K1(平凡图);非平凡树(nontrivial tree): otherwise. 叶(leaf):树的悬挂点(度为1的顶点);分支点(branch vertex:度≥2的顶点 非同构的树

2.1.2图的基本概念 (2) 子图 给定图G=(V,E),G1=(V1,E1),若V1CV,EE,则称G1为G的子图( subgraph),称 G为G1的母图( supergraph),记作:Gg. 若GCG,但G1≠G,则称G1为G的真子图(proper subgraph),记作:1cg 若G是G的子图,且V1=V(E1CE),则称G1为G的支撑(生成)子图(spanning subgraph). 注:(1)二分图的任一子图也均为二分图.(2)边数为E的图的所有(同构或不同构)支撑子 图的个数为C+C2+C2+…+C=2

2.1.1图的基本概念 (1) 图(graph):用(顶)点代表对象,顶点之间的边表示对象之间的关系 滨州 “图是关系的数学表达” 注:图和几何图形不同.几何图形描述物体

2.0图论绪言 千言万语不及一张图(Thousands of words are inferior to graph) -F.Herbart 山东运筹,两论起家.一为规划论,一为图论

一、选择题:(本大题共5个小题,每小题4分,共20分,在每 得分统分人个小题给出的四个选项中,只有一项是符合题目要求的,把所选 项的字母填在题后的括号内) 1、下列函数是奇函数的是