跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2019年8月実施 午前 問4

标签：

Author​

思齐塾, 祭音Myyura

Description​

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

P(θ):最小化:5x1+x2+x3制約:x1+6x3≥8+θ3x1−x2+8x3≥33x2≥4+272θx1,x2,x3≥0.\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}

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

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

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

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

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

题目描述​

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

P(θ):最小化5x1+x2+x3,约束条件x1+6x3≥8+θ,3x1−x2+8x3≥3,3x2≥4+272θ,x1,x2,x3≥0.\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}

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

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

Kai​

解答​

(1)​

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

D(θ):最大化(8+θ)y1+3y2+(4+272θ)y3,制約y1+3y2≤5,−y2+3y3≤1,6y1+8y2≤1,y1,y2,y3≥0\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)​

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

y1=16−43y2−16u3,y3=13+13y2−13u2,u1=296−53y2+16u3,z=83−193y2−43u2−43u3.\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}

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

y∗=[1/601/3],z∗=83\boxed{y^*=\begin{bmatrix}1/6\\0\\1/3\end{bmatrix}}, \qquad z^*=\frac83

を得る。

(3)​

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

zθ=83+143θ+196(θ−2)y2−(43+92θ)u2−8+θ6u3.\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∗y^* が最適であるための還元費用条件は

θ≤2,θ≥−827,θ≥−8.\theta\le2,\qquad \theta\ge-\frac{8}{27},\qquad \theta\ge-8.

これらをまとめると

−827≤θ≤2.\boxed{-\frac{8}{27}\le\theta\le2}.

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

(4)​

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

6x3=8+θ,3x2=4+272θ6x_3=8+\theta,\qquad 3x_2=4+\frac{27}{2}\theta

より

x∗(θ)=[043+92θ8+θ6](−827≤θ≤2).\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)}.

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

−x2+8x3−3=196(2−θ)≥0-x_2+8x_3-3=\frac{19}{6}(2-\theta)\ge0

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

本页目录