せん けい 泉恵女学園物語・その５ おはなしDEA（包絡分析法） － 単体法への準備－ ライオネル学園大学 ここね、先生の大学は… 1 先生、お願いがあるんです。 今度の土曜日、空いてますか？ １０時に先生の研究室に伺います。 一日中、空けといてくださいね。 七瀬 まだかな… 2 先生、遅刻しました。すみません！ 七瀬 いや、いや、こっちも忘れていたよ。 何か頼みがあるんだったね。 まあとりあえず、かき氷でもどう？ 私はコーヒーでも飲もう。 いただきます、先生。 ところで、変な質問していいですか？ ああ…いいよ。 3 先生いま、つきあってる人、いるんですか？ いないな。研究一筋さ。 七瀬 じゃ、土曜日も研究ですか？ すごく忙しいんですね。お邪魔しちゃったかな…。 いや、そんなことはない。 週に一度くらい、こんな時間もいいものさ。 あの、高校生の身分で あつかましいお願いなんですけど…。 なんでも言ってごらん♪ 4 DEAのこと、もっと教えてほしいんです。 毎週土曜日、教えてもらっていいですか？ 七瀬 え？ まあ、いいけど…。 5 みんな、ＯＫだって！ 七瀬 おじゃましまーす！ 残念だったな先公！ 6 あれからみんなで、毎週土曜日、 DEAについて本格的に 教えてもらおうってことになったんです。 OKしてくれてありがとう、先生！ 七瀬 汚い部屋ね。 先生、なんか 元気ないですね。 ごめんなさい。 私は止めたんだけど…。 あ、タバコだ。 コーヒーくらい 出しなさいよ。 吸うんですか？ このマンガ、 私のものー！ 変な本がいっぱいー。 カップ汚れてる。 洗ってないんですか？ 週に一度くらい、 DEAもいいものさ。 あ、グルメ本だ。 センセ、借りていい？ あ、パソコン。 欲しーな。 7 それではDEAの前に、まず線形計画法を教える！ しっかり聞いててくれ！ 一度しか説明しないぞ！ はーい！ なんか怒ってるみたい…。 悲しい奴だよな。 8 線形計画法(Linear Programming)は、 いろんなところに役立つ。 例として、 夏休みの有意義な過ごし方を計算しよう。 星野くん、君の趣味は？ 読書と…ショッピングかな? 9 それぞれの趣味を１回やるのに必要な、 「時間」「お金」「気力」を、それぞれ書いて欲しい。 あと、それを１回やったときの「うれしさ」もね。 読書 買い物 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 うれしさ うれしさ 3 5 こんなとこかな…。 10 さらに、夏休み中に使える「時間」「お金」「気力」の 総量を、それぞれ教えて欲しい。 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 こんなところです。 11 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 さて…それでは夏休み中に「読書」「買い物」を、 それぞれ何回ずつすればいいだろうか? 読書をx1回、買い物をx2回する、としよう。 読書のうれしさは3、買い物のうれしさは5だから、 うれしさの合計は3x1+5x2。これを最大にすればいい! ちなみに3x1+5x2のことを目的関数という。 しばしばZであらわされる。つまりZ= 3x1+5x2。 12 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 x1,x2を大きくすれば、 Z=3x1+5x2は いくらでも大きくなりそうなものだ。 ところがどっこい、そうはいかない。 「お金」「時間」「気力」の制約があるからだ。 たとえば読書はせいぜい40回しかできない。 気力は120しかないのに、読書1回で3気力を 消費してしまうからだ。 だからx1≦40なのさ。 13 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 つまり読書をx1回、買い物をx2回するなら、 お金を x1+7x2 百円、 時間を 2x1+4x2 時間、 気力を 3x1+2x2 気力、消費する。 ところがお金は140百円、時間は100時間、 気力は120気力しか存在しない。 そこで次の３本の制約条件がなりたつ。 お金の制約: x1+7x2 ≦140 百円、 時間の制約: 2x1+4x2 ≦100 時間、 気力の制約: 3x1+2x2 ≦120 気力。 また、x1,x2はいずれも正の値だ。 読書や買い物を「マイナス回」 行なうわけにはいかないからだ。 だから、x1≧0, x2≧0 という条件がつく。(これらを非負条件という) 14 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 ゆえに「夏休み問題」は、 ３つの制約条件、 ２つの非負条件のもとで、 目的関数を最大にする問題なんだ。 目的関数 Z=3x1+5x2 制約条件 非負条件 お金の制約: x1+7x2 ≦140 百円 時間の制約: 2x1+4x2 ≦100 時間 気力の制約: 3x1+2x2 ≦120 気力 x1≧0 x2≧0 15 目的関数 Z=3x1+5x2 制約条件 お金の制約: x1+7x2 ≦140 百円 時間の制約: 2x1+4x2 ≦100 時間 さて、この問題をグラフで解こう。 X軸にx1，Y軸にx2をとって、 制約条件と非負条件をグラフにする。 すると、解の許される範囲は 以下の部分になる。 気力の制約: 3x1+2x2 ≦120 気力 x 2 60 25 20 x 40 50 140 1 16 目的関数 Z=3x1+5x2 目的関数の式を書き直すと、x2=-0.6x1+0.2Zとなる。これは傾き-0.6の直線だ。 ところがZがわからない。つまり領域を通るような傾き-0.6の直線は、どれでも答えだ。 これらのうちで、Zが最大になるのはどれだろう？ ここでx1に0を入れると、x2=0.2Zとなる。つまりZを大きくすることは、 y軸との交点（y切片）を大きくすることと同じなんだ。 いろいろ試すと、点Bを通るとき、y軸との交点は最大になる。 解は 点B(35, 7.5)。つまり x1=35, x2=7.5。そのとき目的関数の値は Z=3x1+5x2= 142.5。 x 2 読書を35回、 買い物を7.5回やれば いいってことね！ C B x A 1 17 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 × × 35回 7.5回 ＝ ＝ - 読書 読書 買い物 使用量 35 百円 70 時間 105 気力 52.5 百円 30 時間 15 気力 87.5 百円 100 時間 120 気力 ＋ ＝ 読書を35回、買い物を7.5回やると、 どの資源をどれくらい使ったかがわかる。 星野くんの場合、 時間と気力を使い切っている。 ＝ お金ばっかり、 ずいぶん 余り 余っちゃったなぁー。 52.5 百円 0 時間 0 気力 18 さて用語の整理をしておこう。 解が存在可能な範囲を実行可能領域といい、その中の点を実行可能解という。 実行可能解のうち、目的関数を最大(もしくは最小)にするものを最適解という。 そして、最適解はかならず図形の頂点のどこかだ。 (この場合、点O, A, B, C, Dの頂点のうち、頂点Bだった) Z=3x1+5x2 x 2 じゃあ、５つの点だけ D C 調べればいいのね！ B 最適解 x O A 1 19 星野さんの「うれしさ」つまり目的関数Zの値を、各点について示そう。 この場合は２次元だし、制約条件も少ないので、 すべての頂点について目的関数、つまりZの値を調べられた。 しかしもっと問題が大きくなると、すべての頂点はとても調べきれない。 x 2 D 100 どうすればいいの？ C 132 B 142.5 x O 0 A 120 1 20 ここで線形計画法のありがたいところは、 (1)原点から出発し (2)Ｚの値が大きくなるような頂点に移動し、 (3)数が大きくなる方向がなければ終了 …すれば、必ず最適解にたどりつくということだ。 x 2 D 100 C 132 ２手かかったわね。 B 142.5 x O 0 A 120 1 21 しつこく繰り返すが…線形計画法のありがたいところは、 (1)原点から出発し (2)Ｚの値が大きくなるような頂点に移動し、 (3)数が大きくなる方向がなければ終了 という手順さえ守れば、 どんなに下手な道の選び方をしても、いつかは必ず 最適解にたどりつく、ということだ。 x 2 こんどは３手。 D 100 でもたどりついた！ C 132 B 142.5 x O 0 A 120 1 22 この性質を利用したものが単体法、 もしくはシンプレックス法というものだ。 これで線形計画法を簡単に解くことができる。 だが話が長くなるから、ここでいったん、休憩にしよう。 はーい！ やっと終わったぜ。 あ、コーヒーだ！ 23 だますみたいで先生に悪い…とは思ったのですが、 仲の悪かったA組とB組が、こんな悪だくみで盛り上がるなんて、 数か月前には考えられなかったことだったんです。 ひさしぶりに楽しいランチタイムでした。 これで第５話は終わりです。ありがとうございました。 七瀬 クーラーが ほかの人たちは こないんですか？ ＣＤの趣味、 最悪だぜ。 ロックにしなよ。 ききすぎよ。 まだまだDEAには 遠そうですね！ ごみ箱どこですか？ え、このバケツ？ 資料もいっぱいー。 この電話、 かけていーい？ あれー、 つながんなーい。 インスタントだって！ 豆の買い置きくらい しておきなさい！ おやつは このコーヒー、 あ、ホントだ。 まずーい。 ないんですね・・・。 24 せん けい 泉恵女学園物語・その６ おはなしDEA（包絡分析法） － スラック変数・基底変換－ ライオネル学園大学 楽しいランチタイムも、 あっという間に終わり… 七瀬 まーかせて。 予習したんだから！ 永倉 25 それでは単体法の準備を続けよう。 眠いだろうが、しっかり聞いててくれよ！ はーい！ うぃーす こうして午後の授業は始まりました。 七瀬 26 目的関数 Z=3x1+5x2 制約条件 非負条件 お金の制約: x1+7x2 ≦140 百円 時間の制約: 2x1+4x2 ≦100 時間 気力の制約: 3x1+2x2 ≦120 気力 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 うれしさ うれしさ 3 5 x1≧0 x2≧0 まず「夏休み問題」の復習だ。 これは３つの制約条件、 ２つの非負条件のもとで、 目的関数を最大にする問題だった。 60 25 20 40 50 140 27 目的関数 Z=3x1+5x2 制約条件 非負条件 お金の制約: x1+7x2 ≦140 百円 時間の制約: 2x1+4x2 ≦100 時間 気力の制約: 3x1+2x2 ≦120 気力 x1≧0 x2≧0 ここで不等号をなくすため、 λ1, λ2, λ3を導入して等式にする。 これらをスラック変数という。 スラック変数は、 資源の使い残し量を示す。 新・制約条件 お金の制約: x1+7x2 +λ1 = 140 百円 時間の制約: 2x1+4x2 +λ2 = 100 時間 気力の制約: 3x1+2x2 +λ3 = 120 気力 スラック変数 スラックって、 英語の「余裕」のことよ。 沢渡 28 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 × 7.5回 ＝ ＝ - × 35回 読書 買い物 使用量 35 百円 70 時間 105 気力 52.5 百円 30 時間 15 気力 87.5 百円 100 時間 120 気力 ＋ ＝ ＝ D 100 どの資源をどれくらい使ったかがわかる。 星野くんの場合、 時間と気力の２資源を使い切っている。 お金ばっかり、 C 132 ずいぶん 余っちゃったなぁー。 B O 0 読書を35回、買い物を 7.5回やると、 余り 52.5 百円 0 時間 0 気力 A 120 たとえば点Bの使いのこしは、 お金=52.5百円、時間、気力は０だった。 ゆえにλ1 =52.5, λ2 =0, λ3 =0。 他の４つの頂点についても求めよう。 29 すると次の表のようになる。面白いのは、 どの行(ヨコのライン)にも、かならず０が２つ、入っていることだ。 頂点 O A B C D x1 0 40 35 14 0 x2 0 0 7.5 18 20 D 100 どうして？ Z 0 120 143 132 100 C 132 B 142.5 O 0 沢渡 λ1 λ2 λ3 140 100 120 100 20 0 52.5 0 0 0 0 42 0 20 80 A 120 30 その理由の直感的な説明は…いま式が３本あり、変数は５つある。 ゆえにどれか２つの変数を消去（０を代入する）しても、 解が求まるからなんだ。 頂点 O A B C D D 100 x1 0 40 35 14 0 x2 λ1 λ2 λ3 0 140 100 120 0 100 20 0 7.5 52.5 0 0 18 0 0 42 20 0 20 80 Z 0 120 143 132 100 C 132 B 142.5 O 0 A 120 ふーん… 沢渡 新・制約条件 お金の制約: x1+7x2 +λ1 = 140 百円 時間の制約: 2x1+4x2 +λ2 = 100 時間 気力の制約: 3x1+2x2 +λ3 = 120 気力 たとえば λ2, λ3を隠しても ３変数に式３本なので 答えは求まります。 これこそ点Bの解よ。 永倉 31 どの頂点も、２つの直線の交点だ。 そして０になるのは、その２直線の示す条件が持つスラック変数だ。 たとえば点Cは、（１）お金の制約と（２）時間の制約の交点。 だからλ1 とλ2が０になった。 新・制約条件 （１）お金の制約: x1+7x2 +λ1 = 140 百円 （２）時間の制約: 2x1+4x2 +λ2 = 100 時間 （３）気力の制約: 3x1+2x2 +λ3 = 120 気力 頂点 O A B C D 60 時間の制約式 ほんとだ… 25 20 C x1 お 金 の 余 り 時 間 の 余 り 気 力 の 余 り x2 0 40 35 14 0 λ1 λ2 λ3 0 140 100 120 0 100 20 0 7.5 52.5 0 0 18 0 0 42 20 0 20 80 Z 0 120 143 132 100 お金の制約式 40 沢渡 50 140 32 より一般的に言えば、次になる。 変数をn個、制約条件の式をm本とする。 実行可能領域の頂点ならば、 対応する変数(n+m)個のうち、少なくともn個が０になる。 新・制約条件 （１）お金の制約: x1+7x2 +λ1 = 140 百円 （２）時間の制約: 2x1+4x2 +λ2 = 100 時間 （３）気力の制約: 3x1+2x2 +λ3 = 120 気力 n個 ふーん… 沢渡 m個 お 金 の 余 り 頂点 O A B C D x1 0 40 35 14 0 x2 時 間 の 余 り 気 力 の 余 り λ1 λ2 λ3 0 140 100 120 0 100 20 0 7.5 52.5 0 0 18 0 0 42 20 0 20 80 Z 0 120 143 132 100 33 いよいよ単体法の説明に入る…前に、もうひとがんばり。 「基底形式」 「基底変数」 「非基底変数」 「基底解」 「基底変換」 という専門言葉を覚えて欲しい。 ふぁーい バリエーションのない 学問だぜ！ 34 制約条件の不等式を、 λで等式に書き直したものを「基底形式」といい、 λのことを 「基底変数」という。 基底変数以外の変数を、非基底変数という。x1,x2のことだ。 基底形式 お金の制約: x1+7x2 +λ1 = 140 百円 時間の制約: 2x1+4x2 +λ2 = 100 時間 気力の制約: 3x1+2x2 +λ3 = 120 気力 「基底解」と 「基底変換」は？ 安達 非基底変数 基底変数 35 非基底変数、つまりx1,x2の値をすべて0にすれば、 基底変数λ1， λ2， λ3の値はあっという間に求まる。 (x1=x2=0, λ1=140， λ2=100， λ3=120) こうして得られた解を 「基底解」というんだ。 基底形式 お金の制約: x1+7x2 +λ1 = 140 百円 時間の制約: 2x1+4x2 +λ2 = 100 時間 気力の制約: 3x1+2x2 +λ3 = 120 気力 非基底変数 基底変数 このくらいの方程式なら あなたも解けるでしょ？ 馬鹿にしやがって！ 星野 松岡 36 基底形式 お金の制約: x1+7x2 +λ1 = 140 ……(1) 時間の制約: 2x1+4x2 +λ2 = 100 ……(2) 気力の制約: 3x1+2x2 +λ3 = 120 ……(3) x1を消去して また基底変数をいろいろ 取り替えることができる。 たとえばx1を消去してみよう。 (1)式を２倍して(2)から引く。 (1)式を３倍して(3)から引く。 すると次のようになる。 基底形式 お金の制約: x1 + 7x2 + λ1 = 140 ……(1) 時間の制約: -10x2 - 2λ1 +λ2 = -180 ……(2) 気力の制約: -19x2 - 3λ1 +λ3 = -300 ……(3) 順番を入れかえると 順序を入れかえて 基底変数を取りかえた ことがはっきりするでしょ。 λ1とx1を入れかえたの。 お金の制約: λ1 + 7x2 + x1 = 140 ……(1) 時間の制約: - 2λ1 -10x2 +λ2 = -180 ……(2) 気力の制約: - 3λ1 -19x2 +λ3 = -300 ……(3) 永倉 これも基底形式になってる! やるわね。 遠藤 37 基底形式 お金の制約: x1 + 7x2 +λ1 = 140 ……(1) 時間の制約: 2x1 + 4x2 +λ2 = 100 ……(2) 気力の制約: 3x1 + 2x2 +λ3 = 120 ……(3) 基底変数は この基底変数の取り替えが 基底変換 なんだ。 λ1 ,λ2 , λ3 お金の制約: λ1 + 7x2 + x1 = 140 ……(1) 時間の制約: - 2λ1 -10x2 +λ2 = -180 ……(2) 気力の制約: - 3λ1 -19x2 +λ3 = -300 ……(3) 基底変数は x1 ,λ2 , λ3 基底変換 の結果を、いつも 基底形式 に直すのはたいへん！ もっと便利な表記法がありそうでしょ？それが 単体表 なの！ シンプレックス・タブローともいうの。 タブローって、表っていう意味のフランス語よ。 語尾を下げて発音すると、どんな言葉もフランス語風に聞こえるわ。 永倉 38 永倉くん、よく知ってるねえ。 まーかせて。数学だけはプロだから。 まず最初の表を単体表にすると、こうなります。 永倉 基底形式 お金の制約: x1 + 7x2 +λ1 = 140 ……(1) 時間の制約: 2x1 + 4x2 +λ2 = 100 ……(2) 気力の制約: 3x1 + 2x2 +λ3 = 120 ……(3) 基底変数に入ってない 変数の値はつねに０ ってことに注意してね！ だから x1=x2=0 なの。 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 x1,x2は基底変数ではないでしょ？ 39 基底変換 はどうやるか言えるかい？ もちろん。さっきやったように、x1を消去してみます。 すると単体表では、次のような表記法になります。 永倉 ステップⅠ お金の制約: x1 + 7x2 +λ1 = 140 ……(1) 時間の制約: 2x1 + 4x2 +λ2 = 100 ……(2) 気力の制約: 3x1 + 2x2 +λ3 = 120 ……(3) ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 この丸は 何ですか？ ステップⅡ お金の制約: x1 + 7x2 + λ1 = 140 …(1) 時間の制約: -10x2 - 2λ1 +λ2 = -180 …(2) 気力の制約: -19x2 - 3λ1 +λ3 = -300 …(3) ステ ップ 式の 番号 Ⅱ (4) (5) (6) 基底 基底変 変数 数の値 x1 λ2 λ3 140 -180 -300 x1 1 0 0 x2 7 -10 -19 杉原 変数 λ1 λ2 λ3 1 -2 -3 0 1 0 0 0 1 40 丸について詳しく説明すると… いまx1を追い出そうと決めたので、タテの列が決まります。 永倉 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 どの行を基本にして、他の行から引くか決めたので、 （この場合は第１行）、ヨコの行が決まります。 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 それで？ 杉原 41 この２つの「輪」は、しばしば１つの図に同時に 書き込みます。すると次の図になります。 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 永倉 もっと省略して、たんに１つの数字をマルで 囲んだのが、さっきの丸だったんです。杉原さん、わかった？ これがもっとも普通の書き方なので、はやく慣れてください。 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 7 4 2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 了解！ この丸のついた場所を、ピボットといいます。 バスケットボールに、「ピボットフット」という言葉があります。 動かしてはいけない軸足のことです。 杉原 42 初期状態（原点）からの最初の一手（基底変換）は、 「６通りしかない」ってこと、わかりますか？ 永倉 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 λ3 0 0 1 ここの９つには 丸をつけてはいけないんですか？ 杉原 つけてはいけない。丸をつけるのは、 「その列の変数を基底変数に組み入れたい」からだろ？ ところがλ1, λ2, λ3は、すでに基底変数だからだ。 43 だから原点からの最初の基底変換は、 ６通りしかないの。 永倉 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 λ3 0 0 1 わかりました。 60 杉原 図で描くと 次の６通りだ。 25 20 140 40 50 44 もう少し詳しく調べてみましょう。 どこに黒丸をつけると、どの矢印になるのでしょうか？ 永倉 x2 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 λ3 0 0 1 x1の列に丸をつけることは、 今まで非基底変数だったx1を基底変数に組み入れることです。 つまり、今までx1は0だったのに、0より大きくなるんですよね…。 x1=0が0以上になるんだから、 上の３つの丸は、それぞれ下の３つの矢印のどれかです。 杉原 140 40 50 x1 45 上から３番目に 丸をつけたら？ ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 λ3 0 0 1 永倉 第３行に丸をつけると、第３行が基準になります。 ですから第３行を３で割って、x1の値を１にします。 すると、基底変数の値は40になります。ということは…この矢印？ x2 60 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 40 x1 1 2 1 x2 7 4 2/3 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1/3 杉原 正解！ 25 20 140 40 50 x1 46 丸を説明していたら、ずいぶん話がそれてしまいました。 元に戻りましょう。 今、単体表のステップⅡまでを説明したのでした。 永倉 ステ ップ 式の 番号 Ⅰ (1) (2) (3) ステ ップ 式の 番号 Ⅱ (4) (5) (6) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 基底 基底変 変数 数の値 x1 λ2 λ3 140 100 120 x1 1 2 3 x1 1 0 0 x2 7 4 2 x2 7 -10 -19 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 変数 λ1 λ2 λ3 1 -2 -3 0 1 0 0 0 1 この表の読み方はわかるかい？ まるっきり！ 松岡 47 この表の意味を知るために、基底解を求めてみましょう。 ステップ１では、すべての資源が余っています。 ステップ２では、x1=140。でもλ2とλ3はマイナス、 これでは資源が不足してしまいます。 永倉 ステップⅠ お金の制約: x1 + 7x2 +λ1 = 140 ……(1) 時間の制約: 2x1 + 4x2 +λ2 = 100 ……(2) 気力の制約: 3x1 + 2x2 +λ3 = 120 ……(3) ステップⅡ お金の制約: λ1 + 7x2 + x1 = 140 ……(1) 時間の制約: - 2λ1 -10x2 +λ2 = -180 ……(2) 気力の制約: - 3λ1 -19x2 +λ3 = -300 ……(3) ステ ップ 式の 番号 Ⅰ (1) (2) (3) ステ ップ 式の 番号 Ⅱ (4) (5) (6) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 基底 基底変 変数 数の値 x1 λ2 λ3 140 -180 -300 x1 1 2 3 x1 1 0 0 x2 7 4 2 x2 7 -10 -19 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 変数 λ1 λ2 λ3 1 -2 -3 0 1 0 0 0 1 これはグラフでいうと、 どこからどこに移動したか、わかるかな？ 48 ステップⅠ お金の制約: x1 + 7x2 +λ1 = 140 ……(1) 時間の制約: 2x1 + 4x2 +λ2 = 100 ……(2) 気力の制約: 3x1 + 2x2 +λ3 = 120 ……(3) ステップⅡ お金の制約: λ1 + 7x2 + x1 = 140 ……(1) 時間の制約: - 2λ1 -10x2 +λ2 = -180 ……(2) 気力の制約: - 3λ1 -19x2 +λ3 = -300 ……(3) ステ ップ 式の 番号 Ⅰ (1) (2) (3) ステ ップ 式の 番号 Ⅱ (4) (5) (6) 基底 基底変 変数 数の値 変数 λ1 λ2 x1 x2 140 100 120 1 2 3 7 4 2 基底 基底変 変数 数の値 x1 x2 140 -180 -300 1 0 0 7 -10 -19 λ1 λ2 λ3 x1 λ2 λ3 1 0 0 0 1 0 変数 λ1 λ2 1 -2 -3 0 1 0 λ3 0 0 1 λ3 0 0 1 x2 実はこの基底変換は、 下の矢印だったんだね！ x1が0から140に増えてるだろ？ 60 25 20 ステップⅠ 40 50 140 ステップⅡ x1 49 読書 買い物 総量 1 百円 2 時間 3 気力 7 百円 4 時間 2 気力 140 百円 100 時間 120 気力 ステ ップ 式の 番号 Ⅱ (4) (5) (6) 基底 基底変 変数 数の値 x1 x2 140 -180 -300 1 0 0 7 -10 -19 x1 λ2 λ3 変数 λ2 λ1 1 -2 -3 0 1 0 λ3 0 0 1 ステップⅡの意味を知ろう。 x1が140でx2が0…ということは、 趣味は「読書」しかない、と考えて、 しかも制約は金銭だけ、と考えれば、 読書は140回できる、ってことね！ x2 そのとおり！ ところが現実には、読書は140回もできない。 60 １回２時間かかるが100時間しかないから50回以下。 気力が３必要だが、120気力しかないから40回以下 …ってことなんだ。 25 20 ステップⅡ 40 50 x1 140 50 ゆえにステップⅡは、現実には実行不可能だ。 だからステップⅡの点は、 実行可能領域ではない（色が塗られていない）んだね。 x2 60 25 20 ステップⅡ 40 50 x1 140 51 つまり基底変換は、やみくもに行ってはいけない。 でないと、実行可能領域からはみ出してしまうからだ。 だって先生、さっきは、 「どんなに下手な頂点の選び方をしても、 かならず最適解にたどりつく」 って言ってたじゃない。 森井 すまない。さっきの説明は舌足らずだった。 どんなに下手な 実行可能領域 の 頂点の選び方をしても、と言うべきだったね。 どんな基底変換をしても自動的に 実行可能領域の頂点に行くのではない、 ということには、十分、注意してもらいたい。 じゃあ先生、 なんだい? 遠藤くん。 遠藤 52 原点からの最初の６通りの基底変換のうち、 どれを選べばいいの？ 遠藤 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 λ3 0 1 0 0 0 1 選んでいいのは、左の図でいえば、 実行可能解に行く２つの矢印だけだ。 右の表で言えば、２つの丸だけが許される。 6 0 2 5 2 0 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 λ3 0 0 1 140 4 0 5 0 53 どの順で基底変換すべきか、組織的に教える方法… それこそ単体法なんだ。 それでは、やっと単体法の説明に入れるぞ！ 先生、ちょうど３時です。 ちょっとお茶にしましょうよ！ 安達 待ってたぜ！ 松岡 依存ありませんわ。 綾崎 54 「恵泉女学園物語・その６」はここで終了です。 つきあってくれて、ありがとう。みなさんもお茶で一服したら？ 単体法って、実は手順だけなら一瞬なんです。 でも、みんなで意味をじっくり考えながら学ぶのは、 高校ではめったにない体験で、すごく新鮮でした。 よく「大学の勉強は役に立たない」って聞きます。そうかもしれません。 でも、「本当に勉強をした」っていう体験は、きっと… なにしてんの？ お茶、お茶！ 呼ばれちゃった。 じゃ、またね！ 永倉 55 せん けい 泉恵女学園物語・その７ おはなしDEA（包絡分析法） － 単体法－ コーヒータイムが終わりました。 かき氷、とてもおいしかったです。 永倉 56 かき氷はおいしかったかな？ それでは勉強をはじめよう。 はーい 気合いれてこーぜ！ これからコーヒータイム後の授業！ やっと単体法に入れそうです。 山本 57 それでは「夏休み問題」を単体法で解こう。 ６種類の基底変換のうち、実行可能領域におさまる、いわば 許される基底変換は、下の２つだった。そこで疑問が産まれる…。 １）どれが許される基底変換かを見分ける方法は？ （６つのうち２つしか許されないのはなぜか？） ２）許される基底変換のうちどれを選べばいいのか？ （２つのうち、どちらを選べばいいのか？） x2 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 x2 1 2 3 7 4 2 変数 λ1 λ2 1 0 0 0 1 0 60 λ3 0 0 1 25 20 40 140 50 x1 疑問１ ６つのうち２つしか 許されないのはなぜ？ 疑問２ 最初の一手はどっち？ 遠藤 保坂 58 なんちゃって単体表 ステ ップ 式の 番号 Ⅰ (1) (2) (3) 基底 基底変 変数 数の値 λ1 λ2 λ3 140 100 120 x1 1 2 3 x2 変数 λ1 λ2 λ3 1 0 0 0 1 0 0 0 1 7 4 2 それを知るために単体表を描こう。 じつは今までの表はニセモノ… なんちゃって単体表 だったのだ！ 本当の単体表は下なの。今までの表と大きな違いは (1)基底変数の欄に Z が入ってること。 (2)変数の欄にも Z が入ってること。 (3)増加臨界の欄が加わったこと。 「説明」の欄もついてるけど、これはあんまり関係ないわ。 永倉 本当の単体表 ステ ップ 式の 番号 (1) Ⅰ (2) (3) (4) 基底 基底変 変数 数の値 0 Z λ1 λ2 λ3 140 100 120 1 -3 変数 x2 λ1 -5 0 0 0 0 1 2 3 7 4 2 Z x1 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 説明 140/7=20 100/4=25 120/2=60 59 本当の単体表 ステ ップ 式の 番号 (1) Ⅰ (2) (3) (4) 基底 基底変 変数 数の値 0 Z λ1 λ2 λ3 140 100 120 1 -3 変数 x2 λ1 -5 0 0 0 0 1 2 3 7 4 2 Z x1 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 説明 140/7=20 100/4=25 120/2=60 Zの欄には何を入れればいいのだろうか？ 目的関数は Z=3x1+5x2。それを変形して 0 = Z -3x1 -5x2。 よってZの欄には0、変数の欄には 1, -3, -5, 0, 0, 0 を入れる。 この状態の意味は、x1=x2=0 のとき Z=0。 つまり読書も買い物も0回で、うれしさも0ってこと。 永倉 増加臨界の欄はどうやって埋めるの？ 山本 60 本当の単体表 ステ ップ Ⅰ (1) Z 0 1 -3 変数 x2 λ1 -5 0 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 7 4 2 式の 番号 基底 基底変 変数 数の値 Z x1 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 説明 140/7=20 100/4=25 120/2=60 いま目的関数Zの欄には 1 -3 -5 0 0 0 が入っている。 書き直せば Z=3x1+5x2。で、今のところ x1, x2 はどちらも0だ。 基底変換して基底変数に組み入れれば、 x1も x2も 0より大きい正の値になる。 つまり、ここにマイナスがある限り、基底変換で解を改善できる んだ。 ここの説明、すごく大事だから、 わからなかったらじっくり復習してね！ 永倉 あの…増加臨界の欄の話は？ 山本 61 本当の単体表 ステ ップ Ⅰ (1) Z 0 1 -3 変数 x2 λ1 -5 0 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 7 4 2 式の 番号 基底 基底変 変数 数の値 Z x1 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 説明 140/7=20 100/4=25 120/2=60 さて、Zの欄には-3,-5という２つのマイナスがある。 これは目的関数が Z=3x1+5x2 という意味だった。 x1を１つ増やすとZが3つ増え、x2を１つ増やすとZが5つ増える。 だから x1 と x2 を増やすチャンスがあるのなら、 より係数の大きなx2の方を増やしたほうが賢い。 だからx1,x2のうち、まず基底変換すべきなのは x2 なんだね！ 私は忘れられてしまったの？ 山本 山本さん、もう少しだからガマンして！ 永倉 62 本当の単体表 ステ ップ Ⅰ (1) Z 0 1 -3 変数 x2 λ1 -5 0 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 7 4 2 式の 番号 基底 基底変 変数 数の値 Z x1 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 140/7 = 100/4 = 120/2 = 20 25 60 説明 最小の 値を選ぶ 基底変換すべきはx2とわかった。 さて、x2はどこまで増やせるだろうか？これが「増加臨界」という意味だ。 結論から言えば、「基底変数の値」を「変数」の値で割った値を計算し、 それらのうち、いちばん少ない値まで は x2 を増やせる。 x2 図で言えば、これら３つの矢印のうち 最小値の20を選んだ、ってことなの！ これが増加臨界の欄の説明よ。わかった？ 60 はい 永倉 25 20 山本 x1 63 本当の単体表 ステ ップ Ⅰ 式の 番号 基底 基底変 変数 数の値 Z x1 (1) Z 0 1 -3 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 変数 x2 λ1 -5 0 7 4 2 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 140/7 = 100/4 = 120/2 = 20 25 60 説明 最小の 値を選ぶ よって、最初の一手のピボットは、x2,λ1の交点なんだ。 これで最初の２つの疑問… １）どれが許される基底変換か？ （Zの欄がマイナスで、かつ増加臨界が最小） ２）どれを選べばいいか？ （Zの欄のマイナスが最大で、かつ増加臨界が最小） に答えたことになる。 右の図で言えば、 ６つの矢印のうち ２つしか許されず、 しかも↑を選ぶべき、 ってことよ！ 永倉 x1 64 ステ ップ Ⅰ Ⅱ 式の 番号 基底 基底変 変数 数の値 Z x1 変数 x2 λ1 -5 0 λ2 0 λ3 0 0 1 0 0 0 1 増加臨界θi 説明 (1) Z 0 1 -3 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 4 2 1 0 0 (5) Z 100 1 -16/7 0 5/7 0 0 (1)-(6)*(-5) (6) (7) (8) x2 λ2 λ3 20 20 80 0 1/7 0 10/7 0 19/7 1 0 0 1/7 -4/7 -2/7 0 1 0 0 0 1 (2) / 7 (3) - (6)×4 (4) - (6)×2 ピボット行 なんで灰色の欄に、 100 1 -16/7 0 が入ってるかわかる？ 7 140/7 = 100/4 = 120/2 = 20 25 60 最小なので ピボット行が 第１行になった それでは単体表で ステップⅡまで 行ってみよう。 5/7 0 0 グラフでいうと 次の一手を進んだんだ。 x2 ピボット行の-5倍を引いたから！ D 100 C B 永倉 O 0 A x1 65 ステ ップ Ⅰ Ⅱ Ⅲ 式の 番号 基底 基底変 変数 数の値 変数 Z x1 x2 λ1 最小のマイナスなので 1 -3 -5 0 λ2 0 λ3 0 4 2 1 0 0 0 1 0 0 0 1 増加臨界θi 説明 (1) Z 0 (2) (3) (4) λ1 λ2 λ3 140 100 120 (5) Z 100 1 -16/7 0 5/7 0 0 (6) (7) (8) x2 λ2 λ3 20 20 80 0 1/7 0 10/7 0 19/7 1 0 0 1/7 -4/7 -2/7 0 1 0 0 0 1 (9) Z 132 1 0 0 -1/5 8/5 0 (5)-(11)*(-16/7) (10) (11) (12) x2 λ2 λ3 18 14 42 0 0 0 0 1 0 1 0 0 1/5 -1/10 -2/5 7/10 4/5 -19/10 0 0 1 (6) - (11)*(1/7) (7) / (10/7) (8) - (11)*(19/7) ピボット列が 0 1 第２列になった 0 0 7 2 3 140/7 = 100/4 = 120/2 = 20 25 60 (1)-(6)*(-5) 20*7 =140 20* 7/10 = 14 80* 7/19≒ 30 (2) / (7) (3) - (6)*4 (4) - (6)*2 最小なので ピボット行が 第２行になった ピボット行 それではステップⅢまで 行ってみよう。 x2 100 C 132 B 永倉 O 0 A x1 66 ステ ップ Ⅰ Ⅱ Ⅲ Ⅳ 式の 番号 基底 基底変 変数 数の値 Z x1 (1) Z 0 1 -3 (2) (3) (4) λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 変数 x2 λ1 -5 0 7 4 2 (5) Z 100 1 -16/7 (6) (7) (8) x2 λ2 λ3 20 20 80 0 1/7 0 10/7 0 19/7 (9) Z 132 1 (10) (11) (12) x2 λ2 λ3 18 14 42 (13) Z (14) (15) (16) x2 λ2 λ3 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 最小のマイナスなので 0 5/7 0 ピボット列が 第２列になった 1 1/7 0 増加臨界θi 140/7 = 100/4 = 120/2 = 20 25 60 0 0 0 -4/7 -2/7 1 0 0 0 1 0 0 -1/5 8/5 0 0 0 0 0 1 0 1 0 0 1/5 -1/10 -2/5 7/10 4/5 -19/10 0 0 1 142.5 1 0 0 0 9/8 1/4 7.5 35 52.5 0 0 0 0 1 0 1 0 0 0 0 1 3/8 -1/4 -19/8 -1/4 1/2 5/4 説明 (1)-(6)*(-5) 20*7 =140 20* 7/10 = 14 80* 7/19≒ 30 (2) / (7) (3) - (6)*4 (4) - (6)*2 (5)-(11)*(-16/7) 18*5 = 90 42* 5/4 = 52.5 (6) - (11)*(1/7) 最小なので (7) / (10/7) ピボット行が (8) - (11)*(19/7) 第３行になった (9)-(16)*(-1/5) (10) - (16)*(1/5) (11) - (16)* (-2/5) (12) / (4/5) ピボット行 ステップⅣ。 x2 もう灰色の欄にマイナスがない。 つまりこれ以上、改善する余地がない。 お疲れさま！ 100 C したがって終了だ。 132 B 142.5 永倉 O 0 A x1 67 これで単体法の説明は終わり。 みんな、わかったかな？ １回でわからなければ、何度も読み返そう！ それではテストだ！ ええーっ！ 土曜日にテストなんて 追試以来だな！ ドキドキするぜ！ 68 問１ ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 売り上げを最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 製品１ M1 M2 M3 M4 売値 2 3 1 3 100 製品2 0 3 3 4 150 利用可能時間 90 150 120 180 どひー！ まず定式化しなきゃ…。 森井 69 ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 売り上げを最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 製品１ M1 M2 M3 M4 売値 製品2 2 3 1 3 100 0 3 3 4 150 利用可能時間 90 150 120 180 まず定式化してみます。 空欄を埋めてみましょう。 正解は次のページです。 森井 Z = x1 + x2 x1+ x2 +λ1 x1+ x2 x1+ x2 x1+ x2 = +λ2 = +λ3 = +λ4 = 70 ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 売り上げを最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 製品１ M1 M2 M3 M4 売値 製品2 2 3 1 3 100 0 3 3 4 150 利用可能時間 90 150 120 180 これが正解です。 いよいよ次は単体表の作成！ 次のページを埋めてください。 森井 Z = 100x1 + 150x2 2x1+ 0x2 +λ1 3x1+ 3x2 1x1+ 3x2 3x1+ 4x2 = 90 +λ2 = 150 +λ3 = 120 +λ4 = 180 71 最小のマイナスなので ピボット列が 第２列になった ステ ップ 式の 番号 Z 1 x1 -3 x2 -5 λ1 λ2 λ3 140 100 120 0 0 0 1 2 3 7 (5) Z 100 1 -16/7 0 5/7 0 0 (1)-(6)*(-5) (6) (7) (8) x2 λ2 λ3 20 20 80 0 1/7 0 10/7 0 19/7 1 0 0 1/7 -4/7 -2/7 0 1 0 0 0 1 (2) / (7) (3) - (6)*4 (4) - (6)*2 (1) Ⅰ (2) (3) (4) Ⅱ 変数 λ1 0 基底 基底変 変数 数の値 Z 0 4 2 1 0 0 λ2 0 λ3 0 0 1 0 0 0 1 増加限界θi 140/7 = 100/4 = 120/2 = 説明 最小なので ピボット行が 第１行になった 20 25 60 製品１ M1 M2 M3 M4 売値 2 3 1 3 100 製品2 0 3 3 4 150 利用可能時間 90 150 120 180 大サービス！ 参考に｢夏休み問題｣の表を途中まで見せてあげる。 これを参考にがんばって埋めて！ ３ステップで終わるわ。 正解は次のページよ！ 森井 値 z x1 x2 λ1 λ2 λ3 λ4 x1 x2 λ1 λ2 λ3 λ4 x1 x2 λ1 λ2 λ3 λ4 z λ1 λ2 λ3 λ4 z λ1 λ2 x2 λ4 z λ1 λ2 x2 x1 72 これが正解…らしいです。 事情が許すなら、 Excelを使うとずっとラクよ！ 杉原 森井 値 z λ1 λ2 λ3 λ4 z λ1 λ2 x2 λ4 z λ1 λ2 x2 x1 z 0 90 150 120 180 6000 90 30 40 20 6600 66 6 36 12 1 0 0 0 0 x1 -100 x2 -150 2 3 1 3 x1 -50 1 0 2 0 2 0 0.333333 0 1.66667 x1 1 0 0 0 0 0 0 0 0 1 λ1 0 0 3 3 4 x2 0 λ2 0 1 0 0 0 λ1 0 0 0 1 0 x2 λ1 0 0 0 1 0 0 1 0 0 λ2 0 1 0 0 0 0 1 0 0 0 λ3 0 λ4 0 0 0 1 0 λ3 50 0 0 1 -1 0 0.333333 0 -1.33333 λ2 λ3 0 10 0 1.6 1 0.6 0 0.6 0 -0.8 0 0 0 1 50 40 45 0 0 0 1 45 15 120 12 λ4 0 λ4 30 -1.2 -1.2 -0.2 0.6 正解はx1=12, x2=36。 そのとき目的関数Zの値は6600。 資源は機械M1は66時間, 機械M2は6時間、余るということさ。 73 問２ ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 問１をちょっとだけ 変えて問２だ！ 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 生産量を最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 製品１ M1 M2 M3 M4 売値 製品2 2 3 1 3 1 利用可能時間 0 3 3 4 1 90 150 120 180 生産量って、x1+x2 のことよね。 だから売値がそれぞれ１円と思えばいいの。 すると定式化は…。 森井 74 ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 生産量を最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 製品１ M1 M2 M3 M4 生産量 製品2 2 3 1 3 1 利用可能時間 0 3 3 4 1 90 150 120 180 空欄を埋めてみましょう。 正解は次のページです。 森井 Z = x1 + x2 x1+ x2 +λ1 x1+ x2 x1+ x2 x1+ x2 = +λ2 = +λ3 = +λ4 = 75 ある会社では２つの製品P1,P2を作って、 それぞれ１kgあたり100千円と150千円で売っている。 製品P1を作るためには機械M1,M2,M3,M4を用いる。 製品P2を作るためには機械M2,M3,M4を用いる。 それぞれの製品を1kg作るために必要な機械の使用時間は以下の通りである。 また各機械の月間の、使用可能時間も示す。 製品１ 生産量を最大にするには、P1,P2の生産量を、それぞれどれだけにすればいいか、 単体法で解け。 M1 M2 M3 M4 生産量 製品2 2 3 1 3 1 利用可能時間 0 3 3 4 1 90 150 120 180 これが正解です。やさしすぎた？ でも単体表の作成は、けっこうホネよ！ それでは、次のページを埋めてください。 森井 Z = 1x1 + 1x2 2x1+ 0x2 +λ1 3x1+ 3x2 1x1+ 3x2 3x1+ 4x2 = 90 +λ2 = 150 +λ3 = 120 +λ4 = 180 76 値 z z λ1 λ2 λ3 λ4 0 90 150 120 180 z λ1 λ2 x2 λ4 6000 90 30 40 20 z λ1 λ2 x2 x1 6600 66 6 36 12 1 0 0 0 0 x1 -100 x2 -150 2 3 1 3 x1 1 -50 0 2 0 2 0 0.333333 0 1.66667 x1 1 0 0 0 0 0 0 0 0 1 λ1 0 0 3 3 4 x2 0 λ2 0 1 0 0 0 λ1 0 0 0 1 0 x2 0 1 0 0 λ2 0 1 0 0 0 λ1 0 0 0 1 0 λ3 0 0 1 0 0 0 λ4 0 0 0 1 0 λ3 50 0 0 1 -1 0 0.333333 0 -1.33333 λ2 λ3 0 10 0 1.6 1 0.6 0 0.6 0 -0.8 0 0 0 1 50 40 45 0 0 0 1 45 15 120 12 λ4 0 製品１ M1 M2 M3 M4 生産量 λ4 30 -1.2 -1.2 -0.2 0.6 製品2 利用可能時間 2 3 1 3 1 0 3 3 4 1 90 150 120 180 問１の正解を見せてあげる！ 今度も３ステップで終わるわ。 森井 値 z x1 x2 λ1 λ2 λ3 λ4 x1 x2 λ1 λ2 λ3 λ4 x1 x2 λ1 λ2 λ3 λ4 z λ1 λ2 λ3 λ4 z x1 λ2 λ3 λ4 z x1 x2 λ3 λ4 77 これが問２の正解です。 どう？ そろそろ単体表にも慣れた？ 杉原 森井 z λ1 λ2 λ3 λ4 z x1 λ2 λ3 λ4 z x1 x2 λ3 λ4 値 0 z 1 90 150 120 180 45 x1 -1 0 0 0 0 50 0 0 0 0 0 0 0 0 λ1 0 0 3 3 4 x2 -1 1 0 0 0 x1 0 1 45 5 60 25 2 3 1 3 x1 0 1 45 15 75 45 x2 -1 x2 0 1 0 0 0 1 0 0 0 λ1 0.5 0 3 3 4 0 1 0 0 λ2 0 λ3 0 0 1 0 0 λ2 0 0.5 0 -1.5 1 -0.5 0 -1.5 0 λ1 λ2 0 0.333333 0.5 0 -0.5 0.333333 1 -1 0.5 -1.33333 λ4 0 0 0 1 0 λ3 0 0 0 0 1 45 50 120 60 0 0 0 1 5 25 11.25 λ4 0 0 0 1 0 λ3 0 λ4 0 0 0 1 0 0 0 0 1 ちょっと待った！ 78 実はもう１ステップ、進めることができる。 いま第Ⅲステップの基底変数はλ3,λ4で、 λ1,λ2は非基底変数だ 。 ところがλ1の係数は0で、λ2みたいに正の値ではない。 これは、まだ進んでいいというサインなんだ。 z λ1 λ2 λ3 λ4 z x1 λ2 λ3 λ4 基底変数 z x1 x2 λ3 λ4 値 0 z 1 90 150 120 180 45 x1 -1 0 0 0 0 50 0 0 0 0 0 0 0 0 λ1 0 0 3 3 4 x2 -1 1 0 0 0 x1 0 1 45 5 60 25 2 3 1 3 x1 0 1 45 15 75 45 x2 -1 1 0 0 0 λ3 0 0 1 0 0 λ4 0 0 0 1 0 0 3 3 4 0 1 0 0 λ2 λ3 λ4 0 0 0 0.5λで、かつ非基底変数なのに 0 0 0のものがある！ -1.5 1 0 -0.5 0 1 -1.5 0 0 λ1 λ2 λ3 λ4 0 0.333333 0 0 0.5 0 0 -0.5 0.333333 0 1 -1 1 0.5 -1.33333 0 0 0 0 1 45 50 120 60 0 0 0 1 5 25 11.25 λ1 0.5 x2 0 1 0 0 0 λ2 0 0 0 0 1 基底変数 79 なぜかって？ いま第ⅢステップのZの行を解読しよう。 すると、z=0×λ1 - 0.333333λ2 となっている。 つまり第Ⅲステップではλ1は非基底解で、値が0なのだが、 λ1にかかっている係数が0だから、 λ1を基底解に組み入れ、その結果λ1が正の値になっても、 Zが小さくはならないからだ。 z λ1 λ2 λ3 λ4 z x1 λ2 λ3 λ4 z x1 x2 λ3 λ4 値 0 z 1 90 150 120 180 45 x1 -1 0 0 0 0 50 0 0 0 0 0 0 0 0 λ1 0 0 3 3 4 x2 -1 1 0 0 0 x1 0 1 45 5 60 25 2 3 1 3 x1 0 1 45 15 75 45 x2 -1 x2 0 1 0 0 0 1 0 0 0 λ1 0.5 0 3 3 4 0 1 0 0 λ2 0 λ3 0 0 1 0 0 λ2 0 0.5 0 -1.5 1 -0.5 0 -1.5 0 λ1 λ2 0 0.333333 0.5 0 -0.5 0.333333 1 -1 0.5 -1.33333 z=0×λ1-0.333333λ2 λ4 0 0 0 1 0 λ3 0 0 0 0 1 45 50 120 60 0 0 0 1 5 25 11.25 λ4 0 0 0 1 0 λ3 0 λ4 0 0 0 1 0 0 0 0 1 80 だから第Ⅲステップからλ1を基底に組み入れ、λ4を追い出した ステップⅣもまた、立派な答えなんだ。 z λ1 λ2 λ3 λ4 値 0 z 1 90 150 120 180 z x1 λ2 λ3 λ4 45 z x1 x2 λ3 λ4 50 z x1 x2 λ3 λ1 50 x1 -1 0 0 0 0 2 3 1 3 x1 0 1 45 15 75 45 0 0 0 0 20 30 35 50 0 0 0 0 0 3 3 4 1 0 0 0 0 1 0 0 x2 0 1 0 0 0 λ2 0 1 0 0 0 λ1 0.5 x2 0 x1 0 1 0 3 3 4 1 0 0 0 0 0 0 0 λ1 0 x2 -1 x1 0 1 45 5 60 25 x2 -1 0 1 0 0 0.5 -1.5 -0.5 -1.5 λ1 0 0.5 -0.5 1 0.5 λ1 0 0 0 0 1 λ3 0 0 1 0 0 λ2 0 λ4 0 0 0 1 0 λ3 0 0 1 0 0 λ2 0.333333 0 0.333333 -1 -1.33333 λ2 0.333333 1.333333 -1 1.666667 -2.66667 0 0 0 1 45 50 120 60 0 0 0 1 5 25 11.25 0 0 0 1 60 50 λ4 0 0 0 1 0 λ3 0 λ4 0 0 0 1 0 λ3 0 λ4 0 0 0 1 0 -1 1 -2 2 具体的には どういうことなんですか？ 杉原 81 A 直感的には…。 問２の領域は左図の着色部分だ。 で、目的関数 Z=x1+x2 の値を できるだけ大きくしようとしたら、 B C D Z=x1+x2 50 Ⅲ z x1 x2 λ3 λ4 50 Ⅳ z x1 x2 λ3 λ1 x1 0 1 45 5 60 25 0 1 0 0 0 点D 0 0 0 x1 0 1 20 30 35 50 x2 0 0 点C 0 0 0 λ1 0 0 1 0 0 x2 0 1 0 0 0 線CDにぴったり重なってしまったんだね！ このとき、線CD上ならどこでも最適解だろ？ 0 1 0 0 0.5 -0.5 1 0.5 λ1 0 0 0 0 1 λ2 0.333333 0 0.333333 -1 -1.33333 λ2 0.333333 1.333333 -1 1.666667 -2.66667 λ3 0 λ4 0 0 0 1 0 λ3 0 0 0 0 1 60 50 λ4 0 0 0 1 0 -1 1 -2 2 C ステップⅢが点D、 ステップⅣが点Cなんですね！ D Z=x1+x2 杉原 82 Ⅲ Ⅳ z x1 x2 λ3 λ4 z x1 x2 λ3 λ1 50 1 45 5 60 25 50 1 20 30 35 50 x1 0 0 0 点D 0 0 x1 0 0 0 0点C 0 x2 0 1 0 0 0 λ1 0 0 1 0 0 x2 0 1 0 0 0 0 1 0 0 0.5 -0.5 1 0.5 λ1 0 0 0 0 1 λ2 0.333333 0 0.333333 -1 -1.33333 λ2 0.333333 1.333333 -1 1.666667 -2.66667 λ3 0 λ4 0 0 0 1 0 λ3 0 0 0 0 1 60 50 λ4 0 0 0 1 0 だから、点Cと点Dを線形結合させた 答えは、みんな答えなんだ。 -1 1 -2 2 答えのグラフ 答えの数式 C （20,30） D （45,5） x1 x2 = ｋ 20 30 ＋（１－ｋ） 45 5 （0≦k≦1） グラフで書くと、こうです。 数式で書くと、こうなります…。 森井 杉原 83 現実問題にはまれなケースかもしれないが、少なくとも理論上は この問題のように、最適解が無数にある可能性を知っておく必要がある。 ちなみに、最適解が１つしかなかった 問１の解答 を見てみよう。 最終ステップに、非基底変数で、かつZの行が0のλがないだろ？ だから問１の場合は、たしかにここで終了なんだね！ 値 z z λ1 λ2 λ3 λ4 0 90 150 120 180 z λ1 λ2 x2 λ4 6000 90 30 40 20 z λ1 λ2 x2 x1 6600 66 6 36 12 1 0 0 0 0 x1 -100 x2 -150 2 3 1 3 x1 1 -50 0 2 0 2 0 0.333333 0 1.66667 x1 1 0 0 0 0 0 0 0 0 1 λ1 0 0 3 3 4 x2 0 λ2 0 1 0 0 0 λ1 0 0 0 1 0 x2 λ1 0 0 0 1 0 0 1 0 0 λ2 0 1 0 0 0 0 1 0 0 0 杉原 λ4 0 0 0 1 0 λ3 50 0 0 1 -1 0 0.333333 0 -1.33333 λ2 λ3 0 10 0 1.6 1 0.6 0 0.6 0 -0.8 基底変数 わかりました。 λ3 0 0 0 0 1 50 40 45 0 0 0 1 45 15 120 12 λ4 0 λ4 30 -1.2 -1.2 -0.2 0.6 どちらも 0より大きい それでは次の問題に いきましょう！ 森井 84 問３ シンプレックス法で次の線形計画問題を解け。 目的関数 Z = 2x1 + 4x2 + x3 を 最大化したい いよいよ最後だ。 がんばれー。 制約条件は x1+ 2x2 ≦4 2x1+ x2 ≦3 x2+ 4x3 ≦3 x1, x2, x3 ≧0 もうλを使っての定式化(基底形式への変換)はいいわ。 いきなり単体表を埋めてちょうだい。 森井 85 問３ 製品１ 材料１ 材料2 材料3 利益 この問題の表を見せてあげる。 今度は４ステップかかるわ。 森井 製品2 1 2 0 2 製品3 2 1 1 4 制限 0 0 4 1 4 3 3 値 z x1 x2 x3 λ1 λ2 λ3 値 z x1 x2 x3 λ1 λ2 λ3 値 z x1 x2 x3 λ1 λ2 λ3 値 z x1 x2 x3 λ1 λ2 λ3 z λ1 λ2 λ3 z x2 λ2 λ3 z x2 λ2 x3 z x2 x1 x3 86 これが問３の正解。 つまり x1=2/3,x2=5/3,x3=1/3、 そのときz=25/3。 これであなたも 単体法をマスターしました！ 森井 杉原 こりごりだぜ！ 問３の正解 z λ1 λ2 λ3 z x2 λ2 λ3 z x2 λ2 x3 z x2 x1 x3 値 0 z 1 4 3 3 値 8 x1 -2 0 0 0 z 1 2 1 1 値 8.25 2 1 0.25 値 8.333333 1.666667 0.666667 0.333333 1 2 0 x1 0 0 0 0 z 1 x2 -4 0.5 1.5 -0.5 x1 0 0 0 0 2 1 1 x2 0 x1 -0.125 0 0.5 0 1.5 0 -0.125 z 1 x3 -1 0 0 4 1 0 0 1 0 0 x3 0 1 0 0 λ2 0 1 0 0 λ1 2 0 0 4 0.5 -0.5 -0.5 0 0 1 λ1 1.875 0.5 -0.5 -0.125 x3 0 x2 0 0 1 0 λ1 0 x3 -1 x2 0 松岡 λ3 0 0 1 0 λ2 0 0 0 1 2 3 3 0 0 1 0.25 λ3 0 0 1 0 λ2 0 λ3 0.25 0 1 0 λ1 λ2 1.833333 0.083333 0 0.666667 -0.33333 0 -0.33333 0.666667 1 -0.16667 0.083333 0 4 0 0.66667 0.25 -2 <-これは選ばない！ λ3 0.25 0 0 0.25 87 あの日は結局、夕方７時まで勉強したので、クタクタになりました。 こんなに苦労するようで、経営工学科でやってけるの？…と不安にもなりました。 でも私は今日はっきりと、ほんとうに心の底から納得したのです。 「経営工学は素晴らしい！」って。 不思議なことにあの日、先生はその口癖を一度も言いませんでした。 これで第７話は終わりです。ありがとうございました。 七瀬 来週は日本茶を おい先公、 寿司でも おごりなよ。 ゴキブリ出ますよ。 掃除してください！ 持ってきましょう。 理系のままでいれば よかったかな…。 あ、もうこんな時間。 たいへん、弟が…。 マージャンできないのに マージャンマンガが 好きなんですか？ インスタントラーメン！ 下賎な食べ物ね。 疲れた…。 あの機械、 何に使うんですか？ ノイズだらけじゃん。 あ、テレビみよ。 電波はいってないね。 88
© Copyright 2024 ExpyDoc
