《第5章通信网中的流量优化》由会员分享，可在线阅读，更多相关《第5章通信网中的流量优化（38页珍藏版）》请在金锄头文库上搜索。
1、通信网理论基础通信网理论基础通信网理论基础通信网理论基础Reference: 1. 通信网理论基础2. 图论与网络流3. 运筹学基础1 1 1 1 引论（通信网概述）引论（通信网概述）引论（通信网概述）引论（通信网概述）2 2 2 2 网内业务分析网内业务分析网内业务分析网内业务分析3 3 3 3 多址接入系统分析多址接入系统分析多址接入系统分析多址接入系统分析4 4 4 4 通信网结构（图论基础）通信网结构（图论基础）通信网结构（图论基础）通信网结构（图论基础）5 5 通信网中的流量优化通信网中的流量优化通信网中的流量优化通信网中的流量优化6 6 通信网的可靠性通信网的可靠性通信网的可靠性通
2、信网的可靠性第第第第5 5章章章章 通信网中的流量优化通信网中的流量优化通信网中的流量优化通信网中的流量优化5.1 流量优化的一般性问题5.2 最大流问题5.3 最佳流问题5.4 线性规划简介（选）1. 1. 线性规划的标准型；线性规划的标准型；2.单纯型解原理和计算步骤；3. 对偶定理；4. 罚款的应用；5. 计算之例5.1 流量优化的一般性问题流量优化的一般性问题1 弧容量 弧容量c(i,j)：在有向图在有向图G(V, E, L)中，对每条弧中，对每条弧(i，j) 赋的非负数值赋的非负数值(或称权值或称权值) C(i，j) 。2 流 流(也称为流型也称为流型, f(i,j)：对图对图G(V
3、,E,L)中每条弧中每条弧 (i，j) 赋一非负权值赋一非负权值 f(i，j)，这个权值就称为该弧的流。，这个权值就称为该弧的流。; Ej)(i, 0,j)f(i,j)c(i,;fst , -fst, ; 0t s,i 0, ,),(),(=是的网络流流入汇点条件为流出中间节点的网流恒条件的网为流出源点称条件t; 流tisfstsifstijfjifjj3 可行流（连续性） 可行流（连续性） (fst)若若fst是网是网G（V,E,c,f）中从节点）中从节点 S 到另一节点到另一节点 t 的一个可行流，则可行流的一个可行流，则可行流 fst必须满足下列的守恒方程，即：必须满足下列的守恒方程，即
4、：5.1 流量优化的一般性问题流量优化的一般性问题例例：考察网：考察网G(V,E,c,f )中各弧的容量和可行流型，并验证它是否满足流的守恒方程。其中中各弧的容量和可行流型，并验证它是否满足流的守恒方程。其中S 是源点，是源点，t 是汇点，是汇点，a,b,d,f 是中间节点。是中间节点。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1解：解：1. 写出各弧容量是：写出各弧容量是：c(s,a)=2, c(a,s)=1, , c(t,a)=1;2. 写出各弧的可行流型：写出各弧的可行流型：f(s,a)=1, f(a,s)=1, , f(t,d)=1;3. 判断各
5、弧的容量是否大于可行流型？ 即 弧判断各弧的容量是否大于可行流型？ 即 弧c(i,j) f(i,j) 0？4. 写出图写出图G 的完备关联矩阵的完备关联矩阵Aa，列出可行流的矩阵守恒方程。，列出可行流的矩阵守恒方程。流量分配（规划）研究的一般问题：流量分配（规划）研究的一般问题：1. 最大流问题。改变可行流最大流问题。改变可行流fij，使端到端总流量，使端到端总流量F最大。最大。2. 最佳流或最小费用流问题：图最佳流或最小费用流问题：图G每条边除了容量每条边除了容量Cij外，还有费用外，还有费用aij，表示单位流所需费用。给定，表示单位流所需费用。给定F，选择路由分配这个流量，即调整，选择路由
6、分配这个流量，即调整fij，使总费用最小。，使总费用最小。5.1 流量优化的一般性问题流量优化的一般性问题min minijijijeEa f=5.2 最大流问题最大流问题一、基本概念一、基本概念1、S-t割割 (记为记为C)设图设图G节点集节点集V=XX，其中点，其中点SX，t X，s-t割是指割是指G 中所有（中所有（X，X ）弧的集合。）弧的集合。2 2、s s- -t t 割容量割容量割容量割容量 = =),(),(),(),(XXyxyxcXXCs-t 割割(X，X)的容量定义为：的容量定义为：),()(minminiiiXXCCC=最小最小s-t 割割Cmin是最小的是最小的s-t
7、 割容量割容量s s- -t t 割例题割例题割例题割例题例例：求下述网：求下述网G 中可能的中可能的 s-t 割和割和 s-t 割容量。割容量。sbat-3,-11,01,04,31,11,12,2注：注：G边赋值（边赋值（容量，流量容量，流量）解解: 1. 若若X1= s，则，则X1=a,b,t，则，则s-t 割割 (X1, X1)=(s, a), (s, b); 4. 若若X4= s, a, b，则，则X4=t，则，则s-t 割割 (X4, X4)= (a, t); 3. 若若X3= s, a，则，则X3=b, t，则，则s-t 割割 (X3, X3) = (s, b), (a, b),
8、 (a, t); 2. 若若X2= s, b，则，则X2=a,t，则，则s-t 割割 (X2, X2)= (s, a); 4、可增流（流增广路径）、可增流（流增广路径）定义定义：在网：在网G(V,E,c,f)中，若节点中，若节点s到到t 的的路径路径为为Pst，沿，沿Pst从节点从节点s 到到t 的所有前向弧的所有前向弧不饱和不饱和，即，即f(i，j)0，称路径，称路径Pst为流为流fst的增广路径。的增广路径。3 3、最大流最小割定理、最大流最小割定理、最大流最小割定理、最大流最小割定理),(maxmaxminiiiXXCfstf= ;. ),(;. )XC(X,;. 0;)X(X, ,0
9、),(饱和弧非饱和弧正弧弧为零弧称所有XXCXXf定义：对于网定义：对于网G中的任意中的任意s-t割割),(XX5. 5. 最大流最大流最大流最大流),(maxXXCf=即性质：性质：当且仅当当且仅当fst不存在增广路径时，流不存在增广路径时，流f 最大最大.例例：已知网：已知网G(V,E,c,f)如下，求节点如下，求节点s 到到t 的最大流。的最大流。Sacbdt2,21,01,12,01,14,31,02,23,13,31,14,4解：解： 若若 X=s,a,b, 则则X=c,d,t，s-t割容量割容量C(X,X)=1+1+4=6;(X,X)的路径有流增广路径。的路径有流增广路径。若若Y=
10、s，则，则Y=a,b,c,d,t,s-t割容量割容量C(Y,Y)=2+2=5;(Y,Y) 路径无流增广路径。节点路径无流增广路径。节点s到到t的最大流的最大流 fmax=5。二、福特二、福特二、福特二、福特- -福克森福克森福克森福克森( (FordFord- -Fulkerson)Fulkerson) ，MM算法算法算法算法(一一)、M算法思想：算法思想：寻找源寻找源宿端流可增广路径，使网络的流量得到增加，直到最大流为止宿端流可增广路径，使网络的流量得到增加，直到最大流为止。算法分。算法分2个过程：个过程：1是是标记过程标记过程，通过标记过程找到一条可增广路径；，通过标记过程找到一条可增广路
11、径；2是是增增广过程广过程，即沿增广路径增加网络流量的过程。标记：，即沿增广路径增加网络流量的过程。标记：(+，x，w)或或(，x，w)表示，其中表示，其中x V，w是标记值。是标记值。 M算法中图算法中图G的节点标记有三种情况：的节点标记有三种情况：1. 未标记节点未标记节点：所有未赋标记的节点所有未赋标记的节点；2. 未检查的标记节点未检查的标记节点：如果节点如果节点 x 已有标记，但其邻接节点已有标记，但其邻接节点y没有完全标记，则没有完全标记，则x称为未检验的标记节点称为未检验的标记节点；3.已检查的标记节点已检查的标记节点：若节点若节点 x 已标记，已标记， x 所有邻接的节点都已标
12、记，则所有邻接的节点都已标记，则x 称为已检验的标记节点称为已检验的标记节点；( (二二二二) )、福特、福特、福特、福特- -福克森算法福克森算法福克森算法福克森算法1 标记过程 标记过程第第1步步：对源节点源节点S标记标记(+, s, )；第第2步步：任选一个未检查的标记节点未检查的标记节点x，对与与x邻接未标记节点邻接未标记节点y：(a).对所有(x, y)E的未标记节点y，若f(x, y)0)0，则对节点y标记（, x, w(y)），其中w(y) = minw(x), f(y, x)；在x的标记 + + 或 - - 上加上圆圈，x就成为已检查的标记节点。第3步：A第3步：A.若目的节点
13、t t 被标记被标记，则转转至算法的增广过程算法的增广过程；B.B.若节点t t 虽然未被标记虽然未被标记，但标记过程不能继续下去，就结束算法；否则，就返回标记过程返回标记过程的第2步第2步。二、福特二、福特二、福特二、福特- -福克森算法福克森算法福克森算法福克森算法 （续）（续）（续）（续）2 增广过程 增广过程第第1步：设节点步：设节点Z = t，转至下面的第，转至下面的第2步；步； (逆向增广逆向增广)第第2步：若步：若Z的标记的标记(+, q, w(t)，或，或( , q, w(t)，将流，将流f(q, z)变成变成f(q, z)+ w(t)；若若Z标记标记( , q, w(t)，或
14、，或(, q, w(t)，将流，将流f(z,q)变成变成f(z,q) w(t)；第；第3步：步：若若 q = s，取消网，取消网G中所有节点的标记，并转至算法标记过程第中所有节点的标记，并转至算法标记过程第1步，进行下一次迭代过程步，进行下一次迭代过程；若若 q s，设，设q = Z，返回增广过程第，返回增广过程第2步。步。(三三)、算法复杂度、算法复杂度在一次迭代中一次迭代中，标记过程需比较比较：(n 1)+(n2)+1=0.5n(n 1)次次;在增广过程的第2步需进行加法/减法运算为：(n-1)次；若网络可增的最大流量为fst，则算法复杂度为O(fstn2)。例例：试用福特-福克森算法求网
15、G(V,E,c,f) 节点S至t的最大流。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+ , S, )(+, S, 1)(+, S, 2)( , a, 1)(+ , d, 1)(+ , d, 1)+1-1+1解：1. 用标记过程寻找第1条流增广路径，先标记S节点， (S, + , )流增广路径为：Sa d t，沿该路径增加1个单位流量。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+ , S, )( , S, 1)(+, S, 2)(+ , b, 2)(+ , b, 1)(+ , d, 2)+1+2+1+2 1+
16、22. 用标记过程寻找第用标记过程寻找第2条流增广路径，先标记条流增广路径，先标记S (S, + , )流增广路径为：Sb d t，增加2个单位流量。流增广路径为：S a b C t，增加1个单位流量。3. 用标记过程寻找第用标记过程寻找第3条流增广路径，先标记条流增广路径，先标记S (S, + , )Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+ , S, )( , S, 1)(+, a, 1)(+, b, 1)(+, b, 1)(+, c, 1)+1+2+1+2 1+2 1+1+1+1Sacbdt2,11,11,12,11,04,11,02,13,
17、03,11,14,1(S, + , )+1+2+1+2 1+2 1+1+1+14. 用标记过程寻找第用标记过程寻找第3条流增广路径，先标记条流增广路径，先标记S (S, + , )由于标记过程不能继续下去，网中再无流增广路径，因此算法中止。最后求得最大流fmaxmax= 5= 5。最小割容量C(s ,t, a, b, c, d ) = 5。MM算法推广算法推广算法推广算法推广1. 1. 无向网和混合网中的最大流无向网和混合网中的最大流无向网和混合网中的最大流无向网和混合网中的最大流在无向图或混合网G中，无向边(x, y)可理解为：C(x, y)=c(y, x)；c(x, y)f(x, y),
18、c(x, y)f(y, x)且f(x, y)f(y, x)=0。求无向网或混合网求无向网或混合网G中最大流的一般过程为：中最大流的一般过程为：1先将混合网先将混合网G( V, E, c, f )中的每条中的每条无向边变换成一对有向边（无向边变换成一对有向边（x, y)和和(y, x)；且；且c(x, y)= c(y, x)= c(x, y)。2为了保证混合网为了保证混合网G(V, E, c, f)的无向边的流量只在一个方向上流动，且满足的无向边的流量只在一个方向上流动，且满足可行流可行流条件，即在有向网条件，即在有向网G(V, E, c, f)中，满足：中，满足：maxf(x, y)，f(y,
19、 x)= f(x, y)，且，且f(x, y) f(y, x) = 0；3应用前面介绍的求最大流方法，求有向网应用前面介绍的求最大流方法，求有向网G的最大流的最大流fmax。4. 应用公式应用公式f(x, y) = max0, f(x, y) f(y, x)，构造原网构造原网G可行流型。可行流型。 例例例例 ：求下列混合网的最大流。：求下列混合网的最大流。：求下列混合网的最大流。：求下列混合网的最大流。解：解：(1) 首先将上图的混合网G变换成有向网G。Sacbdt2,21,01,02,01,14,11,12,23,23,01,04,0(+ , S, )(+, s, 3)(+, b, 3)(+
20、, d, 3)3+33(2) 求出G网的最大流：用福特-福克森算法寻找流增广路径，求出网G的最大流fmx=C(X，X)=C(s，a, b, c, t) = 2+3 = 5；(3) 根据G网求得最大流时各弧的流量，应用公式f (x, y) = max 0,f(x, y) f(y, x)，重新确定原网重新确定原网G中无向边的流量：中无向边的流量：2，02. 2. 节点节点节点节点- -弧限容量网的流弧限容量网的流弧限容量网的流弧限容量网的流 (M(M算法推广）算法推广）算法推广）算法推广）求节点-弧限容量网最大流方法：把节点弧容量网G转化为弧限容量网G，在G中求出最大流，即是G网的最大流。对每个节
21、点和弧有： 可行流存在的条件 ;h(i)f(i,v),i t , (i,v)E;h(t)f(t,v), (t,v)E;求节点-弧限容量的一般过程：1在节点-弧限容量网G(V, E, c, f)中的每一节点每一节点i，对应仅有弧限的容量网G(V, E, C, f)中的两点两点i，i, 其中i，iV；2G网中的弧弧(i, j) E，则对应G中的弧弧(i, j)E；同时，G网中弧容量为：C(i, j)=C(i, j);C(i, i)=h(i), iV；3对弧限网G，用前面介绍的福特-福克森算法求求G网中网中s到到t的最大流的最大流 fmax，这即是网G的最大流。 例例例例 ：考察下述网：考察下述网：
22、考察下述网：考察下述网G(V, E, c, G(V, E, c, f f) )，求其最大流。求其最大流。求其最大流。求其最大流。sabt34123214234解解：(1)将节点将节点-弧限容量网弧限容量网G转换为弧限容量网转换为弧限容量网G，求，求s到到t最大流；最大流；ssaattbb43344211223最后，求出从最后，求出从 s 到到 t 的最大流也为的最大流也为fmax=4。用用Ford-Fulkerson算法找到第算法找到第1条流增广路径：条流增广路径：SSaatt增广增广3单位流；沿单位流；沿SSbb t t增广增广1单位流。单位流。3. 3. 多源多宿最大流问题多源多宿最大流问
23、题多源多宿最大流问题多源多宿最大流问题 (M(M算法推广）算法推广）算法推广）算法推广）虚设虚设总源端总源端Vs和总宿端和总宿端Vt? 将将Vs与网络内所有源端用容量为与网络内所有源端用容量为 的有向边相连接；的有向边相连接；? 将将Vt与网络内所有宿端用容量为与网络内所有宿端用容量为 的有向边相连接；的有向边相连接；上上2步将多源多宿问题转变为单源单宿问题；步将多源多宿问题转变为单源单宿问题；如何如何使用介绍的使用介绍的M算法，求算法，求Vs到到Vt的最大流量方法也就解决了多源多宿总流量最大的问题。的最大流量方法也就解决了多源多宿总流量最大的问题。负价环（负价环（N）算法：）算法：给定网给定
24、网G（V，E），每条边容量），每条边容量Cij和单位流的费用和单位流的费用aij给定，在给定总流量给定，在给定总流量Fst条件下，如何分配流量使费用最小。条件下，如何分配流量使费用最小。5. 3 5. 3 最佳流问题最佳流问题最佳流问题最佳流问题( , )min minijiji jEa f=问题描述：问题描述：对图对图G（V, E, C, f )的每条边的每条边eij赋单位费用函数赋单位费用函数aij，则图，则图G（V, E, c, f, a)，如何寻找满足可行流，如何寻找满足可行流Fst条件的最小费流分配。即条件的最小费流分配。即( , )ijiji jEa f=?如果如果aij为常数，则
25、上述问题为线性规划问题；为常数，则上述问题为线性规划问题；? 如果如果aij为非常数，则上述问题是复杂非线性问题 。为非常数，则上述问题是复杂非线性问题 。负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法1. 基本概念基本概念源源VsVt有有2条路径，存在改变流量分配的可能性。条路径，存在改变流量分配的可能性。?VsV1V2V3Vt ；?VsV1V3Vt ；图图1: G（V，E，C，a）图图1的一组可行流分配，总流量为的一组可行流分配，总流量为Fst= 6，总费用为：，总费用为：2 6+2 1+1 1+6 5+4 6 = 69。图图2: G
26、（V，E，f）负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法1. 基本概念基本概念图中有向边赋值图中有向边赋值容量、费用容量、费用。?前向边：可增加流量前向边：可增加流量=容量容量 已分配流；费用是增加（正数）表示；已分配流；费用是增加（正数）表示；?反向边：可减少流量反向边：可减少流量=已分配流，费用是减小（负数）表示。已分配流，费用是减小（负数）表示。图图3: 图图2可行流的补图可行流的补图图图1图图2: 流分配流分配负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法负价环：负价环：
27、环上各边的费用函数环上各边的费用函数aij之和是负数。之和是负数。沿负价环增加流量（环上最小流量值），不破坏沿负价环增加流量（环上最小流量值），不破坏G的流量连续性，仍得到可行流，但 总费用降低。的流量连续性，仍得到可行流，但 总费用降低。图中，图中，V1V2V3V1环的单位流费用环的单位流费用2+1 6= 3，增，增2流费用流费用 6。则则Fst总费用从总费用从 69 降到降到 63，新可行流如下右图。，新可行流如下右图。69 63333负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法费用负价环算法步骤：费用负价环算法步骤：1. 在图在图
28、G中找到任一满足总流量中找到任一满足总流量Fst的的可行流图可行流图G；2. 作作Fst可行流可行流G的的补图补图。对。对G的边的边eij，若，若cij fij，补图作边，补图作边eij，容量为，容量为cij=cij fij，费用为，费用为aij；若；若G图图fij 0，补图再作边，补图再作边eji，其容量为，其容量为cji= fij，费用为，费用为aij。3. 在补图中找费用在补图中找费用负价环负价环。若无负价环，算法终止。若有，沿这负价环。若无负价环，算法终止。若有，沿这负价环C方向使方向使各边增流各边增流，增流值为修改原图，增流值为修改原图G的边流量，得到新可行流，返回算法第的边流量，得
29、到新可行流，返回算法第2步。步。jiCcmin=解解：找：找G网可行流，满足源宿网可行流，满足源宿Fst= 9。负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法例例：G网如下，要求网如下，要求Fst= 9，求最佳流。，求最佳流。VsV1V2V3V4Vt6644431466补图补图G1：满足网：满足网G的的Fst = 9。可行流图可行流图G，可行流图的总费用为：，可行流图的总费用为：102。负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法补图中找负价环：补图中找负价环：V2V3V4V2。增
30、流。增流3，环费用，环费用2。减小费用。减小费用-6。增流增流3可行流图可行流图G，费用，费用102；可行流图；可行流图G”，费用，费用96负价环（负价环（负价环（负价环（N N）最佳流分配算法）最佳流分配算法）最佳流分配算法）最佳流分配算法原图原图G 增流增流3后的可行流图后的可行流图G”，费用，费用96图图G2中再找负价环，没有。则最佳流分配图中再找负价环，没有。则最佳流分配图G”所示。所示。新补图新补图G2负价环算法在图论中也称为消圈（负价圈）算法，基于图论通过冗余网构造功的最小费用路和最大流最小费用的算法也是求解最小费用问题常用算法；当图论的算法不凑效时，基于线性规划模型的原始负价环算
31、法在图论中也称为消圈（负价圈）算法，基于图论通过冗余网构造功的最小费用路和最大流最小费用的算法也是求解最小费用问题常用算法；当图论的算法不凑效时，基于线性规划模型的原始对偶定理算法、单纯型及改进算法、循环流等算法用代数方法求最小代价流问题。对偶定理算法、单纯型及改进算法、循环流等算法用代数方法求最小代价流问题。5.4 5.4 线性规划简介线性规划简介线性规划简介线性规划简介（Linear Programming）5.4.1 5.4.1 线性规划的标准型（线性规划的标准型（线性规划的标准型（线性规划的标准型（Mathematical ModelMathematical Model）【例】【例】某
32、公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。问问该公司应制造两种家电各多少件，使获取的利润最大？线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。项目项目每天可用能力每天可用能力设备设备A (h)设备设备B (h)调试工序调试工序(h)06152115245利润（元）利润（元）21【解解】 设公司制造、两种家电分别为x1，x2件。问题：问题：x1=? x2=? 利润最大？利润最大？212zxx=+212maxxxZ+=212
33、maxxxZ+=目标函数目标函数约束条件约束条件资源约束资源约束非负约束非负约束+0,524261552121212xxxxxxx其中，约束条件可记其中，约束条件可记 s.t (subject to), 意思为意思为“以以为条件为条件“、”假定假定“、”满足满足“之意。之意。5.4.1 5.4.1 线性规划的标准型线性规划的标准型线性规划的标准型线性规划的标准型线性规划数学模型的线性规划数学模型的特征：特征：1解决问题的目标函数是多个决策变量的线性函数，通常是求最大1解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值值或最小值；2解决问题的2解决问题的约束条件约束条件约束条件：
34、一组多个决策变量的线性不等式或等式约束条件：一组多个决策变量的线性不等式或等式。线性规划数学模型的线性规划数学模型的三要素：三要素：决策变量决策变量( Decision variables); 目标函数目标函数(Objective function);约束条件约束条件(Constraints);建立一个问题的线性规划模型的建立一个问题的线性规划模型的一般步骤：一般步骤：(1)确定决策变量；(2)确定目标函数；(1)确定决策变量；(2)确定目标函数；(3)确定约束条件；(4)确定变量是否有非负约束。(3)确定约束条件；(4)确定变量是否有非负约束。5.4.1 5.4.1 线性规划的标准型线性规划
35、的标准型线性规划的标准型线性规划的标准型LP问题的数学模型的标准形式为：LP问题的数学模型的标准形式为：nnxcxcxcZ+=L2211max=+=+=+), 2 , 1( , 0.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnnLLLLLL其中常数项其中常数项, 0ib(i =), 2 , 1mL5.4.1 5.4.1 线性规划的标准型线性规划的标准型线性规划的标准型线性规划的标准型下面分析如何将下面分析如何将LP问题标准化：问题标准化：若目标函数为若目标函数为nnxcxcxcZ+=L2211min引进新的目标函数,ZZ=Z则
36、Z的最小值即为例例1 将将LP问题问题3212minxxxZ+=+=+)2 , 1(0222.31321ixxxxxxtsi化为标准形。化为标准形。解解：引进新的目标函数：引进新的目标函数,ZZ=于是原于是原LP问题化为标准形式：问题化为标准形式：=+=+)2 , 1(0222.31321ixxxxxxtsi3212maxxxxZ=5.4.1 5.4.1 线性规划的标准型线性规划的标准型线性规划的标准型线性规划的标准型图方法解决图方法解决LP问题问题Graphical Method图解法的步骤：图解法的步骤：1. 在直角坐标系中画出可行解集在直角坐标系中画出可行解集：分别画出满足每个约束包括变
37、量非负要求的区域，其交集就是可行解集，或称分别画出满足每个约束包括变量非负要求的区域，其交集就是可行解集，或称可行域；可行域；2. 绘制目标函数图形：绘制目标函数图形：先过原点作一条矢量指向点先过原点作一条矢量指向点(c c1, ,c c2 )，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；3. 求最优解：求最优解：依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线
38、与可行域相交的点对应的坐标就是最优解。最优解。一般地，先将目标函数直线放在可行域中：一般地，先将目标函数直线放在可行域中：若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最小值，则将目标函数直线沿着矢量的反方向移动。若要求最小值，则将目标函数直线沿着矢量的反方向移动。图方法解决图方法解决图方法解决图方法解决LPLP问题问题问题问题x1x2O1020304010203040(3,4)(15, 10)最优解最优解X = (15, 10 )最优值最优值Z = 8540221=+xx305 . 121=+xx+0, 0305 . 1402212121xxxxxx例：例：2143maxxxZ+=ABC
