6.2树 树(tree):连通的无圈的图

6.3.2割平面法(2) 例1利用割平面法求解整数规划 max z=+x2

6.2具有整数解的线性规划问题 对纯整数规划 max z=cx (IP): s.t. Ax=bx,≥0,整数,j=1,2,…n

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

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

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

4.1整数规划 整数规划(IP, integer programming):决策变量的全部或部分取整数值的线性规划

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

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

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