6.1整数规划 整数规划(IP, integer programming):决策变量的全部或部分取整数值的线性规划显然,整数规划去掉对决策变量的整数性要求即为一般线性规划问题分类:

5.4算法步骤 综合以上讨论,设计平衡型运输问题算法如下: 表上作业法:

5.3最优性的检验 预备知识:对标准形线性规划问题 max z=cx

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