第五章-优化模型.doc

第五章 优 化 模 型

优化问题是人们在工程技术、经济管理和科学研究等领域中经常会遇到的问题类型之一，比如设计师要在满足强度要求等条件下选择材料、形状、尺寸等，使结构总重量最轻；工厂定购生产资料时要考虑订货方案使储存等费用最低;商品经营者要根据生产成本和市场需求制定商品价格以使利润最高；调度人员要在满足物资供需要求和装载条件限制安排从各供应点到各需求点的运量和路线，使运输总费用最低;投资者要选择一些股票、债券等投资，使总获利最大，而风险又最小等等.在很多情况下,我们会凭经验解决面临的优化问题，这样做看似有效,风险也较小，但决策时常常会融入太多决策者的主观臆断,因而无法保证结果的最优性。那么，是否一定要做大量的试验来探索最优方案呢？须知这样往往会花费大量的人力和物力，得到的结果仍可能受到先验的影响,落入事先圈定的试验范围。
最优化方法是数学学科中的一个应用性很强的分支，它包含的内容十分广泛,有数学规划（如线性规划、非线性规划、二次规划、目标规划、多目标规划等)、库存论、排队论、博弈论、组合优化(离散优化）、随机规划等等。这些内容都和实际问题密切相关，但由于涉及面太广,要比较深入地掌握这些最优化方法绝非一朝一夕就能办到。
根据变量取值范围的不同，优化问题有连续模型和离散模型之别.本章将选择一些连续优化问题的实例，以说明建立优化模型的一般方法和求其最优解的一般步骤.在下一章中，我们还将介绍一些较为典型的离散优化模型，并指出研究离散优化模型时经常会遇到的某些困难.
§ 5.1 线性规划问题
线性规划（Linear Programming, 简记LP）是数学规划的一个重要组成部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形法以来,线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。
（线性规划的实例与定义）
例5。1 某厂生产甲、乙两种产品，每单位产品销售后的利润分别为4千元与3千元.生产甲产品需用A、B两种机器加工,每单位产品的加工时间分别为 2小时和1小时；生产乙产品需用A、B、C三种机器加工，每单位产品的加工时间为每台机器各一小时。若每天可用于加工这两种产品的机器时数分别为A机器10小时、B机器8小时和C机器7小时,问该厂应当生产甲、乙两种产品各多少，才能使总利润最大?
例5.1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则 x1、x2应满足
max 4x1 + 3x2
s.t 2x1 + x2≤10
x1 + x2≤8 （5.1）
x2≤7
x1 , x2≥0
（5.1）式中4x1 + 3x2表示生产x1单位甲产品和x2单位乙产品的总利润，被称为问题的目标函数.当希望使目标函数最大时，记为max；反之，当希望使目标函数最小时,记为min。（5.1）中的几个不等式是问题的约束条件，记为S.t（Subject to的简写，意为“受约束于”）。由于(5.1)式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。
（线性规划的标准形式)
线性规划的目标函数可以是求最大值,也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有（称没有非负约束的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为
min
S.t ，i=1，…，m (5。2）
xj≥0， j=1，…，n
或更简洁地，利用矩阵与向量记为
min z = CT x
S.t Ax = b （5.3)
x≥0
其中C和x为n维列向量，b为m维列向量，b≥0,A为m×n矩阵，m<n且rank（A)=m.
如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：
（1）若目标函数为max z = CT x，可将它化为min －z = －CT x
（2）若第i个约束为ai1x1+…+ainxn≤bi，可增加一个松驰变量yi，将不等式化为ai1x1+…+ainxn+yi = bi，且yi≥0。若第i个约束为ai1x1+…+ainxn≥bi，可引入剩余量yi,将不等式化为ai1x1+…+ainxn－ yi = bi，且yi≥0。
（3）若xi为自变量，则可令，其中、≥0
例如,例5。1并非标准形式,其标准形式为
min ― 4x1―3x2
s。t 2x1 + x2 + x3 = 10
x1 + x2 + x4 = 8 （5.4）
x2 + x5 = 7
x1 , x2 , x3 ， x4, x5≥0
（线性规划的图解法）
为了了解线性规划问题的特征并导出求解它的算法，
我们先应用图解法来求解例5.1。满足线性规划所有约束
条件的点被称为问题的可行点（或可行解），所有可行点
构成的集合被称为问题的可行域，记为R.对于每一固定
的值z，使目标函数值等于z的点构成的直线称为目标函
数等位线，当z变动时，我们就得到了一族平行直线
(见图5-1）。 图5-1
对于例5。1，等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，例5.1的最优解为x*=(2,6)T，最优目标值z*=26。
从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时必定是若干个半平面的交集( 除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R非空时,线性规划既可以存在有限最优解,也可以不存在有限最优解（其目标函数值无界）。（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点"，（注：我们称这种“顶点"为极点，但为节省篇幅,我们省去了极点的严格定义）。
上述论断可以推广到一般的线性规划问题，区别只在于空间的维数.在一般的n维空间中，满足某一线性等式aix=bi的点集被称为一个超平面，而满足某一线性不等式aix≤bi（或aix≥bi）的点集被称为一个半空间（其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形,有界的多胞形又被称为多面体。易见，线性规划的可行域R必定为多胞形（为统一起见,空集Φ也被视为多胞形）。
在一般n维空间中,要直接得出多胞形的极点概念还有一些困难。在图5.1中顶点可以看成为边界直线的交点,但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径（代数方法）来定义它。
（基本解与基本可行解)
给定一个标准形式的线性规划问题（5.3）,其中A=（aij)mxn，m < n且秩r(A)=m。取出A的m个线性无关的列,这些列构成A的一个m阶非奇异子矩阵B，称B为A的一个基矩阵。A的其余n－m列构成一个m×（n－m）矩阵N。称对应于B的列的变量为基变量（共有m个），记它们为xB。其余变量称为非基变量，记为xN。
对线性规划(5。3），取定一个基矩阵B，令非基变量xN = 0，可以唯一地解出xB，xB = B-1b。这样得到的点x=（B-1b，0）称为（5.3)的一个基本解。为了叙述方便起见,这里我们将xB放在了前面，其实,它们的位置可以任意，但这并不影响到问题实质。显然，基本解不一定是可行解，因为还要求它们满足非负约束，当一个基本解同时还是可行解时（即B-1b≥0）,称之为（5.3）的一个基本可行解。进而,若B—1b>0，则称x=（B—1b,0)为（5.3)的一个非退化的基本可行解，并称B为一组非退化的可行基。由于基矩阵最多只有种不同的取法，即使A的任意m列均线性无关，且对应的基本解均可行，（5。3)最多也只能有个不同的基本可行解.
（基本可行解与极点的等价定理）
在线性规划的求解中,下列定理起了关键性的作用。在这里，我们不加证明地引入这些定理。对定理证明有兴趣的读者可以参阅 D.G。鲁恩伯杰著的“线性与非线性规划引论”一书的第二章。
定理5.1 （基本可行解与极点的等价定理）
设A为一个秩为m的m×n矩阵（n〉m)b为m维列向量，，记R为（5.3)的可行域。则x为R的极点的充分必要条件为x是的基本可行解（极点的代数定义）。
定理5.1既提供了求可行域R的极点的代数方法,又指明了线性规划可行域R的极点至多只有有限个.
定理5.2 (线性规划基本定理）
线性规划（5。3)具有以下性质：
（1）若可行域R≠Φ，则R必有基本可行解。
（2）若问题(5。3)存在一个最优解 ，则必存在一个最优的基本可行解。
定理5。2并非说最优解只能在基本可行解（极点）上达到，而是说只要（5.3）有有限最优解,就必定可在基本可行解(极点）中找到.
从模型本身来讲，线性规划显然应属于连续模型。但定理5.2表明，如果线性规划具有有限最优解，我们只需比较各个基本可行解上的目标函数值,即可找到一个最优解,而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个极点中去选取一个最优点的问题.正是基于这样一种想法，Dantzig提出了求解线性规划问题的单纯形法.
（求解线性规划的单纯形法）
Dantzig单纯形法的基本步骤如下：
(步1)取一个初始可行基B（一般取法见后面的两段单纯形法）,再用高斯-约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表;
(步2）判断x0是否最优解，如果x0是最优解，输出x0，停,否则到步3；
(步3)按某一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量，求一个更好的基本可行解。这相当于交换B与N的一个列,同样可用高斯—约当消去法，运算可以通过单纯形表上的所谓“转轴运算"实现,（改进的意思是指求得的新基本可行解上的目标函数值更小）。
为了给出算法，我们还需回答以下三个问题：如何确定最初的可行基；如何判断当前的可行基是否为最优基；如果当前的可行基不是最优基,我们应当如何改进。以下,我们将先回答后两个问题，最后再来回答第一个问题。
设B为一组非退化的可行基，=（B—1b，0）为其对应的基本可行解。现在，我们来讨论如何判别x0是否为最优解。为此，考察任一可行解。由Ax=b可得
（5.5）
代入目标函数，得到

（5。6）
定理5.3 （最优性判别定理） 令。
（1）若rN ≥ 0，则x0必为（5.3)的一个最优解。
(2）记 。若 ，rj < 0，则当B为非退化可行基时,x0必非最优解。
证明
（1）若rN ≥ 0,由于变量满足非负约束，必有xN ≥ 0.于是，由(5.6）式知，，故x0为（5.3）的一个最优解.
（2)（5。6）式给出了x处的目标值与x0处的目标值之间的联系.现设， 且j≠j0仍令xj = 0。由非退化假设,B－1b 〉 0,根据（5。5）式可知，当且充分小时,仍有xB 〉 0。此时对应的x仍为可行解，但由（5。6)，其目标函数值：

故x0必非最优解。
定理5.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解时还指出了一条改进它的途径.由于rN在判别现行基本可行解是否为最优解时起了重要作用,所以rN被称为x0处的检验向量，而rj (j∈N）则被称为非基变量xj的检验数.
有趣的是上述过程完全可以在以下的单纯形表上进行.先将CT、A、b及数0写在一个矩阵中，将此矩阵看成一张数表，在此表上用高斯—约当消去法解方程组Ax = b
高斯-约当消去法

(第一行不变）

利用单位矩阵I消第一行的为零向量，则被消成,而0则被消成.将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯型表的表格：
表5.1
xB
xN

I
B－1N
B－1b
0
rN
－Z0

表格(5。1）以极为简洁明了的方式表达了我们需要的全部信息。从其中I所在的m行可以看出哪些变量是基变量并可直接读出对应的基本可行解x0=(B－1b,0）。其最后一行又给出了非基变量的检验数及x0处目标函数值的相反数。
现在,我们以例5.1为例，来看一下单纯形法是如何工作的。例5.1的标准形式为(5。4），容易看出它的一个初始基B=I(以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表表5。2：
表5.2

x1
X2
x3
x4
x5

基
变
量
x3
②
1
1
0
0
10
x4
1
1
0
1
0
8
x5
0
1
0
0
1
7
rj
－4
－3
0
0
0
0

x0=（0,0，10,8，7)T ， z0=CTx0=0， rN=(r1，r2)=（－4，－3)
由于存在着负的检验数，且x0非退化，故x0非最优解.r1，r2均为负，x1，x2增大（进基）均能改进目标函数值。例如，取x1进基,仍令x2=0（x2仍为非基变量），此时由（5。5）式及（5。6）式有
且z = CTx = －4x1
x1增加得越多，目标函数值也下降得越多，但当x1=5时x3=0，x1再增大则x3将变负。为保证可行性，x1最多只能增加到5，此时x3成为非基变量（退基）.
不难看出,上述改进可以在单纯形表上进行.对于一般形式的单纯形表，记最后一列的前m个分量为yi0,i=1，…，m。若取进基，记j0列前m个分量为，i=1，…,m。易见,阻碍增大的只可能是〉0的那些约束。
（1） 若≤0对一切i=1，…，m成立（j0列前m个分量中不存在正值），则可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。
（2） 否则,令

则随着的增大，将最先降为零（退出基变量），故只需以为主元作一次消去法运算(称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取x1进基（j=1）而，以y11为主元作转轴运算（高斯-约当消去法运算），得到：

表5.3

x1
X2
x3
x4
x5

基
变
量
x3
1

0
0
5
x4
0

－
1
0
3
x5
0
1
0
0
1
7
rj
0
－1
2
0
0
20
x1=(5,0,0，3,7）T， z1=－20, rN=(r2,r3）=（－1，2)
表5.3中r2 < 0，x1仍非最优解,按yi0/yi2(yi2>0)最小选定 y22=为主元转轴，得到下一个基本可行解x2处的单纯形表表5.4。
表5。4

x1
x2
x3
x4
x5

基
变
量
x3
1
0
1
－１
0
2
x4
0
1
－１
２
0
6
x5
0
0
１
－２
1
1
rj
0
0
１
２
0
26

x2=(2，6，0,0，1）T ， z2=－26， rN=(r3，r4)=（1，2）
对于x2,由于rN= (1，2) 已为非负向量，x2 为最优解，最优目标值为－26。于是,原问题例5.1的最优解x*=(2，6)T，最优目标值为26。
（初始可行解的求法--两段单纯形法）
当线性规划(5.3）的初始可行解不易看出时，可采用下面的两段单纯形法求解。
阶段1（求初始可行基) 对第i个约束引入人工变量 yi,yi≥0,将其改写为ai1x1 +…+ ainxn + yi = bi ，i=1，…,m。作辅助线性规划LP（1）,其目标函数为 .
容易看出,原规划有可行解(从而有基本可行解）的充分必要条件为辅助规划的最优目标值为零.由于辅助规划具有明显的初始可行基（人工变量对应的列构成单位矩阵I），可利用上述单纯形法逐次改进而求出辅助规划最优解。
阶段2 若辅助规划的最优目标值不等于零,原规划无可行解，计算终止。否则我们已求得原问题的一个基本可行解x0。删去阶段1最终单纯表中最后一行及对应人工变量的列,得到原规划对应x0的初始单纯形表，此时又可利用上述单纯形法求解原规划了。
例5.2 min 4x1+ x2+ x3
S.t 2x1+ x2+2x3 = 4
3x1+ 3x2+x3 = 3
x1、x2、x3≥0
解:因为初始可行基不能直接看出，我们采用两段单纯形法求解.
阶段1 先求解辅助规划:
min x4+ x5
S.t 2x1+ x2+2x3 + x4= 4
3x1+ 3x2+x3+ x5 = 3
x1,…，x3≥0
表5.5

x1
x2
x3
x4
x5

基
变
量
x4
2
1
2
1
0
4
x5
③
3
1
0
1
3
rj
－5
－4
－3
0
0
－7

选取x1进基,以y21=3为主元转轴(x5出基），得表5。6：
表5.6

x1
x2
x3
x4
x5

基
变
量
x4
0
－1
4/3
1
－2/3
2
x1
1
1
1/3
0
1/3
1
rj
0
1
－4/3
0
5/3
－2

因r3 <0，令x3进基。以y13=4/3为主元轴（x4出基），得表5。7：
表5。7

x1
x2
x3
x4
x5

基
变
量
x3
0
－3/4
1
3/4
－1/2
3/2
x1
1
5/4
0
－1/4
1/2
1/2
rj
0
0
0
1
1
0

至此,对新的基本可行解检验数均已非负，辅助规划最优解已获得。又因辅助规划最优目标值为0，已求得原问题的一个基本可行解。
阶段2 现转入求解原规划，初始单纯形表为表5.8
表5。8

x1
x2
x3

基
变
量
x3
0
－3/4
1
3/2
x1
1
5/4
0
1/2
rj
0
－13/4
0
－7/2

因 〈 0，令x2进基，以y22=5/4为主元转轴，求得新的基本可行解及相应的单纯形表表5.9
表5.9

X1
x2
x3

基
变
量
x3
3/5
0
1
9/5
x2
4/5
1
0
2/5
rj
13/5
0
0
－11/5
由表5.9可见，检验数已非负，原问题的最优解已经求得,最优解为，最优目标值。
现将线性规划单纯型算法作一个小结.在求解线性规划时,首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（1）写出初始单纯形表;(2）若检验向量 rN≥0，则已得以最优解；（3)任选一负分量rj。以进基，考察所在列。若对i=1，…,m均有≤0，则问题无有限最优解，停；否则令，以为主元转轴，返回（2），直至rN≥0求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。
上述算法中隐含着非退化假设，即要求B-1b > 0。当B-1b也存在零分量时，我们遇到了一个退化的基本可行解，此时rN存在负分量不一定说明现行基本可行解不是最优解。单纯形法也可能会遇到循环迭代.存在着几种避免循环的技巧,例如，只要每次在rj 〈0的非基变量中选取具有最小足标者进基即可避免产生循环。
变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者可以参阅D.G.鲁恩伯杰的“线性与非线性规划引论"一书的第三章。

§5。2 运输问题

（运输问题的数学模型）
例5。3 某商品有m个产地、n个销地，各产地的产量分别为a1,…,am各销地的需求量分别为b1，…,bn。若该商品由i产地运到j销地的单位运价为Cij，问应该如何调运才能使总运费最省？(注：标准的运输问题要求产销平衡，即)
解:引入变量xij，其取值为由i产地运往j销地的该商品数量。例5.3的数学模型为
min
S.t ,i=1,…，m （5.7）
，j=1,…,n
xij ≥ 0
（5。7）显然是一个线性规划问题,当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便方法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法(简称康-希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用最优性准则检验是否为最优，并逐次改进直至最优性准则成立为止。
（初始可行解的选取）
不难发现,(5。7)的约束条件中存在着多余方程（注：将前m个约束方程相加得到的方程与将后n个方程相加得到的方程相同，故约束条将是线性相关的）.容易证明，只要从中除去一个约束，例如最后一个方程，约束条件就彼此独立了.因而,（5。7)是一个具有m×n个变量的线性规划，其每一基本可行解应含有m+n－1个基变量.
记（5.7)约束条件中前m+n－1个方程的系数矩阵为A,A为（m+n－1)×mn矩阵，它的每一列最多只有两个非零元素且非零元素均为1.利用线性代数知识能够判定A中怎样的m+n－1个列可以取为基(即怎样的m+n－1个变量可以取为基变量），为了判明哪些变量对应的列是线性无关的，先引入下面的定义：
定义5。3 (闭回路）｛xij}（i=1，…,m; j=1,…,n）的一个子集被称为一个闭回路,若它可以被排成

其中互异，也互异。
用下面的方法可以较方便直观地看出｛xij｝的一个子集是否为一闭回路：作一个m行n列的表格，令位于该表格第m行第n列的格（i，j）对应xij.将子集中的变量填于相应的格中，将相邻变量（或同行或同列）用边相连，则此子集构成闭回路当且仅当其点按上述连法作出的折线可构成一个闭回路。
例如，当m=3，n=4时，X1=｛x12,x13，x23，x24,x34，x32｝和X2={x12,x14,x24，x21,x31,x32｝ 均为闭回路，见表5。10和表5。11。
表5.10

。
.

。
。

。

。
表5.11

.

。
。

。
。
。

定理5。4 X为{xij｝（i=1,…，m；j=1，…，n)的一个子集，X中的变量对应的A中的列向量集线性无关的充要条件为X中不包含闭回路。
定理5。4不难用线性代数知识证明,详细证明从略。根据定理5。4,要选取（5。7）的一组基变量并进而得到一个基本可行解，只需选取{xij｝的一个子集X，∣X∣=m + n -1且X中不含闭回路，其中∣X∣表示X中的变量个数。
我们用下面的例子来说明如何选取一个基本可行解。
例5。3给定运输问题如表5.12所示，表中左上角的数字为单位运价Cij。易见，本例是产销平衡的,即。
表5。12
销
地
产
地

1
2
3
4
产量
1
2 2
11 ×
3 ×
4 1
3
2
10 ×
3 3
5 ×
9 2
5
3
7 ×
8 ×
1 4
2 3
7
销量
2
3
4
6

现采用所谓“最小元素法"来求一组基本可行解。每次选取一个当前单位运价最小的变量为基变量。开始时，单位运价最小的为C33=1，令x33=min{a3，b3｝=4，并令x13= x23=0（销地3已满足),相应格打“×"（即不再考虑销地3的需求）.产地3已运出4单位,将产量改为剩余产量3。剩余表中单位运价最小的为C11=2（或C34=2），令x11= min ｛a1,b1｝=2,并令x21= x31=0，相应格打“×"，a1改为剩余产量1，…，直至全部产品分配完毕。注意到除最后一次分配外每次只能对一行或一列找“×”，表示某销地已满足,或某产地产品已分配完（注：当两者同时成立时只能打“×”行或列之一，将剩余需求量或产量记为0，此时基本可行基是退化的）。显然这样分配共选出了m + n - 1个变量,且这些变量的集合不含闭回路，从而构成一个基本可行解。当每一基变量xij选取时i产地的剩余商品量与j销地的剩余需求量总不相等时，选出的基本可行解是非退化的.
初始基本可行解也可按其他方式选取，如“左上角法”等，其方法与原理是类似的，左上角法每次选取剩余表格中位于最左上角的变量，其余均相同。
（最优性判别）
类似于单纯形法,可计算非基变量的检验数，存在着多种求检验数的方法（求得的结果是相同的），下面介绍计算简便且计算量也较小的“位势法"。引入m+n个量（被称为位势）u1，…，um；u1,…，un.对每一变量xij,引入rij，令rij=Ｃij— ui—vj（事实上,这一公式与单纯形法求检验数的公式是相同的).对基变量xij，令rij=0，得到
Cij－ui－vj=0 (xij为基变量） （5。8）
齐次线性方程组（5。8)共有m+n－１个独立方程，但含有m+n个变量。任取一个变量，例如u1作为自由变量，便可解出方程组。容易看出,u1的取值不同虽会改变位势的取值但不会改变非基变量的检验数.因此，为方便起见，只要令u1＝０即可。事实上，我们甚至不必去解方程组(5。8），而只需令u1＝０,对所有基变量令ui＋vj＝cij，即cij— ui-vj＝０，在表上逐次求出所有位势,进而再对非基变量xij计算其检验数
（5。9)
例如,对表5.11中取定的基，我们求出位势及非基变量的检验数，列于表5。13中，表中不带圈的数为基变量取值，带圈的数为非基变量检验数,右上角的数为单位运价cij.
表5.13
u1=0
2 2
11 13
3 0
4 1
u1=5
10 ③
3 3
5 －3
9 2
u3=—2
10 ⑦
8 12
1 4
2 3

υ1 = 2
υ２ =－2
υ3 = 3
υ4 = 4

利用线性代数知识可以证明下列各定理(证明从略)：
定理5。5 任取一组非基变量,将其加入基变量集合中，则在所得变量集合中必存在唯一的闭回路,(注：因为加入新的列后得到的列向量组必定线性相关）.
易见闭回路中含有偶数个变量，若令进基，令=θ,为保持平衡条件，位于偶数位置的变量必须减少θ,而位于奇数位置的变量则必须增加θ（注:）。
定理5。6 设是非基变量与基变量集合的并集中唯一的闭回路，若令=θ并在闭回路上调整基变量取值使之平衡，得一可行解x，则x处的目标值与原基本可行解上的目标值之差为。
根据定理5。6，若存在检验数的非基变量,取进基（取正值）并令
（5.10）
则原取值为θ并位于偶数位置上的基变量退基，得一新的基本可行解，其目标值减少。
定理5。7 设为(5.7)的一个基本可行解，若x0所有非基变量的检验数均非负，则x0必为（5.7）的一个最优解。当x0非退化时，此条件还是必要的。
证明 由定理5.6知，当x0所有非基变量的检验数均非负时，任一非基变量进基均不会使目标值减小，由于（5.7)是线性规划，此性质表明x0已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可(必能降低目标函数值）。
综上所述，康-希表上作业法可如下操作:
（步1） 按最小元素法(或右上角法等）求一初始基本可行解。
（步2） 按（5.8）求出位势ui,υj(i=1,…,m； j=1，…,n）。进而按（5.9）求出非变量的检验数rij.若一切rij≥0，则已求得一组最优解。
（步3) 任取〈0，找出进基后形成的唯一闭回路.在找出的闭回路上调整，按（5。10）取θ，得出新的基本可行解，返回步2。直至找到最优解。
对于例5。3，表5。12已给出非基变量的检验数。因r23〈0，令x23进基,得闭回路x23， x24， x34, x33,取θ=min { x24， ｝=2,调整后得到一个新的基本可行解.求出新的基本可行解对应的位势及非基变量检验数，列成表5.14。
表5。14
u1=0
2 2
11 11
3 ①
4 1
u1=3
10 ⑤
3 3
5 2
9 ②
U3= －1
7 ⑥
8 ⑨
1 2
3 5

υ1 = 2
υ２ = 0
υ3 = 3
υ4 = 4

现在，非基变量检验数均已非负，故已求得最优解:x11=2,x14=1，x22=3，x23=2，x33=2,x34=5，其余=0(非基变量）。
若运输问题是产销不平衡的,则应先将其转化为产销平衡的，然后再求解。例如，若产大于销，可虚设一销地(剩余产量存贮），将各产地运往该虚设销地的单位运价均取为零;若供不应求，则可虚设一个产地,产量为零,且由该产地运到各个销地的单位运价均取零.通过这种虚设产地或销地的方法即可将一个非标准形式的运输问题转化为标准形式的运输问题，从而可用上述康-希表上作业法加以求解。

§5.3 库 存 模 型

库存管理在企业管理中占有很重要的地位.工厂定期购入原料，存入仓库以备生产之用;商店成批购入各种商品,放在货柜上以备零售；水库在雨季蓄水，以备旱季的灌溉和发电；但是,细心的读者会发现，这些情况下都有一个如何使库存量最优的问题，即库存量应取多大才最为合适？存储量过大,存储费太高；存储量过小,会导致一次性订购的费用增加，或不能及时满足需求而遭到损失.为了保证生产的连续性和均衡性，需要确定一个合理、经济的库存量，并定期订货加以补充，按需求发放，以达到压缩库存物资、加速资金周转的目的。
为说明方便，我们先简要说明有关的概念,然后介绍几种比较简单的库存模型和解法。
我们知道，工厂和企业作为一个系统,其基本功能是输入、转换和输出。输入过程也叫供应过程，输出过程也称为需求过程。为保证生产正常进行,供应的数量和速度必须不小于需求的数量和速度，多余的数量可储存于各部门的仓库里。企业的仓库按生产供应和需求对象的不同，可大致分为两类：
1． 原材料库：用于存放生产所需的各原材料的仓库,这些原材料大多是由物资供应部门定期向外采购而来的，当然，也可以是企业自己生产的。这类仓库的库存费用由采购费和保管费两部分构成，即

2． 半成品库和成品库。用于存放经过生产加工而成的半成品和成品的仓库.这类仓库的最大存储量一般就是生产批量，而库存费用由工装调整费和保管费两部分构成，即

易见，随着生产批量的增大，计划期（年）内投产的批数减少,工装调整的次数减少，工装调整费下降，但库存量增加，保管费用上升。因此,为降低库存费用,必须确定一个经济批量（或经济批数），使库存费用最小。
由上所述可见：在讨论库存问题时，涉及到三种费用：
（1)采购费是供应部门处理订货、补充库存所需的费用,包括采购人员的差旅费、手续费、检验费等.它属于一次性费用，直接与计划期内的采购次数或一次采购量有关，计算公式为

这里为计划期（年、季或月）内的总需要量,为每批批量,为一次采购费用。
（2）工装调整费是指每批产品投产前的工艺准备、设备调整及其检修所需的费用。属于一次性的费用，它与计划期内投入的批数有关，计算公式为

其中为计划期内的总产量，为生产批量，为一次工装调整费用。
（3）保管费包括仓库建筑费和设备折旧、管理费、搬运费、保管期内的物资损耗费和库存物资折算成资金的利息等，保管费的计算方法与保管方式、消费方式等等有关，假如消费
速度是均匀的，通常可用下面的公式来计算

　其中为平均库存量，为单位物资在计划期内的保管费,单位物资有时按重量计，有时按占用仓库的面积(或体积)计，是具体情况而定.由于单件保管费有时计算起来比较困难，也可用保管费率计算，为保管费占总库存费的百分比,这时公式可以改写为

这里为库存物资的单价,为平均保管费率。
　　应该指出的是：保管费是一项可观的、不可忽视的费用,依据70年代中期美国十大公司的统计，它约占总库存物资资金的20％，其中以库存物资资金的利息占的份额最大。
下面我们分几种情况来说明几种较为简单的库存模型

一． 瞬时送货的确定型库存问题（不允许缺货的情况）
首先考虑最简单的库存问题。假设某工厂生产需求速率稳定，库存下降到零时，再定购进货，一次采购量为，定购点的提前时间为零（即进货有保障、有规律，可根据需求提前订货），在保证不缺货的条件下，试确定最经济的采购量，使库存费用最小。
此时库存费用为

在本模型中，平均库存量为常量，所以问题归结为求解如下的优化问题

这是一个一元函数求极小值的问题，可用微积分方法求其最优解,求得的解为
=
这就是所要求的经济采购量。而库存的最小费用为

经济学上称这两个公式为平方根公式。

二． 非瞬时送货的确定型库存问题（不允许缺货的情况)
在本模型中,由于运输设备等的限制，经常会出现非瞬时入库的情况，即从再定购点开始的一段时间内，一方面按一定进度入库（设为定购物资每天入库的数量），另一方面按生产需要出库（设为定购物资在入库期内每天出库的数量），直到达到最大库存量为止.设模型的其他参数不变，试确定经济采购量和最小库存费用.
易见为定购物资的入库时间（天）,所以最大库存量为
=
平均库存量为
因此保管费为
库存费用为

所以这一类库存问题归结为求解

这仍然是一个一元函数求极小值的问题，用微积分方法求得最优解即经济采购量为
=　　　　　　　　
而最小库存费用为
=　　　　　　
对于成