スタートページ> Web教材一覧> オペレーションズリサーチ> 線形計画法
割当問題とは、n人の作業員とn個の作業があり、作業員iが作業jに従事したときの費用 c[i][j] が与えられているとします。そのとき、総費用を最小にするには、誰をどの作業につければよいかという問題です(c[i][j] が効果で、総効果を最大にするのであれば、cの値に-1をかければよい)。
作業員iが作業jに従事する値を x(i,j)(0または1の値)として、線形計画法で定式化すると、次のようになります。
目的関数
Z=c(1,1)x(1,1) + c(1,2)x(1,2) + ・・・ + c(1,n)x(1,n)
+ c(2,1)x(2,1) + c(2,2)x(2,2) + ・・・ + c(2,n)x(2,n)
・・・・・・
+ c(2,1)x(2,1) + c(2,2)x(2,2) + ・・・ + c(2,n)x(2,n) →最小
従業員による制約式
x(1,1) + x(1,2) + ・・・ + x(1,n) =1
x(2,1) + x(2,2) + ・・・ + x(2,n) =1
・・・・・・
x(n,1) + x(n,2) + ・・・ + x(n,n) =1
従業による制約式
x(1,1) + x(2,1) + ・・・ + x(n,1) =1
x(1,2) + x(2,2) + ・・・ + x(n,2) =1
・・・・・・
x(1,n) + x(2,n) + ・・・ + x(n,n) =1
これを線形計画法の整数計画法として解くこともできますが、式の特徴に注目すると、もっと簡単に解くことができます。その手順は、次の通りです。
5人の作業員と5個の作業があり、その費用が下表のように与えられている。例えば、作業員1を作業3に割り当てると4の費用がかかり、作業員2を作業3に割り当てると2の費用がかかる。総費用を最小にするには、どのように割りつければよいか。
作 業
1 2 3 4 5
┌─────────┐
1│9 5 1 9 7│
作 2│2 8 2 7 5│
業 3│1 3 9 5 9│ 表1
員 4│8 7 2 6 4│
5│2 3 6 2 8│
└─────────┘
ここで、「作業員1をどの作業に割り当てても、a円の費用が余計にかかる」として、行1の各要素にaを加えても(減じても)問題の本質は変わりません。それで、各行からその行のなかでの最小値を減じた表を作成します。
1 2 3 4 5
┌─────────┐最小値
1│8 4 0 8 6│ 1
2│0 6 0 5 3│ 2
3│0 2 8 4 8│ 1 表2
4│6 5 0 4 2│ 2
5│0 1 4 0 6│ 2
└─────────┘
同様に、ある列から、その列の各要素に同じ数値を加減しても、問題の本質は変わりません。それで、各列からその列のなかでの最小値を減じた表を作成します。
1 2 3 4 5
┌─────────┐
1│8 3 0 8 4│
2│0 5 0 5 1│
3│0 1 8 4 6│ 表3
4│6 4 0 4 0│
5│0 0 4 0 4│
└─────────┘
最小値 0 1 0 0 2
このような操作をすることを正規化といいます。表1でも正規化した後での表3でも、最適解は同じになります。それで、以降は表3が与えられたこととします。
表3において、0となっている要素は、このように割り当てると費用が0になることを示しています。それで、例えば表4のように「各行・各列に0があるように選ぶことができれば、その0の要素が最適な割り当てを示す最適解である」(◎は選ばれた0の要素)といえます。ところが、表3ではうまく割り当てることができません。
1 2 3 4 5ここで、次の問題が発生します。
・どうすれば◎を付けることができるかどうかを確認できるのでしょうか?
・表3の場合には、さらに手を加えて表4のように変形する必要がありますが、
どのような操作をすればよいでしょうか?
理由は省略して、手順だけを示します。
改善の方法は、次の手段で行います。
表3について、この手順を行うと次のようになります。
この結果は、表6(すなわち表4)になります。
1 2 3 4 5この例では、1回の改善で最適解になりましたが、最適解を得るまで「最適性の評価」と「解の改善」を繰り返し行います。
ここで、最小値を減じたり加えたりすることは、「正規化」で行や列から同じ値を加減することと同じです。「解の改善」の内容は、
線に関係なく、すべての要素から最小値を減じる。
線の引かれた行の要素に最小値を加える。列についても同様である。
ことと同じです。それで、それで、
なぜ、線を引いた行や列を特殊視するのか?
がポイントになります。
その理由は(厳密ではありませんが)、表5のような線の引き方では可能解が得られないので、まだ線が引かれていない要素のなかで、新規に0となる要素を探したいからです。
それには、表3が最適解になっていれば総費用が0になって理想的なのですが、それでは不可能ですので、少し条件を緩めて、「最小値」位は費用がかかってもよいと仕方がないとするのです。また、「最適性の評価」と「解の改善」を繰り返し行うのは、可能解が得られるまで、条件を緩めているのだと解釈できます。
可能解になったときが最適解であることは、そのつど「最小値」を用いていることから理解できます。
なお、厳密な説明をするので、双対問題の適用が必要になりますが、ここでは省略します。
1 2 3 4 5
┌─────────┐
1│1 3 4 5 2│
2│3 5 2 2 6│
3│1 2 5 8 5│
4│2 3 4 6 2│
5│2 5 1 3 4│
└─────────┘
(解答)
正規化のプロセス
1 2 3 4 5
┌─────────┐
1│1 3 4 5 2│
2│3 5 2 2 6│
3│1 2 5 8 5│
4│2 3 4 6 2│
5│2 5 1 3 4│
└─────────┘
↓最大化:-1倍
1 2 3 4 5 最小値 1 2 3 4 5
┌──────────────┐ ┌─────────┐
1│-1 -3 -4 -5 -2│-5 1│4 2 1 0 3│
2│-3 -5 -2 -2 -6│-6 2│3 1 4 4 0│
3│-1 -2 -5 -8 -5│-8 → 3│7 6 3 0 3│
4│-2 -3 -4 -6 -2│-6 4│4 3 2 0 4│
5│-2 -5 -1 -3 -4│-5 5│3 0 4 2 1│
└──────────────┘ └─────────┘
最小値 3 0 1 0 0
↓
1 2 3 4 5
┌─────────┐
1│1 2 0 0 3│
2│0 1 3 4 0│
3│4 6 2 0 3│
4│1 3 1 0 4│
5│0 0 3 2 1│
└─────────┘
最適性の評価と解の改善
1 2 3 4 5
┌─────────┐
1│1 2 1 0 3│ 斜字は線を引いた行・列
2│0 1 3 4 0│ 赤字は交点
3│4 6 2 0 3│ 線の数は4(<5) →解の改善
4│1 3 1 0 4│ 線の引かれていない要素の最小値=1
5│0 0 3 2 1│
└─────────┘
↓
1 2 3 4 5
┌─────────┐
1│0 1 ◎ 0 2│
2│0 1 4 5 ◎│
3│3 5 2 ◎ 2│ ←最適解
4│◎ 2 1 0 3│
5│0 ◎ 4 3 1│
└─────────┘
ここで掲げた解法で
・線の本数が最小で、すべての0の要素をカバーするように線を引く。
ことは、表を目視して線を引くのは比較的簡単なのですが、そのアルゴリズムをプログラミングすると、私の能力では、しかるべき計算量で達成することができず、現在放棄したままになっております。
ご指導いただければ幸甚です。