1. No category

離散最適化基礎論 (1)
演習問題
2014 年 10 月 3 日
岡本 吉央
提出締切： 2014 年 10 月 10 日
復習問題 1.1 次の線形計画問題の最適解を１つ答えよ．ま
で定義する．このとき，(P) と (D) に最適解が存在し，(P)
た，最適値を答えよ．
と (D) の最適値が等しいならば，(P) と (LP) の最適値も
maximize
x1 + 2x2
subject to
2x1 + 3x2 ≤ 6,
等しいことを証明せよ．(ヒント：線形計画問題の強双対定
理を利用してもよい．)
補足問題 1.5 任意の自然数 k と任意の s ∈ Rk と t ∈ Rk を
−x1 + 2x2 ≤ 2,
考える．このとき，s ≤ 0 かつ t ≥ 0 であるならば，s t ≤ 0
x1 ≥ 0, x2 ≥ 0.
となることを証明せよ．
復習問題 1.2 次の整数計画問題の最適解を 1 つ答えよ．ま
追加問題 1.6 任意の自然数 m, n と任意の A ∈ Rm×n , b ∈
た，最適値を答えよ．
Rm , c ∈ Rn に対して，次の線形計画問題 (P’)
maximize
x1 + 2x2
maximize
c x
subject to
2x1 + 3x2 ≤ 6,
subject to
Ax = b, x ≥ 0
−x1 + 2x2 ≤ 2,
を考え，その双対問題 (D’) を
x1 ≥ 0, x2 ≥ 0
minimize
x1 , x2 ∈ Z
subject to
復習問題 1.3 任意の自然数 m, n と任意の A ∈ R
m×n
,b ∈
A y≥c
と定義する．
R , c ∈ R に対して，次の線形計画問題 (P)
m
b y
n
maximize
c x
subject to
Ax ≤ b
1. x ∈ Rn が (P’) の許容解であり，かつ，y ∈ Rm が
(D’) の許容解であるならば，c x ≤ b y が成り立つ
ことを証明せよ．
2. 問題 1.3 にある (P) と (D) に対して強双対定理が成
とその双対問題 (D)
り立つことを仮定し，本問題の (P’) と (D’) に対して
minimize
b y
強双対定理が成り立つことを証明せよ．
A y = c, y ≥ 0
subject to
追加問題 1.7 任意の自然数 m, n と任意の A ∈ Rm×n , b ∈
を考える．このとき，x ∈ R が (P) の許容解であり，かつ， Rm , c ∈ Rn に対して，次の線形計画問題 (P’)
y ∈ Rm が (D) の許容解であるならば，c x ≤ b y が成り
maximize
c x
立つことを証明せよ．
subject to
Ax ≤ b, x ≥ 0
復習問題 1.4 任意の自然数 m, n と任意の A ∈ Rm×n , b ∈
を考え，その双対問題 (D’) を
Rm , c ∈ Rn に対して，次の整数計画問題 (P)
n
minimize
maximize
c x
subject to
Ax ≤ b, x ∈ Zn
subject to
subject to
A y ≥ c, y ≥ 0
と定義する．
と別の整数計画問題 (D)
minimize
b y
1. x ∈ Rn が (P’) の許容解であり，かつ，y ∈ Rm が
(D’) の許容解であるならば，c x ≤ b y が成り立つ
b y
A y = c, y ≥ 0, y ∈ Zm
ことを証明せよ．
を考える．また，(P) の線形計画緩和 (LP) を
maximize
c x
subject to
Ax ≤ b
2. 問題 1.3 にある (P) と (D) に対して強双対定理が成
り立つことを仮定し，本問題の (P’) と (D’) に対して
強双対定理が成り立つことを証明せよ．
1