東京工業大学 情報理工学院 数理・計算科学系 2022年8月実施 运筹学

标签：

• TITech
• Linear-Programming-Duality
• Linear-Programming-Problem

Author

思齐塾, 祭音Myyura

Description

問 4

$n$ を 2 以上の整数とし， $\mathbb{R}_{++}$ を正の実数の集合とする． $n$ 次元実ベクトル $\boldsymbol{c}, \boldsymbol{a} \in \mathbb{R}_{++}^n$ と正の実数 $b \in \mathbb{R}_{++}$ に対して，線形計画問題 (P) を以下で定める：

$$\begin{aligned} \text{(P)} \quad \text{maximize} \quad & \boldsymbol{c}^T \boldsymbol{x} \\ \text{subject to} \quad & \boldsymbol{a}^T \boldsymbol{x} \le b, \\ & 0 \le x_i \le 1 \quad (i = 1, \dots, n). \end{aligned}$$

ここで， $\boldsymbol{y}^T$ はベクトル $\boldsymbol{y}$ の転置を表す．ベクトル $\boldsymbol{c}$ と $\boldsymbol{a}$ の要素は

$$\begin{gathered} \frac{c_1}{a_1} \ge \frac{c_2}{a_2} \ge \dots \ge \frac{c_n}{a_n}, \\ a_i \le b \quad (i = 1, \dots, n) \end{gathered}$$

を満たすとし， $\sum_{i=1}^k a_i \le b < \sum_{i=1}^{k+1} a_i$ となる添字 $k \in \{1, \dots, n-1\}$ が存在するとする．このとき，以下の問いに答えよ．

(1) 線形計画問題 (P) の双対問題 (D) を書け．

(2) 線形計画問題 (P) と (D) それぞれの最適解を求め，これらが最適解であることを双対定理に基づいて確認せよ．

(3) 線形計画問題 (P) の最適値を $\alpha$ とし，整数計画問題

$$\begin{aligned} \text{maximize} \quad & \boldsymbol{c}^T \boldsymbol{x} \\ \text{subject to} \quad & \boldsymbol{a}^T \boldsymbol{x} \le b, \\ & \boldsymbol{x} \in \{0, 1\}^n \end{aligned}$$

の最適値を $\bar{\alpha}$ とする．このとき $\bar{\alpha} \ge \frac{1}{2} \alpha$ を示せ．

题目描述

设 $n\geq2$，$\mathbb R_{++}$ 表示正实数集合。给定

$$\boldsymbol c,\boldsymbol a\in\mathbb R_{++}^n, \qquad b\in\mathbb R_{++},$$

考虑线性规划

$$\begin{aligned} \text{(P)}\qquad \text{最大化}\quad&\boldsymbol c^\top\boldsymbol x,\\ \text{约束条件}\quad&\boldsymbol a^\top\boldsymbol x\leq b,\\ &0\leq x_i\leq1\quad(i=1,\ldots,n). \end{aligned}$$

其中上标 $\top$ 表示转置。假设

$$\frac{c_1}{a_1}\geq\frac{c_2}{a_2}\geq\cdots\geq\frac{c_n}{a_n}, \qquad a_i\leq b\quad(i=1,\ldots,n),$$

并且存在 $k\in\{1,\ldots,n-1\}$ 满足

$$\sum_{i=1}^k a_i\leq b <\sum_{i=1}^{k+1}a_i.$$

1. 写出 (P) 的对偶问题 (D)。
2. 分别求 (P) 与 (D) 的最优解，并通过对偶定理验证它们确实最优。
3. 记 (P) 的最优值为 $\alpha$，记相应的 $0$–$1$ 整数规划

$$\begin{aligned} \text{最大化}\quad&\boldsymbol c^\top\boldsymbol x,\\ \text{约束条件}\quad&\boldsymbol a^\top\boldsymbol x\leq b,\\ &\boldsymbol x\in\{0,1\}^n \end{aligned}$$

的最优值为 $\bar\alpha$。证明

$$\bar\alpha\geq\frac12\alpha.$$

Kai

解答

$S_k=\sum_{i=1}^k a_i$ 、 $r=b-S_k$ とおく。仮定から $0\le r<a_{k+1}$ である。

(1) 双対問題

容量制約に双対変数 $y\ge0$ 、上限制約 $x_i\le1$ に $z_i\ge0$ を対応させると

$$\begin{aligned} \text{(D)}\quad \text{minimize}\quad &by+\sum_{i=1}^n z_i\\ \text{subject to}\quad &a_i y+z_i\ge c_i\quad(i=1,\ldots,n),\\ &y\ge0,\quad z_i\ge0\quad(i=1,\ldots,n) \end{aligned}$$

となる。

(2) 最適解

(P) に対して

$$x_i^*=\begin{cases} 1,&1\le i\le k,\\ r/a_{k+1},&i=k+1,\\ 0,&k+2\le i\le n \end{cases}$$

とする。 $0\le r/a_{k+1}<1$ かつ $\boldsymbol a^T\boldsymbol x^*=S_k+r=b$ なので実行可能である。

(D) に対して

$$y^*=\frac{c_{k+1}}{a_{k+1}},\qquad z_i^*=\begin{cases}c_i-a_i y^*,&1\le i\le k,\\0,&k+1\le i\le n\end{cases}$$

とする。 $c_i/a_i$ の降順性から、 $i\le k$ では $z_i^*\ge0$ 、 $i\ge k+1$ では $a_i y^*\ge c_i$ であり、双対実行可能である。

両目的値は

$$\boldsymbol c^T\boldsymbol x^*=\sum_{i=1}^k c_i+\frac{r}{a_{k+1}}c_{k+1}$$

および

$$by^*+\sum_i z_i^*=by^*+\sum_{i=1}^k(c_i-a_i y^*) =\sum_{i=1}^k c_i+r\frac{c_{k+1}}{a_{k+1}}$$

で一致する。弱双対性により両者は最適解であり、

$$\boxed{\alpha=\sum_{i=1}^k c_i+\frac{b-S_k}{a_{k+1}}c_{k+1}}.$$

(3)

最初の $k$ 個だけを選ぶ整数解は実行可能で価値 $C_k=\sum_{i=1}^k c_i$ をもつ。また $a_{k+1}\le b$ より、第 $k+1$ 項だけを選ぶ整数解も実行可能で価値 $c_{k+1}$ をもつ。よって

$$\bar\alpha\ge\max\{C_k,c_{k+1}\}.$$

一方、 $0\le r/a_{k+1}<1$ なので

$$\alpha=C_k+\frac{r}{a_{k+1}}c_{k+1} \le C_k+c_{k+1} \le2\max\{C_k,c_{k+1}\} \le2\bar\alpha.$$

従って

$$\boxed{\bar\alpha\ge\frac12\alpha}.$$