端点（基底解）の列挙による最適解

実数 $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,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)$ を組で求めよ。

$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$ についての次の線形計画問題 $(\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)$ をこの順に求めよ。

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)$ を、この順の組で求めよ。

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)$ を求めよ。

実数 $x_1,x_2,x_3,x_4$ についての次の線形計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\begin{array}{rl}\text{minimize}& 4x_1+3x_2+3x_3+6x_4\\ \text{subject to}& x_1+2x_2+x_3+3x_4\ge 8,\\ & 3x_1+x_2+x_3+2x_4\ge 9,\\ & x_1,x_2,x_3,x_4\ge 0\end{array}$$
$(\mathrm{P})$ の双対問題を作って解き、相補性条件を用いることで、$(\mathrm{P})$ の最適解 $(x_1,x_2,x_3,x_4)$ を求めよ（最適解はただ 1 つに定まる）。答えは組 $(x_1,x_2,x_3,x_4)$ の形で答えよ。