割当問題

人間4人を3つの仕事に割当てる。仕事は一人の人間しかすることができないが、だれでもどの仕事にもつくことはできる。しかし、同じ仕事でも、異なる人が行うと、違った効果になる。さて効果が一番高い最適割当は?

仕事と人間の効果表

人間1 人間2 人間3 人間4
仕事1 5 13 12 8
仕事2 6 8 7 6
仕事3 8 8 9 7

問題定式化

変数説明
X11 : 仕事1を人間1に割当てるとき1、それ以外のときは0となる変数(0,1変数)
....
X13 : 仕事1を人間3に割当てるとき1、それ以外のときは0となる変数(0,1変数)
....
X33 : 仕事3を人間3に割当てるとき1、それ以外のときは0となる変数(0,1変数)

目標行
 5X11+13X12+12X13+8X14+6X21+8X22+7X23+6X24+8X31+8X32+9X33+7X34→最大化
仕事1の制限
 X11+X12+X13+X14 = 1
仕事2の制限
 X21+X22+X23+X24 = 1
仕事3の制限
 X31+X32+X33+X34 = 1
人間1の制限
 X11+X21+X31   ≦ 1
人間2の制限
 X12+X22+X32   ≦ 1
人間3の制限
 X13+X23+X33   ≦ 1
人間4の制限
 X14+X24+X34   ≦ 1

GLPS正式版用インプット・データ

インプット・データの与え方はGLPS操作ガイドを参照していただきたい。実際このモデルのインプット・データは下のようになっています。

TITLE Sampl06
MAX 5X11 + 13X12 + 12X13 + 8X14 + 6X21 + 8X22 + 7X23 + 6X24 + 8X31 + 8X32 + 9X33 + 7X34
ST
X11 + X12 + X13 + X14 = 1
X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1
X11 + X21 + X31 <= 1
X12 + X22 + X32 <= 1
X13 + X23 + X33 <= 1
X14 + X24 + X34 <= 1
END
INT 12

GLPS正式版GLPSの計算結果

//
//***** GLPS Columns変数最適化解 *****
//
[ モデル名 : SAMPL06 ]
NumberColumnsNameAtActivityReducedCost
1X1106
2X1200
3X13BS10
4X1403
5X2100
6X22BS10
7X2300
8X2400
9X31BS10
10X3202
11X3300
12X3401
//
//***** GLPS Rows変数最適化解 *****
//
[ モデル名 : SAMPL06 ]

RowNameAtSlackActivityDualPrice
目標行BS280
仕事1制限EQ011
仕事2制限EQ06
仕事3制限EQ08
人間1制限00
人間2制限02
人間3制限01
人間4制限10
*
**************************
* GLPS 目標達成分析
**************************
*
1 目標行 目標値 28.

評価

仕事1を人間3に割当てる、仕事2を人間2に割当てる、仕事3を人間1に割当てる。効果の合計は28。

[最適化ソフトメンページへ]

Copyright(C)1998-2008 M.Shiimori , All Rights Reserved.