最短路问题，求解法或代码-中国学网-中国IT综合门户网站
> 最短路问题，求解法或代码
最短路问题，求解法或代码
转载 编辑：李强
为了帮助网友解决“最短路问题，求解法或代码”相关的问题，中国学网通过互联网对“最短路问题，求解法或代码”相关的解决方案进行了整理,用户详细问题包括:则将两台设备分别用于1-3，每台设备可作用于一条网线，使网线上传输信息用时减半，0表示它们之间没有网线连接。多台设备可用于同一条网线;4。如何合理使用这些设备;8;=50)台计算机组成，即用两台设备。注意输入数据中。计算机1与计算机5之间传输信息需要42秒。输出描述输出计算机1与计算机n之间传输信息的最短时间，3-5的线路，用三台设备，使计算机1到计算机n传输用时最少，用时为原来的1&#47。输入描述第一行先输入n，边代表网线。(保留两位小数)样例输入5 20 34 24 0 034 0 10 12 024 10 0 16 200 12 16 0 300 0 20 30 0样例输出22。校方请你编程解决这个问题。例如图5。现学校购买了m(1&lt，传输用时可减少为22秒，这是最佳解;=n&lt。其中顶点代表每一部计算机。以下n行。第i行第j列的数为计算机i与计算机j之间网线的传输用时，从计算机1到计算机n至少有一条网路校园网是由n(1&=10)台加速设备，每行有n个实数。不同网线的传输能力不尽相同，其效果叠加，用时为原来的1&#47，途径为机1到机3到机5，如计算机1与计算机2之间传输信息需要32秒,m，，这个问题急需解决，而计算机2与计算机3之间的传输信息只要10秒，若m=2;=m&lt，具体解决方案如下：解决方案1：你应该去搜索一本 线性规划 的书 里面有最短路径的解法这样人脑算只能算非常少节点的网络通过对数据库的索引,我们还为您准备了：答：#include #define N 1000 int R[10][10]; void Print(int n,int m) { int t=R[n][m]; if(t==0) printf("-&%d ",m); else { Print(n,t); Print(t,m); } } int main() { double a[10][10],d[10][10]; int i,j,k; for(i=1;i===========================================问：#include&stdio.h& #define N 100 #define M 10000 int shortest_way(in...答：代码太长，一般人都不想看。 do { if(p[m][i]===========================================问：【问题描述】 一些公司在全世界建立了许多站点，但每个公司只有自己在某...答：Graph问题，用boost的图库解决。===========================================问：设平面上一共有N个整数点(xi,yi)(0& =i& N),现在从中任选出M(M& =N)个点...答：给你matlab的程序行不？呵呵 这个只要看懂算法就可以自己来的 #include void main() { int infinity=100,j,i,n,k,t,**w,*s,*p,*d; cout===========================================问：设平面上一共有N个整数点(xi,yi)(0& =i& N),现在从中任选出M(M& =N)个点...答：貌似运筹学专门有一章就是求最短路的 ，这个用狄克斯拉标号法（D氏标号），比较好用，这个算法在管道路径选择，物流调度，设备更新，很实用的。。不过运算量都挺大的，建议搜索下相关内容，认真看书把原理能透吧。。===========================================问：任意两点的最短路，就是这个图答：你写的完整的是什么 你的问题是什么 加上这些语句怎么了===========================================问：任意两点的最短路，就是这个图答：从下往上，用贪婪算法===========================================问：伪代码 creat H[(n-1) c+1] ; //H是集合群， H[i】表示第i个集合 d(j)=∞...答：/* * File: shortest.c * Description: 网络中两点最短路径 Dijkstra 算法 * Shortest Path Dijkstra Algorithm * Created:
* Author: Justin Hou [mailto:justin_] */ #include #define true 1 #define false 0 #def...=========================================== % Dijkstra's Shortest Path % % final = dijkstra( A, x, y ) % % Description: returns the shortest path from x to y given adjacency % matrix A. Utilizes Dijkstra's shortest path algor...===========================================分支限界法类似于回溯法。它们的求解目标不同。回溯法的目标是:找到解空间树中的满足约束条件的所有解。分支限界法的目标是:找到解空间树中的满足约束条件的一个解。...=========================================== 呵呵,确实是这样过的啊===========================================但是对以后的耗散度的评估是麻烦的,D算法就是把当前有的路的最短的作为,以后耗散度... 采用优先队列式分支定界算法解决具体问题时,应根据问题的特点选用最大优先或最小优...===========================================用最原始的方法,先规划出来,再将其画出流程图,最后用代码实现,这是最现实的方法!===========================================文件的第二行是字符串B。 Output 程序运行结束时,将编辑距离d(A,B)输出。 Sample Input fxpimu xwrs Sample Output 5 请给出完整的代码===========================================在无向完全图中,对于任意两个顶点vi和vj,我们可以在多项式时间内找到vi和vj这两个顶点之间的所有路径,选择其中路程最短的一条,令S[i,j]表示vi和vj这两个顶点之间最短距离的那...=========================================== sets: cities/S,A1,A2,A3,B1,B2,C1,C2,T/; roads(cities,cities)/S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C...===========================================去年学通信网时候学了D算法。 D算法(Dijkstra算法)是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终...=========================================== 1. dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2. 按dij算法求求看。2.这句话还没找到反例...不过教floyd时说是用在非负权...===========================================
本文欢迎转载，转载请注明：转载自中国学网： []
用户还关注
可能有帮助运筹学讲义
运筹学 Operational Research “夫运筹于帷幄之中， 决胜于千里之外” 运筹学简史 战国时代：齐王与田忌赛马的故事 1736年欧拉——哥尼斯堡七桥问题 1915年哈里斯——经济订货批量公式 1917年爱尔朗（A.K.Erlang）自动拨号设备对电话需求影响的实验（排队论） 起源于军事活动  问题：合理利用稀缺战争资源保护自己、消灭敌人  学科产生：第二次世界大战20世纪40年代 布莱克特（P.M.S.Blackett） “OR”小组  扩展：战后用于民用事业  成型：各个分支成熟  成熟：计算机、信息技术结合  发展： 60，70年代 ,学科结合渗透、 应用广度和深度、方法和算法的完善 运筹学在工商管理中的应用 Management Science 生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。 库存管理：多种物资库存量的管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。 人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。 财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其他： 设备维修、更新，项目选择、评价，工程优化设计与管理等。 运筹学定义 “为决策机构在对其控制下的业务活动，提供以数量化为基础的科学方法。” “运筹学是应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。” “运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏。” 一般来说，运筹学的研究对象是各种有组织的系统（主要是经济组织系统）的经营管理问题，运筹学所研究的系统是在一定时空条件下存在的，为人所控制和操纵，有两个以上的行动方案可供选择而需要人们做出决策的系统。 运筹学所研究的问题时能用数量表示与系统各项活动有关而带有运用，筹划，安排，控制和规划等方面的问题。 运筹学的任务就是在现有条件下，根据问题的要求，对有关活动中错综复杂的数量进行分析研究，并归纳为一定的模型，然后运用有关原理和方法求得解决问题的最优途径和方案，以求实现预期目的。 运筹学解决问题的过程 1）提出问题：认清问题。 2）寻求可行方案：建模、求解。 3）确定评估目标及方案的标准或方法、途径。 4）评估各个方案：解的检验、灵敏性分析等。 5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估：考察问题是否得到完满解决。 1）2）3）形成问题；4）5）分析问题：定性分析与定量分析相结合，构成决策。 如何学习运筹学课程 学习运筹学要把重点放在分析、理解有关的概念、思路上。 课程内容：*线性规划 ——单纯形法、对偶理论、灵敏度分析、 运输问题 目标规划 动态规划 图与网络理论 存贮论 决策论 第一章 线性规划与单纯形法原理 § 1. 问题与模型 1.1线性规划数学模型 例1.某工厂生产A、B、C三种产品，每吨利润分别为2000元，3000元，3000元；生产单位产品所需的工时及原材料如表所示。若供应的原材料每天不超过9t，所能利用的劳动力日总工时为3个单位，问如何制定日生产计划，使三种产品总利润最大？ 问题：工时和材料的日可供量已知，求使利润最大的生产方案 利润最大 工时约束，材料约束，非负约束 例2. 设有A1，A2两个砖厂，产量分别为23万块和27万块砖，供应三个工地B1，B2，B3，其需求量分别为17万块、18万块和15万块，而自产地到各工地的运价见表，问应如何调运，才能使总运费最小？ 解] 设xij Ai运往Bj的运量（万块） minS=50x11+60x12+70x13+60x21+110x22+160x23 1.1.线性规划数学模型 定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。 一般形式：max（或min） 称为决策变量 称为价值系数或目标函数系数 称为资源常数或约束右端常数 称为技术系数或约束系数 紧缩形式：max（或min） i=1,2,…..,n 矩阵形式：max（或min） 称为价值系数向量或目标函数系数向量 称为决策变量向量 称为资源常数向量或约束右端常数向量 称为技术系数或约束系数矩阵 线性规划模型特点： ① 用一组未知变量（决策变量）表示要求的方案。通常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束。 ② 存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组线性等式或者线性不等式来表示 ③ 有一个目标要求，并且可以表示为决策变量的线性函数，称为目标函数，按所研究问题的不同，要求目标函数实现最大化或者最小化。 例 3 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）第一化工厂每天排放污水2万m3，第二化工厂每天排放污水 1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？ Min z=x2 (2-x1)/500 ≤0.002 [0.8(2-x1)+1.4-x2]/700≤0.002 x1≤2, x2≤1.4 x1, x2≥0 例4.某厂在今后四个月内需租用仓库堆存物资。已知每个月所需的仓库面积数字列于表： 月份 1 2 3 4 所需仓库面积（百米2） 15 10 20 12 仓库租借费用，当租借合同期限越长时，享受的折扣优待越大，具体数字见下表: 合同租借期限 1个月 2个月 3个月 4个月 合同期内每百米2仓库 00 7300 面积的租借费用（元) 租借仓库的合同每月都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需求在任何一个月初办理租借合同，且每次办理时，可签一份，也可同时签若干份租用面积和租借期限不同的合同，总的目标是使所付的租借费用最小 [解]设xij 为第i个月初签订的租借期限为j个月的合同租借面积（i=1,2,3,4;j=1,2,…4-i+1） min S=0x12 +00x14 +00x22 +00x31 +00x41 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 xij≥0 (i=1,2,3,4; j=1,2, …4-i+1) 例5．(合理下料问题) 现要做100套钢架，每套用长为2.9m,2.1m和1.5m的圆钢各一根。已知原料长7.4m。问应如何下料，使用的原材料最省？ [解]每一根原料上截取2.9m,2.1m,1.5m的圆钢各一根，组成一套则原材料省下料头0.9m。若做100套，就有90m料头。若采用套裁，就可以节约原材料。下面有几种方案可供采用 1.2 图解法 用作图的方法确定可行域，判断目标函数的大小，达到求解的目的。 适用对象：仅有两个变量的LP问题 步骤：1建立平面坐标系 2图解约束条件和非负条件 3做目标函数等值线 4平移目标函数等值线 5联立求解相应约束条件 1.2 图解法 最优解 无最优解 唯一最优解 无穷多个最优解 没有有限最优解 猜想1 线性规划的可行域是凸集； 猜想2 最优解若存在，则可以在可行域的顶点上得到； 猜想3 可行域的顶点的个数是有限的； 猜想4 若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个 1.3线性规划标准形式 化一般问题为标准形式： (一)若ak1x1+ak2x2+…aknxn≤bk 加一变量xn+k≥0（松驰变量），改写为 ak1x1+ak2x2+…aknxn+xn+k=bk 若ak1x1+ak2x2+…aknxn≥bk 减一变量xn+k≥0(剩余变量），改写为 ak1x1+ak2x2+…aknxn-xn+k=bk (二) 若目标函数为minΖ=c1x1+c2x2+…+cnxn max Ζ’=-Ζ=-( c1x1+c2x2+…+cnxn) (三）若xj&0，令xj=xj’-xj”,xj’≥0,xj”≥0 (四) 若bi&0,则在约束式的两边乘以-1，使得bi&0 例1：将以下线性规划问题转化为标准形式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 0 解：首先，将目标函数转换成极大化： 令 z = -f = 3x1–5x2–8x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x6 ,x7 ≥0 ；由于x2无非负限制，可令x2=x2’-x2”,其中x2’≥0，x2”≥0 ；由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 标准型的主要特征：① 目标最大；② 约束等式；③ 变量非负；④ 右端非负。 标准型的紧缩形式： 标准型的矩阵形式： 标准型的向量形式： 其中： 1.4线性规划问题解的概念 可行解：满足约束条件的解 最优解：使目标函数达到最大的可行解 基:若B是A中m*m阶非奇异子矩阵，(|B|≠0)，则称B是一个基，相应于B的变量称为基变量。 B被称为一个基，是由于B由m个线性无关列组成，这m个线性无关的列向量可以作为一个基。 基本解：令非基变量取零，则得唯一解，称为基本解。 基本可行解：所有变量非负的基本解。 可行基：对应于基可行解的基。 例. Min Z=2X1+X2 s.t. x1+x2+x3 =5 -x1+x2 +x4 =0 1 1 1 0 0 1 0 0 6x1+2x2 +x5=21 A = -1 1 0 1 0 p3= 0 p4= 1 p5= 0 xj≥0,j=1,2, …5 6 2 0 0 1 0 0 1 因此{P3,P4,P5}是一个基，对应的x3,x4,x5为基变量 例. Min Z=2X1+X2 s.t. x1+x2+x3 =5 -x1+X2 +X4 =0 6X1+2X2 +X5=21 Xj≥0,j=1,2, …5 令X1=X2=0,则得X3=5,X4=0,X5=21,X0=(0,0,5,0,21)T是对应于基B= {P3,P4,P5}= 的一个基本解。因Xi≥0, ∴X0为基本可行解。 令X4=X5=0,得 X1=21/8,X2=21/8,X3=-2/8 则X’=(21/8,21/8,-2/8,0,0)T也是基本解，但其不是可行解。 又向量P1，P2，P3线性无关，其为一基，X2，X3，X5为对应的基变量，令X1=X4=0，则X2=0，X3=5，X5 =21，所以X2=（0，0，5，0，21）T也是一基本可行解。 下面讨论线性规划标准形式的基、基本解、基本可行解的概念。 考虑线性规划标准形式的约束条件： AX=b，X≥0 其中A为m×n的矩阵，n&m，秩(A) = m，b  Rm 。在约束等式中，令n维空间的解向量： X = (X1，X2，…，Xn)T 中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量X就对应于n维空间中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。 根据以上分析，我们建立以下概念： （1）线性规划的基：对于线性规划的约束条件 AX=b， X≥0 设B是A矩阵中的一个非奇异（可逆）的m×m子矩阵，则称B为线性规划的一个基。用前文的记号，A=( p1 ，p2 ，…，pn ) ，其中 pj=( a1j ，a2j ，…，amj )T  Rm ，任取A中的m个线性无关列向量 pj  Rm 构成矩阵 B=( pj1 ，pj2 ，…，pjm )。那么B为线性规划的一个基。 我们称对应于基B的变量Xj1 ，Xj2，…，Xjm为基变量；而其他变量称为非基变量。 可以用矩阵来描述这些概念。 设B是线性规划的一个基，则A可以表示为 XB A=[ B , N ] X也可相应地分成X= XN 其中XB为m维列向量，它的各分量称为基变量，与基B的列向量对应；XN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。这时约束等式AX=b可表示为 XB B,N = b XN 或 BXB + NXN = b 如果对非基变量XN取确定的值，则XB有唯一的值与之对应 XB = B-1b - B-1NXN 特别，当取XN = 0，这时有XB=B-1b。关于这类特别的解，有以下概念。 （2）线性规划问题的基本解、基本可行解和可行基： 对于线性规划问题，设矩阵B = ( pj1，pj2，…，pjm ) 为一个基，令所有非基变量为零，可以得到m个关于基变量Xj1 ，Xj2 ，…，Xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。 矩阵描述为，对于线性规划的解 XB B-1b X= = 称为线性规划与基B对应的基本解。若其中B-1b0，则称以 XN 0 上的基本解为一基本可行解，相应的基B称为可行基。 我们可以证明以下结论：线性规划的基本可行解就是可行域的极点。 这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。 例: 考虑线性规划模型 MaX z = 1500 X1 + 2500 X2 Max z=00X2 s.t. 3 X1 + 2 X2 ≤ 65 s.t. 3X1 +2X2 +X3 =65 2 X1 + X2 ≤ 40 2X1 +X2 + X4 =40 3 X2 ≤75 3X2 + X5 =75 X1 , X2 ≥ 0 X1 ,X2,X3,X4 ,X5≥ 0 注意，线性规划的基本解、基本可行解（极点）和可行基只与线性规划问题标准形式的约束条件有关。 3 2 1 0 0 A = [P1 ,P2 ,P3 ,P4 ,P5] = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个3×3的子矩阵： B1=[p1 ，p2 ，p3] B2=[p1 ，p2 ，p4] B3=[p1 ，p2 ，p5] B4=[p1 ，p3 ，p4] B5=[p1 ，p3 ，p5] B6=[p1 ，p4 ，p5] B7=[p2 ，p3 ，p4] B8=[p2 ，p3 ，p5] B9=[p2 ，p4 ，p5] B10=[p3 ，p4 ，p5] 其中᧥= 0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。 对于基B3=[p1 ，p2 ，p5]，令非基变量X3 = 0， X4 = 0，在等式约束中令X3 = 0，X4 = 0，解线性方程组： 3 X1 + 2 X2 + 0 X5 = 65 2 X1 + X2 + 0 X5 = 40 0 X1 + 3 X2 + X5 = 75 得到X1 =15，X2 = 10，X5 = 45，对应的基本可行解： X=(X1 ，X2 ，X3 ，X4 ，X5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。类似可得到 X(2) = (5,25,0,5,0)T （对应B2） X(7) = (20,0,5,0,75)T （对应B5） X(8) = (0,25,15,15,0)T （对应B7） X(9) = (0,0,65,40,75)T （对应B10）是基本可行解； 而X(3)= (0,32.5,0,7.5,-22.5)T（对应B9） X(4)= (65/3,0,0,-10/3,75)T （对应B6） X(5)= (7.5,25,-7.5,0,0)T （对应B1） X(6) = (0,40,-15,0,-45)T （对应B8）是基本解。B2 B3 B5 B7 B10都是可行基。 1.4线性规划问题解的概念 这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。 1.5 线性规划问题的几何意义 1.基本概念 凸集：设k为n维欧氏空间的一点集，任取X,Y∈K,若连接X,Y的线段仍属于K,则称K为凸集。即任取α,0&α&1 , αX+(1-α)Y∈K 称K为凸集。 顶点（极点）：设K是凸集，X∈K,若X不能用不同的两点X(1) ∈K,X(2) ∈K的线性组合表示为 X=αX(1)+(1-α)X(2) (0&α&1) 则称X为极点。 2.基本定理 定理1.线性规划问题的可行域为凸集。 定理2.可行域的点X是顶点的充分必要条件为X是基本可行解。 定理3.若可行域有界，最优解可以在极点上达到。 § 2.单纯形法原理 单纯形方法引例 从约束等式中解出基变量,用非基变量表示基变量,代入目标函数,用非基变量表示目标函数 此时目标函数中非基变量的系数称为该变量的检验数，表示为j 判别定理：若对于所有非基变量，检验数均非正（j≤0），则当前基本可行解最优。 方法步骤总结： 1确定（观察法）一个初始基本可行解; 2从约束中解出基变量（用非基变量表示基变量）； 3代入目标消去基变量（用非基变量表示目标函数），得到非基变量Xj的检验数 j。 4判断最优。若 j≤0，当前解最优; 若k &0，则选Xk进基 5用最小比值法确定Xk的最大值θ，使基变量Xl取0值，其它基变量非负, 即Xl出基，若θ不存在, 则Z→∞，没有有限最优解。 重复上述1到5的工作。 2.2单纯形法一般描述 初始基本可行解的确定（观察法） 基 基本可行解 从约束中解出基变量 代入目标消去基变量，得到非基变量xj的检验数s j 判断最优 最优性判别定理：若是对应于B的基本可行解， j是用非基变量表示目标函数的表达式中非基变量Xj的检验数，若对于一切非基变量的角指数j均有j ≤0，则当前基本可行解为最优解。 对于任意可行解X， 对于基本可行解X0， 没有有限最优解的判断 无最优解判别定理：若 是对应于B的基本可行解， 非基变量X k的检验数k &0 , 且对于i=1,2,……,m 均有ai’k ≤0, 则问题没有有限最优解。 改进目标 若k &0,则选Xk进基, 用最小比值法确定Xk的最大值θ, 使基变量Xl取0值，其它基变量非负； 即xl出基，目标改善skθ，换基过程 若θ不存在, 则Z→∞，没有有限最优解。 主元变换Xk进基， Xl出基，解出新的基变量 2.3表格单纯形法 标准型： 表格单纯形法图示 2.4一般问题的处理 2.5单纯形法矩阵描述 单纯形表的矩阵形式 CB XB cj CB CN1 Cs XsT q xj b XBT XN1T CBT XB B-1b B-1B B-1N1 B-1 －Ｚ -CB B-1b CB- CB B-1B CN- CB B-1N1 -CB B-1 在单纯形法中几点注意事项 1、每一步运算只能用矩阵初等行变换； 2、表中第3列(b列)的数总应保持非负（≥0）； 3、当所有检验数均非正（≤0）时，得到最优单纯形表。若直接对目标求最小，要求所有检验数均非负； 4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解； 5.进基变量的选取 若有不止一个变量可以进基时,只取一个 6.最小比值 若有不止一个最小比值时，只能选取其中之一行对应的基变量出基 7.没有有限最优解的情况 8.关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量XBi=0 (i=1,2,…,m)，则称此基本可行解是退化的基本可行解。 可能出现以下情况：① 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。② 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。 在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”， 这些方法都比较复杂，同时也降低了迭代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定： ① 在选择进基变量时，在所有 j & 0的非基变量中选取下标最小的进基； ② 当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。 这样就可以避免出现循环,当然，这样可能使收敛速度降低。 § 3.线性规划应用 线性规划建模 ①设立决策变量； ②明确约束条件并用变量的线性等式或不等式表示； ③用变量的线性函数表示目标，并确定是求极小还是极大； ④根据变量的物理性质研究变量是否有非负性 有时根本无法用变量的线性函数来描述目标函数或约束条件，在这种情况下，可以尝试增加一些变量或重新设定变量 用若干种原材料（资源）生产某几种产品，原材料（或某种资源）供应有一定的限制，要求制定一个产品生产计划，使其在给定资源限制条件下能得到最大收益。 解 设生产产品Aj的数量为Xj 例1A，B两种产品，两道工序 产品 工序一 工序二 A 加工2小时 加工3小时 B 加工3小时 加工4小时 可利用工时 15 25 每生产一吨B，可得到两吨产品C A每吨盈利400元， B每吨盈利800元 销售一吨C盈利300元 报废每吨C损失200元 市场预测，C最大销量为5吨 决定A，B的产量，使工厂总的盈利最大。 例1 设A，B产品的生产量分别为X1和X2，C产品销量X3 ,报废量X4 利润总值　 Z=400x1 +800x2 +300x3 -200x4 工序1工时　　　 2X1＋ 3X2≤15 工序2工时　　　 3X1＋ 4X2≤25 C产品数量 2X2-X3-X4=0 C产品销售量 　 x3 ≤5 非负约束　 x1，x2，x3，x4≥０ 例2 合理下料问题 从给定尺寸的材料中，按需要的尺寸截取给定数量的零件，使残余废料总量最小的问题。 三维（积材）下料问题 长、宽、高 二维（面料）下料问题 长、宽 一维（线材）下料问题 长 合理下料问题 例3用长9米的原料截取 3.1米 200根, 2.5米 100根, 1.7米 300根 方案 1 2 3 4 5 6 7 8 9 3.1米 2 2 1 1 1 0 0 0 0 2.5米 1 0 2 1 0 3 2 1 0 1.7米 0 1 0 2 3 0 2 3 5 废料长 0.3 1.1 0.9 0 0.8 1.5 0.6 1.4 0.5 设用第j种方案下料xj根 任务：2X1 +2X2 +X3 +X4 +X5 =200 　 X1 +2X3 +X4 +3X6 +2X7 +X8 =100 　 X2 +2X4 +3X5 +2X7 +3X8 +5X9 =300 目标：废料最少或用料根数最少 用料根数*9=用料长度+废料长度 废料：Z=0.3X1+1.1X2+0.9X3+0.8X5+1.5X6+0.6X7+1.4X8 +0.5X9 用料：Z`=X1+X2+X3 +X4 +X5+X6+X7+X8+X9 非负约束 Xj≥０ j=1,2 ……,9 例3合理配料问题（饮食问题） 由多种原料制成含有m 种成份的产品，已知产品中所含各种成份的比例要求，并且知道各种原料所含成份的数量，问应如何配料，才能使产品的成本最低。饲料、药品、工业制品等 饮料、食品等 例4 根据对77种食物所含的九种营养素：热量（糖与脂肪）、蛋白质、钙、铁、维生素A、维生素B1、维生素B2、草酸与维生素C的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表 问怎样采购食物才能保证营养要求的前提下花费最省？ 食 物 每天的最低需要量 营养成份 A B C D 维生素A（国际单位） 50
维生B（毫克） 0.6 0.27 0.68 0.3 1 维生素C（毫克） 17.5 7.5 0 30 30 单 价（元） 0.8 0.5 0.9 1.5 设每天购买甲、乙、丙、丁四种食物的数量分别为 x1 ，x2 ，x3 ，x4 总花费最省 应买甲乙丁食品分别约0.72,2.03,0.075单位 物资运输问题：某种物资有m个产地Ai，i=1,2,….,m，产量分别为ai个单位；有n个销地Bj，销量分别为bj个单位，j=1,2,…..n，Ai与Bj之间的单位运价为Cij，问应如何安排运输方案，才能使总运费最少？ 设从产地Ai，运往销地Bj的销量为Xij，则 某地区有两个煤矿A1 A2 ，所产的煤要运往三个城市B1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案 B1 B2 B3 产量 A1 90 70 95 200 A2 80 65 75 230 销量 100 150 180 总运费为Z=32500元 最大流量问题 例5 某油田通过输油管道向港口输送原油，中间有4个泵站，每段管道上的输送能力如图所示，求这个系统的最大输送能力（泵站上没有贮存能力）。 对偶原理 对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。 对称形式的对偶问题 对偶问题的特点 • 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 • 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 • 极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。 一般线性规划问题的对偶问题 对偶问题对应表 原问题（对偶问题） 对偶问题（原问题） 目标函数maxZ 目标函数minZ 约束条件： m个 第i个约束类型为“≤” 第i个约束类型为“≥” 第i个约束类型为“＝” 变量数： m个 第i个变量≥0 第i个变量≤0 第i个变量是自由变量 变量数：n个 第j个变量≥0 第j个变量≤0 第j个变量是自由变量 约束条件右端项 约束条件：n个 第j个约束类型为“≥” 第j个约束类型为“≤” 第j个约束类型为“＝” 约束条件右端项 例 max Ζ=2x1+x2+3x3+x4 s.t. x1+x2+x3+x4≤5 2x1-x2+3x3 =-4 x1 -x3+x4 ≥1 x1≥0,x2,x4无约束,x3 ≤0 其对偶问题为 min ω=5y1+4y2+y3 s.t. y1-2y2+y3 ≥2 y1+y2 =1 y1-3y2-y3 ≤3 y1 +y3 =1 y1≥0，y2无约束， y3 ≤0 对偶问题的基本性质 对称性：对偶问题的对偶问题是原问题。 定理1.弱对偶定理：若互为对偶的线性规划分别有可行解 ， 则其相应的目标函数值满足 推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。 推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。 推论3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。 定理2 最优性准则定理：若X和Y分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解. 证明：由弱对偶定理可知，对任意可行解有，CX≤Yb 因此对于X和Y也将分别有 CX≤Yb CX≤Yb 又因为 CX=Yb 故有 Yb ≤Yb CX≤CX 定理3 （主对偶定理）若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。 证明：由两者均有可行解，则根据弱对偶定理可知两者均有界，因此均有最优解。 7.原问题单纯形表的检验数行对应其对偶问题的一个基解. 其对应关系见表： XB XN XS 0 CN-CBB-1N -CBB-1 YS1 –YS2 -Y YS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。 影子价格 —— 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若X*,y* 分别为（LP）和（DP）的最优解， 那么， cT X* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+L+bmym* 可知 &f / &bi = yi* yi* 表示 bi 变化1个单位对目标 f 产生的影响. 称 yi* 为 bi的影子价格。 当B是原问题的最优基时，Y=CBB-1就是影子价格向量。 影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价，企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。 影子价格举例 从原始问题最优表求影子价格 影子价格举例 对偶单纯形法 对偶单纯形法的基本思想：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发； 然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行。 当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 在生产计划问题的一般形式中， A代表企业的技术状况， b代表企业的资源状况， C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 价值系数C的改变 资源数量b变化的分析 增加一个变量 灵敏度分析 讨论题 试用灵敏度分析的方法判断 1.目标函数 或 分别在什么范围内变化，上述最优解不变； 2.约束条件右端项 ， 当一个不变时，另一个在什么范围内变化上述最优基不变； 3.问题的目标函数变为 上述最优解的变化； 4.约束条件右端项 变为 时上述最优解的变化 第三章 运输问题  运输问题与有关概念  运输问题的求解—表上作业法  运输问题应用—建模 问题的提出：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 150 150 200 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量 Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij≥0(i=1,2；j=1,2,3） 系数矩阵 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 模型系数矩阵特征： 1.共有m+n行，分别表示各产地和销地；m列，分别表示各变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。 一般运输问题的线性规划模型及求解思路 一般运输问题的提法： A1, A2,…,Am表示某物资的m个产地；B1,B2,…,Bn 表示某物资的n个销地； si 表示产地 Ai 的产量；dj 表示销地 Bj 的销量； cij 表示把物资为从产地 Ai 运往销地 Bj 的单位运价。 如果s1 + s2 + … + sm = d1 + d2 + … + dn ，则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论产销平衡问题。 表1 运输问题数据表 表2 运输问题变量表 一般运输问题的模型： m n Min f = & & cij xij （1） i=1 j=1 n s.t. & xij &si i = 1,2,…,m （2） j=1 m &xij & dj j = 1,2,…,n （3） i=1 xij≥0(i=1,2,…,m;j=1,2,…,n)（4） 在模型（1）—（4）中，式（2）为 m 个产地的产量约束；式（3）为 n 个销地的销量约束。 在产销平衡问题中，约束条件成为等式。 在实际问题建模时，还会出现如下一些变化： （1）有时目标函数求最大，如求利润最大或营业额最大等； （2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； (3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（3）每一式中加上 1 个松弛变量，共 n 个。 运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。在这里需要讨论基本可行解、检验数以基的转换等问题。 产销平衡的运输问题 约束方程系数矩阵结构 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 重要概念: 闭回路、闭回路的顶点 其中，i1i2,….,is互不相同，j1j2,….,js互不相同）上述形式的变量的集合称为一个闭回路 。 其中的变量称为闭回路的顶点，闭回路的特点：封闭、每行每列至多两个顶点。 闭回路的一些明显特点： (1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； (2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。 基变量的构成 对于闭回路 其对应的列向量 线性相关 若变量组中有一部分构成闭回路，则变量组线性相关。 孤立点是其所在行和所在列中包含在该变量组中的唯一向量。 定理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。 推论：m+n-1个变量构成基变量的充要条件是不含闭回路。 运输问题求解—表上作业法 初始基本可行解的确定 ①在供需表中任选一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置； ②调整Ai的拥有量及Bj的需求量，分别减去xij ，得到调整后的拥有量ai和需求量bj ； ③若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）； ④若平衡表中所有的行或列均被划去，则结束。 否则，在剩下的平衡表中选下一个变量，转② 按照上述方法所产生的一组变量的取值将满足下面条件： a．所得的变量均为非负，且变量总数恰好为m+n-1个； b．所有的约束条件均得到满足； c．所得的变量不构成闭回路。 因此所得的解一定是运输问题的基本可行解。 在上面的方法中： xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法 西北角法：若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法） 最小费用法：若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。 基本可行解的最优性检验 最优性检验就是检查所得到的方案是不是最优方案。 检查的方法与单纯形方法中的原理相同，即计算检验数。 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。 以非基变量 x22 为起始顶点的闭回路 以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 – 2 + 3 – 10 + 5 – 4 ＝ 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。 当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。 这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。也称这个综合影响为该非基变量对应的检验数。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。 可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。 如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点……，那么就有 sij = (闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和) 其中 ij 为非基变量的下角指标。 显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。 最优性检验：位势法 其原理是利用约束条件的特殊性来找到非基变量的检验数。 从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。这一过程若用消元的方法加以实现，则会产生位势法。 若所有非基变量检验数≥0，则最优。 调整流量 调运量的调整步骤： ①闭回路上的奇数次顶点的调运量减去θ； ②闭回路上的偶数次顶点（包括起始变量）的调运量加上θ； ③非闭回路顶点的其他变量调运量不变； ④奇数点上被修改为0的变量为出基变量，在新的方案中不再标出其值。但若有两个为零的变量，则只取其一作为出基变量 表上作业法计算中的问题  无穷多最优解  退化 产大于销的运输问题 销大于产的运输问题 运输问题的应用 例2:设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。 1 2 3 4 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 --- 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 解：根据题意，作出产销平衡与运价表:最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 生产与储存问题 生产能力（台） 单位成本（万元） 一季度 25 10.8 二季度 35 11.1 三季度 30 11.0 四季度 10 11.3 例3:某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。 解： 设 Xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 ≤ 25 x12 + x22 = 15 x22 + x23 + x24 ≤ 35 x13 + x23 + x33 = 25 x33 + x34 ≤ 30 x14 + x24 + x34 + x44 = 20 x44 ≤ 10 目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题： 第一季度 第二季度 第三季度 第四季度 D 产量 第一季度 10.80 10.95 11.10 11.2 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 销量 10 15 25 20 30 三、转运问题:原运输问题上增加若干转运站。运输方式有：产地 & 转运站、转运站 & 销地、产地 & 产地、产地 & 销地、销地 & 转运站、销地 & 产地等。 例5:腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产450台,广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？ 图中 1—广州、2—大连、3—上海、4—天津 5—南京、6—济南、7—南昌、8—青岛 解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件：对产地（发点） i ：输入量 - 输出量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量 目标函数： Min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+ 5x48 约束条件： s.t. x13+x14 ≤ 600 (广州分厂供应量限制） x23+x24+x28 ≤ 450 (大连分厂供应量限制） -x13-x23+x35+x36+x37+x38 = 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 150 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （南京的销量） xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8 用“管理运筹学”软件求得结果： x13 = 550,x14 = 0 x23 = 0,x24 = 150,x28 = 300 x35 = 200,x36 = 0,x37 = 350,x38 = 0 x45 = 0,x46 = 150,x47 = 0,x48 = 0 试求总费用为最少的调运方案。 假设： 1、每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运； 2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。 第四章 目标规划 Goal Programming §1.目标规划的数学模型 目标规划是在线性规划的基础上适应各种复杂的多目标最优决策的需要而逐步的发展起来的。它对众多的目标分别确定一个希望实现的目标值，然后按目标的重要级别依次进行考虑与计算，以求得最接近实现各个目标预定的数值方案。 如果某些目标由于种种原因而不能完全实现，它也能指出目标值不能实现的程度和原因。 例1 某工厂生产A,B两种产品确定获利最大的生产方案。 A B 拥有量 原材料 设备 2 1 1 2 11 10 利润元/件 8 10 这是一个单目标规划问题，用线性规划表示如下 最优方案为 实际上工厂在作决策时要考虑到市场等一系列其他条件。 （1）根据市场信息产品A销量有下降的趋势，故考虑产品A的产量不大于B。 （2）超过计划供应的原材料时，需要高价采购，这就使成本增加，所以原材料有严格限制。 （3）应该尽可能的充分利用设备台时，但尽量不加班。 （4）应尽可能达到并超过计划利润指标56元。 决策者在原材料供应受严格限制的基础上考虑： p1产品B的产量不应低于产品A的产量； p2充分利用设备有效台时，不宜加班； p3利润额不应小于56元。 目标规划数学模型的有关概念 1.决策变量与正负偏差变量di+,di & (i=1,…,m) 对每个目标函数引入正负偏差变量di+,di &, di+,di & ≥0 (i = 1, 2,…,m)， di+表示第i个目标超出期望值的数值, di &表示第i个目标未达到期望值的数值 di+×di & =0 2.绝对约束和目标约束 绝对约束 ：必须严格满足的等式和不等式约束. a11x1+a12x2≤b1 ——硬约束 目标约束：把约束右端看作要追求的目标，有正负偏差的约束. —软约束 3.优先因子(优先等级)与权系数 优先因子：目标的重要程度. 首先达到的目标赋予优先因子P1，次位的目标赋于优先因子P2,…,并规定 Pk&&Pk+1 k=1,…,K， 权系数：相同的优先级，各目标的重要程度 4.目标函数（达成函数） 目标接近期望值, 构造一个新的目标函数，以求得有关偏差变量的最小值。Min z= f (di+，di &) 目标函数表达形式 在达成函数中，根据对各个目标的不同要求，一般采用三种形式: (1).若要求尽可能地实现某个目标(第i个目标)的期望值，则希望相应的正、负偏差变量di+,di-尽可能地小。Min z=f (di++di &) (2).若某个目标允许超过期望值，但希望尽可能不低于期望值。Min z=f (di & ) (3).若某个目标允许低于期望值，但尽量不超过期望值。Min z=f (di+ ) §1.目标规划的数学模型 例 某电子公司录音机和收音机两种产品，它们均需经过两个工厂的加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验2.5小时才变成成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验1.5小时才变为成品。 录音机与收音机每台厂内的每月储存成本分别为8元和15元。第一个工厂有12台制造机器，每台每天工作8小时，每月正常工作天数为25天； 第二个工厂有7台装配试验设备，每台每天工作时间16小时，每月正常工作天数仍为25天。每台机器每小时运转成本，第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润20元，收音机为23元，依市场预测次月的录音机与收音机的销售量估计分别为1,500台和1,000台。 录音机 收音机 加工 2小时 4小时 装配试验 2.5小时 1.5小时 利润 20元/台 23元/台 预计销量 1,500台 1,000台 月储存成本 8元 15元 第一工厂 第二工厂 设备 12台 7台 工作时数/台天 8小时 16小时 工作天数/月 25天 25天 运转成本/台 18元 15元 该公司依下列次序为目标的优先次序，以实现次月的生产与销售目标。 P1 厂内的储存成本不宜超过23,000元； P2 录音机销售量应完成1,500台； P3 第一，二两工厂的设备应全力运转,避免有空闲时间，两厂的单位运转成本当作它们间的权系数。 P4 第一个工厂的超时作业时间全月份不宜超出30小时； P5 收音机销售量应完成1,000台 P6 两个工厂的超时工作时间总和应予限制，其限制的比率依各厂每小时运转成本核算为准。 试建立这个问题的数学模型。 [解] 设x1,x2分别表示下月份录音机与收音机的生产量。 di+,di &为相应目标与约束的正、负偏差变量。i=1,… 1.第一、二两工厂设备运转时间约束 第一个工厂设备的总工作时间为8&12&25=2400小时 第二个工厂装配试验设备总工作时间为16&7&25=2800小时 2x1+4x2+ d1 & -d1+=2400 2.5x1+1.5x2+d2 & -d2+=2800 2.厂内储存成本约束 8x1+15x2+d3 & -d3+=23000 3.销售目标约束 x1 +d4 & -d4+=1500 x2 +d5 & -d5+=1000 4.第一个工厂的超过作业时间约束 d1++d11 & -d11+=30 5.达成函数 min Ζ=P1d3++P2d4-+P3(6d1 & +5d2 &) +P4d11++P5d5-+ P6(6d1+ +5d2+) 达成函数中P3与P6级目标的权系数是取第一、第二两工厂设备每小时运转成本的比率18:15=6:5。 这个问题的目标规划模型为： min Ζ=P1d3++P2d4 & +P3(6d1 & +5d2 &) +P4d11++P5d5++P6(6d1++5d2+) s.t 2x1+4x2+d1 & -d1+=2400 2.5x1+1.5x2+d2 & -d2+=2800 8x1+15x2+d3 & -d3+=23000 x1 +d4 & -d4+=1500 x2 +d5 & -d5+=1000 d1++d11 & -d11+=30 x1,x2≥0,di &,di+≥0 (i=1,2,3,4,5,11) 目标规划的一般数学模型为min Ζ=ΣPl[Σ(ωlk+dk++ωlk &dk &)] Σckjxj+dk & -dk+=gk k=1,2,…,k Σaijxj≤(=,≥)bi i=1,2,…,m xj≥0 j=1,2,…,n dk &,dk+≥0 k=1,2,…K 目标规划的图解法 目标规划图解法是在可行域内， 一.寻找一个使P1级别的各目标均满足的区域R1 二.再在R1中寻找一个使P2级别的各目标均满足的区域R2(R1&ER2)三.在R2中寻找一个满足P3级别各目标的区域R3(R1&ER2&ER3 )； 如此下去直到寻找到一个区域Rk，满足Pk级别各目标，这个Pk即为我们的解。称Ri为第i级的解空间。 如果某一个Ri已退化为一点，则计算亦应终止，这一点亦即为最优解，它只能满足P1,P2,…,Pi级目标，而无法进一步改进；以满足Pi+1, Pi+2, …, Pk各级目标。 运筹学第八章 图与网络理论 图的概念 所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。 在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。 顶点数 集合V中元素的个数，记作p(G)。 边数 集合E中元素的个数，记作q(G)。 若e=[u,v]∈E，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联。 例如图中的图G，p(G)=6，q(G)=9，v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。 若点u和v与同一条边相关联，则u和v为相邻点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。 例如在图中v1和v2为相邻点， v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。 若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。 例如图的e8为环，e1，e2为两重边，e4，e5也是两重边。 含有多重边的图称作多重图。 无环也无多重边的图称作简单图。 次 点v作为边的端点的次数，记作d(v)，如图中，d(v1)=5, d(v4)=6等 端点次为奇数的点称作奇点；次为偶数的点称作偶点。 次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边； 次为0的点称为孤立点。 图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。 若图G中所有点都是孤立点，则称图G为空图。 定理1 所有顶点的次的和，等于所有边数的2倍。即 定理2 在任一图中，奇点的个数必为偶数。 设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有 由两两相邻的点及其相关联的边构成的点边序列称为链。 v0称为链的起点， vn称为链的终点。 若v0 ≠vn则称该链为开链，反之称为闭链或回路。 若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。 除起点和终点外点均不相同的闭链，称为初等回路或称为圈。 若一个图G的任意两点之间均至少有一条链连接起来，则称这个图G是一个连通图，否则称作不连通图。 连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。 子图的定义 设， G1=(V1,E1), G2=(V2,E2)，如果V1&IV2 ，又E1&IE2 ，则称G1是G2的子图。 必须指出，并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。 支撑子图 若V1=V2，E1&IE2 ，则称G1为G2的一个支撑子图。 在有些图中，边是没有方向的，即[u,v]=[v,u]，这种图称为无向图。 而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。 从顶点u指向υ的弧a，记作＝a=(u,v),(u,v)≠(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D＝（V，A） 有向图中，在不考虑边的方向时，也可以相同地定义链，若有向图D＝（V，A）中，P是一个从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链P就称为是D中从u到v的一条路。 当路的起点与终点相同，即u=v时，称作一条回路。 顶点全不相同的路称为初等路。 除起点和终点外点均不相同的回路称为初等回路。 一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。 定理 以下关于树的六种不同描述是等价的： ①无圈连通图。 ②无圈，q=p-1。 ③连通，q=p-1。 ④无圈，但若任意增加一条边，则可得到一个且仅一个圈。 ⑤连通，但若任意舍弃一条边，图便不连通。 ⑥每一对顶点之间有一条且仅有一条链。 一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。 若T是图G＝（V，E）的支撑子图，且T是树，则称T为G的支撑树。 定理 图G有支撑树的充分必要条件是图G是连通的。 证明：必要性是显然的。 充分性： 设G是连通的，如果G不含圈，则G本身是一个树，从而是它自身的一个支撑树。 现设G含圈，从圈中任意去掉一条边，得G的一个支撑子图G1，如G1不含圈，则G1是G的一个生成树；如G1含圈，则从G1中任取一圈，从圈中再任意去掉一条边，得G的一个支撑子图G2，如此重复，终可得G的一个不含圈的支撑子图Gk，于是Gk是G的一个支撑树。 （二）避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。(找到支撑树或判定没有支撑树) 图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。 网络 赋权的图 权 程度的度量，数量描述。 若 网络中边( i , j )的权为dij ,则网络的支撑树的权为支撑树的各边的权的和. 如果支撑树T*的权w（T*）是G的所有支撑树的权中最小的，则称T*是G的最小支撑树（简称最小树）。即 最小支撑树问题的一般提法是：选取网络中的支撑子图，使得网络连通，且使总权数最短。 （三） 生长法 方法步骤 ①从图上任选一点υi，令 ②从Sk中的各点到Sk中各点的边中选权数最小的边，设为[υi，υj]，则 ，若这样的边不存在，则原图没有最小支撑树。 ③令 若S=V，则已找到最短树，否则②， 最短路线问题的一般提法是：欲寻找网络中从起点υ1到终点υn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。 给定有向网络D=（V，A，W），任意有向边aij∈A，有权w（ aij ）=wij，给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权（长度）是P中所有有向边的权之和，记为w（P）。最短路问题就是要在所有从vs到vt的路中，求一条路P0 ，使 ，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。 如下事实经常要用到，如果P是从vs到vt最短路，vi是P中一点，那么从vs 沿着P到vi 的路就是从vs 到 vi 的最短路。 根据上述事实，可以逐步比较各段路的长短，从vs 出发逐步向外探寻最短路，从而求得从初始节点vs到其他各点的最短距离及路线。 最短路问题的狄克斯拉Dijkstra算法 算法进行时，给每一个节点一个标号，标号分为T标号和P标号 T标号：为临时标号，表示从 vs到该点的最短路的权的上界。 P标号：为固定标号，表示从 vs到该点的最短距离。 • 算法的每一步是去修改T标号，并且把某一个具有T标号的点改为具有P标号的点，从而使图中具有P标号点的顶点数多一个，直到所有点都具有P标号。 • 给出发点 标上固定标号P(s)=0，其余节点标上临时标号 • 若节点i是刚得到P标号的点，把所有还具有T标号的节点，改为下列T标号 • 把T标号中标号最小的节点m 的临时标号T(m)改为P（m），L(m)记为其前节点，直至算法结束。 最短路径问题 Dijkstra算法仅适合于所有的权wij&=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如图中，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v的最短路是（v1,v3,v2）,权是-1。 福德算法1 适用于有负权，但无负回路的有向或无向网络，其算法步骤如下： 令 计算 ，若对所有j， 则最优，否则把k的值加1，继续计算。 若k=n-1，则说明存在负回路，最短路线不存在。 设备更新问题 某企业使用一台设备，每年年初决定是更新机器还是继续使用旧的，若购新的，就要支付一定购置费，若继续使用旧的，则需要支付一定的维修费用，现在的问题是如何制定一个几年之内的设备更新计划，使得总支付费用最小。 • 此问题可转化为网络的最短路问题来求解 • 可选方案很多 • 若每年购置一台新设备11+11+12+12+13=59\ • 若一，三，五年更新11+12+13=36维修费用5+6+5+6+5=27共63 • 用点vi代表“第i年年初购进一台新设备”的状态。 • 假设一点v6，表示第5年年底。 • 每两点间有一条弧，构成一个赋权有向图。 基本概念 1. 网络与流 给定一个有向网络D=（V，A），在V中指定 一点vs 称为发点，指定另一点vt 称为收点，其余点称中间点。任意有向边(vi ，vj )∈A，有 cij ≥0，称为有向边的容量。称D为一个容量网 络.记为D=（V，A，K）。 流: 定义在边集A上的一个流量函数f={f(vi ,vj )}，边 (vi ,vj )上的流量简记为 fi j . 2. 可行流与最大流 定义2 满足下述条件的流 f 称为可行流: 1)容量限制条件: 对每一边(vi , vj )∈A 0≤fij ≤cij 2)平衡条件: 对中间点vi (i≠s,t ),有 V( f ) 称为可行流 f 的流量,即发点的净输出量。 3. 增广链 对可行流 f ={ fij }： 非饱和弧：fij & cij 饱和弧：fij =cij 非零流弧：fij &0 零流弧：fij =0 链的方向：若&是从vs到vt的一条链，定义链的方向是从vs到vt 。 前向链：有向弧的方向与链的方向一致。 后向链：有向弧的方向与链的方向相反。 定义3 设 f 是一个可行流, & 是从vs 到vt 的一条链,若&满 足下列条件,称之为(关于可行流 f 的)一条增广链。 0≤ fij 0 & fij ≤ cij 后向有向弧是非零流弧， 4. 截集与截量 设S，T&IV，S&CT= F ，始点在S，终点在T中的所有有向弧的集合，记为（S，T）。 定义4 网络D=(V,A,K）,若点集V被剖分为两个非空集合S和S,使vs∈S，vt ∈ S，则把弧集(S，S)称为是分离vs和vt的截集。 定义 把截集（S，S）中所有弧的容量之和称为这个截集的容量（简称为截量），记为C （S，S）， 不难证明，任何一个可行流的流量V( f )都不会超过任一截集的容量。即V(f) ≤ C(S,S) 可行流 f *，截集(S*，S*), 若V( f *)=C( S*，S*）， 则 f *必是最大流， (S*，S*) 必是D的最小截集。 定理1 最大流最小截定理。任一个网络D中，从vs 到vt 的最大流的流量等于分离vs，vt 的最小截集的容量。 定理2 可行流 f *是最大流，当且仅当不存在关于 f *的增广链。 寻求最大流的增广链方法 标号法 （Ford—Fulkerson 从任一个可行流 f 出发（若网络中没有给定 f ，则从零流开始或自己找出一个可行流），经过标号过程与调整过程。 1． 标号过程 在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分： 第一个标号表示这个标号是从那一点得到的。以便找出增广链。 第二个标号是为了用来确定增广链上的调整量θ。 标号过程开始，先给vs标号（0，+∞）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj： （1）如果在弧（vi,vj）上，fij（2）如果在弧（vj,vi）上，fij&0,那么给vj标号（-vi,l(vj)）.其中l(vj)=min[l(vi),cij-fij].这时，vj成为标号未检查点。 于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。 2.调整过程 从vt 开始，反向追踪，找出增广链 &，并在&上进行流量调整。 （1）找增广链 如vt 的标号为k（或-k），则弧（vk，vt）∈&（或弧（vt，vk) ∈&)。检查vk 的标号，若为i（或-i），则(vi,vk) ∈& (或(vk,vi) ∈&)。再检查vi 的标号,依此下去,直到vs 。被找出的有向弧构成了增广链&。 （2）流量调整 令q1=前向弧的容量与流量之差的最小值, q2=后向弧的流量的最小值,则增流量q=min｛ q1 , q2 ｝，构造新的可行流 f ′，或者取调整量θ=l(vt),即vt的第二个标号， 令 去掉所有的标号,对新的可行流 f ′={ fij′},重新进入标号过程。 最小费用最大流问题 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。 设一个网络D=（V1，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij&=0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=∑bijfij达到最小。（Vi,Vj）∈A 在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f’的流量，有v(f’)=v(f)+1，而此时总费用b(f’)比b(f)增加了 b(f’)-b(f)=∑bij(f’ij-fij)- ∑bij(fij-f’ij)= ∑bij-∑bij μ+ μ- μ+ μ- 我们将上式叫做这条增广链的费用。 关于f的所有增广链中的费用最小增广链，那么沿增广链μ调整可行流f，得到的新可行流f’，也是流量为v(f’)的所有可行流中的最小费用流。当f’是最大流时，它就是我们所要求的最小费用最大流 显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。 对此，从新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为： bij,当fij• wij= +∞,当fij=cij -bij,当fij&0 • wij= +∞,当fij=0 • 并且将权为+∞的弧从M(f)中略去。 这样，在网络D中寻找关于f的最小费用增广链就等于价于在M(f)中寻求从vs到vt的最短路。 算法开始，取零流f(0) ={0}.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图M（f(K-1)）。在图M（f(K-1)）中，寻求从vs到vt的最短路。如果存在最短路，则f(K-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链μ0 在增广链μ上对f(K-1)进行调整，取调整量θ=min{min((cij-f(k-1)ij),min(f(k-1)ij)}. μ+ μ- 令 f(k-1)ij+θ，在μ+上 f(k)ij = f(k-1)ij-θ，在μ-上 其他的不变。 得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。 • 例1:求图所示网络中的最小费用最大流，弧旁的权是（bij,cij）.
本词条由以下会员参与贡献
→如果您认为本词条还有待完善，请
词条内容仅供参考，如果您需要解决具体问题（尤其在法律、医学等领域），建议您咨询相关领域专业人士。
暂无同义词
关于本词条的评论 (共0条）