关于最短路问题的一个简明表格处理法

最短路问题(short-path problem)若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径）1、Dijkstra算法：用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度代码：procedure dijkstra（v0：longint）；//v0为起点做一次dijkstrabegin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongintfor i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里visit[v0]:=true;//已经连接v0结点for i:=1 to n-1 do//剩下n-1个节点未加入路径里；beginmin:=maxlongint;//初始化minfor j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小begin min:=d[j];k:=j;end;visit[k]:=true;//连接进去for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值，if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k];end;writeln(d[n]);//结点v0到结点n的最短路。

Microsoft Excel 11.0 运算结果报告工作表 [20103848李园园.xls]Sheet1报告的建立: 2003-1-19 6:23:54目标单元格 (最小值)单元格名字初值终值$E$13V7010可变单元格单元格名字初值终值$D$2V2 路径00$D$3V5 路径01$D$4V7 路径00$D$5V5 路径00$D$6V2 路径00$D$7V6 路径00$D$8V3 路径00$D$9V8 路径00$D$10V6 路径01$D$11V8 路径01$D$12V5 路径00$D$13V7 路径00约束单元格名字单元格值公式状态型数值$G$2V1 网络流1$G$2>=$H$2到达限制值0 $G$3V2 网络流0$G$3=$H$3未到限制值0 $G$4V3 网络流0$G$4=$H$4未到限制值0 $G$5V4 网络流0$G$5=$H$5未到限制值0 $G$6V5 网络流0$G$6=$H$6未到限制值0 $G$7V6 网络流0$G$7=$H$7未到限制值0 $G$8V7 网络流0$G$8=$H$8未到限制值0 $D$2V2 路径0$D$2=二进制到达限制值0 $D$3V5 路径1$D$3=二进制到达限制值0 $D$4V7 路径0$D$4=二进制到达限制值0 $D$5V5 路径0$D$5=二进制到达限制值0 $D$6V2 路径0$D$6=二进制到达限制值0 $D$7V6 路径0$D$7=二进制到达限制值0 $D$8V3 路径0$D$8=二进制到达限制值0 $D$9V8 路径0$D$9=二进制到达限制值0 $D$10V6 路径1$D$10=二进制到达限制值0 $D$11V8 路径1$D$11=二进制到达限制值0 $D$12V5 路径0$D$12=二进制到达限制值0 $D$13V7 路径0$D$13=二进制到达限制值0。

最短路问题何谓最短路？最短路问题考虑的是有向网络N=（V，A，W），其中弧（i,j）∈A 对应的权又称为弧长或费用。

对于其中的两个顶点s，t∈V,以s 为起点，t 为终点的有向路称为s-t 有向路，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）。

所有s-t 有向路中权最小的一条称为s-t 最短路。

ij w 如何得到最短路？最短路问题的线性规划描述如下：(,)m i ni j i j i j A w x ∈∑ (1):(,):(,)1,,..1,,0,,ij ji j i j A j j i A i s s t x x s i s t ∈∈=⎧⎪t −=−=⎨⎪≠⎩∑∑ (2) 0ij x ≥ (3) 其中决策变量表示弧（i,j）是否位于s-t 路上：当=1时，表示弧（i,j）位于s-t 路上，当=0时，表示弧（i,j）不在s-t 路上。

本来，应当是0-1变量，但由于约束（2）的约束矩阵就是网络的关联矩阵，它是全幺模矩阵，因此0-1变量可以松弛为区间[0，1]中的实数（当用单纯形法求解时，将得到0-1整数解）。

ij x ij x ij x ij x 值得注意的是，我们这里将变量直接松弛为所有非负实数。

实际上，如果可以取0-1以外的整数，则约束条件并不能保证对应于非零的弧所构成的结构（记为P）一定是一条路，因为这一结构可能含有圈。

进一步分析，我们总是假设网络本身不含有负圈，而任何正圈不可能使目标函数最小，因此上面的约束条件（2），（3）可以保证当达到最优解时，P 如果包含圈，该圈一定是零圈，我们从P 中去掉所有的零圈，就可以得到最短路。

ij x ij x ij x 无圈网络与正费用网络一般采用标号设定算法。

Bellman 方程（最短路方程）将约束条件（2）两边同时乘以-1，得到其对偶问题为：m ax()t s u u − （4）..,(,)j i ij s t u u w i j A −≤∀∈ （5）根据互补松弛条件，当x 和u 分别为原问题和对偶问题的最优解时：()0,(,i j j i i j )x u u w i j −−=∀∈A （6） 因此,当某弧（i，j）位于最短路上时，即对应的变量＞0时，一定有ij x j i i u u w −=j 。

最短路最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

单源最短路径包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

）算法可以采用Dijkstra 算法。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法代码1#include <string.h>2#include<algorithm>3using namespace std;45const int maxnum = 100;6const int maxint = 99999999;78int dist[maxnum];9int prev[maxnum];//记录当前点的前一个结点10int c[maxnum][maxnum];11int n,line;1213void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum])//v代表源点14{15 bool s[maxnum];//判断是否已存入该点到S中16 for(int i = 1;i <= n;++i)17 {18 dist[i] = c[v][i];19 s[i] = 0;20 if(dist[i] == maxint)//代表当前点与源点没有直接相连21 prev[i] = 0;22 else23 prev[i] = v;//代表当前点的前一个节点是v，即源点24 }25 dist[v] = 0;//源点到源点的距离初始化为026 s[v] = 1;//源点已被遍历过，标记为12728 for(int i = 2;i <= n;++i)29 {30 int tmp = maxint;31 int u = v;32 for(int j = 1;j <= n;++j)33 {34 if((!s[j]) && dist[j] <tmp)//该点没有被遍历到并且源点到j点的距离小于记录的距离35 {36u = j;//记录下这一点37tmp = dist[j];//记录下这一点到源点的距离38 }39 }40 //找到距离最短的点退出循环41 s[u] = 1;//标记该点已经遍历过4243 for(int j = 1;j <= n;++j)44 {45 if((!s[j]) && c[u][j] <maxint)//j没有被遍历过并且从u到j还有这条路径46 {47 int newdist = dist[u] + c[u][j];//新的距离是从源点到u的距离加上从u到的距离48 if(newdist <dist[j])//如果新的距离比原来到j的距离要短49 {50 dist[j] = newdist;//则更新dist数组51 prev[j] = u;//标记j的前一个节点是u52 }53 }54 }55 }56}5758void searchpath(int *prev,int v,int u)//查找从v到u的最短路径59{60 int que[maxnum];//保存路径61 int tot = 1;62 que[tot] = u;//把终点存入路径数组63 tot++;64 int tmp = prev[u];65 while(tmp != v)66 {67 que[tot] = tmp;68 tot++;69tmp = prev[tmp];70 }71 que[tot] = v;72 for(int i = tot;i >= 1;--i)73 {74 if(i != 1)75 printf("%d->",que[i]);76 else77 printf("%d\n",que[i]);78 }79}808182int main()83{84 scanf("%d",&n);//输入结点数85 scanf("%d",&line);//输入路径数目86 int p,q,len;87 for(int i = 1;i <= n;++i)//初始化存储数组88 {89 for(int j = 1;j <= n;++j)90 {91 c[i][j] = maxint;92 }93 }94 for(int i = 1;i <= line;++i)//往存储数组里存放路径95 {96 scanf("%d%d%d",&p,&q,&len);97 if(len <c[p][q])//如果两个点之间有多条路，取路径较短的那一条98 c[p][q] = len;99 c[q][p] = len;//该语句根据实际情况写，用于无向路径中100 }101 for(int i = 1;i <= n;++i)//初始化标记数组102 dist[i] = maxint;//该数组记录从起点到该点的最短路径长度103104105 dijkstra(n,1,dist,prev,c);106 printf("从源点到最后一个顶点的最短路径长度为：%d\n",dist[n]);107 printf("从源点到最后一个顶点的路径为：");108 searchpath(prev,1,n);109}全局最短路求图中所有的最短路径。

最短路径问题的求解最短路径问题是信息学竞赛中常见的一类中等难题，这是一个非常能联系实际的问题，甚至有时一些看似跟最短路径问题无关的问题也可以归结为最短路径问题。

本文就简要分析一下此类问题的算法，以使大家一起探讨一下该类问题，也使没参加信息学竞赛的同学对信息学竞赛有个简单了解。

下面我们以具体例题来看看这类问题的解法：例1、假设A、B、C、D、E各个城市之间旅费如下图所示。

某人想从城市A 出发游览各城市一遍，而所用费用最少。

试编程序输出结果。

解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。

这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。

实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A 出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。

首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下：const dis:array[1..5,1..5] of integer =( ( 0, 7, 3,10,15),( 7, 0, 5,13,12),( 3, 5, 0, 5,10),(10,13, 5, 0,11),(15,12,10,11, 0));以下是几种解法：一、宽度优先搜索宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法。

具体方法是：1、从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；2、再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离；3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离；4、再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其距离；5、到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。

浅谈最短路的数学模型解问题在生产与科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整个过程达到最好的活动效果。

因此，各个阶段的决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。

当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。

这种把一个问题可看作一个前后关联且具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题，而最短路问题是这类问题中的比较典型的一种。

现在我们一起来探讨这类问题的特点和解决方法。

问题1（最小价格的管道铺设方案）如下图用点表示城市，现有共7个城市。

点与点之间的连线表示城市间有道路相连。

连线旁的数字表示道路的长度。

现计划从城市A到城市D铺设一条天然气管道，请设计出最小价格管道铺设方案。

首选我们要明确以下2点：（1）管道长短与成本价格之间有什么关系？显然，管道越短，成本越低。

（2）你能在众多管道路线中找到一条最短的管道路线吗？答案是肯定的。

这是一般人都有的最直接最原始的思路。

我们在这里就是要寻找一个比较简便的方法。

本题的实质就是求从城市A到城市D的一条最短路。

1、建立数学模型：Min{d（xk，xk+1）+f（xk+1）}的含义是：前一个阶段距离加上后一状态变量到终点的最短距离，然后在这些距离和中取最小者，即为所求的最短距离。

其中xk+1=u（xk），即从状态xk出发，采取决策uk到达下一状态xk+1；Sk表示从状态xk 出发的所有可能选取的决策的集合；而f4（x4）=0称为边界条件，因为状态x4=D已经是终点；各个决策路径xk+1=u（xk）都是所有决策的集合Sk中的一种，即xk+1=u（xk）∈Sk。

2、模型求解：①从最后一个阶段即第三阶段开始，按f3的定义有②第二个阶段有2个状态，而每个状态又有3个决策可选取，因此有B1到D的最短路长得B1到D的最短路径B2到D的最短路长得B2到D的最短路径③当k=1时，有A到D的最短路长得A到D的最短路径，故从A到D的最短弧长为6，路径为最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它优化问题。

例题：基于office2010求解最短路问题用Excel 求解最短路问题的原理设决策变量为xij ，当xij=1，表示最短路P*通过边<vi,vj>；当xij=0，表示最短路P*不通过边<vi,vj>；最短路P*中，除起点和终点之外，每个点的进出度数和为0，起点为1，终点为- 1。

目标函数为各边权数与对应决策变量xij 的乘积之和的最小值。

步骤：第一步：制作表格，第一行依次输入：从、到、是否走、距离、节点、净流量、空、供应/需求；在相应列输入已知数据（是否走列填0；供应/需求列依次填1,0,0,…，0,0，-1）。

并在到列数据下空一格，输入总距离。

第二步：在净流量列全都输入=SUMIF （从，节点，是否走）-SUMIF （到，节点，是否走），回车，得到净流量列全为0.第三步:在总距离同一行右边单元格Z 内输入=SUMPRODUCT （是否走，距离），回车，得到0.第四步：选中Z ，单击菜单栏中<数据>，选择<规划求解>。

设置规划求解参数。

目标函数为最小值；可变单元格为是否走列；遵守约束为净流量=供应/需求；√使无约束变量为非负数；选择求解方法为单纯线性规划。

第五步：点击求解，并确定。

解：i ）制作表格，第一行依次输入：从、到、是否走、距离、节点、净流量、空、供应/需求；在从列输入V1，V1,V2,V2,V2,V3,V3,V4,V4,V5,V5,V6;到列输入V2，V3，V3，V4，V5，V4，V6，V5，V6，V6，V7，V7；是否走列输入V1V2V3V4V5V6V752 52442 441 630,0,0,0,0,0,0,0,0,0,0,0；距离列输入5,2,2,4,5,2,4,4,4,1,3,6；节点列输入V1，V2，V3，V4，V5，V6，V7；空列输入=，=，=，=，=，=，=；供应/需求列输入1,0，0,0,0,0，-1.如下图：ii）在净流量列单元格内全都输入=SUMIF(A2:A13,E2:E8,C2:C13)-SUMIF(B2:B13,E2:E8,C2:C13)，回车（注意：选择复制粘贴时，切勿使用键盘下键，不然改变单元格内公式，直接按enter键即可），得到净流量列全为0.如下图：iii）在总距离同一行右边单元格Z内输入=SUMPRODUCT(C2:C13,D2:D13)，回车，得到0.如下图：iv）选中Z，单击菜单栏中<数据>，选择<规划求解>，设置规划求解参数。

① 图与网破圈法：任取一个圈，去掉一条权最大的边，直到最小树。

避圈法：选最小权的边，避圈前进，直到最小树。

最短路算法：Dijkstra 法：从V s给定P 标号T 标号λ标号（T 标号变成P 标号λ标号记位置）反向追踪：列表，d 1(V 1,V j )→d k (V 1,V j )=min(ωij +d k (V 1,V i ))据最小权反向追踪网络优化：最小截集最大流：找到最小截集（弧的集合） 标号法：开始，为的标号， 最小费用最大流：邮递员问题：通过消灭奇点，找欧拉回路工期优化：人力，费用，工期优化。

费用率=（最短时刻费用-正常时刻费用）/（正常时刻-最短时刻）② 排队论（保证效劳质量，又减少费用）顾客源→（排队规那么）队列→（效劳规那么）效劳机构→离去 效劳规那么：FCFS ，LCFS ，随机效劳，PRM(顾客抵达)|A(效劳时刻)|1(效劳台数)|∞（容量）|∞（顾客源） N(t)队长N q (t)排队长T(t)顾客停留时刻T q (t)顾客等待时刻 L 平均队长L q 平均等待队长W 平均停留时刻W q 平均等待时刻 R 为系统利用率泊松流(M)：无后效性；平稳性；单个性；P 1(t,t+Δt)=λΔt+o(Δt)； o(Δt)=∑∞2P n (t,t+Δt);E ξ=D ξ=λt （t 时刻n 个顾客的概率） 负指数散布(M)：无经历性(P(T>t+s/t>s)=P(T>t));[0,t)至少抵达一个顾客1-P 0(t ）=1-e -t λ,t>0!)()(K t e t V Ktk λλ-= ,2,1,0=K ⎩⎨⎧<≥-=-0,00,1)(t t e t F tiλξ),2,1( =i 爱尔朗散布(E K )：（相当于泊松流抵达后被k 个效劳台均分顾客形成）(其中，t>0,E(T)=1/μ,Var(T)=1/μ2k ）)!1()()(1>-=--t e k t t f tk μμμK=1为M ，k=∞定长散布D,k ≥30正态散布近似G 表示一样彼此独立的随机散布 Little 公式：（四者知一即可）μ1+=q W W W L λ= q q W L λ= ρ+=q L L∑∞==0n nnP L∑∑∞=∞=+=-=sn n ms n q nP P s n L 0)(效劳率：ρ=λ/μ(λ为抵达μ为效劳)排队系统分析：M|M|1|∞|∞（抵达服从λ泊松进程，效劳服从μ负指数散布）空闲：P 0=1-ρ.有k 个顾客：P k =（1-ρ）ρk .L=（1-ρ）ρM|M|1|N|∞（抵达服从λ泊松进程，效劳服从μ负指数散布）P 0=(1-ρ)/(1-ρ)N+1.P k =(1-ρ)ρk /(1-ρ)N+1. L=（1-ρ）ρ-(N+1)ρN+1/(1-ρ)N+1M|M|1|∞|m （抵达服从λ泊松进程，效劳服从μ负指数散布）P 0=1/∑m 0ρn m!/(m-i)!.P k =m!/(m-k)!/∑m0m!/(m-i)!. L=m-(1-P)/ρM|M|c|∞|∞（抵达服从λ泊松进程，效劳服从μ负指数散布） ρs =λ/μc=ρ/c ，L q =(ρ)C ρs P 0/c!(1-ρs )2.1100)(11!1)(!1--=⎥⎦⎤⎢⎣⎡⋅-⋅+=∑c k c k c k P μλρμλ)(!1)(!100⎪⎪⎩⎪⎪⎨⎧>≤=-c n P c c c n P n P n cn nn ρρM|M|c|N|∞（抵达服从λ泊松进程，效劳服从μ负指数散布）⎪⎪⎩⎪⎪⎨⎧≤≤<≤=-N n c p cc c n p n p c n n nn ! 0 !00ρρ⎪⎪⎩⎪⎪⎨⎧=⎪⎪⎭⎫ ⎝⎛+-+≠⎪⎪⎭⎫ ⎝⎛--+=--=--=+-∑∑1 )1(!! 1 )1(!)1(!11011010c c n c n c c n c c N c c n c N c n c n p ρρρρρρρρ)(∑=-=Ncn n q p c n LM|M|c|∞|m （抵达服从λ泊松进程，效劳服从μ负指数散布） KMC CC M K M C C M C K M K M P ∑∑+-+-•=10)()!(1!)()!(!11!10ρρ⎪⎪⎩⎪⎪⎨⎧≤≤+-≤≤-=-)1(,)(!)!(!)0(,)(!)!(!0nm n c P c c n m m c n P n n m m P nc n n μλμλ其中μλρc m =，∑=m 1nSnP L M|G|1（抵达服从λ泊松进程，效劳服从μ负指数散布）)1(2222ρσλρ-+=q L（抵达服从λ泊松进程，效劳服从μ负指数散布）)1(22ρρρ-+=L（最优效劳率μ）λμλμ-+=ws c c z &&0=μd dz →λλμswc c +=*（最优效劳台数C ）Z(c*)≤z(c*-1)&Z(c*)≤z(c*+1)→)()1(/)1()(**'**c L c L c c c L c L w s --≤≤+- ③ 存储论存储费用，定货费用，生产费用，缺货费用 经济订购批量：不许诺缺货，备货快：C(t)=C 3/t+kR+C 1Rt/2;dC/dt=0→t 0=sqrt(2C 3/C 1R),Q 0=Rt 0. 许诺缺货，备货快:C(t)=C 3/t+C 1(P-R)Tt/2t;dC/dt=0→t 0=sqrt(2C 3P/C 1R(P-R)),Q 0=Rt 0. 许诺缺货，生产需要时刻：C(t,S)=(C 3+S 2C 1/2R+(Rt-S)2C 2/2R)/t;dC/dt=dC/dS=0→t 0=sqrt(2C 3(C 1+ C 2)/C 1R(P-R)),S 0=sqrt(2C 3C 2R/C 1(C 1+C 2)),Q 0=Rt 0.需求随机离散：C(Q)≤C(Q+1)，C(Q)≤C(Q-1)→∑-10Q P(r)≤k/(k+h)≤∑Q0P(r)需求随机持续：E(C(Q))=P ⎰∞Q(r-Q)φ(r)dr+C 1⎰Q0(Q-r)φ(r)dr+kQdE/dQ=0→F(Q)=⎰Q0φ(r)dr=(P-k)/(C 1+P)C 2>P 时，F(Q)=(C 2-k)/(C 1+C 2) （s,S ）型存储策略：➢ 需求为持续的随机变量（货物本钱K/单位，存储费C 1/单位，缺货费C 2/单位，订购费C 3/单位，需求密度φ（r ）,S=I+Q ，其中I 表示原始积存，Q 表示进货数量） C(S)=C 3+KQ++⎰S 0C 1(S-r)φ（r ）dr+⎰∞SC 2(r-S)φ（r ）drC'(S)=0→ ⎰S 0φ（r ）dr=(C 2-K)/(C 1+C 2)查表可得S➢ 需求为离散的随机变量C(S)=C 3+KQ++∑≤Sr C 1(S-r)φ（r ）dr+∑>Sr C 2(r-S)φ（r ）drC(S i+1)≥C(S i )&&C(S i )≤C(S i-1)求得S需求备货时刻都随机离散：（t 时刻内需求量r 随机φt （r ），t 时刻内平均需求为ρt,备货时刻x随机，概率为p(x),存储费C1/单位.年，缺货费C2/单位.时期，订购费C3，年需求D，缓冲存量B）先通过确信性模型求Q=E.O.Q=132CDC,N=QD(每一年订购N次每次订Q0 )L=μρ+B,PL=∑X p(x)FX(L)那么：C(L,B)=(B+Q0/2)C1+PLC2PL.求极值④决策论（单目标决策）➢战略决策(全局性，久远问题)、策略决策(为完成目标而定)、执行决策(执行方案选择)；定量决策、定性决策；确信型决策、风险决策、不确信型决策；单项决策、贯序决策；程序决策(可重复，有章可循)、非程序决策(凭直觉应变)➢面向进程（预决策→决策→决策后）面向结果(确信目标→搜集信息→提出方案→方案选优→决策)➢不确信型决策：⏹悲观主义准那么：maxi minj(aij)⏹乐观主义准那么：maxi minj(aij)⏹等可能准那么：maxi (E(Si))⏹最小机遇准那么：maxi (aik)⏹折中主义准那么：Hi=αa imax+(1-α)a imin。