スタートページ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

これを線形計画法の整数計画法として解くこともできますが、式の特徴に注目すると、もっと簡単に解くことができます。その手順は、次の通りです。

ステップ1:正規化
最大値問題の場合は、行列の表を-1倍して最小化問題にする。
各行につき、その行での最小値を減じる。
各列につき、その列での最小値を減じる。
ステップ2:最適性の評価
すべての0要素をカバーする最小限の線を引く。
その数が表のサイズであれば、最適解である。
ステップ3:解の改善
線が引かれていない要素の最小値を求める。
線の引かれていない要素から最小値を減じる。
交点になっている要素に、最小値を加える。

割当問題の数値例

問題

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
      ┌─────────┐
     1│8 2 ◎ 7 3│
     2│◎ 4 0 4 0│
     3│0 ◎ 8 3 5│     表4
     4│7 4 1 4 ◎│
     5│1 0 5 ◎ 4│
      └─────────┘

ここで、次の問題が発生します。
・どうすれば◎を付けることができるかどうかを確認できるのでしょうか?
・表3の場合には、さらに手を加えて表4のように変形する必要がありますが、
 どのような操作をすればよいでしょうか?

 

理由は省略して、手順だけを示します。

  1. 線の本数が最小で、すべての0の要素をカバーするように線を引く。
  2. その線の数が、行(列)の数(ここでは5)必要であれば最適解である。
    その理由は、◎となる要素を(i,j)とすれば、必ず行iかjの一方に線を引く必要があり、以前に線を引いたところは、既にその行か列に◎があるから、重複して◎にすることができないこと、そして、線が5本になったことは、◎が5つあることから説明できます。
  3. 線の数が行数よりも少なければ、最適解ではなく、改善をする必要がある。

解の改善

改善の方法は、次の手段で行います。

  1. 線が引かれていない全要素の最小値を探す。
  2. 線が引かれていない要素については、最小値を減ずる。
  3. 交点になっている要素については、最小値を加える。

表3について、この手順を行うと次のようになります。

この結果は、表6(すなわち表4)になります。

       1 2 3 4 5
      ┌─────────┐
     1│8 2 0 7 3│
     2│0 4 0 4 0│
     3│0 0 8 3 5│     表6
     4│7 4 1 4 0│
     5│1 0 5 0 4│
      └─────────┘

この例では、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の要素をカバーするように線を引く。
ことは、表を目視して線を引くのは比較的簡単なのですが、そのアルゴリズムをプログラミングすると、私の能力では、しかるべき計算量で達成することができず、現在放棄したままになっております。
 ご指導いただければ幸甚です。