証明：Ｆの証明

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

命題Ｆ）は、p=qの時に

  • （補題４）
    • (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=q+1の時にも補題４が成り立つ、というものでした。


(6)

  • A_n^j=\max\{D_n^{j-1},A_{n-C_j}^{j+1}\}・・・・・(6)

でn=m+1,j=q+1とすると

  • A_{m+1}^{q+1}=\max\{D_{m+1}^q,A_{m+1-C_{q+1}}^{q+2}\}・・・・・(a-23)

同様に(6')

  • \tilde{A}_n^j=\max\{\tilde{D}_n^{j-1},\tilde{A}_{n-C_j}^{j+1}\}・・・・・(6')

でn=m+1,j=q+1とすると

  • \tilde{A}_{m+1}^{q+1}=\max\{\tilde{D}_{m+1}^q,\tilde{A}_{m+1-C_{q+1}}^{q+2}\}・・・・・(a-24)


q{\le}qなので補題４より

  • D_{m+1}^q{\le}\tilde{D}_{m+1}^q・・・・・(a-25)


もしm+1-C_{q+1}{\le}0ならば部品1-C_{q+1}は存在しないので

  • A_{m+1-C_{q+1}}^{q+2}=0
  • \tilde{A}_{m+1-C_{q+1}}^{q+2}=0

なので

  • A_{m+1-C_{q+1}}^{q+2}=\tilde{A}_{m+1-C_{q+1}}^{q+2}

もしm+1-C_{q+1}>0ならば、m+1-C_{q+1}{\le}mなので補題１から

  • A_{m+1-C_{q+1}}^{q+2}{\le}\tilde{A}_{m+1-C_{q+1}}^{q+2}

よっていずれの場合にも

  • A_{m+1-C_{q+1}}^{q+2}{\le}\tilde{A}_{m+1-C_{q+1}}^{q+2}・・・・・(a-26)

よって(a-23)、(a-25)、(a-26)から

  • A_{m+1}^{q+1}{\le}\max\{\tilde{D}_{m+1}^q,\tilde{A}_{m+1-C_{q+1}}^{q+2}\}

これと(a-24)から

  • A_{m+1}^{q+1}=\tilde{A}_{m+1}^{q+1}・・・・・(a-27)


(7)

  • D_n^j=\max\{D_{n-1}^j,A_n^j\}+S_n^j・・・・・(7)

でn=m+1,j=q+1とすると

  • D_{m+1}^{q+1}=\max\{D_m^{q+1},A_{m+1}^{q+1}\}+S_{m+1}^{q+1}・・・・・(a-28)

(9)

  • \tilde{D}_n^j=\max\{\tilde{A}_{n-1}^{j+1},\tilde{A}_n^j\}+S_n^j・・・・・(9)

でn=m+1,j=q+1とすると

  • \tilde{D}_{m+1}^{q+1}=\max\{\tilde{A}_m^{q+2},\tilde{A}_{m+1}^{q+1}\}+S_{m+1}^{q+1}・・・・・(a-29)

m{\le}mなので補題１から

  • D_m^{q+1}{\le}\tilde{D}_m^{q+1}

これと(a-27)と(a-28)から

  • D_{m+1}^{q+1}{\le}\max\{\tilde{D}_m^{q+1},\tilde{A}_{m+1}^{q+1}\}+S_{m+1}^{q+1}

さらに定義から

  • \tilde{D}_m^{q+1}{\le}\tilde{A}_m^{q+2}

なので

  • D_{m+1}^{q+1}{\le}\max\{\tilde{A}_m^{q+2},\tilde{A}_{m+1}^{q+1}\}+S_{m+1}^{q+1}

ここで(a-29)を用いれば

  • D_{m+1}^{q+1}{\le}\tilde{D}_{m+1}^{q+1}・・・・・(a-30)

(a-27)と(a-30)から、Ｆ）が証明されました。

以上で、Ｃ）、Ｄ）、Ｅ）、Ｆ）の証明が出来ました。
Ｃ）とＤ）からＡ）が証明されます。
Ｅ）とＦ）からＢ）が証明されます。
Ａ）とＢ）から定理１が証明されて、この証明は完了します。