船‥メモランダムご‥一了予言：．二、酢頗′・．十y∴・ −や㍉ヤぎゃ畔ご正ヰ
松井 三知払 並木 誠

この原稿は，肝arka．sの補題及びそれを用いた強双対定理の初等的な証明の試みです．この原稿を書くに至ったより㌧ガが空である事が容易に判定される．事実，汐＝（2，りの重みで∬の定義中の等式を加えると，
2＊卜ご1＋￡2＋￡3）＝2＊ト5）

きっかけは，2人の筆者の間で交わされた次のような疑問

1＊（2∬1＋￡2−ご3）＝1＊7でした；「KKT条件も単体法も一次独立もコーーシー列も（0∴rl十3ご2十￡3）＝−3

知らない生徒がいる授業で∴双対定理を証明できるか？」となり，諾＝（ぷ1，；ご2，￡3）≧のとは両立しない式となってさてその結果が以下の証明ですが「いかがでしょう 7」．

多くの線形計画法の本では，強双対定理の証明は7単体法の正当性から導かれている事が多い．しかしながら，単体法の有限性の証明や，2段階単体法の詳細は決して簡単なものではない．また非線形計画のKK甘条件の特殊形として示そうとしても，適用できる簡単な制約想定が無いため，その証明は安易ではない．そもそも最適解があるかという問題についても，許容領域のコンパクト性が保証されず，決して自明ではない．

実は強双対定理の証明は，許容解の存在性つまり線形不等式系の解の存在性の特長付けと本質的な関わりがある。線形不等式系の解の存在性については，以下の『arkasの補題と呼ばれるものが成り立ついることから，∬が空であることが分かる．
以下では，Farkasの補題の初等的な証明を試みる．この証明は以下のような特徴も持っている・（1）コーシー列等の知識が不必要，（2ト単体法の知識が不必要，（3）非常に短い、（4）証明の手続きに従うと1Farkasの補題の性質を達成するベクトルを有限ステップで生成できる．では，始めよう．

集合5と集合‡ノ）に対し，5 ∪（刀を5十ノと書く・
またJ∈ Sの時，g＼打）を5−ノと書く・ 集合
5，J，ノ，存がJn．′ ＝ ノ∩ム丁 ＝ 左nJ＝ ￠と ぎ ＝Ju，∫∪Ⅳ を満たすとき，J，J，在は5の分割であると言う．本稿では，冒頭の主張を証明する
代わりに、より・一般的な形式の以下の主張を証明する．

肝a訂汰asの補題ご任意のm x円実行列月と，任意の7れノ次元実ベクトル払に対し，以下∬とiノアのうち丁度1つが要素をもつ∬＝‡諾∈R′れiA鮮＝あ，諾≧叶

y＝‡暫∈毘mI即Tノ4≧叶野Tぁ＜叶∬＝l■∵＝とする′・ノ1∵・＼J月Jヽモ1︑二例えば

濫＝（￡1，影2，￡3）−ズ1＋∬2＋ご3＝仰5，
2∬1＋諾：2−￡3＝7，諾＞￠即＝（封1，封2）

岬汐1＋2封2≧0，封1＋封2≧0，
択一的≧0，−5封1＋7封2く0，l／rが要素即＝（2，1）を持つ事とFaノrkasの補題

まつい ともみ東京大学大学院工学系研究科計数工学専攻〒113−8656東京都文京区本郷7−3−1
hモモp：／／wwⅦ。misoが止0。七．u一七地yo。aC・jp／ 七OmOmi／
なみき まこと東邦大学理学部情報科学科〒274−8510千葉県船橋市三山2綱2−1
E−mail‥nam土姐鮎s。SC宜・℃0王10−nqaC。］p5霊感（34）

上記においてナ＝Ⅳ＼ノ＝存＝ゆとすると，冒頭の『a1七asの補題となる．集合吉（J，ノ，〃），lr （J，J，吉）の定© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ◎リサーチ

解雷，否の定義より，義中の制約は，以下のようになっている．
表1・∫（J，ノ，〟）とy（ナノ，〟）における制約・添え字まr、J0 ＞ 否T♭＝否T（A雷）八

非負 自由 ゼロ
非負 ゼロ 自由ガ（石ノ）における∬宣の符号

1r（ナノ）におけるyT4の符号＝ ∑宜∈トJ否T」4五言五＋否丁宥和十∑∈九収否TA痛＝ ∑才∈ト′否TJ4去雷戌＋否TJ4何≧否TA何となり，否TAJ＞0または烹〜＞0が成り立つ

証明＝斎∈∫（丁，J，五）かつ否∈y（ナノ，∬）とすると，否T．4〜＞0ならばっ否は1′（ナ，J，∬）の要素である．

0＞否T♭＝否TA雷雷J＞0ならば，斎はズ（Jノ，∬）の要素である・＝∑よ∈′否TAま雷才＋∑宜∈J否T」4古君壱＋∑五。∬否TA五官五補題1：且すを〃lXm行列とする．以下の2つの集合のうち丁度1つが要素を持つ．

＝∑z∈′否Tノ4吉富盲＋0＋0≧0となり矛盾．ゆえにズけノ，ム ）とy（ナノ，〟）が同時に解芽（〟，♭）＝†諾∈Rれ−〃諾＝呵，を持つことは無い・以下ではガ（ナノ，∬）とy（丁，J，∬）のl′（凡才，♭）＝‡γ∈Rmt封丁凡才＝OT，封T♭＜0）．

一方が要素を持つ事を，Jの要素数に関する帰納法を用い

注：けl＝0の場合のFarkasの補老は，（劫l盲∈J）中の縦ベて示す．

クトルを並べた行列をAオとすると，上記の補遺となる．

（1）け−＝0の場合．補題1において証明する．

証明：ベクトルわを 凡才の列ベクトルの張る線形空間に（2）正整数たに関して，けt＜たならば補題の主張が成り

直交射影して得られるベクトルを♭′とし，否＝♭′−ぁ立つと仮定して，けl＝たの場合を示す．と定義する・直交射影の定義より［∃斎，♭′＝几す斎］とJ中の要素を1つ選びgとする．以下では6つの集合［否Tルす＝OT］が成り立つ．面の定義より，否Tむ ＝．＼・／．ノ．／＼■−．＼−−／−／、／ト／／＼−−‥＼−／＝／、／、／＼∴−／−、

否T（b′一面）＝否丁凡才斎一脂Il2＝−1㈲l2≦0である．

1′ナ（ナノ，吉），Y （才一J，J＋J，〟），l′（才一J，J，在＋〜），（i）面Tむ＜0ならば，否丁几す＝OTより否∈l′岬，む）≠￠について議論する．これらの集合の定義中の制約を表1にとなる．

倣ってまとめると，次のようになる．

（ii）否Tむ＝0ならば，0＝否Tb＝−11副2より否＝0が成り立ち，〃斎＝む′＝b′−0＝む′一面＝ぁとなり，表2．制約の一覧表．
凍え字才一g JJ ムー斎∈ズ（几す，♭）≠￠である．

非負 非負 自由 ゼロ

上記の証明の特徴の1つは，構成的な事である．すなわ∫（才一J，J＋J， 〟）． 非負 自由 自由 ゼロ

ち上記の証明は，Farkasの補題の主張を示すベクトルを∫（J−J， J，〟＋り 非負 ゼロ 自由 ゼロ

実際に求める 有限時間算法になっている．その際補題1∫（J， J， ∬）i（J，J， ∬） 非負 非負 ゼロ 自由1′▼（J−J，ノ＋〜， 〟） 非負 ゼロ ゼロ 自由i′▼（J−J，J，〟＋り 非負 自由 ゼロ 自由∫（J−Jノ，〟＋りはズ（J，J，〟）の定義の￡J≧0を￡J＝0に換えた物なのでズ（J，J，〟）⊇ズ（才一り，〟＋J）が成り立つ・よってズ（J−㍉J，∬＋g）≠￠ならば■の直交射影には，グラムーシュミットの直交化法を用いる辛ができる．しかし，本稿の初期の目的に「線形代数の知識を要求しない」を課したので，直交射影等の知識を要求しない補題1の証明を付録に付けた．

最後に，FaTkasの補題を用いて双対定理を証明しよう．

∫（ナノ，∬）≠￠である・ゆえにズ（才一り，〟＋り＝￠m，れを任意の正整数とし，A，む，Cをmxれ実行列，m次の場合のみ議論する・帰納法の仮定より，ズ（才一左J，〟＋

元実ベクトル，円次元実ベクトルとする．次の線形計画問りとy（才一り，〟＋りは丁度一方が非空となる辛から，題Pとその双対問題Dについて議論する．

y（才一〜，J，∬＋g）が非空の場合のみ議論する．
同様に，i′ （ト左J＋g，∬）の定義はy（ナ，ノ，〃）の定義のP‥maX（cT諾IA諾＝む，諾≧0），D：nliniyTむ】yTA≧cT）．

封T4≧0をγTノ1g＝0に換えた物なので，y（J，J，呵⊇y（才一り＋J，∬）が成り立ち，y（才一gノ＋〜，∬）≠￠な

弱双相克理：2つの線形計画問題PとDの任意の実行らばl′ （J，J，〃）≠￠である．ゆえにy（トトJ＋J，∬）＝可能解の対語，否は，CT言≦否T♭を満たす．

￠の場合のみ議論する．帰納法の仮定より，2つの集合

証明：問題P，Dの定義と京，吾が各々の実行可能解であ∫（才一J，J＋J，〟）とy（才一り＋J，〟）は丁度一方が非る事から否Tむ＝否TA京≧cT雷となる．

空なので，ぷ（才一り＋J，斤）が非空の場合のみ議論する．

上記より，以下の要素が存在する場合のみ議論すれば良い；］富∈方（丁−J，J＋〜，〟），］否∈y（J−Jノ，∬＋り．

2000年10月号■

強双対定理：2つの線形計画問題PとDのどちらも実行可能解を持つならば，P とDのいずれも最適解を持ち，最適値は一致す・る．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）529

−﹁・・ニ‖・・・・／−：、について議論する．∬が空でなく，要素諾，即を持つならば，弱双対定理より明らかに認，即はそれぞれPとmの最適解であり，Pとりの最適値も一致する．以下では，P、D嘗ノA諾＝む，認＞の，nR

朋び∈

nR

避∈

二∬′トいノ＼！1︑証明：不等式系（1）肘の行数が1のとき，明らかに成り立つ（2）凡才の行数が2以上のとき，財をm x閏行列とし，
汀之＋n＝＝ん＋1とする．行数と列数の和がた以下の任意の行列に関して，補題の主張が成り立つと仮定する
行列胴の【【一番上の行をαT恒∈Rn）とし，ベクトルぁの第一要素の値をβ（β∈R．）とする．さらに凡才′，あ′をがそれぞれ実行可能解を持つにもかかわらず仁方が空であると仮定をして矛盾を導く．スラック変数漣を導入し，αT．＝ −㌻

ガの不等式系を見やすく書くと，∴（￡）〕）

凡才′および∴WノTの行数と列数の和はんであり，帰納法の仮定が成り立つ事を用いる．

0

帰納法の仮定より，次の2つの集合−AT0と走去する．以下では，行列

あ＝凡才／∬（且ノダノ，ぬ′）＝拉∈粗目′l財′諾＝打），ーCT折目〃牒′）＝‡即′∈Rr−−￣1l野′T凡才′＝OT，野′T払′＜0），あT

諾＞町β＞0，は，いずれか一方のみ要素を持つ．また，となる，ただし，互は単位行列を表し，0は適当なサイズ∬（几す′Tlα）＝（z∈駅】nl￣1l〟′Tg＝α），の零行列を表す。『arkasの補題（一般形）より，ぶが空な†ノ （胴′T，可＝（ぴ∈択ノn【ⅧT凡才′T＝OT，Ⅷ丁α＜0），らば次の線形不等式系の解集合とすると，帰納法の仮定より上記2つの集合はいずれか一

lノ「＝〈何丁，ZT，留）T∈R？＋叫1【方のみ要素を持つ・ゆえに，下記（i）（ii）（iii）に場合分けすwTjl山qCT≧OT）ZT＞OT，q≧0．
−ZTノ4T＋qbT＝OT，WTぁーZT（三＜0）る辛ができる．
∈l′r（肘牒）となる（i）預∈‡′▼（朋′｝わ′）の場合が非空となる．以下では与′−が要素（面Tl吉T，百）Tを持つと仮定して矛盾を導く∴計画をP，0の実行可能解とすると，弱双対定理よりcT葱】面Tぁ≧0が成り立つが，（芸）（iり詣∈ノⅤ（Aす′，あ′）かつ］ぴ∈i一▼（凡才′丁，α）の場合．ベ也丁恵一β

T【 αTこ君＊＝の已班−−≧離丁恵一面Tノl烹＝すCT恵一面丁すゎÅす／諾＊＝」W／恵一となり矛盾。

′′l＼＼．′しO ＞面TぁMCT烹＝面TA蕊−CT吉≧百CT富川CT吉＝す（cT面一面Tぁ）≧0αT雷一β

クトルごだつ喀を，避※＝面…

）Ⅷ と定義すると，

丁α乳び＝β，凡才′ぴ＝凡才′面＝む′となりパ仇が＝溌が成り立ちが∈吉（且牛わ）である・『arkasの補題を強双対定理から導くことは容易であり（例えば［2］参照）っ逆に『arkasの補凄から強双対定理も容（iii）詣∈Å（凡才′，あ′）かつ］z∈Ⅹ（財′T，α）の場合．
αT葱＝βならば、面∈J（碑あ）が成り立つ．zTぁ′≠β

易に導かれる（上記の証明や［1］参照）辛から，この2つは殆ど等価な性質に見える．ではどちらがより始原的なのならば，即＊＝とすると−（二1）か？『arkasの補題は許容解の存在性について述べており，がT凡才＝−αT＋zT」W′＝OT，強双対定理は最適解について述べている。最適解がある
野＊Tぁ＝一ノβ＋のならば許容解は当然存在するのだから，FarkaSの補題

zTぁ′≠0，を満たし，野＊∈i′（財，あ）または一宮＊∈y（財，あ）のどの方がより簡単で本質的な性質と考えるのは自然だろう．

ちらかが成り立つ．αT雷≠βかつzTぁ′＝βならば，

実は，Farkasの補題と強双対定理を，数値の符号のみに注β≠αT雷＝ZT胴信＝ZTぁ′＝βとなり矛盾．

目した組合せ的な構造に拡張した場合，『arkasの補題が成り立っていながら，強双対定理が成り立たない状況が存

参考文献
日伊理正夫，「線形計画法∴共立出版，19弧在する革も知られている［叶［2］今野乳付録補題且の別証明≡∬（財，あ）とち′r（財，払）が同時に解を持つことは無いのは，『arkasの補題の証明中で示した．以下では−Ⅹ（凡才，あ）「線形計画法」，日科技凰1987・［3］田村明久，『線形計画法と有向マトロイド計画法』「維散構造とアルゴリズム立Ⅴ」第1章，室田一雄編
近代科学社，1995．とy（Aぜ，払）の少なくとも一方が要素を持つ事を，行列凡才の列数と行数の和に関する帰納法を用いて示す．

5冨田（36）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ♪リサーチ