Mathematics
Examination
Test
Archives
問1) 次の文章を読んで,本文中の空欄(ア)〜(ウ)に適した整数をそれぞれの解答欄に記入しなさい.
あなたは大学病院の外科で,手術の予定を決める担当をしています.ある日,つの異なる手術が予定されていて,それぞれの手術に人の医師の中から人ずつ執刀医として割り当てる必要があります.人の医師がつ以上の手術を担当することはできません.各医師は得意分野が各々異なるため,各手術を完了するために要する時間は表1の通りです(単位:時間).
表1
| 手術 | 手術 | 手術 | 手術 | 手術 | |
| 医師 | |||||
| 医師 | |||||
| 医師 | |||||
| 医師 | |||||
| 医師 |
しかしながら,医師の勤務時間や手術ができる時間帯には制限があります.医師と医師は育児中のため,医師は時から時まで,医師は時から時までの短時間の勤務です.そのため,たとえば医師は手術を行うことができません.また,医師は「医師の働き方改革」が開始されたことに伴い,勤務間インターバル確保(前の勤務から次の勤務までの間を法律で決められた時間あけること)のため,時から時までの勤務です.医師と医師は定時の時から時までの通常勤務が可能です.手術室はつあるためそれぞれの手術は独立して行うことができますが,手術ができる時間帯に制限があり,手術手術手術は時から時の間,手術は時から時の間,手術は時から時の間に行う必要があります.そのため医師によっては行うことが手術があります(たとえば医師は手術と手術を行うことができません).
以上のような制限の下で「ハンガリアン法」を用いて,を考えます.まず準備として,表1で各医師が行うことができない手術のマス(たとえば医師の手術と手術に×をつけ,以下の作業では考慮に入れません.次に,各医師の最小の手術時間をその医師のそれぞれの手術時間から引きます(たとえば医師なら手術の時間が最小なので医師の手術からまでそれぞれのマスは,×,×になります).これを全ての医師について行います.そこから次に,各手術(縦の列)についても最小の数字をその列のそれぞれの数字から引きます(医師の手術のマスはになります).これも全ての手術について行います.
最終的に得られた表において,それぞれの医師の手術からまでのマスでがつだけの場合は,その医師はそのマスの手術をすることになります(たとえば医師は手術のマスだけがなので,医師は手術を担当します).次にそれぞれの手術(縦の列)でのマスがつだけの場合は,そのマスの医師がその手術を行います.このようにそれぞれの医師が担当する手術を割り当てると,医師は手術(ア),医師は手術(イ)を担当することになり,全手術の合計時間は(ウ)時間となります.