最適化・線形計画法

ある工場では $2$ 種類の製品 $\mathrm{P}$, $\mathrm{Q}$ を作っている。それぞれを $1$ 個作るのに必要な原料・作業時間・機械時間と、$1$ 個あたりの利益は次のとおりである。

• 製品 $\mathrm{P}$：原料 $2\mathrm{kg}$、作業時間 $1$ 時間、機械時間 $3$ 時間、利益 $4$ 千円
• 製品 $\mathrm{Q}$：原料 $1\mathrm{kg}$、作業時間 $3$ 時間、機械時間 $2$ 時間、利益 $5$ 千円

$1$ 日に使える量は、原料 $10\mathrm{kg}$、作業時間 $15$ 時間、機械時間 $18$ 時間までである。製品 $\mathrm{P}$, $\mathrm{Q}$ の $1$ 日の生産量をそれぞれ $x_1$, $x_2$（$0$ 以上の実数）とし、$1$ 日の利益を最大にする問題を
$$\max c^{\top }x,Ax\leqq b,x\geqq 0\left(x=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\right)$$
の形に定式化する。ただし $A$ の第 $1$ 行・第 $2$ 行・第 $3$ 行をそれぞれ原料・作業時間・機械時間の制約とする。

さらに、各制約に $0$ 以上のスラック変数 $s_1$（原料）, $s_2$（作業時間）, $s_3$（機械時間）を加えて、等式制約の標準形
$$Ax+s=b,x\geqq 0,s\geqq 0\left(s=\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\right)\right)$$
に直す。生産計画 $(x_1,x_2)=(2,3)$ に対応するスラック変数の値 $(s_1,s_2,s_3)$ をこの順に求めよ。

ある工場では 2 種類の製品 $\mathrm{P},\mathrm{Q}$ を生産している。製品 1 単位あたりに必要な資源と利益は次のとおりである。

• 製品 $\mathrm{P}$：原料 A を $2\mathrm{kg}$、原料 B を $1\mathrm{kg}$、機械時間を $1$ 時間使い、利益は $3$ 万円
• 製品 $\mathrm{Q}$：原料 A を $1\mathrm{kg}$、原料 B を $3\mathrm{kg}$、機械時間を $1$ 時間使い、利益は $2$ 万円

使える量は、原料 A が $10\mathrm{kg}$、原料 B が $15\mathrm{kg}$、機械時間が $6$ 時間である。製品 $\mathrm{P},\mathrm{Q}$ の生産量をそれぞれ $x,y$（単位）とする。$x,y$ は $0$ 以上の実数とし、利益の合計を最大にしたい。

この問題を線形計画問題 $\max c^{\top }\mathbf{x}$, $A\mathbf{x}\le b$, $\mathbf{x}\ge 0$（$\mathbf{x}=(x,y{)}^{\top }$）の形に定式化し、原料 A・原料 B・機械時間の制約にこの順にスラック変数 $s_1,s_2,s_3(\ge 0)$ を加えて等式制約の標準形に直す。利益の合計が最大となる生産計画におけるスラック変数の値の組 $(s_1,s_2,s_3)$ を求めよ。

ある工場では $2$ 種類の製品 $\mathrm{X},\mathrm{Y}$ を作っている。製品 $\mathrm{X}$ を $1$ 単位作るには原料 $\mathrm{P}$ が $2\mathrm{kg}$、原料 $\mathrm{Q}$ が $1\mathrm{kg}$、機械の稼働時間が $1$ 時間必要で、利益は $3$ 万円である。製品 $\mathrm{Y}$ を $1$ 単位作るには原料 $\mathrm{P}$ が $1\mathrm{kg}$、原料 $\mathrm{Q}$ が $3\mathrm{kg}$ 必要で、機械は使わず、利益は $4$ 万円である。$1$ 日に使える原料 $\mathrm{P}$ は $10\mathrm{kg}$、原料 $\mathrm{Q}$ は $15\mathrm{kg}$、機械の稼働時間は $4$ 時間までである。

製品 $\mathrm{X},\mathrm{Y}$ の $1$ 日の生産量をそれぞれ $x,y$ 単位（$x,y$ は $0$ 以上の実数）として、$1$ 日の利益（万円）を最大にする線形計画問題 $\max c^{\top }\mathbf{x}$, $A\mathbf{x}\le b$, $\mathbf{x}\ge 0$ を立てる。ただし制約は原料 $\mathrm{P}$、原料 $\mathrm{Q}$、機械の稼働時間の順に並べる。この $3$ つの不等式制約にそれぞれスラック変数 $s_1,s_2,s_3(\ge 0)$ を加えて等式制約の標準形に直したとき、利益を最大にする生産計画における $(s_1,s_2,s_3)$ をこの順に求めよ。

$a$ を実数の定数とし、実数全体で定義された関数
$$f(x)=x^4-4x^3+a{x}^2$$
を考える。ここで $f$ が $\mathbb{R}$ 上の凸関数であるとは、任意の実数 $p,q$ と $0\le \lambda \le 1$ を満たす任意の実数 $\lambda$ に対して
$$f(\lambda p+(1-\lambda )q)\le \lambda f(p)+(1-\lambda )f(q)$$
が成り立つことをいう。$f$ が $\mathbb{R}$ 上の凸関数となるような $a$ の最小値を求めよ。

$a$ を実数の定数とし、$\mathbb{R}$ 上の関数
$$f(x)=x^4+a{x}^3+6x^2$$
を考える。$f$ が $\mathbb{R}$ 全体で凸関数となるような $a$ の最大値を求めよ。

実数 $x$ の関数
$$f(x)=x^4-4x^3+x$$
を考える。実数 $c$ に対して、$f$ が区間 $[c,\infty )$ 上で凸関数となる、すなわち区間内の任意の $p,q$ と $0\le \lambda \le 1$ を満たす任意の実数 $\lambda$ に対して
$$f(\lambda p+(1-\lambda )q)\le \lambda f(p)+(1-\lambda )f(q)$$
が成り立つような $c$ の最小値を求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+2y^2\\ \text{subject to}& g(x,y)=6-x-2y\le 0\end{array}$$
この問題の KKT 条件
$$\nabla f(x,y)+\mu \nabla g(x,y)=0,g(x,y)\le 0,\mu \ge 0,\mu g(x,y)=0$$
をみたす $(x,y,\mu )$ はただ 1 組である。その組を $(x,y,\mu )$ の順に求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+2y^2\\ \text{subject to}& g(x,y)=3-x-y\le 0\end{array}$$
この問題の KKT 条件
$$\nabla f(x,y)+\mu \nabla g(x,y)=0,\mu \ge 0,\mu g(x,y)=0,g(x,y)\le 0$$
をみたす点 $(x,y)$ と乗数 $\mu$ を求め、組 $(x,y,\mu )$ の形で答えよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+2y^2\\ \text{subject to}& g(x,y)=3-x-y\le 0\end{array}$$
この問題の KKT 条件
$$\nabla f(x,y)+\mu \nabla g(x,y)=0,g(x,y)\le 0,\mu \ge 0,\mu g(x,y)=0$$
をみたす点 $(x,y)$ と乗数 $\mu$ はただ 1 組ある。これを組 $(x,y,\mu )$ の形で求めよ。

実数 $x_1,x_2,x_3,x_4$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=x_1+3x_2+4x_3\\ \text{subject to}& x_1+x_2+x_3+x_4=6,\\ & x_1+2x_2+3x_3=10,\\ & x_1,x_2,x_3,x_4\ge 0\end{array}$$
基底解を列挙することにより、この問題の最適解を求め、組 $(x_1,x_2,x_3,x_4)$ の形で答えよ。

実数 $x_1,x_2,x_3$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=3x_1+4x_2+2x_3\\ \text{subject to}& x_1+x_2+x_3=6,\\ & x_1+2x_2+3x_3=10,\\ & x_1\geqq 0,x_2\geqq 0,x_3\geqq 0\end{array}$$
基底解をすべて求めて調べることにより、$z$ の最大値と、最大値を与える $(x_1,x_2,x_3)$ を求めよ。答えは $(z\text{ の最大値},x_1,x_2,x_3)$ の順の組で答えよ。

実数 $x_1,x_2,x_3$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=2x_1+3x_2+x_3\\ \text{subject to}& x_1+x_2+x_3=6,\\ & x_1+2x_2+3x_3=10,\\ & x_1\ge 0,x_2\ge 0,x_3\ge 0\end{array}$$
基底解をすべて求めて実行可能かを調べることにより、この問題の最適解 $(x_1,x_2,x_3)$ を求めよ。

実数 $x_1,x_2$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 2x_1+3x_2\\ \text{subject to}& x_1+x_2\leqq 4,\\ & x_1+3x_2\leqq 6,\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
$(\mathrm{P})$ の双対問題 $(\mathrm{D})$（実数 $y_1,y_2$ についての最小化問題）を作り、$(\mathrm{D})$ の最適値（目的関数の最小値）を求めよ。

実数 $y_1,y_2,y_3$ についての次の線形計画問題 $(\mathrm{D})$ を考える。
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 5y_1+8y_2+8y_3\\ \text{subject to}& y_1+y_2+2y_3\geqq 3\\ & y_1+2y_2+y_3\geqq 2\\ & y_1\geqq 0,y_2\geqq 0,y_3\geqq 0\end{array}$$
$(\mathrm{D})$ の最小値を求めよ。

実数 $x_1,x_2,x_3$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 3x_1+5x_2+4x_3\\ \text{subject to}& x_1+x_2+x_3\leqq 5\\ & x_1+2x_2+3x_3\leqq 8\\ & x_1\geqq 0,x_2\geqq 0,x_3\geqq 0\end{array}$$
$(\mathrm{P})$ の双対問題 $(\mathrm{D})$ を作ると、変数は 2 つになる。$(\mathrm{D})$ を座標平面上の図を使って解き、強双対定理を用いて $(\mathrm{P})$ の最適値（目的関数の最大値）を求めよ。

$a$ を実数の定数とし、${\mathbb{R}}^2$ 上の関数
$$f(x,y)=3x^2+2axy+12y^2+x-y$$
を考える。$f$ が ${\mathbb{R}}^2$ 全体で凸関数となるような $a$ の最大値を求めよ。

$a$ を実数の定数とし、${\mathbb{R}}^2$ 上の関数
$$f(x,y)=x^4+3x^2+2axy+y^2$$
を考える。$f$ が ${\mathbb{R}}^2$ 全体で凸関数となるような $a$ の最大値を求めよ。

${\mathbb{R}}^2$ 上の関数
$$f(x,y)=x^3+y^3-3xy$$
を考える。正の実数 $t$ に対して、正方形の領域
$$D_t=\{(x,y)\in {\mathbb{R}}^2\mid t\le x\le t+1,t\le y\le t+1\}$$
を定める。$f$ が $D_t$ 上で凸関数となるような $t$ の最小値を求めよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=3x_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4\\ & 2x_1+x_2\leqq 6\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数 $s_1,s_2(\geqq 0)$ を導入し、原点 $(x_1,x_2)=(0,0)$ を初期基底解として単体法で解け。入る変数は目的関数の係数（被約費用）が最大の非基底変数とする。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形でこの順に答えよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=4x_1+3x_2\\ \text{subject to}& x_1+x_2\leqq 5\\ & 2x_1+x_2\leqq 8\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数を導入して初期辞書（またはシンプレックス表）を作り、単体法で解け。入る変数は目的関数の係数が最大の非基底変数とし、出る変数は最小比テストで決めること。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形でこの順に答えよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=3x_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4\\ & 2x_1+x_2\leqq 6\\ & x_2\leqq 3\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数 $s_1,s_2,s_3(\geqq 0)$ を加えて初期辞書を作り、単体法（入る変数には目的関数の行で係数が正のもののうち最大のものを選ぶ）で解け。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形で答えよ。

実数 $x_1,x_2$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 4x_1+3x_2\\ \text{subject to}& x_1+x_2\leqq 5\\ & 2x_1+x_2\leqq 8\\ & x_1+3x_2\leqq 12\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
$(\mathrm{P})$ の最適解は $(x_1^{\ast },x_2^{\ast })=(3,2)$ である。$(\mathrm{P})$ の双対問題
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 5y_1+8y_2+12y_3\\ \text{subject to}& y_1+2y_2+y_3\geqq 4\\ & y_1+y_2+3y_3\geqq 3\\ & y_1\geqq 0,y_2\geqq 0,y_3\geqq 0\end{array}$$
の最適解 $(y_1,y_2,y_3)$ を、相補性条件を用いて求めよ。答えは組 $(y_1,y_2,y_3)$ の形で書け。

実数 $x_1,x_2$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 4x_1+3x_2\\ \text{subject to}& x_1+x_2\leqq 5\\ & 2x_1+x_2\leqq 8\\ & x_2\leqq 4\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
その双対問題は、実数 $y_1,y_2,y_3$ についての
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 5y_1+8y_2+4y_3\\ \text{subject to}& y_1+2y_2\geqq 4\\ & y_1+y_2+y_3\geqq 3\\ & y_1\geqq 0,y_2\geqq 0,y_3\geqq 0\end{array}$$
である。$(\mathrm{P})$ の最適解が $(x_1^{\ast },x_2^{\ast })=(3,2)$ であることが分かっているとき、相補性条件を用いて $(\mathrm{D})$ の最適解 $(y_1^{\ast },y_2^{\ast },y_3^{\ast })$ を求めよ。

実数 $x_1,x_2$ についての線形計画問題 $(\mathrm{P})$ と、実数 $y_1,y_2,y_3$ についてのその双対問題 $(\mathrm{D})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 5x_1+4x_2\\ \text{subject to}& x_1+x_2\leqq 5\\ & 2x_1+x_2\leqq 8\\ & x_1+3x_2\leqq 12\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 5y_1+8y_2+12y_3\\ \text{subject to}& y_1+2y_2+y_3\geqq 5\\ & y_1+y_2+3y_3\geqq 4\\ & y_1\geqq 0,y_2\geqq 0,y_3\geqq 0\end{array}$$
$(\mathrm{P})$ の最適解は $(x_1^{\ast },x_2^{\ast })=(3,2)$ であることがわかっている。相補性条件を用いて、$(\mathrm{D})$ の最適解 $(y_1,y_2,y_3)$ を求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+2y^2\\ \text{subject to}& g(x,y)=3-x-y\le 0\end{array}$$
この問題が凸計画問題であることを確かめ、KKT 条件を満たす点を求めて、$f(x,y)$ の最小値を求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+2y^2\\ \text{subject to}& g(x,y)=3-x-y\le 0\end{array}$$
この問題が凸計画問題であることを確かめ、KKT 条件を用いて $f$ の最小値を求めよ。

正の実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=\frac{1}{x}+\frac{4}{y}\\ \text{subject to}& g(x,y)=x+y-3\le 0,x>0,y>0\end{array}$$
この問題が凸計画問題であることを確かめ、KKT 条件を解いて最小値を求めよ。

$c$ を実数の定数とし、次の線形計画問題 $({\mathrm{Q}}_c)$ を考える。
$$({\mathrm{Q}}_c)\begin{array}{rl}\text{maximize}& c{x}_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4,\\ & x_1+3x_2\leqq 6,\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
点 $x^{\ast }=(x_1,x_2)=(3,1)$ は $c$ の値によらず実行可能解である。$x^{\ast }$ が $({\mathrm{Q}}_c)$ の最適解となるような $c$ の範囲は $\alpha \leqq c\leqq \beta$ の形に表される。$\alpha$ と $\beta$ をこの順に組 $(\alpha ,\beta )$ で求めよ。

$c$ を実数の定数とし、次の線形計画問題 $({\mathrm{P}}_c)$ を考える。
$$({\mathrm{P}}_c)\begin{array}{rl}\text{maximize}& c{x}_1+2x_2\\ \text{subject to}& x_1+x_2\le 4\\ & x_1+3x_2\le 6\\ & x_1\ge 0,x_2\ge 0\end{array}$$
点 $(x_1,x_2)=(3,1)$ が $({\mathrm{P}}_c)$ の最適解（の一つ）となるような $c$ の範囲は $p\le c\le q$ の形に表される。双対問題の解を用いて、$p$ と $q$ をこの順に求めよ。

$c$ を実数の定数とし、次の線形計画問題 $({\mathrm{Q}}_c)$ を考える。
$$({\mathrm{Q}}_c)\begin{array}{rl}\text{maximize}& c{x}_1+2x_2\\ \text{subject to}& x_1+x_2\le 4\\ & x_1+3x_2\le 6\\ & x_1\ge 0,x_2\ge 0\end{array}$$
点 $(x_1,x_2)=(3,1)$ が $({\mathrm{Q}}_c)$ の最適解となるような $c$ の範囲は $\alpha \le c\le \beta$ の形に表される。$\alpha ,\beta$ を求め、組 $(\alpha ,\beta )$ の形で答えよ。

実数 $x,y$ が次の制約条件を満たすとする。
$$x+2y\le 14,3x+y\le 18,x-y\le 4,x\ge 0,y\ge 0$$
このとき、目的関数 $z=5x+4y$ の最大値を求めよ。

実数 $x,y$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{minimize}& z=3x+2y\\ \text{subject to}& x+y\ge 6,\\ & x+3y\ge 10,\\ & 2x+y\ge 8,\\ & x\ge 0,y\ge 0\end{array}$$
この問題の最適解はただ 1 つである。最適解 $(x,y)$ を組で求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=(x-4{)}^2+(y-1{)}^2\\ \text{subject to}& g_1(x,y)=x+2y-4\le 0,\\ & g_2(x,y)=-x\le 0,\\ & g_3(x,y)=-y\le 0.\end{array}$$
KKT 条件を
$$\nabla f(x,y)+{\mu }_1\nabla g_1(x,y)+{\mu }_2\nabla g_2(x,y)+{\mu }_3\nabla g_3(x,y)=0,{\mu }_i\ge 0,{\mu }_i{g}_i(x,y)=0(i=1,2,3)$$
と、制約 $g_i(x,y)\le 0(i=1,2,3)$ の組とする。この問題の最適解 $(x^{\ast },y^{\ast })$ と、そこでの KKT 乗数 ${\mu }_1^{\ast }$ を、組 $(x^{\ast },y^{\ast },{\mu }_1^{\ast })$ の形で求めよ。

5 個のデータ点
$$(x_i,y_i)=(0,1),(1,2),(2,2),(3,4),(4,5)(i=1,2,3,4,5)$$
に、実数 $a,b$ を係数とする直線 $y=a+bx$ を当てはめる。残差の二乗和
$$S(a,b)=\sum _{i=1}^5{\left(y_i-a-b{x}_i\right)}^2$$
を最小にする $(a,b)$ を、正規方程式 $A^{\mathsf{T}}A\left(\begin{array}{c}a\\ b\end{array}\right)=A^{\mathsf{T}}\mathbf{y}$（$A$ は第 $i$ 行が $(1,x_i)$ の $5\times 2$ 行列、$\mathbf{y}=(y_1,\dots ,y_5{)}^{\mathsf{T}}$）を解いて求め、組 $(a,b)$ の形で答えよ。

実数 $x,y$ についての次の連立一次方程式を考える。
$$\{\begin{array}{l}x+y=1\\ x-y=2\\ 2x+y=4\end{array}$$
この連立方程式は解をもたない。そこで、各式の左辺と右辺の差の二乗和
$$S(x,y)=(x+y-1{)}^2+(x-y-2{)}^2+(2x+y-4{)}^2$$
を最小にする実数の組 $(x,y)$（最小二乗解）を考える。$S(x,y)$ を最小にする $(x,y)$ を求めよ。

$a$ を実数の定数とし、${\mathbb{R}}^2$ 上の関数
$$f(x,y)=e^x+a{x}^2+4xy+2y^2$$
を考える。$f$ が ${\mathbb{R}}^2$ 全体で凸関数となるような $a$ の最小値を求めよ。

実数 $x,y$ についての次の連立一次方程式を考える。
$$\{\begin{array}{l}x+y=2\\ x-y=0\\ 2x+y=5\end{array}$$
この連立方程式は解をもたない。そこで、残差の二乗和
$$S(x,y)=(x+y-2{)}^2+(x-y{)}^2+(2x+y-5{)}^2$$
を最小にする実数の組 $(x,y)$（最小二乗解）を考える。この組 $(x,y)$ をこの順に求めよ。

${\mathbb{R}}^2$ 上の関数
$$f(x,y)=5x^2+4xy+2y^2-3x+y$$
を考える。実数 $m$ に対して $g_m(x,y)=f(x,y)-\frac{m}{2}(x^2+y^2)$ が ${\mathbb{R}}^2$ 上で凸関数となるような $m$ の最大値を $m_0$、実数 $L$ に対して $h_L(x,y)=\frac{L}{2}(x^2+y^2)-f(x,y)$ が ${\mathbb{R}}^2$ 上で凸関数となるような $L$ の最小値を $L_0$ とする。$(m_0,L_0)$ をこの順に求めよ。

実数 $x_1,x_2$ を変数とする次の線形計画問題を考える。
$$\begin{array}{rl}\text{最大化}& 3x_1+2x_2\\ \text{制約}& x_1+x_2\le 4,\\ & x_1+3x_2\le 6,\\ & x_1\le 3,\\ & x_1\ge 0,x_2\ge 0\end{array}$$
この問題の最適解（制約をすべて満たし、目的関数 $3x_1+2x_2$ の値を最大にする点 $(x_1,x_2)$）はただ 1 つで、それが $(x_1,x_2)=(3,1)$ であることを証明せよ。

関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x,y)=x^2-2xy+3y^2+e^{x+y}$$
で定める。$f$ が ${\mathbb{R}}^2$ 上で狭義凸関数であることを証明せよ。

ここで $f$ が狭義凸関数であるとは、相異なる任意の 2 点 $\mathbf{p},\mathbf{q}\in {\mathbb{R}}^2$ と $0<\lambda <1$ を満たす任意の実数 $\lambda$ に対して
$$f(\lambda \mathbf{p}+(1-\lambda )\mathbf{q})<\lambda f(\mathbf{p})+(1-\lambda )f(\mathbf{q})$$
が成り立つことをいう。

なお、次の事実は用いてよい: 「${\mathbb{R}}^2$ 上の $C^2$ 級関数 $g$ のヘッセ行列 ${\nabla }^{2}g(x,y)$ が、すべての $(x,y)\in {\mathbb{R}}^2$ で正定値ならば、$g$ は ${\mathbb{R}}^2$ 上で狭義凸関数である。」

$xy$ 平面上の 5 点で、ある量 $z$ を測定したところ、次のデータ $(x_i,y_i,z_i)$ $(i=1,2,3,4,5)$ を得た。
$$(0,0,1),(1,0,2),(0,1,4),(1,1,4),(2,1,7)$$
このデータに、実数 $a,b,c$ を係数とする平面のモデル $z=a+bx+cy$ を当てはめる。残差の二乗和
$$S(a,b,c)=\sum _{i=1}^5{\left(z_i-a-b{x}_i-c{y}_i\right)}^2$$
を $a,b,c$ が実数全体を動くときに考える。$S(a,b,c)$ の最小値を求めよ。

次の $5$ 個のデータ $(t_i,y_i)$ $(i=1,2,\dots ,5)$ が与えられている。
$$(t_i,y_i)=(-2,6),(-1,1),(0,0),(1,2),(2,7)$$
このデータに $2$ 次関数のモデル $y=a+bt+c{t}^2$ （$a,b,c$ は実数）を当てはめる。残差の二乗和
$$S(a,b,c)=\sum _{i=1}^5{\left(y_i-a-b{t}_i-c{t}_i^2\right)}^2$$
を最小にする $a,b,c$ を最小二乗法で求めたとき、$S(a,b,c)$ の最小値を求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=x^2+xy+y^2-6x\\ \text{subject to}& g_1(x,y)=x+y-1\le 0,\\ & g_2(x,y)=x-y-3\le 0.\end{array}$$
ラグランジュ関数を
$$L(x,y,{\mu }_1,{\mu }_2)=f(x,y)+{\mu }_1{g}_1(x,y)+{\mu }_2{g}_2(x,y)$$
とし、${\mu }_1,{\mu }_2\ge 0$ を KKT 乗数とする。この問題の最適解 $(x^{\ast },y^{\ast })$ と、それに対応する KKT 乗数 ${\mu }_1^{\ast },{\mu }_2^{\ast }$ を求め、$(x^{\ast },y^{\ast },{\mu }_1^{\ast },{\mu }_2^{\ast })$ の順に答えよ。

$a$ を実数の定数とし、${\mathbb{R}}^3$ 上の関数
$$f(x,y,z)=x^4+x^2+2y^2+3z^2+2axy+2yz$$
を考える。$f$ が ${\mathbb{R}}^3$ 上で凸関数となるような $a$ の最大値を求めよ。

$2$ つの倉庫 $\mathrm{A},\mathrm{B}$ から $3$ つの店舗 $\mathrm{P},\mathrm{Q},\mathrm{R}$ へ、ある品物を輸送する。倉庫 $\mathrm{A},\mathrm{B}$ の在庫はそれぞれ $30$, $40$（単位：トン）で、在庫はすべて出荷する。店舗 $\mathrm{P},\mathrm{Q},\mathrm{R}$ の需要はそれぞれ $20$, $25$, $25$（トン）で、ちょうど需要量だけ受け取る。$1$ トンあたりの輸送費（単位：万円）は次の表のとおりである。

ただし、$\mathrm{B}$ から $\mathrm{Q}$ への輸送量は $15$ トン以下でなければならない。各経路の輸送量は $0$ 以上の実数で、総輸送費は各経路の（輸送量）$\times$（$1$ トンあたりの輸送費）の和とする。総輸送費の最小値（万円）を求めよ。

実数 $x_1,x_2,x_3$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{maximize}& f(x_1,x_2,x_3)=\log (1+x_1)+\log (2+x_2)+\log (4+x_3)\\ \text{subject to}& x_1+x_2+x_3\le 4,\\ & x_1\ge 0,x_2\ge 0,x_3\ge 0\end{array}$$
この問題の最大値を求めよ。ただし $\log$ は自然対数である。

実数 $x_1,x_2,x_3$ についての線形計画問題 $(\mathrm{P})$ と、実数 $y_1,y_2,y_3$ についてのその双対問題 $(\mathrm{D})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 3x_1+x_2+4x_3\\ \text{subject to}& x_1+x_2+x_3\le 3,\\ & x_1+2x_2\le 4,\\ & 2x_1+x_2+3x_3\le 7,\\ & x_1,x_2,x_3\ge 0\end{array}$$
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 3y_1+4y_2+7y_3\\ \text{subject to}& y_1+y_2+2y_3\ge 3,\\ & y_1+2y_2+y_3\ge 1,\\ & y_1+3y_3\ge 4,\\ & y_1,y_2,y_3\ge 0\end{array}$$
$(x_1,x_2,x_3)=(2,0,1)$ は $(\mathrm{P})$ の最適解であることが知られている。このとき $(\mathrm{D})$ の最適解はただ 1 つに定まる。$(\mathrm{D})$ の最適解を $(y_1,y_2,y_3)$ の組として求めよ。

実数 $x_1,x_2,x_3$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{minimize}& 6x_1+8x_2+4x_3\\ \text{subject to}& x_1+2x_2+x_3\ge 3,\\ & 2x_1+x_2+x_3\ge 4,\\ & x_1\ge 0,x_2\ge 0,x_3\ge 0\end{array}$$
$(\mathrm{P})$ の最適解はただ 1 つである。双対問題を利用して、その最適解 $(x_1,x_2,x_3)$ をこの順に求めよ。

実数 $x_1,x_2,x_3$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{maximize}& 3x_1+x_2+4x_3\\ \text{subject to}& x_1+x_2+2x_3\le 4,\\ & 2x_1+x_3\le 5,\\ & x_1+3x_2+x_3\le 7,\\ & x_1\ge 0,x_2\ge 0,x_3\ge 0\end{array}$$
$(x_1,x_2,x_3)=(2,0,1)$ は $(\mathrm{P})$ の最適解である。$(\mathrm{P})$ の 3 つの不等式制約に上から順に双対変数 $y_1,y_2,y_3$ を対応させた双対問題 $(\mathrm{D})$ の最適解 $(y_1,y_2,y_3)$ を、相補性条件を用いてこの順に求めよ。

5 個のデータ点
$$(x_i,y_i)=(-2,3),(-1,1),(0,0),(1,1),(2,5)(i=1,2,3,4,5)$$
に、実数 $a,b,c$ を係数とする 2 次関数 $y=a+bx+c{x}^2$ を当てはめる。残差の二乗和
$$S(a,b,c)=\sum _{i=1}^5{\left(y_i-a-b{x}_i-c{x}_i^2\right)}^2$$
を最小にするように $a,b,c$ を定めるとき、$S$ の最小値を求めよ。

$A$ を $m\times n$ 実行列、$\mathbf{b}\in {\mathbb{R}}^m$ とし、${\mathbb{R}}^m,{\mathbb{R}}^n$ には標準内積 $\mathbf{u}\cdot \mathbf{v}={\mathbf{u}}^{\mathsf{T}}\mathbf{v}$ を考える。正規方程式の解全体の集合を
$$S=\{\mathbf{x}\in {\mathbb{R}}^n\mid A^{\mathsf{T}}A\mathbf{x}=A^{\mathsf{T}}\mathbf{b}\}$$
とし、$A^{\mathsf{T}}$ の像を $\mathrm{Im}{A}^{\mathsf{T}}=\{A^{\mathsf{T}}\mathbf{y}\mid \mathbf{y}\in {\mathbb{R}}^m\}\subset {\mathbb{R}}^n$ とする。

共通部分 $S\cap \mathrm{Im}{A}^{\mathsf{T}}$ がちょうど 1 つの元からなることを証明せよ。

ただし、次の事実は用いてよい: ${\mathbb{R}}^k$ の任意の部分空間 $W$ に対し、$W^{\perp }=\{\mathbf{v}\in {\mathbb{R}}^k\mid \text{任意の }\mathbf{w}\in W\text{ に対し }\mathbf{v}\cdot \mathbf{w}=0\}$ とおくと、任意の $\mathbf{v}\in {\mathbb{R}}^k$ は $\mathbf{v}=\mathbf{w}+{\mathbf{w}}^{\prime }$（$\mathbf{w}\in W,{\mathbf{w}}^{\prime }\in W^{\perp }$）と表せる。

4 個のデータ点
$$(x_i,y_i)=(0,0),(1,4),(3,2),(4,6)(i=1,2,3,4)$$
に、直線 $y=a+bx$ を当てはめる。ここでは、残差の絶対値 $|y_i-a-b{x}_i|$ の最大値を最小にする直線を考える（チェビシェフ近似）。この問題は、実数 $a,b,t$ を変数とする次の線形計画問題 $(\mathrm{P})$ として書ける。
$$(\mathrm{P})\begin{array}{rl}\text{minimize}& t\\ \text{subject to}& -t\le y_i-a-b{x}_i\le t(i=1,2,3,4)\end{array}$$
$(\mathrm{P})$ の最適解はただ一つに定まる。その最適解 $(a,b,t)$ を、この順の組で求めよ。

$k$ を正の実数の定数とし、${\mathbb{R}}^2$ 上の関数
$$f(x,y)=x^2+xy+y^2-k\log \left(e^x+e^y\right)$$
を考える。$f$ が ${\mathbb{R}}^2$ 全体で凸関数となるような $k$ の最大値を $K$ とする。$K$ と、$k=K$ のときの $f$ の ${\mathbb{R}}^2$ 上での最小値を、この順に組 $(K,\text{最小値})$ で求めよ。

実数 $x,y$ についての次の最適化問題を考える。
$$\begin{array}{rl}\text{minimize}& f(x,y)=(x-3{)}^2+(y-2{)}^2\\ \text{subject to}& g_1(x,y)=x^2+y^2-5\le 0,\\ & g_2(x,y)=x+2y-4\le 0.\end{array}$$
ラグランジュ関数を $L(x,y,{\lambda }_1,{\lambda }_2)=f(x,y)+{\lambda }_1{g}_1(x,y)+{\lambda }_2{g}_2(x,y)$ とする。この問題の最適解 $(x^{\ast },y^{\ast })$ において KKT 条件を満たすラグランジュ乗数 ${\lambda }_1,{\lambda }_2(\ge 0)$ は一意に定まる。その組 $({\lambda }_1,{\lambda }_2)$ をこの順に求めよ。

4 個のデータ点
$$(x_i,y_i)=(0,1),(1,2),(2,1),(3,5)(i=1,2,3,4)$$
に直線 $y=a+bx$ を当てはめる。残差 $r_i=y_i-(a+b{x}_i)$ の絶対値の最大値 ${\max }_i|r_i|$ を最小にしたい。これは、実数 $a,b,t$ を変数とする次の線形計画問題として書ける。
$$\begin{array}{rl}\text{minimize}& t\\ \text{subject to}& -t\le y_i-(a+b{x}_i)\le t(i=1,2,3,4)\end{array}$$
この線形計画問題の最適解はただ 1 つである。その最適解 $(a,b,t)$ を求めよ。