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

标签：

• TITech
• Simplex-Method
• Linear-Programming-Duality
• Linear-Programming-Problem

Author

思齐塾, 祭音Myyura

Description

パラメータ $\theta \in \mathbb{R}$ をもつ次の線形計画問題 $\mathcal{P}(\theta)$ を考える：

$$\mathcal{P}(\theta) : \begin{aligned} \text{最小化} \quad & : 5x_1 + x_2 + x_3 \\ \text{制約} \quad & : \begin{aligned} x_1 + 6x_3 & \ge 8 + \theta \\ 3x_1 - x_2 + 8x_3 & \ge 3 \\ 3x_2 & \ge 4 + \frac{27}{2}\theta \\ x_1, x_2, x_3 & \ge 0. \end{aligned} \end{aligned}$$

$\mathcal{P}(\theta)$ の双対問題を $\mathcal{D}(\theta)$ とする．以下の問に答えよ．

(1) $\mathcal{D}(\theta)$ を書き下せ．

(2) $\mathcal{D}(0)$ の最適解を $\boldsymbol{y}^*$ とする． $\boldsymbol{y}^*$ をシンプレックス法により求めよ．

(3) $\boldsymbol{y}^*$ が $\mathcal{D}(\theta)$ の最適解でもある $\theta$ の範囲を求めよ．

(4) $\mathcal{P}(\theta)$ の最適解を $\boldsymbol{x}^*(\theta)$ とする．(3) で求めた $\theta$ の範囲において， $\theta$ を用いて $\boldsymbol{x}^*(\theta)$ を表せ．

题目描述

对实参数 $\theta$，考虑线性规划问题

$$\mathcal P(\theta): \begin{aligned} \text{最小化}\quad&5x_1+x_2+x_3,\\ \text{约束条件}\quad &x_1+6x_3\geq8+\theta,\\ &3x_1-x_2+8x_3\geq3,\\ &3x_2\geq4+\frac{27}{2}\theta,\\ &x_1,x_2,x_3\geq0. \end{aligned}$$

把 $\mathcal P(\theta)$ 的对偶问题记为 $\mathcal D(\theta)$。

1. 明确写出 $\mathcal D(\theta)$。
2. 设 $\boldsymbol y^*$ 是 $\mathcal D(0)$ 的最优解，用单纯形法求 $\boldsymbol y^*$。
3. 求使同一个 $\boldsymbol y^*$ 仍为 $\mathcal D(\theta)$ 最优解的全部 $\theta$ 取值。
4. 记 $\mathcal P(\theta)$ 的最优解为 $\boldsymbol x^*(\theta)$。在第 3 问所得参数范围内，用 $\theta$ 表示 $\boldsymbol x^*(\theta)$。

Kai

解答

(1)

主問題は「最小化、 $Ax\ge b$ 、 $x\ge0$ 」の形なので、双対変数を $y_1,y_2,y_3\ge0$ とすると双対問題は

$$\mathcal D(\theta):\quad \begin{aligned} \text{最大化}\quad & (8+\theta)y_1+3y_2+\left(4+\frac{27}{2}\theta\right)y_3,\\ \text{制約}\quad &y_1+3y_2\le5,\\ &-y_2+3y_3\le1,\\ &6y_1+8y_2\le1,\\ &y_1,y_2,y_3\ge0 \end{aligned}$$

である。

(2)

各制約にスラック変数 $u_1,u_2,u_3\ge0$ を加える。 $\theta=0$ で、初期基底 $(u_1,u_2,u_3)$ から $y_1$ を入れて $u_3$ を出し、次に $y_3$ を入れて $u_2$ を出すシンプレックス・ピボットを行うと、最終辞書は

$$\begin{aligned} y_1&=\frac16-\frac43y_2-\frac16u_3,\\ y_3&=\frac13+\frac13y_2-\frac13u_2,\\ u_1&=\frac{29}{6}-\frac53y_2+\frac16u_3,\\ z&=\frac83-\frac{19}{3}y_2-\frac43u_2-\frac43u_3. \end{aligned}$$

非基底変数 $y_2,u_2,u_3$ の目的関数係数はすべて非正なので、この辞書は最適である。非基底変数を $0$ として

$$\boxed{y^*=\begin{bmatrix}1/6\\0\\1/3\end{bmatrix}}, \qquad z^*=\frac83$$

を得る。

(3)

同じ基底辞書へパラメータ付き目的関数を代入すると

$$\begin{aligned} z_\theta ={}&\frac83+\frac{14}{3}\theta +\frac{19}{6}(\theta-2)y_2\\ &-\left(\frac43+\frac92\theta\right)u_2 -\frac{8+\theta}{6}u_3. \end{aligned}$$

したがって $y^*$ が最適であるための還元費用条件は

$$\theta\le2,\qquad \theta\ge-\frac{8}{27},\qquad \theta\ge-8.$$

これらをまとめると

$$\boxed{-\frac{8}{27}\le\theta\le2}.$$

実際、この基底解では $y_1=1/6$ 、 $y_3=1/3$ 、 $u_1=29/6$ がすべて正である。上の範囲外では正の還元費用をもつ非基底変数を微小に増加させて目的値を改善できるため、この条件は必要でもある。

(4)

(3) の範囲では $y_1^*>0$ 、 $y_3^*>0$ なので、相補性条件より主問題の第1、第3制約は等号となる。また双対の第1制約には正のスラック $5-1/6$ があるので $x_1=0$ である。したがって

$$6x_3=8+\theta,\qquad 3x_2=4+\frac{27}{2}\theta$$

より

$$\boxed{x^*(\theta)= \begin{bmatrix} 0\\[2pt] \dfrac43+\dfrac92\theta\\[2pt] \dfrac{8+\theta}{6} \end{bmatrix} \quad\left(-\frac{8}{27}\le\theta\le2\right)}.$$

この範囲では $x_2,x_3\ge0$ であり、残る第2制約も

$$-x_2+8x_3-3=\frac{19}{6}(2-\theta)\ge0$$

を満たすので、確かに主問題の実行可能解である。