証明：大枠

ファブ内物流の論理を求めて

「MitraとMitrani 1990年のかんばん方式に関する研究（２）」で保留にした証明をここで考えてみます。

  • D_n^0=0・・・・・(5)
  • A_n^j=\max\{D_n^{j-1},A_{n-C_j}^{j+1}\}・・・・・(6)
  • D_n^j=\max\{D_{n-1}^j,A_n^j\}+S_n^j・・・・・(7)
  • \tilde{D}_n^0=0・・・・・(5')
  • \tilde{A}_n^j=\max\{\tilde{D}_n^{j-1},\tilde{A}_{n-C_j}^{j+1}\}・・・・・(6')
  • \tilde{D}_n^j=\max\{\tilde{A}_{n-1}^{j+1},\tilde{A}_n^j\}+S_n^j・・・・・(9)


証明したいのは、
（定理１）

  • (5)(6)(7)(5')(6')(9)が成り立てば、任意の自然数nと1{\le}j{\le}Nについて
    • A_n^j{\le}\tilde{A}_n^j、D_n^j{\le}\tilde{D}_n^j・・・・・(10)
  • が成り立つ。

ということです。


（定理１）を証明するために、以下の補題１を考えます。

（補題１）

  • (5)(6)(7)(5')(6')(9)が成り立てば、任意の自然数[tex:n
    • A_n^j{\le}\tilde{A}_n^j、D_n^j{\le}\tilde{D}_n^j・・・・・(10)
  • が成り立つ。


そして
Ａ）k=1の時に補題１が成り立つ。
Ｂ）k=mの時に補題１が成り立つと仮定するとk=m+1の時にも補題１が成り立つ。
このＡ）、Ｂ）を証明出来れば数学的帰納法により定理１が証明されます。


Ａ）は
（補題２）

  • (5)(6)(7)(5')(6')(9)が成り立てば、任意の自然数1{\le}j{\le}Nについて
    • A_1^j{\le}\tilde{A}_1^j、D_1^j{\le}\tilde{D}_1^j・・・・・(a-1)
  • が成り立つ。

ことを証明することと同等です。そこで補題２を証明するために、以下の補題３を考えます。

（補題３）

  • 1{\le}k{\le}Nであるようなkを定めた時、
  • 1{\le}j{\le}kである全てのjについて
    • A_1^j{\le}\tilde{A}_1^j、D_1^j{\le}\tilde{D}_1^j
  • が成り立つ。


そして
Ｃ）k=1の時に補題３が成り立つ。
Ｄ）k=mの時に補題３が成り立つと仮定するとk=m+1の時にも補題３が成り立つ。
このＣ）、Ｄ）を証明出来れば数学的帰納法により補題２が証明され、その結果Ａ）が証明されます。


Ｂ）を証明するために以下の補題を考えます。
（補題４）

  • (5)(6)(7)(5')(6')(9)が成り立っているとする。さらに、k=mの時に補題１が成り立っているとする。さらに
  • 1{\le}p{\le}Nであるようなpを定めた時、
  • 1{\le}j{\le}pである全てのpについて
    • A_{m+1}^j{\le}\tilde{A}_{m+1}^j、D_{m+1}^j{\le}\tilde{D}_{m+1}^j
  • が成り立つ。


そして
Ｅ）p=1の時に補題４が成り立つ。
Ｆ）p=qの時に補題４が成り立つと仮定するとp=q+1の時にも補題４が成り立つ。
このＥ）、Ｆ）を証明出来れば数学的帰納法によりＢ）が証明されます。