运输问题悖论及其出现的条件①.pdf

第 2 O卷第 1期 8 0 0 1年 3月 新疆 师 范 大 学学 报，(自然科 学 版)J o ur n o f Xi n j b mg No r ma l Uni v e r s i t y (Na t ur s l Sc i e n c e s Ed i t i o n)v0 J 2 0，No 1 M ar 2001 运输 问题悖论及其 出现 的条件 文 平(新 一时 蛏学 院基柚 每 乌 术 齐 8 3 0 0 1 2)摘 要 车丈提出了运糟同题的奇特理簟运糟问置悖论，井筑退化运问厦和非退化运输同 曩悖 论 出现 的基 件进 行 了讨论 摹 词运问置蕞盈墓壹量 中圈分类 号 o z 2 1 文献 标识 码：A 文章编 号：1 0 0 8 9 6 5 9(2 0 0 1)0 1 0 0 1 6 0 4 1问 题 的 提 出 为 先 看一 个例 子 例 1 最优 运输计 划 表如下 A l B1 B2 B3 l 3 2 2 3 1 l 4 4 6 2 4 9 最优值为。一3 6 现将 产 地 A1的产 量增 加 2个 单位，销 地 B2的销 量增 加 2个单 位，则 最 优运 输计 划 表 A l Bl B2 B3 i 3 2 2 5 3 l 4 6 4 收 薯 日期 2 O 一9 2 8 2 6 9 7 维普资讯 http:/ 第 1期 文平 运 输 问 题悖 论 及其 出现 的条 件 1 7 最优值为 ：3 4 从 上 面例 子可 以看劐；在产 地、销地、单位运 价均 相 同的情 况下，运 输总 量增 加 了 2个 单 位，但 总运 价却 减少 了 2个单位，这种奇 特 的现象称 为运 辖 问题悖 论。2非退化运 输 问题悖论 出现 的条件 弓 l 理 l 设】【i o 是一 个 非基变 量，则一 定 可 以找到 若 干个基 变量 再 _ I，x i ，x ，与 构 成一 个闭 回路。I 理 2 设 是一非 基变 量。和基 变量 I J l，x t 构成 一个 闭 回赂，当第 个 产 地增 加产 量 Y，第 j。个 销地 增加销 量 Y，且 Y 满足 Ymi n x。_)，是 闭 圆路上 的奇点 t 则原 来 的基变量 仍 是基变 量 t 原来 的非 基变量 仍是非 基变 量。证 明：设 x j 是运 输 问题的 最优解，则存 在 常数 u ，u “u v _，v：v。满足。x a。(i 1，2 m)、2 5x ，b，(j 1，2 n)(u。+v )一 O X ii 11-o (i l，2 n)现 在 x 所 在 闭 回赂 的偶 点上 加 Y，在 奇点 是减 Y，而其 它 值 不 变，这样 就构 成 了一 组 新 的 x (i 1，2 m j=l 2 n)且 x I 满 足。厶 x =a (i i 0 t i 1 2 )厶 x a。0+Y(i=i 0)厶 x =b (j ，i l t 2 m)厶 x ：b +Y(j j 0)(u +j)-C 0 (i 1，2 t r i o t j l 2 n)又 Y-mi n x l j)，是 X io j 所 在闭路 上 的奇点 故 x O，(i l 2 m j 1，2 n)所 以最优 解 只发生值 的变 化。但其 变量仍 是其变 量非其 变 量仍 是非基 变 量。定 理 1 设 x ，是运 辖 问题 的最优 解 涵 上 一非基 变量，若。+O，则 当 a”b l o 同 时 增 加 Y，总运 价不会 增加。特 别 当 i o j o+c 0时，总 运价 减 少，其 中 Yrai n )，是 闭 回 路 上 的奇点。证 明 0 j 0 是一 个非 基变 量，由引理 1，存在若 干 变量”，X i i k 与之 构成 闭回赂，当 a ，b j o 同时增加 Y 时 t 让闭 回路 上 的偶点 增 加 Y，奇 点(不 包括 x 。)减少 Y，由 引理 2，原来 的 基变 量仍 是基变 量，只不过值 发生变 化而 已，现在来 看 总运价：一 一，Y一 Y 目 目鼻 f直=(+)Y 维普资讯 http:/ 新 疆师 范 大 学 学报(自然科 学 版)O 1年 故 当 0 j 0+c O时，总运 费 不增。特别+c 0 j 0 O时，总运费 下 降。简 育之 在非 退 化运 输问 题 中，当某个 非基 变 量 的检 验数 加 上非 基 变量 的单 位运 价小 于 等于 0时，就 会 出现运量 增加，总运价不 增 的现象。3退化运输 问题悖论 出现 的条件 例。倒 2 最优 运 输计划表 如 下 A 1 A 2 B1 B2 B3 2 4 1 2 5 2 5 1 3 1 3 3 最优值为 c ix。一1 8 2 5 由定理 一 可知，产地 A1的产量，销地 B2的销量 同增 1 个 单位，则最优 化 运输 计划表 为 B1 B2 B3 A 1 A 2 2 4 l I 3 5 2 5 1 4 O 4 3 3 5 最优值为。，一1 6 现考察 两个 非基 变量，均不 满 足定理 一的条件，我们 自然要 阅，悖论 还会 出现 吗?请 看下 倒 3 产地 A1的产量，销 地 B 2的销量 同增 1 个 单 位，则最优 化运 输 计兜 表 为 B1 B2 B3 A 1 A 2 I。4 l 0 3 5 2 5 5 5 3 最优值为 c i 一 1 5 从例 3可知悖 论还 会 出现 定理 2 设运 输表 是一 最优运 输计划，非 基 变量 满足 4 5 维普资讯 http:/ 第 l期 文平 运 输 问 题悖 论 及 其 出现 的 条件 l 9 1)m+e O 2)存 在非基 变量 X l I I I 和 X i lt i O 组成 回路(此 时 m作 基 变量对 待)使+O 同时 增 加 Y 使 总 运 价增 加 了 e i o l o Y，现 又通 过 改变 基 变 量 使 总 运 价减 少 了 I l Y 因为 _ I c 所 以总 运 价减 少。1 蕾 答 睦性 规 捌 山东 大 学 出版 杜 2 运 筹 学 清华 大 学 出版杜 参 考文 献 Re s e a r c h o n t h e Co n t r a d i c t i o n o f Tr a n s p o r t a t i o n Qu e s t i o n s w e n P_ n (Xi n j i a n g Fi n a n c e a n d Ec o n o mi c s Co l l e ge)Ab s t r a c t The p a p e r g i v e s t he c o n d i t i o ns wh e n t h e c o n t r a d i c t i o n o f t r a n s p o r t a t i o n q u e s t i o n e me r g e s a nd d i s c us s e s i t s e me r ge n c e Ke y wo r d s Tr a n s p o r t a t i 0 n q u e s t i o n M o d e l Ba s i c v a r i a b l e 维普资讯 http:/