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

图论的应用范围: 1、中国邮路问题: 邮递员如何选择适当的投递路线,使每条街道至 少走过一次且所走的总路程最短? 2、最短路问题: 一个乡有9个自然村,其间道路如下图所示, 要以村为中心建有线广播网,如要求沿道路 架设广播线,应如何架设使所用电线最短？

一、例限期采购问题(随机型) 某部门欲采购一批原料,原料价格 原料价格(元)概率p 在五周内可能有所变动,预测得每 种价格的概率如右表所示,试问该

一、对最短路问题:

一、决策问题与0-1变量 决策变量x,--是否做第i件事i=1,2,…,n