与a,交换它们的列指标,变成a,与a,其结果该二子圈便合成一个圈,该变化用图简示,则为 由图可知,此四元素形成一矩形,调整是把该矩形原先对角线上的二画圈元素an与an的圈转给了 另一对角线上的二画圈元素an与a。显然,调整结果,目标函数将增加 (air +as)-(a+as,) 考虑所有可能的对调调整,取其中增值最小的,加以调整,便破掉一圈。如此进行,直到无子圈为 止 对于大规模问题,求最短调整路线可用标号算法,详见文献[η 例1.已知五个城市间的距离如下表所示,求旅行商的最短路线 3×567 (1°)先求出相应分配问题的最优解:(用最小调整法) 34 3(4)25 3.×567 ×567 → ×56 2)6 265×(4 764 576 故此例的分配问题最优解为a13,a2a21,a45,as,转(3°)。 检验结果,此方案形成两个子圈:(a32a12,a21),(a5a54)
15 与 st a ，交换它们的列指标，变成 it a 与 sj a ，其结果该二子圈便合成一个圈，该变化用图简示，则为 ij a st a it a sj a → ij a st a it a sj a it a 由图可知，此四元素形成一矩形，调整是把该矩形原先对角线上的二画圈元素 ij a 与 st a 的圈转给了 另一对角线上的二画圈元素 it a 与 sj a 。显然，调整结果，目标函数将增加： ( ) ( ) a a a a it sj ij st + − + 考虑所有可能的对调调整，取其中增值最小的，加以调整，便破掉一圈。如此进行，直到无子圈为 止。 对于大规模问题，求最短调整路线可用标号算法，详见文献[7]。 例 1．已知五个城市间的距离如下表所示，求旅行商的最短路线。 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 A = （4） （1º）先求出相应分配问题的最优解：（用最小调整法） 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 → 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 （5） 故此例的分配问题最优解为 13 32 21 45 54 a a a a a , , , , ，转（3º）。 检验结果，此方案形成两个子圈： 13 32 21 45 54 ( , , ),( , ) a a a a a
城市3 城市1(413 as4城市5 容易看出,在两个圈中任意各取一个元素,交换它们的列下标,则这两个圈便合成一个圈 例如,将第一个圈中的a13与第二个圈中的a45的列下标对调(或交换),便成为: 4354 此 1s,als4:443,al2 于是便破掉一个圈,此例经此处理便得到一个可行方案。在(5)中上述处理相当于:若把分属于不 同圈中的两元素看成为矩形一对角线的二顶点,则其圈调换给了该矩形另外两个对角顶点对应的元 素,即 342 5 4(5× 265 26 4 576(4) 576 调整的结果将导致目标函数(总路程)的增加。若每次对调都选择增值最小的进行,当所有的子圈 全被破掉后,即得原问题的一个更好的解。 此例中的最优解为:(对调增值为0) 34(2)5 5/67 4(5 56 26 4 57(6)4 由此最短路线即为:1→>4→>5→3→2→>1,f=20,此问题的解不唯一,另一条是 1→2→>3→5-4→1,它不能通过一步对调调整得到 例2,设旅行商的关系矩阵为(8),求最优解。 16
16 容易看出，在两个圈中任意各取一个元素，交换它们的列下标，则这两个圈便合成一个圈。 例如，将第一个圈中的 13 a 与第二个圈中的 45 a 的列下标对调（或交换），便成为： 15 32 21 43 54 a a a a a , , , , 此即： 15 54 43 32 21 a a a a a ,,,, 于是便破掉一个圈，此例经此处理便得到一个可行方案。在（5）中上述处理相当于：若把分属于不 同圈中的两元素看成为矩形一对角线的二顶点，则其圈调换给了该矩形另外两个对角顶点对应的元 素，即： 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 → （6） 调整的结果将导致目标函数（总路程）的增加。若每次对调都选择增值最小的进行，当所有的子圈 全被破掉后，即得原问题的一个更好的解。 此例中的最优解为：（对调增值为 0） 3 4 2 5 3 5 6 7 4 5 5 6 2 6 5 4 5 7 6 4 （7） 由 此 最短 路 线即 为： 1 4 5 3 2 1, 20 → → → → → = f ， 此 问 题的 解不 唯 一， 另一 条 是 ： 1 2 3 5 4 1 → → → → → ，它不能通过一步对调调整得到。 例 2，设旅行商的关系矩阵为（8），求最优解。 a45 城 市 4 a54 城 市 5 a13 a32 a21 城 市 1 城 市 3 城 市 2
2743163026 2013×3552 (8) 211625×1818 462748 5 求解过程图示如下 ×274313026 2743163026 16 3025 7)×1613025 A→2013×3562013x352 21625 1818 1818 12462748×5 12462748×( 5)95 235(5)95 得到相应分派问题最优解 a14,a42,a21,a35,a5,a63,但其中有二个子循环, 2743 3026 实行最小对调调整 1613025 )|2013 35(5)2 2116(25)×1818 12462748 23 检验(3°)成立,故得较好的可行解:a14,a43,a352a56,aa2,a21,它实际上是最优解,可通过对相应 分派问题最优解按増值最小的原则继续调整得到并加以验证。当问题规模较大时,寻找最短调整路 线可像最短路那样实行标号算法。 当松弛问题的最优解有较多的圈时,破圈需涉及较多的矩形,可以证明,当问题的规模为η时, 所涉及的总的矩形数不超过n2,总的计算量不超过3n2,可见此算法相当有效。 对调调整对于破圈来说简单而有效,但其增值最小却又仅限于所有对调调整所破的圈,并不包 括其他非对调调整所破的圈,换句话说,既能破圈而又增值最小的路线未必一定是对调调整路线 因此,我们得到的解只是近似解 由最小对调调整得到的可行解虽然未必是最优的,但也是较好的可行解。设x为最优解,x°是 相应松弛问题一一分派问题的最优解,x是对调最优解,则有f(x0)<f(x)≤f(x),若 f(x)-f(x°)不是很大,或可以接受,则x便可以作为可接受的近似解使用
17 27 43 16 30 26 7 16 1 30 25 20 13 35 5 2 21 16 25 18 18 12 46 27 48 5 23 5 5 9 5 A = （8） 求解过程图示如下： 27 43 16 30 26 7 16 1 30 25 20 13 35 5 2 21 16 25 18 18 12 46 27 48 5 23 5 5 9 5 A → → 27 43 16 30 26 7 16 1 30 25 20 13 35 5 2 21 16 25 18 18 12 46 27 48 5 23 5 5 9 5 得 到 相 应 分 派 问 题 最 优 解 ： 14 42 21 35 56 63 a a a a a a , , , , , ，但其中有二个子循环， 实行最小对调调整。 检验（3º）成立，故得较好的可行解： 14 43 35 56 62 21 a a a a a a , , , , , , ，它实际上是最优解，可通过对相应 分派问题最优解按增值最小的原则继续调整得到并加以验证。当问题规模较大时，寻找最短调整路 线可像最短路那样实行标号算法[7]。 当松弛问题的最优解有较多的圈时，破圈需涉及较多的矩形，可以证明，当问题的规模为 n 时， 所涉及的总的矩形数不超过 2 n ，总的计算量不超过 3 2 n ，可见此算法相当有效。 对调调整对于破圈来说简单而有效，但其增值最小却又仅限于所有对调调整所破的圈，并不包 括其他非对调调整所破的圈，换句话说，既能破圈而又增值最小的路线未必一定是对调调整路线。 因此，我们得到的解只是近似解。 由最小对调调整得到的可行解虽然未必是最优的，但也是较好的可行解。设 x 为最优解， 0 x 是 相应松弛问题——分派问题的最优解， x 是对调最优解，则有 0 f x f x f x ( ) ( ) ( ) ，若 0 f x f x ( ) ( ) − 不是很大，或可以接受，则 x 便可以作为可接受的近似解使用。 → 27 43 16 30 26 7 16 1 30 25 20 13 35 5 2 21 16 25 18 18 12 46 27 48 5 23 5 5 9 5
若不然,可以对x°继续使用最小调整法,以便求得最优解,其最小调整路线的求法仍可归结为 求最短路,但考虑到最短路线可能不减少(有时甚至增加)圈,故要做些限制,即在调整后圈必须 减少的限制条件下求最短路,为此需要给出某一调整是否减圈的判别方法,此问题正在研究中。 §4投入产出方法 投入产出方法是考察各种经济活动的投入与产出之间的数量关系的一种方法,于本世纪三十 年代产生于美国,创始人列昂节夫因之获得73年诺贝尔经济科学奖,近年来有很大发展,目前已普 遍地用来研究和分析国民经济各部门之间的数量依存关系、计划和安排未来的经济活动、预测和分 析采取一项重要经济政策的经济后果研究和计算产品的价格形成等,在实践中取得一定效果,我国 曾编制了1973年国民经济投入产出表 投入:指从事一项经济活动的消耗,如原材料、能源、机器设备和人的劳动等。 产出:指经济活动的结果,如产品等 模型分静态和动态二种类型,下表是静态价值型投入产出表。 中间产品 最终产品 总产品 合计消费新固定库存及合计 12 资产进出口 (I) X X X X 资料转移价值 X 折旧 新劳动报酬|v吃 () 创造价值 社会纯收入 MM 合计 总产品 表中X表示第i个部门的产品用作第j的部门生产消耗的数量 Ⅰ)反映各部门之间的生产技术联系,相互提供劳动对象(如原材料、辅助材料、燃料 动力等)的情况,是编表和计算的基础(如计算直接消耗系数a= 等) (Ⅱ)反映最终产品的构成及使用(分配),其中∑yi即为社会最终产值或国民生产总值, 数量上它等于国民收入加上本年度的固定资产折旧额之和:∑y=∑(D+H+M)
18 若不然，可以对 0 x 继续使用最小调整法，以便求得最优解，其最小调整路线的求法仍可归结为 求最短路，但考虑到最短路线可能不减少（有时甚至增加）圈，故要做些限制，即在调整后圈必须 减少的限制条件下求最短路，为此需要给出某一调整是否减圈的判别方法，此问题正在研究中。 §4 投入产出方法 投入产出方法是考察各种经济活动的投入与产出之间的数量关系的一种方法，于本世纪三十 年代产生于美国，创始人列昂节夫因之获得 73 年诺贝尔经济科学奖，近年来有很大发展，目前已普 遍地用来研究和分析国民经济各部门之间的数量依存关系、计划和安排未来的经济活动、预测和分 析采取一项重要经济政策的经济后果研究和计算产品的价格形成等，在实践中取得一定效果，我国 曾编制了 1973 年国民经济投入产出表。 投入：指从事一项经济活动的消耗，如原材料、能源、机器设备和人的劳动等。 产出：指经济活动的结果，如产品等。 模型分静态和动态二种类型，下表是静态价值型投入产出表。 中间产品 最终产品 总产品 1 2 n 合计 消费 新固定 资产 库存及 进出口 合计 生 产 资 料 转 移 价 值 1 2 n 小计 11 12 1 21 22 2 1 2 ( ) n n n n nn X X X X X X I X X X （ II ） 1 2 n Y Y Y 1 2 n X X X 固定资产 折旧 合计 D D D 1 2 n 新 创 造 价 值 劳动报酬 社会纯收入 合计 V V V 1 2 n M M M 1 2 n ( ) III ( ) IV 总产品 X X X 1 2 n 表中 Xij 表示第 i 个部门的产品用作第 j 的部门生产消耗的数量。 （Ⅰ）反映各部门之间的生产技术联系，相互提供劳动对象（如原材料、辅助材料、燃料、 动力等）的情况，是编表和计算的基础（如计算直接消耗系数 ij ij j X a X = 等） （Ⅱ）反映最终产品的构成及使用（分配），其中 = n i 1 yi 即为社会最终产值或国民生产总值， 从数量上它等于国民收入加上本年度的固定资产折旧额之和： n n i 1 i 1 ( ) i i i i y D V M = = = + +
(Ⅲ)反映社会最终产值即国民生产总值的价值形成过程,它包含二个内容,一是固定资产 折旧,二是新创造价值(其中社会纯收入由利润税金等组成)。 (Ⅳ)反映国民收入的再分配 从水平看有关系式: x+y1=X1,i=1,2……,n 将X=anX代入,并写成矩阵形式,可得: X=(1-A)y 其中A是直接消耗系数矩阵:A=(an)m,上式表明根据最终产品的需要量Y即可算出总产 品产量X应是多少(以销定产) 从垂直方向看有如下关系式: ∑X+D+V+M,=X,j=12,…,n 这个式子的经济意义为各部门的产值等于中间产品转移价值、固定资产折旧、劳动报酬和社 会存收入之和,引入直接消耗系数a 写成矩阵形式,可得: X=(1-C)(D++M) 其中C是对角阵,其对角线上第i个元素为C=∑a。当已知C及各部门D、V、M的数值后, 即可算出各部门总产量X的数值来。 投入产出方法的发展趋势,一是与数学规划结合,编制最优表(把上述方程组看作基本约束 再补充一些其它约束,求一个目标函数的最大值)二是进一步与经济计量学结合。 §5决策论 决策是人们工作和生活中普遍存在的一种活动,是为解决问题选择最佳方案的一种过程。决策 效果的好坏,关系重大。它是管理过程的核心,因此决策者必须掌握科学的决策原理和方法 一般说来,每一实际问题经常可能面临几种不同的客观环境,它不以人的意志而改变,称为自 然状态(全体自然状态的集合记为I,简称状态集);又有几种不同的行动方案(所有可供选择的行 动方案之集合记为D,简称行动集):人们希望通过对各个方案在每一状态下可能产生的效果(称为 后果,用C表示)进行综合分析、比较,进而选定一个最优方案加以实施。这就提出了决策问题 例1.某农场考虑是否提早种植某种农作物的决策问题,详情见下表 状态 不遇霜冻 遇霜冻 提早种 不提早种
19 （Ⅲ）反映社会最终产值即国民生产总值的价值形成过程，它包含二个内容，一是固定资产 折旧，二是新创造价值（其中社会纯收入由利润税金等组成）。 （Ⅳ）反映国民收入的再分配 从水平看有关系式： n j 1 , 1,2, , X Y X i n ij i i = + = = 将 X a X ij ij j = 代入，并写成矩阵形式，可得： 1 X I A Y ( )− = − 其中 A 是直接消耗系数矩阵： ( ) A a = ij n n ，上式表明根据最终产品的需要量 Y 即可算出总产 品产量 X 应是多少（以销定产） 从垂直方向看有如下关系式： n i 1 , 1,2, , X D V M X j n ij j j j j = + + + = = 这个式子的经济意义为各部门的产值等于中间产品转移价值、固定资产折旧、劳动报酬和社 会存收入之和，引入直接消耗系数 ij ij j X a X = 写成矩阵形式，可得： 1 X I C D V M ( ) ( ) − = − + + 其中 C 是对角阵，其对角线上第 i 个元素为 1 n ij ij j C a = = 。当已知 C 及各部门 D、V、M 的数值后， 即可算出各部门总产量 X 的数值来。 投入产出方法的发展趋势，一是与数学规划结合，编制最优表（把上述方程组看作基本约束， 再补充一些其它约束，求一个目标函数的最大值）二是进一步与经济计量学结合。 §5 决策论 决策是人们工作和生活中普遍存在的一种活动，是为解决问题选择最佳方案的一种过程。决策 效果的好坏，关系重大。它是管理过程的核心，因此决策者必须掌握科学的决策原理和方法。 一般说来，每一实际问题经常可能面临几种不同的客观环境，它不以人的意志而改变，称为自 然状态（全体自然状态的集合记为 I，简称状态集）；又有几种不同的行动方案（所有可供选择的行 动方案之集合记为 D，简称行动集）；人们希望通过对各个方案在每一状态下可能产生的效果（称为 后果，用 C 表示）进行综合分析、比较，进而选定一个最优方案加以实施。这就提出了决策问题。 例1． 某农场考虑是否提早种植某种农作物的决策问题，详情见下表。 状态 后果 行动方案 不遇霜冻 遇霜冻 提早种 不提早种 45 30 10 20