整数計画問題
数理計画 小テスト No.8
学籍番号
氏名
整数計画問題
【問題 1】
長さ 30cm の板が 52 枚あり, これを切って長さ 3cm の板 4 枚と, 5cm の板 3 枚, 6cm の
板 2 枚を 1 組みとするセットをなるべく多く作りたい.
30cm の板の切り方は以下の 5 通りある:
52
(1)
(2)
(3)
(4)
(5)
3cm を 10 枚
3cm を 5 枚と 5cm を 3 枚
3cm を 4 枚と 6cm を 3 枚
5cm を 6 枚
6cm を 5 枚
4
3cm
30cm
3
5cm
1
2
6cm
図 1: セット
(1),(2),(3),(4),(5) の切り方で切る板の枚数をそれぞれ x1 , x2 , x3 , x4 , x5 とする. この問題を整数計画問
題として表現したい. 以下の各問いに答えよ.
1. 30cm の板が 52 枚という条件から得られる制約式は?
2. 作るセットの数を x とする (従って目的関数
は z = x になる). このとき変数 x に関係する
以下の制約式を完成せよ.
≤ 52
≥ 4x
≥ 3x
≥ 2x
【問題 2】 (分割問題)
4, 6, 14, 19, 25, 31, 45 の合計すると 144 になる 7 つの整数がある. この
7 つの整数を 2 つのグループ A と B に分割し (つまり A ∪ B = {4, 6, 14, 19, 25, 31, 45}, A ∩ B = ∅), A
に属する数の合計と B に属する数の合計との差がなるべく小さくなるように A と B の 2 つのグルー
プに分割したい.
1. この問題を整数計画問題として表現せよ. (ヒント : ナップサック問題と同じような考えをする).
2. 他の問題が全て解けていてるなら, この問題がどれくらい面倒か実際に解いて体感してみよ.
答え
A={
}
【問題 3】
(ジョブスケジューリング問題)
図 2 のように M1 から M5 の 5 台の機械 (machine) で処
理時間が 2 時間, 3 時間, 4 時間, 6 時間, 8 時間かかる仕
事 (job) をそれぞれ 1,2,4,5,2 個処理したい. 各仕事はど
の機械でも処理可能で, 機械による処理時間の違いは無
い (つまりどの機械で処理させても同じ). 図 2 のように
各機械に仕事を割り当てると, 全部の仕事が終るのに 15
時間かかってしまう. なるべく早く全部の仕事を終えた
い. どのように各機械に仕事を割り当てればよいか? こ
の問題を整数計画問題として表現せよ.
M1
M2
M3
M4
M5
図 2: スケジューリング
答え
【問題 4】 (研究室配属問題)
学生が s 人いて, ` 個の研究室がある. 各学生が 1 つの研究室
に配属される. 学生の人数は, 研究室の人数よりかなり多い (つまり s À `). 各研究室 `i には, 定員
(capacity)bi が決まっている. 研究室の定員の合計は学生数 s と等しい. 各学生 sj は, 各研究室 `i に希
望順位をつける. 学生 sj が研究室 `i を第 k 希望の研究室として選んだ場合を cij = k で表す.
1. 各学生が配属された研究室の希望順位の合計がなるべく少なくなるような配属が, なるべく公
平な研究室配属だと考えた. この考えにもとづいた研究室配属問題を整数計画問題として表現
せよ.
答え
2. 上記の考えで配属を行った場合, 学生の反応はどうなるか色々な状況を想像して答えよ. 例えば,
ある研究室を上位に希望する学生が多い場合, 学生から多くの指示をえられるか? それとも多く
の学生が不満を持つか? それとも · · · .
解答
【問題 1】
1. x1 + x2 + x3 + x4 + x5 ≤ 52
2. 10x1 + 5x2 + 4x3 ≥ 4x
3x2 + 6x4 ≥ 3x
3x3 + 5x5 ≥ 2x
【問題 2】
問題文を機械的に数式に翻訳してみと . . .
• 「A に属する数の合計と B に属する数の合計との差がなるべく小さくなるように A と B の 2 つ
のグループに分割したい」とあるので, 4 が A に入るとき x1 = 1, そうでないとき x1 = 0 とす
る. また, 4 が B に入るとき y1 = 1, そうでないとき y1 = 0 とする. 同様に, 6, 14, . . . , 45 に対し
て変数 x2 , x3 , . . . , x7 , y2 , y3 , . . . , y7 を用意する. さらに, (そうすると何かと便利なので) a1 = 4,
a2 = 6, . . ., a7 = 45 としておく.
P
P
• 「A に属する数の合計」は ai xi となり, 「B に属する数の合計」は ai yi となるので, それ
P
P
らの差は | ai xi −
ai yi | と表現できる.
• xi と yi は連動しているので, 例えば xi = 1 なのに yi = 1 でもあるというような, それぞれ勝手
気ままに値をセットされ得る状況は困る. なので, 連動の関係を考慮して, xi = 1 − yi という縛
りを設ける.
• この xi = 1 − yi という縛りを制約条件の中に入れてももちろん良いが, 良く考えると, yi = 1 − xi
ということなので, 各 yi を式から消去できる.
P
P
P
P
• そうすると, 目的関数 | ai xi − ai yi | は, | ai (xi − yi )| = | ai (2xi − 1)| と表現でき, これ
P
P
をもう少し整理すると, |2 ai xi −
ai | と表現できる.
• ここまでをまとめると以下のように書ける:
P
minimize z = 2| ai xi − 72|
subject to
x1 , x2 , x3 , x4 , x5 , x6 , x7 ∈ {0, 1}
絶対値を取るには？
• 分割が問題なので, ここでは目的関数の値 (つまり最適値の表現) は気にせず, 最適解 (つまり分
け方) のみを気にする.
• 2 つに分割したとき, どちらかの集合は 72 以上で, 別の集合は 72 以下である. 72 以上の集合を
A とし, 72 以下の集合を B とする.
• 変数 xi を, 対応する数が集合 B に属する場合 1 で属さない場合 0 をとるとすると:
minimize z = 72 − (4x1 + 6x2 + 14x3 + 19x4 + 25x5 + 31x6 + 45x7 )
subject to
4x1 + 6x2 + 14x3 + 19x4 + 25x5 + 31x6 + 45x7 ≤ 72
x1 ,
x2 ,
x3 ,
x4 ,
x5 ,
x6 ,
x7 ∈ {0, 1}
xi ∈ B とするために上記制約式が必要となる. 上記式は, 中間である 72 に対し, 72 を越えない
ようにしてどれくらい 72 に近づけられるかという考えから得られる.
• 変数 yi を, 対応する数が集合 A に属する場合 1 で属さない場合 0 をとるとすると:
minimize z = (4y1 + 6y2 + 14y3 + 19y4 + 25y5 + 31y6 + 45y7 ) − 72
subject to
4y1 + 6y2 + 14y3 + 19y4 + 25y5 + 31y6 + 45y7 ≥ 72
y1 , y2 ,
y3 ,
y4 ,
y5 ,
y6 ,
y7 ∈ {0, 1}
• 上記 2 つは実質同じです. xi = (1 − yi ) と置いて式変型すると, 上の式から下の式が得られる.
• ナップサック的に考えると以下のようになる:
maximize w = 4x1 + 6x2 + 14x3 + 19x4 + 25x5 + 31x6 + 45x7
subject to
4x1 + 6x2 + 14x3 + 19x4 + 25x5 + 31x6 + 45x7 ≤ 72
x1 , x 2 ,
x3 ,
x4 ,
x5 ,
x6 ,
x7 ≥ 0
これは, 最初の計画問題 (最小化問題) を最大化問題にすり替えるため, 目的関数の両辺に −1 を
P
P
掛け, z を w = −z とすればよい. さらに −72 +
ai xi を最大化することは ai xi を最大化す
ることと同値なので, 上記の最大化問題を得る.
• A = {4, 25, 45}
【問題 3】
• 問題 2 の分割問題は, この問題の特別な場合と考えられる. 実際, 機械が 2 台しかない場合がそ
れにあたる.
• この問題の難しい点は, 目的関数をどう表現するかにある. 自然に考えると max が出てくるの
で, その max をどう処理するかがポイントとなる.
• 変数 xij の意味は, 機械 i に処理時間 j の仕事を xij 個処理させたと解釈する. また, x1 は全ての
仕事が完了した時間を表す.
•
minimize z
= x1
subject to
2x12 + 3x13 + 4x14 + 6x16 + 8x18 − x1 ≤ 0
2x22 + 3x23 + 4x24 + 6x26 + 8x28 − x1 ≤ 0
2x32 + 3x33 + 4x34 + 6x36 + 8x38 − x1 ≤ 0
2x42 + 3x43 + 4x44 + 6x46 + 8x48 − x1 ≤ 0
2x52 + 3x53 + 4x54 + 6x56 + 8x58 − x1 ≤ 0
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 2
x14 + x24 + x34 + x44 + x54 = 4
x16 + x26 + x36 + x46 + x56 = 5
x18 + x28 + x38 + x48 + x58 = 2
x12
, x22 , x32 , x42 , x52 ∈ Z ∗
x13
, x23 , x33 , x43 , x53 ∈ Z ∗
x14
, x24 , x34 , x44 , x54 ∈ Z ∗
x16
, x26 , x36 , x46 , x56 ∈ Z ∗
x18
, x28 , x38 , x48 , x58 ∈ Z ∗
• 図 3 に最適なスケジューリングの一例を示す.
M1
M2
M3
M4
M5
図 3: 最適なスケジューリング
【問題 4】
• 変数 xij を以下のように意味付ける:
(
1 学生 j が研究室 i に配属されたとき
xij =
0 上記以外
• 目的関数は,
minimize
z=
s
X̀ X
cij xij
i=1 j=1
• 変数 xij の性質から,
xij ∈ {0, 1}
i ∈ {1, . . . , `}, j ∈ {1, . . . , s}
• 各研究室 i は丁度 bi 人の学生が配属されるので, 以下の制約式を得る.
x11 + x12 + . . . + x1s = b1
x21 + x22 + . . . + x2s = b2
..
.
x`1 + x`2 + . . . + x`s = b`
• 各学生 j は必ずどこかのの研究室に配属され, 2 つ以上の研究室には所属できないで, 以下の制
約式を得る.
x11 + x21 + . . . + x`1 = 1
x12 + x22 + . . . + x`2 = 1
..
.
x1` + x2` + . . . + xs` = 1
© Copyright 2024 ExpyDoc
