运筹学复习资料.pdf

第二章内 容 提 要一、 线性规划的实际模型1 .规划间题数学模型三个要素( 1 )决策变量( 2 )目标函数( 3 )约束条件2 .线性规划问题的赘学模型( 1 )一般形式*目标函数:m a x( 或min)z= 产，i - i.' Z %工, =(=・2 ) "( i = l .2 ., •, .« )约束条件［， -】了 ,i 0 1 , 2 , …, n )其中叼( j = l , 2 , …, n )为决策变量…,…, n )为工艺系数,瓦( i = l , 2 , ….小) 为资源系数位( ， =1 , 2为价侑系数.( 2 )标准型式( 也称规范形式)*m a x z =*= bt ( t = 1 , 2 , …& t . 4 / - 1工i >0 (j = L 2 » - .n )二 、 线性规划的求解方法1.图解法(1)优缺点：(D图解法: 图解法简单直观， 求解线性规划问题时不需将数学模型化为标准型,可以直接在平面上作图， 但此法只适用于二维问题， 故有一定局限性②用图解法求解， 有助于了解线性规划问题求解的基本原理它可以直接看出线性规划问题解的几种情况：1 0有惟一最优解；2 °有无穷多组最优解；3 °无可行解；4 °无有限最优解( 即为无界解) .(2)图解法的步骤：①建立平面直角坐标系；②图示约束条件， 找出可行域；③图示目标函数， 即为一条直线；④将目标函数直线沿其法线方向在可行域内向可行域边界平移直至目标函数。

2.单纯形法(1)单纯形法原理①基本思想: 从可行域中的某个基本可行解开始到另一个基本可行解， 直到目标函数达到最优.②理论基础；定 理1若LP问题可行域存在, 则可行域是个凸集定理2 LP问题的基可行解与可行域的顶点一一对应.定理3若LP问题存在最优解， 则一定存在一个基可行解是最优解.(2)单纯形法的步骤及解法①找出初始可行基， 确定初始基本可行解, 建立初始单纯形表.②检验此基本可行解是否为最优解.即检验各非基变景町的检验数 , , 若所有句( 0 加 +1,•“, 〃 ) 则已经得到最优解， 计算停止; 否则转下一步.2④ 根 据m axQ ,>0） = 6 ,确定非基变量z *为换入变量; 再根据 法则6=tnin（1a *> 0 ] ——i 〈a* ） an确定基变量与为换出变量⑤实施枢轴运算， 即以 为主元素进行枢轴运算（ 亦即进行矩阵的行变换） ， 使P *变换为第1行的元素为1.其余的元素为0 ;并将XB列中的工, 换为H ，从而得新的单纯形表; 重复②〜⑤， 直到终止.3 .两阶段法、 大M法以及运用人工变量法求解非规范型的线性规划问题（ 1）两阶段法①原理: 此方法是将加入人工变量后的线性规划问题分成两个阶段来求解.第一阶段: 其目的是为原问题求初始基本可行解。

为此， 对于求极大化（ 或极小化） 的线性规划问题， 建立一个新的人工变量的目标函数 人工变量的系数均为一 1或（ + D ,对新的问题：max w = -JE,+ 1 - x.+z - - x .+.或 min w = x ,+ l +工” +? + ••• + x ,+1.411N1 + …+a11rxl,+N.+ I =bi・ • •8. t. JX i， …，N.2 O ,N.+I ,•••， 工—用单纯形法求解.若w = 0 ,即所有的人工变量都变换为非基变量， 说明原问题已得到了初始基本可行解； 反之， 若目标函数3的值为负（ 或为正） ， 则人工变量中至少有一个为正， 这表示原问题无可行解， 应停止计算.第二阶段: 将第一阶段求得的基本可行解对原问题的目标函数进行优化, 即将目标函数换成原目标函数， 以第一阶段得到的最终单纯形表除去人工变量的列后作为第二阶段计算的初始表， 继续用单纯形法以求得问题的最优解②计算方法: 单纯形法 2）大M法① 原 理 ： 人工变量在目标函数中的系数确定： 若目标函数为max z ,则系数为- M ；否则为②计算方法: 单纯形法.3三、 了解线性规划的解及其几何意义1 .可行解： 凡满足线性规划约束条件的解称为可行解.2 .最优解: 使目标函数达到最大的可行解称为最优解.3 .基: 设A是约束方程组mXn维系数矩阵， 其秩为m , B 是矩阵A中 mXn阶非奇异子矩阵， 则称B是线性规划问题的一个基.4 .解的几何意义：( 1 ) 若线性规划问题有可行解， 其所有可行解构成的区域称为可行域， 则此可行域D = { X | 25叼 =， = 1 , 2 , …， 机； 工) 2 0 }必是一个四集.( 2 ) 线性规划问题的基本可行解与可行域D的顶点一一对应.( 3 ) 如果线性规划问题有有限的最优解， 则其目标函数的最优值一定可以在可行域的顶点上达到。

0 1 . 1 |用图解法求解下列线性规划问题， 并指出问题是具有惟一最优斛、 无穷多最优解、无界解还是无可行解？( l ) m a x z-x\ + 3 工 z节力+ 1 0 亚4 5 0X 1 +s . t . J与《4X1 , 2 2 2 0( 3 ) m a x z = 2 x ) + 2X2( X\s . t . J —0 . 5 x i + 工? 4 2I x i ， 工 2 2 0( 2 ) m i n z=i\ + 1 . 5 H 21 - x j + 3 e 2 2 3s . t . J X j + Xi＞2[ 工 1 ， 工 2 》0( 4 ) m a x z=Xi + x2(X |—x： ＞0s. t . J 3 x) -亚4—3[ xi , x： ＞0解( 1 ) 图 1 一2中的阴影部分为此线性规划问题的可行域， 目标函数z= zi + 3 z2 ， 即与4=-4©+高是斜率为一 J的一族平行线， 易知©=35 =0为可行解， 由线性0 u 0规划的性质知， 其最值在可行域的顶点取得， 将直线为+ 3 处=3沿其法线方向逐渐向上平移， 直至A点， 八点坐标为( 2 , 4 ) .图 1一2所以 m a x z= 2 4 - 3 X 4 = 1 4此线性规划问题有惟一最优解.( 2 ) 图 1 一3中的阴影部分为此线性规划问题的可行域， 目标函数z= zi + 1 . 5z2 , 即“= 一 枭 ― 与 是 斜 率 为 一 ■ 1 •的一族平行线, 易知皿=3』 =0为可行解, 由线性规划的性质知， 其最值在可行域的顶点取得.将直线m+ 1 . 5与 = 3沿其法线方向逐渐向下平移， 直 至B 点， B点坐标为(14)所以 m i n z =^ + l. 5 X ； = ?I I 4此线性规划问题有惟一最优解。

54 z i + N c -2为 + g- +X I Q = 27 1 + 与 +3 1 3 - x5+ x« +x7 = 1 4s. t. J—2 Z] + 3 jr2 - xs + 2N5 — 2工6 —工 & +J： 9 = 2Z] ， N z， ％5， 1 6， 为， N g ， N 9， 《Z1 0》0其中M是一个任意大的正数初始单纯形表见表1 — 2表 1一23- 42- 5S00- M-M0CBXBbXiX iX iX i4Ng一MX102- 41- 21- 1000120X714113- 11100014一M2- 2[3]- 12- 20T1023- z4M3 - 6M4M—42 - 3M3M -55-3M0一M00( 2 )在上述问题的约束条件中加入人工变量勺， 与， …, ，， 得m a x s = — X X SC -M% -M r ?一…一Mz ”P * i - l A T小卜+官kl g， 2 ， F )［ 工. )0 , 6 2 0 G = l, 2 , … ,, zn)其中M是一个任意大的正数.初始单纯形表见表1一3 .表 1一3勺MM• ••MA llPhanX港•••a・ iPha魄外•••ph0CBXBbxi6・ ♦ ・xaXllNilX1M• • •x«iX・ ・ ・MX I110・ ・ ♦0111• • •00・ ・ ・0M4101・ ♦ ・0000• • •00・ ・ ・0*(•：*•** •:・ ♦ ・*• }；•：；・ ・ ・；M100・ ・ ♦1000• • •11・ ・ ・1- snM00・ ・•0}+ M% + M八— + M• • •— + Mp*驯+ Mpk・ ・ ・— +M6将下列线性规划问题变换成标准型， 并列出初始单纯形表。

1) min z = - 3x] + 4JE2- 24-5x<4xi —x： +2xa-= - 2Xi + 3X3- Z 4 1 4s. t・ <- 2xj + 3与一xj + 2X4^ 2—2 ♦ JEj > 0 >X 4 无约束(2) max s = z jpktt mZ i= S S a3* »=1 41mY X 一工尸―1 (£= 1,…,71)4-1期 》0 (£= 1,・ ・ ・， 几次= 1 ,…， tn)分析 本题考查了线性规划问题的标准形式和初始单纯形表解(D 将此线性规划问题化为标准型令 X4 = x5 - t6 , / = - Z其中x$ 9曲》0所以 max z = - min ( 一—) = -min z则得到标准型为max z =3x\ - 4X2 + 2X>- 5(x$- x6)+ 0 • xy + 0 • 与一M r 一Mz\Q・1 6 ] 分 别 用 单 纯 形 法 中 的 大 M 法 和 两 阶 段 法 求 解 下 述 线 性 规 划 问 题 . 并 指 出 属 哪 一 类解 O(1) max z=2xi +3xa 一5x3( Zi + x2 + x3 =7s. t. J 2 xi—5xa + x3 ^10Ixi eNz， 工 9 NO分析 本题考查' 了单纯形法中的大M 法， 两阶段法以及解的类型的概念。

解(1)解 1：大 M 法.在上述线性规划问题的约束条件中加上人工变量x4， 工 ‘ ， 减去剩余变量工$ ， 得max z = 2阳 + 312- 5x3- Mx4 +0x5- Mx$/ X)+ Xi + X)+ ~~ 7S. t. J 2 Xi- 5亚 + 13 —马+ 工6=10[Xi ,*2 9az9 , *4 ,25 9*6 > 0其中M 是一个任意大的正数据此可列出单纯形表表1-617表1一623-5一M0MftCBXBbX Ixix>xsM1 471111007-Mx«10[2]5101153M+23- 4M2M—50一M0-M1 420[7/2]1/211/2-1/24/72X ]515/21/20-1/21/2—c, 孙03M/2 + 8M/2 60M/2+13M/2-13Xx4/7011/72/71/7-1/72XI45/7106/75/7-1/71/7立一句0050/7M 16/71/7M+l/7由单纯形表的计算结果得：最优解X， =（竿, 午,0, 0, 0, 0> ,目标函数的最优值Z ， =2X竽+ 3X尹 半 .解2 ：两阶段法先在上述线性规划问题的约束条件中加入人工变量工, ， 与， 减去剩余变量4,得第一阶段的数学模型m i n w = xi + 4，x\ + " + 1 3 + 1 4 = 7s . t . J 2 i ] -5ZZ+Z3 -XS+X6 = 1 0X ]， 工2 , 2 3 9 X 4 1 X 5 ^ 0据此可列出单纯形表表1 - 7 ：8< 1 -7000101ACBXBbX 1力4以g11 471111007110[2]510-115C ， %-34-201011 420[7/2]1/211/2-1/24/70X151-5/21/20-1/21/2—0-7/2一 1/201/23/20XI4/7011/72/71/7-1/70X145/7106/75/7-1/71/7弓一句000101第一阶段求得的最优解X・=（ 竽 号 , 0,0,0,0） T ,目标函数的最优值” = 0.内人工变量Z L Z = O ,所 以 有，% 0,0,0,0）T是原线性规划问题的基可行解。

于是可以进行第二阶段运算， 将第一阶段的最终衷中的人工变量取消， 并填入原问题的目标函数的系数, 进行第二阶段的运算， 见表 1 — 8.表1一8盯23一50f tCBXBbXlX lxjN 532N ,X l4/745/701101/76/71/71/7盯一同0050/71/7由表中计算可知， 原线性规划问题的最优解X -= （ 竿 ， 彳, 0,0,0,0 人目标函数的最优值z・= 2 X 华+ 3X ＞ 华 .第三章9一、 原问题与对偶问题的关系若某线性规划（ 原问题） 约束系数矩阵为A ,约束条件右端为向量b ,目标函数中的价值系数向量为C， 则其对偶问题形式如表2・1所示.表 2-1原问题（ 对偶问题）对偶问题（ 原问题）a目标函数max z= £ 用，叼 0 = 1,… ， n）变 句》0量 N,<0产, 无约束.min w —＞瓜i-i有n个（ ， =有…X % ”《 勺X % " = ciy'㈤约束条件有m个（ £=19…， 利）约 / j C LijX j & d靠' I —— 一j flyX； = bi= …， m）y & oy ,无约束1$' 量二、 对偶理论及其性质1 . 对称性: 对偶问题的对偶是原问题。

2 . 弱对偶性: 若T 是原问题的可行解,Y 是对偶问题的可行解，则有3 . 无界性: 若原问题（ 对偶问题） 为无界解, 则其对偶问题（ 原问题） 无可行解4 . 可行解是最优解时的性质：设£ 是原问题的可行解才是对偶问题的可行解， 当= 时 **均 为 最 优 解 5 . 对偶定理: 若原问题有最优解， 那么对偶问题也有最优解， 且目标函数值相等.6,互补松弛性: 若分别是原问题和对偶问题的可行解. 那么XXs=O 和Ys% = 0 当且仅当X 」 为最优解.107. 设原问题是max z=CXiAX + Xs=biX,Xs^Q它的对偶问题是min w=Y&；yA -Ys=C |y,Ys>0则原问题单纯形表的检验数行对应其对偶问题的一个基解三、 对偶单纯形法1 .对偶单纯形法与单纯形法的区别对偶单纯形法是运用对偶原理求解原问题的一种方法， 而不是求解对偶问题的单纯形法. 它和单纯形法的主要区别在于： 单纯形法是从一个原始问题的基本可行解转到另一个基本可行解， 即迭代中始终保持原问题的可行性， 亦 即 常 数 列 而 检 验数 “= C -CBB T A = C -Y A由有正分量逐步变为全部4 0(即变为满足YA>C,Y是对偶问题的基本可行解) 为止。

对偶单纯形法则是保持对偶问题解是基本可行解( 即全部检验数 》0 ),而原问题在非可行解( 即常数列6有负的分量) 的基础上通过逐步迭代达到基本可行解( 即常数列b全 部 >0 ) .这样， 同时得到原问题和对偶问题的最优解2 . 对偶单纯形法的计算步骤(1 )将问题化为标准型， 列出初始单纯形表格.(2 )若存在初始对偶可行的基本解， 则进行迭代3 )检验b列的数字, 若检验数全部非正而b列都为非负， 则问题已得到最优解， 终止迭代; 否则, 若检验数全部非正而b列至少还有一个负分量, 进行下一步.(4 )确定换出变量•即按对应的基变量与为换出变量5)确定换人变量: 检查x ,所所在行的各系数人 1,2,…， 而.若所有4 > 0 ,则无可行解停止迭代, 若存在％ V 0,按6法则， 即8= min ］色• ® VO j =幺i S u। J所对应的列的非基变量马为换人变量6 )实施枢轴运算， 即 以 生 为主元素按原单纯形法在表中进行迭代运算， 得新的单纯形表格, 转步骤(3)继续迭代.II四、影子价格影子价格: 根据资源在生产中作出的贡献而作的估价. 影子价格是一种边际价格， 其值相当于在资源得到最优利用的生产条件下， 资源每增加一个单位时目标函数增加量。

影子价格的大小反映了资源的稀缺和富有程度在完全市场经济的条件下， 当某种资源的市场价格低于影子价格时, 企业应买进该资源以扩大再生产; 反之, 则应将已有资源卖掉可见， 影子价格对市场有调节作用五、 灵敏度分析由于可用资源的数量发生变化, 右边限制系数6 ,会发生变化， 由于市场条件发生变化.价值系数0会发生变化； 由于生产工艺的改进， 约束条件系数与会发生变化当线性规划问题中的一个或几个系数发生变化后， 原来求得的结果一般会发生变化灵敏度分析的步骤可归纳如下：1.将参数的改变计算反映到最终单纯形表上来：具体计算方法是, 按下列公式计算出由参数/出、c ,的变化而引起的最终单纯形表上有关数字的变化：△b ， = BAP . ' = B' ,AP .m△ （ q 一句） • = A （ C/—Z , ） - 2 a g y Jt - 12 . 检杳原问题是否仍为可行解；3 . 检查对偶问题是否仍为可行解；4 .按表2- 2所列情况得出结论和决定继续计算的步骤.表2- 2原问题对偶问题结论或继续计算的步骤可行解可行解仍为问题最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量， 编制新的单纯形表重新计算12|O 2 .1 |用改进单纯形法求第以下线性规划向密.(l)m ax之-6工 ］ - 2工.+3工 】2xi —Xj +2工 > 42I Xi +4工 《 4工 1 , 工 ］ «x>>0分 析 先将线性规划问题转化为标准形式再用改进单纯形法求解。

解(1 )将上述线性规划问题转化为标准形式max 彳= 611 — 21, + 31,+0 • x« +0 • 工 $- 亚 +2，1+工 4 0=2s. L« x> +4必 + 上 ,= 4X \ f i t «1 ,t X)20取B°・（ P ,，Ps） ■ （ : ；） , XB0= （X4,XS）T, Cao = （ 0,0） ,2 — 1 2N0 = （ P］，H，巴）= Q 0 j , X % = 5，y , q ） T,£\二 （ 6 .-2 ,3 ） , & ' = （：：），瓦啕非基变量的检验数ont =C$ —CntB0 ' No=Gv. = (6, - 2*3)V x ,的检验数叫= 6 为正的最大，A x .为换人变依.由 0 规则得i . i n ( ^ ^ | ( BJ P ) > 0)=min 传由=】••・工 ， 为换出变景8 以一( 力况由= (； )由0 规则得13" T n （ 那皓| （ 凡 由 ） ＞ 0 ） = m in 传由=1• •・人为换出变ftBI=(P .,PS) = (2 ；), XB1= (xl txs)T, C > = (6 ,0),M = (P ,.P ,,P；) = ( ；C .V [ = ( o , - 2,3), Bt , =…7 ° 1 2 iX 1 YE)非基变房的检验数XN] = (X* IXJ .xj)7 ,叫 =Gv] - Cgj B J M~ 2= (0 ,-2 ,3 )-(6 .0 )A - 1 2、= ( 0 ,-2 ,3 )-(3 ,0 )( ]10 0 4)- ( 0 ,- 2 ,3 ) - ( 3 ,- 3 ,6 ) = ( - 3 ,1 ,- 3 )•・F的检验数s = 1 为正的最大,A x .为换人变量.由6 规则得（5 4）,（8 F）,夕 =min(Bo 'P i).> 0 = mini:, 工 、为换出变髭.B，=(P】 ， H ) = (； € .,= ( 6 ,- 2 ) ,M = (P 4・P， ，R )H (： : ^,X ,vt-(x*,x*.x»)T,CWt = (0 ,0 ,3 ),14Bf：亦―( 一： 流啕非基变量的检验数ON. —Cgj B： NIz0 lx A 0 2\=(0 ,。

⑶ FT) " 2)(- 4)A 0 2、= (0 ,0 ,3 )-(2 ,2)f .](0 1 4)= (0 ,0 ,3 )-(2 .2 .1 2 ) = ( - 2 , - 2 , - 9 )「非萼变景的检验数均为负,, 原何即已达到最优解.最优解即X- =(4,6,O )T目标函数最优值max 1= 6X 4-2X 6 + 3X0 = 12.[02. 3| 写出下列线性规划问题的对偶问题 l ) m i n z = 2x i + 2 + 4x32x i + 3 马 + 5马 > 23阳 + 12+ 7±3&3X| + 4 工 2 + 6 1345x i分析 本题考餐了对偶问题的转化解( 1) 将原问题化为m a x ( -N) = ­ 2© -2叫一44_ 2x i - 3x 2 — 5xa 4 一 23x i +R2 + 71343v X\ + 4x2+ 6x j ^ 5X\， 孙， 亚》0设 “， "， “ 分别为与约束条件①②③对应的对偶变量此问题的对偶问题为m i n ( - w ) = - 2v i + 3y2 + 5v3①②③©15m i n m= 51y l ~ ~ 5第 一 8 g + 20 »4‘ ― v+ 6 3 + 1 2y 4) 1yi- yt-7yJ— 9”' 2”- ”+ 3 “+ 9”》一3t . J— 3“+3y 2+5 3 + 9y 4 > 431y l -3 %- 5js—9y4> —4, y i 5， g , “2 0第四章：运输问题表 中 为 各 产 地 的 产 量 之 和 ，£ 瓦为各销地的销量之和i - l > -1当即产量= 销量时， 称为产销平衡。

i= l i= 1m it当s«- >2；句， 即产 量 > 销量时j二 二 ［ 统称为产销不平衡当V 2；如即产量v 销量时I2】 ， ■1二、 表上作业法及其在产销平衡问题中的应用1. 产销平衡问题与衰上作业法( 1) 产销平衡问题的数学模型具有m个产地A, 0 =1, 2, …, m ) 和 ”个销地B, G = 1, 2, …， 〃 ) 的运输问题的数学模型为：・ ttm i n z= Xi - i > - im= bj (j = 1, 2 - 〃 )t - l.'J = % ( i = 1. 2, …, m )> - i它包含mX 〃个变量， ( m +冷个约束方程， 其系数矩阵的结构松散, 且比较特殊其系数矩阵为，16( 2 ) 表上作业法.表上作业法是单纯形法在求解运输问题的一种简化方法.其计算步骤如下：①列出产销平衡表②确定初始基可行解， 即在产销平衡表上给出m+ n - 1个数字格， 确定初始基可行解一般用最小元索法和伏格尔法.③求各非基变量的检验数, 即在表上计算空格的检验数， 判别是否达到最优解如已是最优解， 则停止计算， 否则转入下一步.④确定换人变量的空格.⑤确定换出变量的空格.⑥沿闭回路调整运输数量1 9⑦重复步骤③一⑥， 直至所有空格的检验数与均为非负为止， 此时便可得到最优方案。

1 ) 产大于销问题对于此类问题， 设有一个假想销地B . + i ， 其销量m«b .+ i = X 4 - X 与i - 1但实际上没有运输， 故其单位运价为0 , 这样就转化产销平衡问题， 但没有破坏原问题的性质 2 ) 销大于产问题对于此类问题， 设有一个假想产地A m T ， 其产量R ■ «a . + i = £d一但实际上没有运输， 故其单位运价为0 , 这样就转化为产销平衡问题， 但没有破坏原问题的性质.4 . 3 用表上作业法和伏格尔法求表中的运输问题的最优解和近似最优解^ 地产 地甲乙丙T戊产量11020591052210830663120710424863759销量4462417解表3 — 2 3 ： 利用伏格尔法求出初始解. 步骤和过程参考解表3 -2 2 .第一步: 分别计算表3 —2 3 中各行、 各列的最小运费和次最小运费的差额， 并填入该表的最右列和最下行.第二步: 从行或列差额中选出最大者, 选择它所在行或列中的最小元素.第三步: 对未划去的元素再分别计算出各行、 各列的最小运费和次最小运费的差额,并填入该表的最右列和最下行， 重复第一、 二步， 直到给出初始解为止.最后再利用位势法检验.解表3 — 2 4 ： 表 3 — 3 3 是产销不平衡的运输问题， 所以增加一个假想销地巳， 并令其运价为。

， 其销量为 5 + 6 + 2 + 9 —(4 + 4 + 6 + 2 + 4 ) = 2 ,见表 3 -3 6 .表 3 -3 6销地产地甲乙丙T戊巳产量110205910052210830606312071040248637S09销母446242利用伏格尔法求出初始解.第一步: 分别计算表3 — 3 6 中各行、 各列的最小运费和次最小运费的差额， 并填入该表的最右列和最下行.第二步: 从行或列差额中选出最大者， 选择它所在行或列中的最小元素第三步: 对未划去的元素再分别计算出各行、 各列的最小运费和次最小运费的差额.并填入该表的最右列和最下行， 重复第一、 二步， 直到给出初始解为止最后利用位势法进行检验.所有检验数都非负， 故解为最优解. 这时得到的总运费最少， 为 9 0故该运输问题有无穷多最优解2.表 3 — 23岫甲乙丙T产 M110671242161059935410104的 量S24618分 析 本题考查了表上作业法， 可先利用伏格尔法求出初始解， 再利用位势法进行检验.解解表3 — 2 2 ： 利用伏格尔法求出初始解.第一步: 分别计算表3 —2 2 中各行、 各列的最小运费和次最小运费的差额， 并填入该表的最右列和最下行， 见表3 - 2 6 .表 3-267地地甲乙丙T列基额137641224320343851列一顿1132第二步: 从行或列差额中选出最大者, 选择它所在行或列中的最小元素. 在表3 - 2 6中， 丙列是最大差额所在列， 丙列中的最小元素为3 , 可确定产地2的产品先供应给销地丙， 因为产地2的产姑等于销地丙的销姑， 所以在（ 2 , 丁） 处填入一个0 , 得表3 —2 7 并同时将运价表中丙列数字和第二行数字划去， 如表3 — 2 8 所示.表 3—27精 地产地甲乙丙T产量12320523销量3322表 3-28产 地地甲乙丙T产量1376452243223438S3用量3322第三步: 对表3 — 2 8 中未划去的元素再分别计算出各行、 各列的最小运费和次最小运费的差、 额， 并填入该表的最右列和最下行， 重复第一、 二步， 直到给出初始解为止。

用此法给出表3 - 2 2 的初始解如表3 - 2 9 所示.19表 3-29产 地地甲乙丙T产量130252202333销量3322利用位势法进行检验第一步: 在对应表3 - 2 9 的数字格处填入单位运价， 见表3-30.表 3-30第二步: 在表3 - 3 0 上增加一行一列， 在列中填入”, 在行中填入5 , 得表3-31.产 地地甲乙丙T137423233表 3 — 31产 地地甲乙丙TUi13740232一 233- 43754先令出=0,然 后 按 叼 =% 相 继 地 确 定 由 表 3 - 3 1 可见， 当M 1= 0时， 由 小 + 功 = 3 可得m = 3 ； 由ui = 7 可得”=7|由 “ 1 + ” 4 = 4 可 得 口 = 4； 由VX = 7,U}+V2 = 3 可得 “ 3 = —4； 由 q = 4 , “ z + q = 2 可得 知 = —2； 由 “ 2 = - 2,如 +v3 =3 可得 t / j =5第三步: 按% =%—（ 出+ 叼） ， 3 ， €可计算所有空格的检验数， 如表3—32所示.2()表 3 — 32销地产地甲乙丙T1030716040212-140302-23540378554叼3754an =Qi - ( 如+ 0)=2 —( - 2+3) = 1 必i = 5 - (“3)= 4 —( - 4 +3) = 5att =Q： ­(«2 + “)=4 - ( - 2+7) = -1 =" 一( % +vj) =6 —(0+5) = 10” =c” 一( % + s)= 8 —( - 4+5) =7 0 < =c“ 一( 〃 s + a)= 5 - ( - 4+4) = 5在表3—32中还有负检验数， 说明未得到最优解， 可以利用闭回路调整法加以改进。

由表3 -3 2 得（ 2 ,乙） 为调入格， 以此格为出发点， 作一闭回路， 如表3 -3 3 所示表 3-33销地产地甲乙内T产量130(-1)2( + 1)520(41)2 ：0(-1)2333销量3322（ 2,乙） 格的调入量 是选择闭回路上具有（ 一1） 的数字格中的最小者， 即0=min{0,0},然后按照闭回路上的正、 负号， 加上和减去此值, 得到调整方案， 如表3—34所示表 3 — 34销地产地甲乙丙T产量130252022333销 量332221对表3—34给出的解， 再用位势法求各空格的检验数， 如表3—35所示所有检验数都非负， 故表3 — 34中的解为最优解这时得到的总运费最少， 为 3 2 由于表3-35中(1,丙) 格的检验数为0 ,故该运输问题有无穷多最优解.表 3-35侑地产地甲乙丙T4100221-33565-4叼3764第五章：目标规划4 . 3 | 用单纯形法求解以下目标规划问班的满意解.(1) min +P1d]X) +2x> + 4 —= 10lOxj+Hxt+c/, 一4 =62.4K 2xiXj = 0 , i = 1,2分 析 本题考查解目标规划的单纯形法.解(D 将上述目标规划问题化为如下形式：min z= P id i +P]d* +P*diXi +2x> + d 1 ~d\ =01 0 0 + 12图 + 4 - di =62. 4, 2x\ +N* +x> =8Xi , 工 ] , ar, d > O .i= l ,2.3其中马为松弛变量.对于此问题用单纯形法进行计算, 见表4- 1.22表 4-1000p,0p,P leCBXnbX|x1Xi4d t小火P ldi101201一］005p ,&62.410120001TS.20X|82110000aPip ,-1 0一】-1 2-20000010020051T101TL00Pldi2.44006[ « ]1一】0.4Cj000P l0PiPlCBXBbXlX lX3d ldpd idiV0Xj330111006Pi一4006- 602Pi00010000X15.25T10001Tz1F6. 240d t0.4/0011Vi Vi0.60X32.87V01001121122.4Pl0000011Pi0001000由 表 4 - 1 可 得 皿 = 0 ,皿 = 5. 2 为原问题的满意解.而 非 基 变 量 为 的 检 验 数 为 0 ,故原问题存在多重解.4 — 1 的基础卜以 力 为撞人有身工士为撞出有信•再佚伴一去. 得靠4 — 2.衣4 - 2000P t0PiPl0CBXBbXtXfXld rd tdrd t0X14.70105V立V1V1V0X I0. 61003310XS2・10017V733VP ]0000011P l000100023由表4 - 2 可得耳=0.6,川 = 4. 7 也为满意解。

由线性规划的性质可得： （ 0. 6,4. 7） 和（ 0,5. 2） 这两点之间的线段上的所有点均为原问题的满意解.第六章：整数线性规划◎ 5.2|用分支定界法解：m ax z = X \ + 处- 皿+ 看必s. t . r2x i + Xt 9 "】I' x, +nx, x,C 204 工 , 4 2max r-3 x i +2x>上 9 々51口 +记(B.) S. LR2»+ x,x«>2x«>3无可行解， 故 剪 去 以 分支.因为&< 多 = 4,故剪去B ,分支. 从而可以断定x： = 2 ,方 = 2 为最优整数解, z' =4.|O5.6| 解 0—1 规划：(l)min Z = 4J：I+ 3N Z + 2工 ！,2xi —5 Xi +3 x34 44xi + x2 +3 x3) 3Xi + 2 1X\ tXj 9X2，13=0 或 1分析 本题考查了 0 — 1 型整数规划.解（1） 给各约束条件编号如下：262o ： i —5 JC2 + 3 x3 <44N I + n * + 3 4 2 3工2 + 工3工 】 ， 工2， 以 =。

或1先 找 到(0,0. 1 )T为 可 行 解 ， 相 应 的N = 2 ,故 增 加 约 束 条 件4 x i + 3孙 + 2 2 3 0 2表 5 — 10(0)(工 1 ， / * Hj )条件是 否 清足 条 件Z(0)(1)(2)⑶(0 ,0 .0 )000X(0 ,0 .1 )2333V2(0 .1 ・ 0)3X(0 ,1 ,1 )5X(1 ,0 .0 )4X(1 .0 .1 )6X(1 ,1 ,1 )7X(1 ,1 ,1 )9X所 以 ， 可 判 定 最 优 解X - = (0,0,1 )丁， 目 标 函 数 最 优 值 之 .= 2.05 . 7 |有4个 工 人 ， 要 指 派 他 们 分 别 完 成4种 工 作 ， 每 人 做 各 种 工 作 做 消 耗 的 时 间 如 下 表所 示 ， 问 指 派 哪 个 人 去 完 成 那 种 工 作 ， 可 使 总 的 消 耗 时 间 为 最 小 ？表 5-12ABCD甲15182124乙19232218丙26171619T19212317分 析 本 题 考 查 的 是 指 派 问 题 ， 用 匈 牙 利 法 求 解 .解 变 换 系 数 矩 阵 为1 5 1 821 24 '1 503 69-min(c^ ) =2923 221 81 8 ― >15 4 0= (b 过)261 71 61 91 61 01 03_ 1 921 231 7-1 7. 24 60.再 进 行 试 分 配 ， 得©11 026 94 ◎① 36 1因 为 也=3V双= 4 ,试 指 派 不 成 功 转 下 步 ， 所以27指派成功， 故此项工作有多种指派方案,Z = 70,指派矩阵如下:1 0 00 0 00 0 10 1 0即最优指派方案为；( 1 ) 甲f A , 乙- D , 内- C . 丁一3 】( 2 ) 甲-B .乙-A ,丙—C ,丁—D.0] [01或 10 00J 101 00 00 10 00001第七章：动态规划28（ 5 ） 状态转移方程①逆序递推的基本方程尔 G二阈;水…） + 力 + 小 8（ i = n ,n —1 , ••• ,2,1 ） ,边界条件为/.+I（S.+I） = 0 , 式 中 应 +i = △ （ ”， “ •） 。

其求解过程， 根据边界条件从4 = 〃开 始 ， 由后向前逆推， 可逐步求得各段的最优决策和相应的最优值， 当 最 后 求 出 力 （ 4） 时 ， 便得到整个问题的最优解,其各阶段和各变量之间的关系如图8 -1所示4 «| i «2 ♦， * ，3芭2 面］ 工 …上 匚 亡 | 如 7 . . . 2苣 七 '图8- 1②顺序递推的基本方程/ *（ « *+! ） = O p t | U4（ J *+1 ,« *） +/ * ! （ j *） }a = l , 2 , - , n ） ,边界条件为f 0 G ） = 0; 式中即状态转移是由s - i 必去确定其求解过程， 根据边界条件从及=1开始， 由前向后顺推， 可逐步求得各段的最优决策和相应的最优值， 当 最 后 求 得 £ ,（ & + 】 ） 时 ， 便得到整个问题的最优解其各阶段和各变量之间的关系如图8—2 所示.二自］ + 乜 自 之 . . . 生 「户 | 拉 | . . . 工 刍图8- 2一般地说， 当过程的始点给定时， 用逆序递推比较方便； 而当过程的终点给定时 ， 用顺序递推比较方便.解 设阶段变量&=1 , 2 , 3 , 4 依次表示4个阶段选路的过程， 第 1 阶段从A 出发到或 B , , 第 2阶段从3 、 B z 或 & 出 发 到 C i 、 C ? 或 C , , 第 3阶段从C i 、 C z 或 C 1 出发到D . 或 。

， 第 4阶段从D , 或 ， 出发到E；状态变量s * 表示左阶段初可能的位置；决策与表示上阶段初可能选择的路线；阶段指标S 表示4阶段与所选择的路段相应的路长；指标函数叨, =表示及至4阶段的总路长；. *递推公式:人= m i n { 5 + fk + i } , 1 = 4 , 3 , 2 , 1 =0.29解 设阶段变量6 = 1 ,2 ,3 ,4依次表示4个阶段选路的过程， 第1阶段从A出发到&、B?或 耳 ， 第2阶 段 从 、B z或 &出 发 到C1、G或G，第3阶段从G C 或G出发到□ 或A ,第4阶段从D ,或D z出发到E ；状态变量》表示&阶段初可能的位置；决策x *表示上阶段初可能选择的路线；阶段指标a表示为阶段与所选择的路段相应的路长；指 标 函 数 % =S V ,表示4至4阶段的总路长；»-4递推公式:人= min {v4+ / *+i) ,4 = 4,3,2,1 »/s= 0 .表8 - 2kVks = s + / i - ih工 」4DiE3030+030ED,E4040+040E3GDi1010 + 3040DiDi4040+40CtD,6060+3070DtDa3030+40GDi3030 + 300DiD,3030+402BiCl70704-40G4040+70110Ci、CtG6060 + 60B:Cl30304-4070ClCt2020 + 70Cj4040 + 60B,Cl4040 + 40G1010+7080Ci sCtc,5050 + 601ABi2020+110110Bi4040+70Bi3030 + 80由 表 中计算结果可以看出， 运 费 最 低 的 路 线 为 ：A B z G A E或A B jG d E或A B . C ^ E .最低运费为110.3008. 5］ 用递推方法求解下列问题（ l） m ax z=4xt + 9 工 ,+ 2 r >（ Xi +N, +X J = 1 0S . L国 >0. i =l, 2 , 3分析当初始状态给定时,使用逆推解法； 当终止状态给定时,使用眼推解法.解（ D由题意， 将问题划分为三个阶段•设状态变量为勾・力・” •力•并记力二1 0. 必.孙・N」 为各阶段的决策变曷,各阶段指标函数按加法方式结合./•（ ”） 表示第k阶段结束状态为。

第 1 至第*阶段的最大值则由约束条件可知X1 =S j * * 1 4 - X 1 =3 1 » 力+N」S, = 1 0即$ 1 =N 1 , 0《工 2 &$2 ， 0&N J &S 3由顺推法/ i （ 5i ） = m ax （ 4 x i ） =4 s ,« i "» i最优解: 工； =S 1■（ *） = m ax ［ 9z ? + / i （ 门） ］ =9$2—最优解: 贫=S z/ , （ " ） = m ax ［ 2 x J + / » （ * » ） ］ = 2 00o j V lo最优解：NJ =1 0xi =S i = 1 0—z ； =0X i ' =X | =s2 —xz = 0 —0=0从而得到最优解xi =0, xi =0, x / =1 0最优值为： 2 0031|O9. 1 )有一部货车每天沿着公路给四个零售店卸下6箱货物, 如果各零科店出的该货物所得利涧如表9一2所示. 试求在各零售店卸F几箱货物， 能使获得的总利涧最大?其值是多少？* 9 - 2利 海 、]2340000014234264SS3767647886579866710a6分 析 本题是一维资源的分配问题•利用动态规划的逆推关系式进行逐段计算.解 将问题按零售店数分为4个阶段, 阶段变量4 = 1,2,3・ 4, 第A阶段为第A个零仰店分配货物；状态变量”表示分配给第A至第4个零售店的货物箱数；决策变量x»表示分配给第人个零售店的货物箱数；状态转移方程：="一 工 ”阶段指标” ( n )表示将八箱货物分配给第A个零售店的效利；最优值函数人( 弘) 表示将船箱货物分配给第A至第4个¥ 俗店的最大盈利;( f t(J*) = max Lp*(x*) + / * - »)J»4 —4,3»2»1递推公式1计算过程如表9一3所示.32表 9一3k%Pk/a 4-1(“ + i)Ph Cxi) + fk+l ("+1)x /400000001140441225055233606634460664556066566606663000004010044130320055711347250530066921358254937074006611313692551037411480850066123,41369256113751248412580860066133,413692561137613485135841268080000000100444012022007770124624043009990,11279244836064001111110,1,212911247113641048085001212131,2,312111324913367134841259096001313152,3,41212142411153691548715594136100106001515171.2141317261117379164771457411670733由计算表格的结果可以看出， 最 大 总 利 润 为17.按计算表格的顺序反推算， 可知最优分配方案有六 个 ：(l)x* = 1 = 1 = 3, =1;(2)x； = l,x2' = 2 ,x； = 2,x； = 1 ；(3)xi* = 1, x2" = 3 .£ ； = 1, 土 ; =1;(4)x； = 2 ,i； = 0 ,x； = 3 H = 1 ；(5)xf = 2、 工 ；1 »X 3 = 2 ,N； =1;(6)xi* = 2 ,以= 2 ,z； = l,x ； = l0)9 .4某工厂有100台机器， 拟分四个周期使用， 在每一周期有两种生产任务。

据经验， 把机器© 台投入第一种生产任务, 则在一个生产周期中将有为/ 3 台机器作废； 余下的机器全部投入第二种生产任务， 则 有 1 / 1 0台机器作废, 如果干第一种生产任务每台机器可收益1 0, 干第二种生产任务每台机器可收益7 .问怎样分配机器， 使总收益最大？解 将问题按周期分为4个阶段, 阶段变量左= 1 , 2 , 3 , 4 , 第k阶段为第k周期分配机器；状态变量X 表示第& 周期初完好的机器台数；决策变量以表示第6周期用于第一种任务的机器台数， 相应的5-须 表 示 第 A周期用于第二种任务的机器台数；状态转移方程: S& + 1 = 等4 +4( S* —N* ) ；阶段指标a G， 皿) 表示第々周期用川台机器于第一种任务， 用 5 * - X * 台机器于第二种任务的总收益， 5,X* ) = 1 0X* + 7(J4—x* ) j最优值函数7•& •) 表示第k周期初完好的机器台数为5 4 时， 从 第k至第4周期的最大总收益；( / * ( “) = max »X* ) + / * +I( i * + i ) ], A = 4 , 3 , 2 , 1理推关系式11 人 ( % ) = 0当 k = \ 时. f ( s , ) = max ( 3 x< + 7s < ) = 1 0s4 . z； = s 《 ；o当 k = 3 时 9 八 ( 口 ) = max ( 1 6 § 3 + 当 G =黑门 = s3 ；3 3Q当一= 2 时 J式“)=max ( 2 2 * 一捺/ ) = 2 2 “, 1 ； = ( ho9当yy 归, = 11 时n4 ( Si、)_= max (r-1=3-45 | -T3T2X 1 )x=_-1=3-4$ i >5 | • =_0o34因为$= 1 00, 故最大总收益7, ( 5 ^ = ^X10 0 = 2 6 8 0.□反推得出最优策略如下：第一周期1 00台机器全部用于第二种任务的生产；第二周期9 0台机器全部用于第二种任务的生产；第 = 周 期 8 1 台机器全部用于第一种任务的生产；第四周期5 4 台机器全部用于第一种任务的生产.第八章：图论与网络优化1 0 . 1 证明如下序列不可能是某个简单图的次的序列：⑴ 7, 6 , 5 4 3 , 2 .( 2 ) 6 , 6 , 5 , 4 , 3 , 2 , 1 .( 3 ) 6 , 5 , 5 , 4 , 3 , 2 , 1 .分 析 一 个 无 环 、 无多重边的图称为简单图。

任一图中， 所有点的次之和是边数的两倍，穿点的个数为偶数.证 明 ( D 已知定理：= 而在此序列中，X 册 力 = 2 7, 为奇数， 所以此序列不可能为图的次的序列. 又知定理： 奇点的个数应为偶数， 而在此序列中， 奇点 7、 5 、 3为奇数个， 所以此序列不可能为图的次的序列.( 2 ) 此序列中， 奇点5 、 3 、 1 为奇数个， 所以此序列不可能为图的次的序列 3 ) 对于七顶点的图. 假定4 ( 0) = 6 , 4 ( “) = 5 3 « 7 ) = 1 , 并假设6为简单图， 则5 存在与其它六个点的连线( 包含与巧) 、 5与 5 间存在边〜， 而 s 次 为 1 ,所以必不与幼外的其它点相连， 因而s 与除5 , 巧外的四点间各有一连线假设G ( V, E ) 为简单图， 则 余 下 的 中 任 一 点 ( 用 矶 表 示 ) 已 确 定 存在 e “ ， 上， 无 打 ， 对于d ( “)=5的该点来说, 必与除s 外的每一点都有连线，设 d(v3) = 5.由此推论, ” 4, 5 tVt都同时与Pi >vt » vj 相连， 即5 , 5 的次至少是3 , 这与d( % ) = 2 相矛盾。

故假设不成立， 该图中可能有环或多重边， 非简单图的次的序列.35。