（系统工程专业论文）库存管理和随机规划中的若干问题研究.pdf

摘要 本报告研究库存管理和随机规划中的一些问题 在第一章我们研究了在定时信用支付条件下的e o q 问题在同样的 模型环境中，得到了当2 时，c a r l s o n 和r o u s s e a u 的猜想( + ) 不成 立的充分性条件，并用反例验证了当a k 2 、m = 3 时，该猜想不成立 猜想( + ) ：在定时信用支付条件下，如果m 次订购恰好满足个月 的需求，那么等量订购是最优订购策略，这里m 和互素 第二章研究了费用参数发生变动的有限时域e o q 问题彻底解决了 美国( 前) 管理科学协会主席l e v 的有限时域中的库存管理问题，从而 将此前许多学者包括l e v 在内的工作大大地改进或者纠正 第三章研究了允许延期付款的多阶段货价变动型存贮问题，得到了 最优订购策略并设计了算法以说明模型的使用 第四章研究了在供应链中成员企业进行协作情况下的库存模型，并得 到了最优订购策略我们提出的以供应商提供信用为基础作为协作机制 的思想为今后进一步研究供应链的整合问题提供了新的思路 第五章对随机多目标规划的弱有效解的逼近性进行了分析，证明当 随机向量序列( f ” ) ) 分布收敛于f ) 时，相应于f ( c o ) 的随机多目标 规划的任何弱有效解序列将逼近于原问题的某个弱有效解，这个结果为 如何设计逼近算法提供了一个理论基础 第六章对概率约束规划问题的稳定性作了探讨，得出了当随机矢量 序列 2 时，由于巩，= ( 七一鲁) + 号笋与，无关，表明同一个月中每 次订购量相等；又由于以。一d k ，= = 挚= 常数，说明后一个月每次订购 量比前一个月每次订购量按相同的量递增，而且递增量为翕= 卺。 因此可不妨设第一个月的每次订购量恰好满足d 天需求，于是第i 个月每 次订购量可满足卅( f 一1 ) a 天需求( 卢1 ，2 ，) 由，1 + 2 + 十厶尸m 可得： i v 。】+ 艿( v 1 ) + v 2 卜占( v 2 ) + i + v 肛1 】+ 文v 。一1 ) + v 。= 彤 ( 1 ，2 。1 1 ) 其中 c x ，= ：的整数部分：，ac x ，= ：二三：； v 。= 了3 0 ； 鑫象 班一群班一 v ：型：! ! 垡二生堕盟二：! ：二丛垡型二! 幽 。d + ( f 一1 ) “ ! 一l 3 0 f 一( f i ( d + ( t 一1 ) ) ) = 生生一 d + ( f 一】) 由于m 与互素，因此只有最后一个月的最后一次订购可恰好满足完该 月的需求，所以 3 0 n k ( d + ( 一1 ) ) ，女= 1 o 2 再两j f 。 ，。= v 。+ 5 ( v a ) = 【等 + 占( 詈) = 【詈 + 1 其它各月t = i v 。】+ 6 ( v 。) ( f - 2 , 3 ，n 一1 ) f 值之所以是v ，取整再加5 ( v ) 这 一项，主要是因为当v 0 时，第i 月订购货次数为零，说明了该月以订 购量蠡( d + ( f 1 ) ) 订购的次数为零；g _ g e 情形在m 2 ，：挚 0 ，若方程( 1 2 1 1 ) j 2 有大于零的解d ，则说明以，= d + ( 红1 ) 爿为最优订购方式( 妊1 ，2 ， l = 1 ，2 ，f ) 这意味着此时不可能是由等量订购来保证总费用最低，亦即 此时猜测( + ) 不成立由此，我们得下述结论： 定理1 , 2 1 在假定的模型环境中，对于给定的口 o ，m ，2 ，( m 、 互素) 若方程( 1 2 1 1 ) 有解孑 0 ，则最优订购策略为： 第1 个月第，次订购为未孑：蠹( ，= 1 ，2 ，3 ，【号】+ 1 ) ，订购时间为 一1 ) 孑；第i - 个- 户1 第j 次订购量为羔( 孑+ ( f 一1 ) p ) 订购时间为 x “l 。( d + ( i 一1 ) ) ) + ( j 一1 ) ( 孑+ ( f 一1 ) ) ( f = 2 ，3 ，= 1 ，2 - ，。) ，这里= 三粤， 此时猜测( + ) 不成立 特别地当n = 2 ，m = 3 时有 推论1 2 2在定理1 2 1 的模型环境中，对于n = 2 和m = 3 ，若 e ( o ，妻) ，则方程( 1 2 1 1 ) 必有解，从而此时猜测( 4 ) 不成立 f 2 二 证明：仍记：3 0 i _ _ a l ，则有方程： ”+ 等：和+ 掣挚矗 2 可以断定 詈 2 ，否则由( 1 2 1 2 ) ) i nd = 2 0 ，可得 警 = l ，矛盾于是从 ：6 0 - 石3 d ( 1 2 1 3 ) 胪鬲 。 扯嚣 o ，解之郫划 2 o ，毗 且 0 6 删s 扎2 精娟捌钔嘲 o ，b 0 ，m 是整数，并设衍为m i n i m i z e f ( m ) 的最优解那么 m ： m = m a x ，o ) ，特别地如果c 彰爿+ 口2 4 4 2 一b o ， 那么m = o 这里 表示大于或者等于x 最小整数 证明：首先我们证明对固定的卅o ，如果足m + 1 ) 只掰) ，那么就有 只掰+ 2 ) 只川+ 1 ) 由k m + 1 ) f ( 埘) ，我们可得 f ( m + 1 ) 一f ( 川) = a c 以“珊日+ a + 6 ) ( 口+ 6 ) ) 0 因为c 0 ，a 0 ，b o ，所以 f ( m + 2 ) f ( m + 1 ) = a - c a ( ( m a + 2 a + b ) ( m a + + 6 ) ) a - c a ( ( m a + 口+ b ) ( m a + 6 ) ) 0 上海交通大学博士君研究工作报告 考虑到当o 6 d 时，尺垅) 是严格凸的因此我们有 = m a x r a i n 删lf ( 研+ 1 ) 尺垅) ，0 ) = m a x m i n 珊i ( m a + a + b ) ( m a + b ) c a a ) ，0 ) = m a x m i n m l m ( 吲爿+ a 2 4 - a 2 6 ) 屈) ，0 ) = m a x ，o 特别地，如果# c w a + a 2 4 一a 2 一b o ，那么聊+ = o 证毕 2 2 最优策略结构分析 第一次订购的货物在第一时域的初始时刻达到令朋为在时域 o ，t ) 中的订购次数；为在第二时域亿爿 e p i , t 购的次数，此外在丁时刻可能 存在一次订购设疋为在r 时刻订购货物的消耗时间：1 ，f 为时域【o ，t ) 中第i 次订购量的消耗时间；t 2 ，为在第二时域伍日】中第次的订购量的 消耗时间我们可以得到对应于消耗时间l ，和兀订购的各种相关费用 分别为 女i = a t 七h t d t j j ：| 2 + p ，d t t i j = a i + 而d 巧2 + p 1 d 冗 因此与b p e 1 策略的相对应的总费用为 缸+ ，+ 黔z ， ( 2 2 1 ) 同样与t y p e 2 策略的相对应的总费用为 黔+ 黔：， ( 2 2 2 ) 下面我们就t y p e l 和t y p e 2 这两种情形分别来研究相应的最优订购策 略 ( i )t y p e l 策略研究 由于在这种情形下，库存在丁时刻为零，因此 “一r 势2 + 兀：h t ( 2 2 3 ) ( 2 2 4 ) 这样我们可以得到下面的最优化问题： m i n i m i z em i n i m i z e 黟+ 五十黟：一 ( 2 2 5 ) n m 劲“，劲，n 。r 2 ，j 0 t 2 l刮 一1 2 对于固定，2 1 ，m 0 ，我们先考虑 m i n ，i m i z e 缸l + + 墨：， d 1 1 j ，d27 ，= jj = 】 ib = r 文l 1 i = l + 五：日丁。 l ，= 1 不妨设尤和，( 1 ( n ，m ) 分别为( 2 2 6 ) 的最优解和最优值 们构造拉格朗日函数如下： l ：苎y + 乒+ 苎y ：，+ a 。( 势丁) + 五：( 兀+ 竞r 2 , j - ( h 丁) ) i = 1 = 1 1 i = l j = l 对三用 ，和见分别求偏导得 o l a t , ，- = h l d t l 、+ p i d + 五i = 0 ，i = 1 ，2 ，聍 o l a r , = h t d t ；+ 尸i d + 丑2 = 0 o l o t2 ，= h 2 d t 2 ，j + p 2 d + 五2 = 0 ，产1 ，2 ，m o l o a i = d 一t = 0 叫a 五2 = 努2 ，+ l 一( ，) = 0 = l 将( 2 2 8 ) 的门式子相加，并将( 2 2 11 ) 代入得 l = 一( h l d t + n p i d ) n ( 2 2 6 ) 由( 2 2 6 ) ，我 ( 2 2 1 2 ) 把上面兄- 的表达式代入( 2 2 8 ) 中的每个式子得 t i ，一t n( 卢l ，2 ，厅) ( 2 2 1 3 ) 由( 2 2 9 ) 知正= ( 2 2 + d p o d h l ，再由( 2 2i o ) 矢ht 2 严一( 丑2 + d p 2 ) d h 2 因 此由( 2 2 1 2 ) 我们有 a 2 = - ( _ d ( h t ) h l h 2 + d p i h 2 + d p 2 h l m ) ( m h t + 矗2 ) ( 2 2 14 ) 将( 2 2 14 ) 分别代a ( 2 2 9 ) 与( 2 2 10 ) 得 7 1 s _ ( ( p ，一p o m + ( 日一r ) h 2 ) ( m h , + ：) ( 2 2 1 5 ) 如，7 = ( ( 一r ) a 1 一( p 2 一p 1 ) ) ( m ，+ 2 ) ，户1 ，2 ，m ( 2 2 1 6 ) 另一方面，扫+ ，+ 缸z ，的h e s s i a n 距阵显然为正定n 止t ( 2 2 1 3 ) 、 t 1 j = l ( 2 2 1 5 ) 和( 2 2 1 6 ) 正是( 2 2 6 ) 的最优解将这些式子代入( 2 2 6 ) ，可得 - 1 3 7 r 日 i j i ” 乃 轻一 努h ，、，l ts d 趵叻d z 2 2 = i u 似仁龙勉 上海交通大学博士后研究工作报告 ，1 ( ， 2 ) = 聍( ax + h i d ( t i n ) 2 2 + p , d ( t n ) ) + 4 ，+ h l d ( ( ( p 2 一p o m + ( h t ) h 2 ) ( m h l + a ：) ) 2 2 + p i d ( ( p 2 一p 1 ) m + ( 日一t ) h 2 ) ( m h , + 2 ) ) + p 2 d ( ( ( h 一丁) - ( p 2 一p 1 ) ) ( m t + h o ) + r e ( a 2 + h 2 d ( ( ( h r ) l 一( p 2 一p o ) ( m h a + 2 ) ) 2 2 ) = 儿4 】+ d t p i + d a l 7 1 2 2 + m a 2 + 口+ p ( m h , + a 2 )( 2 2 t 7 ) 其中a = a + d ( h t ) p 2 一d ( p 2 - p - ) 2 2 h , ， p = d ( ( 胃丁) 而一( p 2 一p i ) ) 2 h z 2 h ，( 2 2 1 8 ) 显然，如果( h - dh i - ( p 2 p 1 ) 0 ，那么m = 0 因此p h ( 2 2 1 6 ) 戋h ：如果( h - d h 1 一( p 2 一p 1 ) o ，那么( 2 2 5 ) 就简化为 m i n i m i z e f 1 ( ，z ，m ) ( 2 2 19 ) 令。i 与m ? 为( 2 2 1 9 ) 的最优解注意到m 与九是独立变量，因此由引理 2 1 可得 n ? = m a x ，1 ) = ( 2 2 2 0 ) m i = m a x ，0 ) = m a x ，0 ) ( 2 2 2 1 ) 显然由( 2 2 1 6 ) a n d ( 2 2 2 1 ) 有 如果( 1 ) ( 麒乃h i - 2 一p 1 ) o ；或者( 2 ) ( h - dh 1 一( p 2 一p i ) o 且 _、dhff(h-t)h,-(p2-pt)22a2+h,24i2一h：o，那么m：=o 由上面分析可得b p e1 的最优订购策略为：若( h - t ) h i 一( p 2 - p i ) 0 或者( h - 力h 1 ( p 2 - p 1 ) o 且m ：( ( 一t ) h a 一( p z a ) ) 2 2 4 z + h i 2 4 一州2 一 z o 那么在第二时域不需要订购，此种情形下的最优总费用为厂1 ( ”：，o ) ；否则 最优总费用为，( n ? ，m ：) ，其中n ：与m ：分别由( 2 2 2 0 ) 与( 2 2 2 1 ) 决定 ( i i ) b p e 2 策略研究 对固定的门1 和m o ，考虑如下问题： m i n i m i z e 2 s + 黜2 ，j i ，2ji = 1 = l s t 势+ ：，h 令和厂2 ( 亿m ) 分别为( 2 2 2 2 ) 的最优解和最优值 策略相类似的分析方法可得： ( 2 2 2 2 ) 用与最优t y p e1 1 4 骆建文：库存管理和随机规划中的若干问题研究 t l ，。( ( p2 i p 】j 2 + h h 2 ) ( m h l + n h 2 )i = 1 ，2 ，n ( 2 2 2 3 ) t 2 & ( 爿7 n ( p 2 一p ，) ) ( m 岛+ n h 0j 2 1 ，2 ，m ，f 2 2 。2 4 ) 因此 ，1 ( ”，m ) 2 ，“1 + d 矗i ( ( ( p 2 一p o m + h h 2 ) ( m h l + 2 ) ) 2 2 + n d p j ( ( p 2 - p o m + h h 2 ) ( m h l + n h 2 ) + m a 2 + m d h 2 ( ( ( 1 1 h 1 n ( p 2 p o ) ( m h 】+ n h 2 ) ) 2 2 + m d p 2 ( h h l n ( p 2 一p o ) ( m h , + n h 2 ) 经化简得 ( ”，”) = p 2 d h 棚( a x - d ( p 2 - p 1 ) 2 2 砒m a ：f 2 2 2 5 ) + d ( h h l 一胛( p 2 一p 1 ) ) 2h 2 2 h , ( m h l + n h 2 ) 、 。 如果月z 广船( p 2 - p 1 ) 0 ，那么问题( 2 2 2 2 ) 可以归结为 m i n i m i z e ，2 ( 抗m ) ( 2 ，2 2 6 ) 月】m 2 0 设t l ：和m ：为( 2 2 2 6 ) 的最优解由于库存在时刻丁不为零，根据l e v 和 w e i s s 的定理2 ，我们有n ：等于n i 或者等于 t ：+ l ，这里”? = 为t y p e l 策略在第一时域 o ，t 的最优订购次数显 然，由( 2 2 2 4 ) 失n ，如果h h l - n ：( p 2 一p 1 ) o ，那么聊o 如果h h l n ； ( p 2 p 】) o ，考虑到当o 时，( 2 ( n ：，m ) 关于m 严格凸，我们易得 m ：= m a x m i n mi 厂2 ( ：+ l ，) 厂2 ( m m ) ) ，0 ) = m a x ，o ) ( 2 - 2 2 7 ) 显然由( 2 2 2 4 ) 、( 2 2 2 7 ) ，我们有 卅o 当且仅当( i ) 厶陆1 一”：( p 2 - p i ) 0 或者( i i ) h h l 一阼：( p 2 一p 1 ) o 且 d z ( h h h ：( p ：- p ) ) 2 2 a 2 + hj 2 4 一h , 2 一”；矗，o ( 2 2 2 8 ) 这样对最优t y p e2 策略的确定可以通过比较n ：= n ：和”：+ 1 时，相应 的总费用的较低者来进行 2 3 算法的比较分析 由上一节的分析，我们得到费用参数发生变动的有限时域e o q 模型的 优化算法如下： p a r ta - - - 最优耐p e1 策略的求解 s t e p1 根据( 2 2 2 0 ) ，设船= n ：如果c 缮dh i 一( 心- p i ) 0 ，那么令m 2 0 ， 否则由( 2 2 2 1 ) 令m = m i 根据( 2 2 1 7 ) 计算c ( t y p e1 ) 2f 1 ( ”，一 1 5 p a r t b 最优b p e2 策略的求解 s t e p2 如果h h l - i l ( p 2 - p i ) o ，那么令m = o 否则根据( 2 2 2 7 ) ，令m = 。： s t e p 3 如果”2 n ；，那么根据( 2 2 2 5 ) 计算c 1 ，l ( t y p e2 ) = 厂( 亿m ) ，然后令 胛2 ”：+ l 转第2 步否则计算c l ，2 ( t y p e2 ) = 厂2 ( ，m ) ，并转第4 步 s t e p4 设c ( t y p e 2 ) - - m i n c 1 ，l ( t y p e2 ) ，c 1 ，2 ( t y p e2 ) 1 s t e p5 ，设c m i n 2 m i n c ( t y p e1 ) ，c ( t y p e 2 ) ，结束 我们的结果与l e v 和w e i s s 结果主要差别在于第二时域中的最优订 购次数的确定上对t y p e1 策略，l e va n d w e i s s 通过引用s c h w m - z ( 1 9 7 2 ) 的结论得到了第二时域中的最优订购次数为 m + = i n f m ：m ( m + 1 ) ( d h z 2 爿：) ( 日一t 一乃) 2 = i n f m j ：m ( m + 1 ) ( d h 2 2 a 2 ) ( m ( h , ( h r ) 一p 2 + p 1 ) ( ，” 】+ 2 ) ) 2 ) ( 2 3 1 ) 对t y p e2 策略，l e v 和w e i s s 同样通过引用s c h w a r z ( 1 9 7 2 ) 的结论得到 了第二时域中的最优订购次数为 m t ( 日一”m = i n f m ，：m ( 晰+ 1 ) _ ( d h z 2 a z ) ( h 一- ) 2 j 5 i n f 珑，：( m h i + n h z ) 2 ( m + 1 ) m ( d h 2 2 a ：) ( h 1 h 一 ( p 2 p 1 ) ) 2 ( 2 3 2 ) 尽管s c h w a r z 的结果并没有任何错误，但是在这里不能引用s c h w a r z 的定理来得到了第二时域中的最优订购次数因为s c h w a r z 的定理在这 里隐含地要求体弘珏和h - n t ，与m 无关，也就是要求对固定的珂， 鼹瓦和h - n t l 应该为常数不幸的是日r 一瓦和h - n t l 随m 的变化而 变化对t y p e1 策略，由于在时刻丁那次订购的相关费用与第二时域 中的所有订购的相关总费用的和随m 变化而变化，而在第一时域中订购 的相关总费用与m 无关这样g q ( 2 3 1 ) 决定的m s 是第二时域中的最优 订购次数的必要条件是对固定的”，m + 能够使在时刻丁那次订购的相关 费用与第二时域那些订购的相关费用的和达到最小但事实上，由f 2 3 1 ) 决定的朋+ 不一定能使这个费用和达到最小例如：3 = 1 ，仔= 2 7 ，t = 3 ， 爿l = 1 0 ，a 2 = 5 0 ，p i _ 2 ，p 2 = 1 2 ，h i = 5 ，h 2 = 5 0 ，那么由( 2 3 1 ) 得珑 = 1 而 实际上，根据( 2 2 1 ) 知此时第二时域中的最优订购次数为6 在这种情况 下，l e va n dw e i s s 的总费用为1 4 7 5 2 5 ，而按我们提供的策略进行订购 的话，总费用为1 3 8 1 5 类似地对于t y p e2 策略来说，对固定的九，第 二时域中的最优订购次数必须是使整个有限时域中的各种费用和达到最 小因此第二时域中的最优订购次数应该由( 2 2 2 7 ) 决定的m ：，而不是由 ( 2 3 2 ) 决定的m * ( h - n t l ) 应该看到，我们得到的第二时域中的最优订购 次数的表达式非常简单而深刻，并很容易得到了在第二时域中不需要进 1 6 骆建文；库存管理和随机规划申的若干问题研究 行订购的充要条件所以我们的结果无论如何要比l e v 和w e i s s 及以前 的所有相关研究的结果要好 为了更正l e v 和w e i s s 论文中的数值方面错误，也为了从具体的实 例中再进行比较分析，我们通过l e v 和w e i s s 的例子进行两种方法的对 比分析例：设d = - 1 0 ，a l = 4 2 = 8 0 ，p 1 = 1 0 0 ，p 2 = 1 0 1 ，h j = 1 ，h 2 = 1 叭， 弘6 - 并令f 1 ( ，m ) 2 厂o ( 几m ) h ，r ( ，) 2 厂啦( m ) 肛假定考虑的整个 时域长度日从1 2 到3 6 按单位时间增加我们的相关计算结果显示在 表i ；而l e v 和w e i s s 的相关计算结果显示在表i i ，表示两种方法所 得数值结果不同处通过表i 和表对比可以看出：对于t y p e1 策略， 当月三1 2 ，1 7 ，1 8 ，2 1 ，2 5 ，2 9 和3 3 ，我们的总费用要比他们的相关 总费用来得低；按我们提供的方法知道，当爿兰1 3 或者1 7 时，该实例的 t y p ei i 策略要比t y p ei 策略好其余情形则更宜采用t y p ei 策略；而 l e v 和w e i s s 计算结果显示当日兰1 2 ，1 3 ，1 7 ，1 8 和2 1 ，该实例的t y p e i i 策略要比耐p ei 策略好，其余情形则更宜采用t y p e i 策略从这个简单 的实例可以看出l e v 和w e i s s 的结果确实是错误的 从以上的分析与数值比较可以看出，我们确实彻底解决了l e v 和 w e i s s 的问题，而且我们的方法为经典e o q 问题的扩展性研究提供 了一个新的思路 1 7 表i 我们的数值结果9 = - 1 0 ，a l i 彳2 = 8 0 ，p 1 = 1 0 0 ，r = 1 0 1 ，向尸1 ， 2 = 1 0 1 ， t = - 6 1 8 表i il e va n dw e i s s 的数值结果d = - i o ，a 1 刊2 = 8 0 ，p 1 = 1 0 0 ，p 2 = 1 0 1 ， h l = l ，h 2 = 1 0 1 ，t = 6 最优策 日 丌州 正f 1 ( 门，m ) 玎研 f 1f 2 ( n ，聊) 略类型 1 2 +213 。5 l1 0 4 3 9 82 14 ，3 41 0 4 3 1 02 4 1 3214 0 l1 0 4 3 4 92l4 6 71 0 4 3 2 52 1 4214 。5 11 0 4 3 4 32l5 0 11 0 4 3 6 2 1 1 5215 0 11 0 4 3 7 2215 3 41 0 4 4 1 7 1 1 62l5 5 21 0 4 4 2 8224 5 11 0 4 4 7 6 1 1 7 +216 0 21 0 4 5 0 72 24 7 61 0 4 4 8 6 22 1 8 +2 16 5 21 0 4 6 0 5225 0 11 0 4 5 0 82 + 1 9225 0 21 0 4 5 0 82 25 2 71 0 4 5 4 21 2 0225 3 61 0 4 5 4 2 234 6 21 0 4 5 7 91 2 1 +225 6 91 0 4 5 8 923 4 8 21 0 4 5 8 6 2 2 2234 7 71 0 4 5 8 32 35 0 21 0 4 6 0 11 2 323 5 0 21 0 4 5 9 7235 2 21 0 4 6 2 4 1 2 4235 2 81 0 4 6 2 0 244 6 91 0 4 6 5 01 2 5423 5 5 31 0 4 6 5 22 44 8 51 0 4 6 5 51 2 6244 8 31 0 4 6 4 9 245 0 21 0 4 6 6 6 1 2 724 5 0 31 0 4 6 6 0245 1 91 0 4 6 8 2 1 2 8245 2 31 0 4 6 7 6 254 7 41 0 4 7 0 1 1 2 9 4 245 4 31 0 4 6 9 925 4 8 81 0 4 7 0 4 1 3 02 54 8 61 0 4 6 9 8255 0 21 0 4 7 1 3 1 3 1255 0 31 0 4 7 0 6 255 1 71 0 4 7 2 5 1 3 2255 2 01 0 4 7 1 92 64 7 71 0 4 7 3 9 1 3 38255 3 6 1 0 4 7 3 626 4 9 01 0 4 7 4 21 3 4264 8 91 0 4 7 3 5 265 0