运筹学讲义(共13页).doc

精选优质文档-倾情为你奉上第二讲 运输问题定理1 运输问题的数学模型必有最优解。运输问题基变量的个数为m+n1 。对于运输问题的基可行解，mn个变量中至多只能有m+n1个变量取正值，而其他的变量为零一、基本概念1）数字格 2）空格 3）闭回路结论1： 运输问题的一个可行解是基可行解的充要条件是：1）数字格的个数为m+n-1个2） m+n-1个数字格不构成闭回路（从数字格出发）结论2： 对每一个空格处，有且仅有一条闭回路。例：判断下表给出的调运方案能否作为表上作业法求解时的初始解B1B2B3B4产量A101515A2151025A355需求量5151510二、表上作业法（1）初始方案的确定：最小元素法；伏格尔法（2）最优性检验：闭回路法；位势法（3）闭回路内改进方案(1.1)最小元素法(就近供应)就进供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为