2022年度交通社会システム論<br>第2回：線形計画問題(1) 標準形<br>Mangament of Transpotation Networks in Social Systems - Linear Programming(1): Standard Form

--- lang: ja tags: MTNS-2022, lecture, linear programming --- # 2022年度交通社会システム論<br>第2回：線形計画問題(1) 標準形<br>Mangament of Transpotation Networks in Social Systems - Linear Programming(1): Standard Form [ポータルへ戻る | Back to Portal](https://hackmd.io/@nagae/MTNS_2022) <div style="text-align: center"> このページへは以下のQRコードまたはURLからアクセスできます： You can access to this page via the following QR code or URL: ![](https://i.imgur.com/syx5ohA.png =200x) <code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch01</code> </div> # リア充問題 | How Mr. Adam can be happy? - Aくんは彼女ができたばかり． ==**1日8時間**== ある自由な時間を, **バイト** と **デート** に振り分ける. - バイトすると ==**1時間あたり800円**== の**収入**に,デートすると ==**1時間あたり400円**== の **支出** になる. - Aくんの仕送りから家賃・食費などの生活費を除くと**リア充資金** として ==**1 日あたり 800 円**== を充当できる. - バイトもデートも**体力**を消耗する.Aくんの体力はバイトだけなら ==**1日9時間分**==, デートだけなら ==**1日6時間分**== ある. - Aくんはバイトからもデートからも充実感が得られるが，できたばかりの彼女と過ごす時間の方が，バイトの時間よりも充実感を味わえる. そこで, 1 時間あたりの充実感の比率を ==**バイト:デート = 1:2**== とする. - リア充資金とバイト給料でデート代を賄いつつ, ==**最も充実した生活**== を送るには 1日あたりバイトとデートを何時間づつすればよいだろう? --- - Mr. Adam just got a new girflriend and wants to make his life rich and happy by assigning his free ==**8 hours**== per day to **part-time work** and **dating**. - Working part-time yields **800 JPY** per hour, while datng costs **400 JPY** per hour. - He has an endowment fund for his activity as **800 JPY** per day. - Both of part-time job and dating are physically demanding. Mr. Adam's physical strength is equivalent to **9 hours part-time job** or **6 hours dating.** - Although Mr. Adam can feel fulfilled from either part-time job or dating, he feels more fulfilled by spending time with his girlfriend. We assume that the hapiness of spending one hour on the date is ==**twice**== as much as that of spending one our on a part-time job. ## 定式化 | Formulation 最適化問題の構成要素: Components of optimization problems: 1. 未知変数 | (unknown) variables 2. 制約条件 | constraints 3. 目的関数 | objective function ### 未知変数(variables)と非負制約(non-negativity constraint) 求めたいのは最適なバイトとデートの時間．それぞれ, $x_{1}, x_{2}$とする．これらは，いずれも非負でなければならない． Let $x_{1}$ be the time for part-time job per day, as well as $x_{2}$ be the time for date per day. Each should be non-negative. $$ x_{1}, x_{2} \geq 0 $$ ### 制約条件(constraints) バイト時間とデート時間の組$(x_{1}, x_{2})$は，**時間**，**予算**，**体力**の制約を満たす中でしか選べない． The pair of variables $(x_{1}, x_{2})$ should satisfy the following three constraints: #### 時間制約 (time constraint) バイト時間とデート時間の合計は8時間を超えてはいけない: The sum of times for part-time working and dating must not exceed 8 hours per day: $$ x_{1} + x_{2} \leq 8 $$ #### 予算制約 (budget constraint) 「バイトの収入とリア充資金の合計」が「デートへの支出」以上でなければいけない: The sum of part-time income and the endowment fund must be equal to or greater than the expenditure for dating: $$ 800 x_{1} + 800 \geq 400 x_{2} $$ 両辺を 400 で割って整理すれば， A straightforward mathematic yields: $$ -2 x_{1} + x_{2} \leq 2 $$ #### 体力制約 (physical constraint) 1日の体力が「バイト9時間分」もしくは「デート6時間分」なので, バイトとデートの時間の組 $(x_1, x_2)$ は $(x_1, x_2) = (9, 0)$ と$(x_1, x_2) = (0, 6)$ を結ぶ直線を超えてはいけない: The time allocation $(x_{1}, x_{2})$ must not exceed the line between $(x_{1}, x_{2}) = (9,0)$ and $(x_{1}, x_{2}) = (0,6)$: $$ 2x_{1} + 3 x_{2} \leq 18 $$ ### 目的関数 (objectives) バイト時間とデート時間のそれぞれに充実感の比率を乗じた和(=充実度)を最大化したい： Mr. Adam wants to maximize his happiness, which is a weighted-sum of spending times for his activities: $$ Z(x_{1}, x_{2}) := x_{1} + 2 x_{2} $$ ## 線形計画問題として定式化されたリア充問題 | Linear Programming Formulation $$ \begin{alignat}{3} \max_{x_{1}, x_{2}} \quad & x_{1} + 2x_{2} &&\quad& \text{(目的関数 | objective)}\\ \text{s.t.} \quad & x_{1} + x_{2} &\leq 8 && \text{(時間制約 | time const.)}\\ & - 2x_{1} + x_{2} &\leq 2 && \text{(予算制約 | budget const.)}\\ & 2x_{1} + 3x_{2} &\leq 18 && \text{(体力制約 | physical const.)}\\ & x_{1}, x_{2} &\geq 0 && \text{(非負制約 | non-negativity)} \end{alignat} $$ s.t. は *subject to* の略． :::info **線形計画問題** (LP: *linear programming*): 目的関数が未知変数に対して **線形** で，制約条件が未知変数の **線形不等式** で表される. A mathematical programming with linear objective and liner constraints. ::: ## 幾何学的イメージ | Algebra of LP ### 許容領域 | Feasible set 下図において，緑色で塗り潰された領域は，3つの制約条件と非負制約の全てを満たす ==**許容領域(feasible set)**== を表す． The feasible set of the variable $(x_{1}, x_{2})$ is represented by the green area. This is the intersection of five areas, each of which corresponds to a linear inequality (3 constraints and 2 non-negativity constraints). ![](https://i.imgur.com/YqkjRbf.png ) 下図において，青い点線は，目的関数$Z(x_{1},x_{2})=x_{1}+2x_{2}$の ==**等高線**== を表す．目的関数の等高線は，ベクトル $\begin{bmatrix}1 \\2\end{bmatrix}$ を法線とする直線で， *原点方向(左下)に向かうほど目的関数は小さく，逆方向(右上)に向かうほど目的関数は大きくなる*． ==**最適解**==(i.e. 緑色の領域内で最も原点から遠い等高線が通る点)は，$(x_{1}^{\ast}, x_{2}^{\ast}) = (\frac{3}{2}, 5)$であり，その時の目的関数値(==**最適値**==)は，$Z(x_{1}^{\ast}, x_{2}^{\ast}) = 11.5$である． The blue dotted lines in the following picture contour lines of the objective function, $Z(x_{1}, x_{2})=x_{1}+2x_{2}$. These lines are orthogonal to the vector $\begin{bmatrix}1 \\2\end{bmatrix}$. The objective value is smaller toward the origin (lower left) and larger toward the opposite direction (upper right). The ==**optimal solution**== (i.e. the farthest point from the origin in the green area) is $(x_{1}^{\ast}, x_{2}^{\ast}) = (\frac{3}{2}, 5)$ and the ==**optimal value**== is $Z(x_{1}^{\ast}, x_{2}^{\ast}) = 11.5$. ![](https://i.imgur.com/61UmshR.png) # 線形計画問題の例 | Some Examples of LP. ## 1. 食生活問題 | A Diet Problem 4種類の栄養素$N_{1}, N_{2}, N_{3}, N_{4}$を，3種類の食材$F_{1}, F_{2}, F_{3}$ から摂取したい． - 栄養素 $N_{j}$の1日あたりの ==**必要摂取量**== は定数$c_{j}$ で表される($j=1,2,3,4$) - 食材 $F_{i}$ 1単位あたりの ==**価格**== は定数$b_{i}$ で表される($i=1,2,3$) - 食材 $F_{i}$ 1単位から摂取できる栄養素$N_{j}$の量は定数$a_{ij}$で表される． :::warning **食生活問題**： **最も安価**に全ての栄養素を**必要な量だけ摂取**するには，**どの食材を何単位づつ**購入すればよいか? ::: - 未知変数: $y_{1}, y_{2}, y_{3}$ を，それぞれ，食材$F_{1}, F_{2}, F_{3}$の購入量とする - 目的関数: 最小化すべき食材購入費は以下の式で表される： $$Z(y_{1}, y_{2}, y_{3}) = y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} $$ - 制約条件：$y_{i}$単位の食材$F_{i}$からできる栄養素$N_{j}$の量は$y_{i} a_{ij}$であるから，必要摂取量$c_{j}$を満たすための条件は，以下の式で表される: $$ y_{1} a_{1j} + y_{2} a_{2j} + y_{3} a_{3j} \geq c_{j} \qquad \forall j = 1, 2, 3, 4. $$ - 非負制約：食材の購入量は非負なので， $$ y_{1}, y_{2}, y_{3} \geq 0 $$ これより，食生活問題は，以下の線形計画問題として定式化できる： $$ \begin{alignat}{3} \min_{y_{1}, y_{2}, y_{3}} \quad & y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} &&&&\text{(目的関数)}\\ \text{s.t.} \quad & y_{1} a_{11} + y_{2} a_{21} + y_{3} a_{31} &&\geq c_{1} \quad &&\text{(栄養素$N_{1}$の摂取量制約)}\\ & y_{1} a_{12} + y_{2} a_{22} + y_{3} a_{32} &&\geq c_{2} &&\text{(栄養素$N_{2}$の摂取量制約)}\\ & y_{1} a_{13} + y_{2} a_{23} + y_{3} a_{33} &&\geq c_{3} &&\text{(栄養素$N_{3}$の摂取量制約)}\\ & y_{1} a_{14} + y_{2} a_{24} + y_{3} a_{34} &&\geq c_{4} &&\text{(栄養素$N_{4}$の摂取量制約)}\\ &y_{1}, y_{2}, y_{3} &&\geq 0&&\text{(非負制約)} \end{alignat} $$ --- Suppose that you want to obtain four nutrients, $N_{1}, N_{2}, N_{3}$ and $N_{4}$ from three different foods, $F_{1}, F_{2}$ and $F_{3}$. It is also assumed that - The required intake of nutrient $N_j$ is denoted by a given constant $c_j$ ($j=1,2,3,4$). - The price per unit of food $F_i$ is denoted by a given constant $b_i$ ($i=1,2,3$). - The amount of nutrient Nj that can be obtained from one unit of food $F_{i}$ is denoted by a given constant $a_{ij}$ ($i=1,2,3$ and $j=1,2,3,4$). ::: warning **Diet Problem**: How many of each food should you buy to get the required amount of all nutrients at the lowest cost? ::: - **Variables**: Let $y_{1}, y_{2}$ and $y_{3}$ be the amount of foods $F_{1}, F_{2}$ and $F_{3}$, respectively. - **Objective**: The total expenditure to be minimized is: $$Z(y_{1}, y_{2}, y_{3}) = y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} $$ - **Constraints**: Since the amount of nutrient $N_{j}$ from $y_{i}$ food $F_{i}$ is $y_{i} a_{ij}$, the required intake of nutrient $N_{j}$ is denoted by $$ y_{1} a_{1j} + y_{2} a_{2j} + y_{3} a_{3j} \geq c_{j} \qquad \forall j = 1, 2, 3, 4. $$ The amount of each food can not be negative: $$ y_{1}, y_{2}, y_{3} \geq 0. $$ Accordingly, the diet problem can be formulated as the following LP: $$ \begin{alignat}{3} \min_{y_{1}, y_{2}, y_{3}} \quad & y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} &&&&\text{(total expenditure)}\\ \text{s.t.} \quad & y_{1} a_{11} + y_{2} a_{21} + y_{3} a_{31} &&\geq c_{1} \quad &&\text{(required intake of nutrient $N_{1}$)}\\ & y_{1} a_{12} + y_{2} a_{22} + y_{3} a_{32} &&\geq c_{2} &&\text{(required intake of nutrient $N_{2}$)}\\ & y_{1} a_{13} + y_{2} a_{23} + y_{3} a_{33} &&\geq c_{3} &&\text{(required intake of nutrient $N_{3}$)}\\ & y_{1} a_{14} + y_{2} a_{24} + y_{3} a_{34} &&\geq c_{4} &&\text{(required intake of nutrient $N_{4}$)}\\ &y_{1}, y_{2}, y_{3} &&\geq 0&&\text{(non-negativity constraints)} \end{alignat} $$ ## 2. 輸送問題 | Hitchcock's Transportation Problem 3箇所の生産地$P_{1}, P_{2}, P_{3}$から4箇所の消費地$M_{1}, M_{2}, M_{3}, M_{4}$ までガソリンを輸送したい． - 生産地$P_{i}$から供給できるガソリンの量は定数$s_{i}$で表される$(i=1,2,3)$ - 消費地$M_{j}$で必要とされるガソリンの量は定数$r_{j}$で表される$(j=1,2,3,4)$ - 生産地$P_{i}$から消費地$M_{j}$までのガソリン1単位あたりの輸送費用は定数$b_{ij}$で表される． :::warning **輸送問題**： **最も安価**に，各生産地の**供給能力内**で**全ての消費地で必要とされる量を賄う**には， **どの生産地からどの消費地に何単位**のガソリンを運べばよいか? ::: - 未知変数: $y_{ij}$を生産地$P_{i}$から消費地$M_{j}$までの輸送量とする．$\boldsymbol{y} = (y_{ij}: i = 1, 2, 3, j = 1, 2, 3, 4)$ とする． - 目的関数: 最小化すべき総輸送費用は，以下の式で表される： $$ Z(\boldsymbol{y}) = \sum_{i=1}^{3}\sum_{j=1}^{4} y_{ij} b_{ij} $$ - 制約条件(1)：生産地$P_{i}$から運び出されるガソリンの量は $y_{i1} + y_{i2} + y_{i3} + y_{i4} = \sum_{j=1}^{4} y_{ij}$ であり，これが生産地$P_{i}$からの供給量$s_{i}$を上回ってはいけないから， $$ \sum_{j=1}^{4} y_{ij} \leq s_{i} \qquad \forall i = 1, 2, 3 $$ - 制約条件(2): 消費地$M_{j}$に運び込まれるガソリンの量は $y_{1j} + y_{2j} + y_{3j} = \sum_{i=1}^{3} y_{ij}$ であり，これが消費地$M_{j}$での需要量$r_{j}$を下回ってはいけないから， $$ \sum_{i=1}^{3} y_{ij} \geq r_{j} \qquad \forall j = 1, 2, 3, 4 $$ - 非負制約：輸送量は非負なので， $$ y_{ij} \geq 0 \quad \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 $$ これより，輸送問題は，以下の線形計画問題として定式化できる： $$ \begin{alignat}{3} \min_{\boldsymbol{y}} \quad &\sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} &&&&\text{(目的関数)}\\ \text{s.t.} \quad & \sum_{j=1}^{4} y_{ij} \leq s_{i} && \forall i = 1, 2, 3 \quad && \text{(生産地$P_{i}$の供給制約)} \\ & \sum_{i=1}^{3} y_{ij} \geq r_{j} && \forall j = 1, 2, 3, 4 \quad && \text{(消費地$M_{j}$の需要制約)} \\ & y_{ij} \geq 0 && \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 \quad && \text{(非負制約)} \end{alignat} $$ --- Suppose that you want to transport gasoline from three production sites $P_1, P_2$ and $P_3$ to four consumption sites $M_1, M_2, M_3$ and $M_4$. It is also assumed that - The gasoline supply from $P_{i}$ is denoted by a given constant $s_{i}$ ($i=1,2,3$). - The gasoline demand at $M_{j}$ is denoted by a given constant $r_{j}$ ($j=1,2,3,4$). - The transportation cost per unit of gasoline from $P_i$ to $M_j$ is denoted by a given constant $b_{ij}$ ($i=1,2,3$ and $j=1,2,3,4$). :::warning **Hitchcock's Transportation Problem**: How much gasoline should be transportated from each production site to each demand site at the lowest cost? ::: - **Variables**: Let $y_{ij}$ be the amount of gasoline transported from $P_{i}$ to $M_{j}$ ($i=1,2,3$ and $j=1,2,3,4$). - **Objective**: The total transportation cost to minimize is $$ Z(\boldsymbol{y}) = \sum_{i=1}^{3}\sum_{j=1}^{4} y_{ij} b_{ij} $$ - **Constraints (supply side)**: The total amount of gasoline transported *from* $P_{i}$ is $y_{i1} + y_{i2} + y_{i3} + y_{i4}$ and it should not exceed the supply $s_{i}$: $$ \sum_{j=1}^{4} y_{ij} \leq s_{i} \qquad \forall i = 1, 2, 3 $$ - **Constraints (demand side)**: The total amount of gasoline transported *to* $M_{j}$ is $y_{1j} + y_{2j} + y_{3j}$ and it should not smaller than the demand $r_{j}$: $$ \sum_{i=1}^{3} y_{ij} \geq r_{j} \qquad \forall j = 1, 2, 3, 4 $$ - **Non-negativity constraints**: The amount of gasoline should not be negative: $$ y_{ij} \geq 0, \qquad \forall i=1, 2, 3\, \forall j=1,2,3,4. $$ The transportation problem thus can be formulated as $$ \begin{alignat}{3} \min_{\boldsymbol{y}} \quad &\sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} &&&&\text{(total cost)}\\ \text{s.t.} \quad & \sum_{j=1}^{4} y_{ij} \leq s_{i} && \forall i = 1, 2, 3 \quad && \text{(supply const. at $P_{i}$)} \\ & \sum_{i=1}^{3} y_{ij} \geq r_{j} && \forall j = 1, 2, 3, 4 \quad && \text{(demand const. at $M_{j}$)} \\ & y_{ij} \geq 0 && \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 \quad && \text{(non-negativity)} \end{alignat} $$ ## 3. 割当問題 | Assignment Problem $N$人の学生に$M$個の研究テーマを割り当てたい． - それぞれの学生 $i=1, 2, \cdots, N$ には，たかだか1つのテーマしか割り当てられない． - それぞれのテーマ $j=1, 2, \cdots, M$ には，たかだか1人の学生しか割り当てられない． - 学生$i$が研究テーマ $j$ に従事した時の生産量(論文の本数)は定数$c_{ij}$ で表される． :::warning **割当問題**: **総生産量を最大化**するには**どの学生にどの研究テーマを**割り当てればよいか? ::: - 未知変数: $x_{ij}$を，研究テーマ$j$の学生$i$への「割り当て」とする．本来なら$x_{ij}$ は0か1のいずれかを離散的に取る変数(二値変数)であるが，ここでは$[0,1]$の範囲内の任意の実数値を取り得る連続変数として取り扱う． - 目的関数：最大化すべき総生産量は， $$ Z(\boldsymbol{x}) = \sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij} $$ - 制約条件(1): 学生$i$に割り当てられる研究テーマの総数は $x_{i1} + x_{i2} + \cdots + x_{iM} = \sum_{j=1}^{M} x_{ij}$ であり，各学生にはたかだか1つの研究テーマしか割り当てられないから， $$ \sum_{j=1}^{M} x_{ij} \leq 1 \quad \forall i = 1, 2, \cdots, N. $$ - 制約条件(2): 研究テーマ$j$ に割り当てられる学生の総数は $x_{1j} + x_{2j} + \cdots + x_{Nj} = \sum_{i=1}^{N} x_{ij}$ であり，各研究テーマにはたかだか1人の学生しか割り当てられないから， $$ \sum_{i=1}^{N} x_{ij} \leq 1 \quad \forall j = 1, 2, \cdots, M. $$ - 非負制約：割当は非負なので， $$ x_{ij} \geq 0 \qquad \forall i = 1, 2, \cdots, N, \, \forall j = 1, 2, \cdots, M. $$ これより，割当問題は，以下の線形計画問題として定式化できる： $$ \begin{alignat}{3} \max_{\boldsymbol{x}} \quad &\sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij} &&&&\text{(目的関数)}\\ \text{s.t.} \quad & \sum_{j=1}^{N} x_{ij} \leq 1 && \forall i = 1, 2, \cdots, N \quad && \text{(学生$i$への割当上限)} \\ & \sum_{i=1}^{N} x_{ij} \leq 1 && \forall j = 1, 2, \cdots, M \quad && \text{(研究テーマ$j$への割当上限)} \\ & x_{ij} \geq 0 && \forall i = 1, 2, \cdots, N\, \forall j = 1, 2, \cdots, M\quad && \text{(非負制約)} \end{alignat} $$ --- Suppose that you want assign $M$ tasks to $N$ workers. It is assumed that - Each worker is assigned at most 1 task. - Each task is assigned to at most 1 worker. - The performance of worker $i$ assigned to task $j$ is denoted by a given constant $c_{ij}$ ($i=1,\cdots,N, j=1, \cdots, M$). :::warning **Assignment Problem**: To maximize the total performance by assigning the workers to the tasks. ::: - **Variables**: Let $x_{ij}$ be the assignment of worker $i$ to task $j$. If worker $i$ is assigned to task $j$, $x_{ij}=1$, while if worker $i$ is not assigned to task $j$, $x_{ij}=0$. - **Constraint (worker side)**: Worker $i$ should not be assigned more than one tasks: $$ \sum_{j=1}^{M} x_{ij} \leq 1 \quad \forall i = 1, 2, \cdots, N. $$ - **Constraint (task side)**: No more than one workers are assigned to task $j$: $$ \sum_{i=1}^{N} x_{ij} \leq 1 \quad \forall j = 1, 2, \cdots, M. $$ - **Non-negativity constraints**: The assignment should not be negative: $$ x_{ij} \geq 0, \qquad \forall i=1, \cdots, N, \, \forall j=1,\cdots, M. $$ Thus the assignment problem is formulated as the following LP. $$ \begin{alignat}{3} \max_{\boldsymbol{x}} \quad &\sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij} &&&&\text{(total performance)}\\ \text{s.t.} \quad & \sum_{j=1}^{N} x_{ij} \leq 1 && \forall i = 1, 2, \cdots, N \quad && \text{(const. for worker $i$)} \\ & \sum_{i=1}^{N} x_{ij} \leq 1 && \forall j = 1, 2, \cdots, M \quad && \text{(const. for task $j$)} \\ & x_{ij} \geq 0 && \forall i = 1, 2, \cdots, N\, \forall j = 1, 2, \cdots, M\quad && \text{(non-negativity)} \end{alignat} $$ :::success 割当問題は，その最適解 $x_{ij}^{\ast}$ が **0か1のいずれかになる** (常に離散解が得られる)ことが保証されている． It is well known that the optimal solution to the assignment problem, $x_{ij}^{\ast}$, always takes either $1$ or $0$. ::: # 標準形とベクトル・行列表現 | Standard Form and Vector/Matrix Representation ## 線形計画問題の分類 | Variations of LPs - 目的関数(objective): 最大化(maximize) or 最小化 (minimize) - 未知変数(variables): 非負制約あり(with non-negativity) or 非負制約なし(without non-negativity) - 制約条件(constraints): 線形式 $\leq$ 定数 or 線形式 $=$ 定数 or 線形式 $\geq$ 定数特定の組み合わせに限定されない**システマティック**な分析・解法が欲しい → 標準形 **Standard form** enables us to formulate and analyze any LPs in a uniform manner. ## 標準形 | Standard Form 任意の線形計画問題を ==**同一の形式**== で記述でき，問題の性質(解の存在や双対性)の分析や解法の開発をシステマティックに行える： - ==**不等式標準形**==(**標準最大化**/標準最小化) → 双対問題の導出に便利 - ==**等式標準形**== → 単体法(数値解法)の開発に便利 --- There are two standard forms: - **Inequality standard form** (**Standard maximization** Standard minimization): Useful for obtaining dual problems. - **Equiality standard form** Useful for numerical solution method (simplex method). # 標準最大化問題 | Standard Maximization $N$ 個の未知変数$x_{1}, x_{2}, \cdots, x_{N}$ を用いて，$M$本の不等式制約条件を満足しながら，目的関数を最大化する． To maximize the objective function by choosing $N$ variables $x_{1}, x_{2}, \cdots, x_{N}$ with $M$ inequality conditions. $$ \begin{array}{rcccccccccc} \displaystyle\max_{x_{1}, x_{2}, \cdots, x_{N}} &c_{1} x_{1}& + &c_{2} x_{2}& +&\cdots& +&c_{N} x_{N}\\ \text{s.t.} & a_{11} x_{1} &+& a_{12} x_{2} &+& \cdots &+& a_{1N} x_{N} &\leq& b_{1}\\ & a_{21} x_{1} &+& a_{22} x_{2} &+& \cdots &+& a_{2N} x_{N} &\leq& b_{2}\\ & \vdots & & \vdots & & \ddots & & \vdots & & \vdots\\ & a_{{M}1} x_{1} &+& a_{{M}2} x_{2} &+& \cdots &+& a_{{M}N} x_{N} &\leq& b_{M}\\ & x_{1}, & & x_{2}, & & \cdots & & x_{N} & \geq & 0 \end{array} $$ ## 標準最大化問題のベクトル・行列表現 | Vector/Matrix Representation ### 目的関数 | Objecive Function 標準最大化問題の目的関数は，2つのN次元列ベクトル $$ \boldsymbol{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{N} \end{bmatrix} , \quad \boldsymbol{c} = \begin{bmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{N} \end{bmatrix} $$ を用いて， $$ c_{1} x_{1} + c_{2} x_{2} +\cdots +c_{N} x_{N} = \sum_{i=1}^{N} c_{i} x_{i} = \boldsymbol{c}^{\top} \boldsymbol{x} $$ と表せる．ただし，${}^{\top}$は行列・ベクトルの転置を表す記号． --- The objective function of a standard maximization problem can be represented as $$ c_{1} x_{1} + c_{2} x_{2} +\cdots +c_{N} x_{N} = \sum_{i=1}^{N} c_{i} x_{i} = \boldsymbol{c}^{\top} \boldsymbol{x},$$ where $\boldsymbol{x}$ and $\boldsymbol{c}$ are $N$-dimensional column vectors, $$ \boldsymbol{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{N} \end{bmatrix} , \quad \boldsymbol{c} = \begin{bmatrix} c_{1} \\ c_{2} \\ \vdots \\ c_{N} \end{bmatrix}$$ and ${}^{\top}$ is a tranpose operator. ### $j$ 番目不等式制約 | $j$ th Inequality Constraint $j (= 1, \cdots, M)$ 本目の不等式制約は, $N$次元行ベクトル$\boldsymbol{a}_{j}$: $$ \boldsymbol{a}_{j} = \begin{bmatrix} a_{j1} & a_{j2} & \cdots &a_{jN} \end{bmatrix} $$ を用いて $$ a_{j1} x_{1} + a_{j2} x_{2} + \cdots + a_{jN} x_{N} = \sum_{i=1}^{N} a_{ji} x_{i} = \boldsymbol{a}_{j} \boldsymbol{x} \leq b_{j} $$ と表せる．さらに，$M\times{N}$行列$\boldsymbol{A}$ および$M$次元列ベクトル: $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{a}_{1} \\ \vdots \\ \boldsymbol{a}_{M} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M1} & a_{M2} & \cdots & a_{MN} \end{bmatrix} , \boldsymbol{b} = \begin{bmatrix} b_{1} \\ \vdots \\ b_{M} \end{bmatrix} $$ を用いれば，不等式制約全体を以下のようにベクトル・行列表現できる： $$ \begin{bmatrix} a_{11}x_{1} + a_{12} x_{2} + \cdots + a_{1N} x_{N}\\ \vdots \\ a_{M1}x_{1} + a_{M2} x_{2} + \cdots + a_{MN} x_{N} \end{bmatrix} = \begin{bmatrix} \boldsymbol{a}_{1} \boldsymbol{x} \\ \vdots\\ \boldsymbol{a}_{M} \boldsymbol{x} \end{bmatrix} = \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} $$ --- $j$ th inequality constraint can be represented as $$ a_{j1} x_{1} + a_{j2} x_{2} + \cdots + a_{jN} x_{N} = \sum_{i=1}^{N} a_{ji} x_{i} = \boldsymbol{a}_{j} \boldsymbol{x} \leq b_{j}, $$ where $\boldsymbol{a}_{j}$ is $N$-dimensional row vector: $$ \boldsymbol{a}_{j} = \begin{bmatrix} a_{j1} & a_{j2} & \cdots &a_{jN} \end{bmatrix} $$ The whole inequality constraints can be represented as $$ \begin{bmatrix} a_{11}x_{1} + a_{12} x_{2} + \cdots + a_{1N} x_{N}\\ \vdots \\ a_{M1}x_{1} + a_{M2} x_{2} + \cdots + a_{MN} x_{N} \end{bmatrix} = \begin{bmatrix} \boldsymbol{a}_{1} \boldsymbol{x} \\ \vdots\\ \boldsymbol{a}_{M} \boldsymbol{x} \end{bmatrix} = \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, $$ where $\boldsymbol{A}$ and $\boldsymbol{b}$ are the following $M \times N$ matrix and $M$-dimensional column: $$ \boldsymbol{A} = \begin{bmatrix} \boldsymbol{a}_{1} \\ \vdots \\ \boldsymbol{a}_{M} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M1} & a_{M2} & \cdots & a_{MN} \end{bmatrix} , \boldsymbol{b} = \begin{bmatrix} b_{1} \\ \vdots \\ b_{M} \end{bmatrix} $$ ### 非負制約 | Non-negativity Constraints 非負制約は，全ての要素が0の$N$次元列ベクトル$\boldsymbol{0}$ を用いて， $$ \boldsymbol{x} \geq \boldsymbol{0} $$ と表せる． Non-negativity constraints can be denoted by $$ \boldsymbol{x} \geq \boldsymbol{0}, $$ where $\boldsymbol{0}$ is $N$-dimensional column with all elements $0$. ## 標準最大化問題のベクトル・行列表現 | Vector/Matrix Representation of Standard Maximization 結局，標準最大化問題は， - $M\times{}N$行列 $\boldsymbol{A}$ - $M$次元列ベクトル $\boldsymbol{b}$ - $N$次元列ベクトル $\boldsymbol{c}$ を与件(定数)とし，未知変数を - $N$次元列ベクトル $\boldsymbol{x}$ とする以下の問題として表現できる． $$ \begin{align*} \max_{\boldsymbol{x}} \quad &\boldsymbol{c}^{\top}\boldsymbol{x} \\ \text{s.t.} \quad & \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ &\boldsymbol{x} \geq \boldsymbol{0} \end{align*} $$ より簡潔に $$ \max_{\boldsymbol{x}} \left\{\left. \boldsymbol{c}^{\top} \boldsymbol{x} \right| \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \right\} $$ と表すこともある. --- A standard maximization problem can be denoted as $$ \begin{align*} \max_{\boldsymbol{x}} \quad &\boldsymbol{c}^{\top}\boldsymbol{x} \\ \text{s.t.} \quad & \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\ &\boldsymbol{x} \geq \boldsymbol{0} \end{align*}. $$ or, more simply $$ \max_{\boldsymbol{x}} \left\{\left. \boldsymbol{c}^{\top} \boldsymbol{x} \right| \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \right\}. $$  # 標準最大化問題への変換 | Reduction to Standard Maximization Problem 任意の問題は不等式標準形に変換できる．たとえば，次の問題: $$ \begin{align*} \min_{x_{1}, x_{2}, x_{3}} & x_{1} + 3 x_{2} + 2x_{3}\\ \text{s.t.} & x_{1} + x_{2} = 2\\ & 2 x_{1} + x_{3} \geq x_{2} + 3 \\ & x_{1}, x_{2} \geq 0 \\ & x_{3} \text{ is free (正でも負でもよい)} \end{align*} $$ は，以下の手順で標準最大化問題に変換できる． Any linear programming problem can be reduced to standard form. Suppose the following LP as an example: $$ \begin{align*} \min_{x_{1}, x_{2}, x_{3}} & x_{1} + 3 x_{2} + 2x_{3}\\ \text{s.t.} & x_{1} + x_{2} = 2\\ & 2 x_{1} + x_{3} \geq x_{2} + 3 \\ & x_{1}, x_{2} \geq 0 \\ & x_{3} \text{ is free (either positive, negative or 0)} \end{align*} $$ 1) 最小化問題は，目的関数の全ての係数に$-1$を乗じることで最大化問題に置き換える： Minimization is converted to maximization by multiplying objective function by $-1$ : $$ \min_{x_{1}, x_{2}, x_{3}} x_{1} + 3 x_{2} + 2 x_{3} \Rightarrow \max_{x_{1}, x_{2}, x_{3}} - x_{1} - 3 x_{2} - 2 x_{3} $$ 2) 等式制約は，==**線形式=定数**== の形に揃えた後， ==**線形式$\leq$定数**== と ==**線形式$\geq$定数**== なる2つの不等式に置き換える： Each equality constraint is replaced by two inequalities: $$ x_{1} + x_{2} = 2 \Rightarrow \begin{cases} x_{1} + x_{2} \leq 2 \\ x_{1} + x_{2} \geq 2 \end{cases} $$ 3) 不等式制約は ==**線形式$\leq$定数**== の形に揃える： Each inequality constraint is alined to the form of linear expression $\leq$ constant. $$ \begin{align*} 2 x_{1} + x_{3} \geq x_{2} + 3 &\Rightarrow -2x_{1} + x_{2} - x_{3} \leq -3\\ x_{1} + x_{2} \geq 2 &\Rightarrow -x_{1} - x_{2} \leq -2 \end{align*} $$ 4) 非負制約のない未知変数は，非負なる2つの未知変数を導入し，その差で置き換える．ここでは，非負なる2つの未知変数$x_{3}^{+}, x_{3}^{-} \geq 0$を新たに導入し，正負どちらでもよい未知変数$x_{3}$を,$x_{3}^{+}-x_{3}^{-}$で置き換える． Each free variable is replaced by the difference between two (artificial) non-negative variables. Here two non-negative variables $x_{3}^{+}$ and $x_{3}^{-}$ are introduced and $x_{3}$ is replaced by the their difference. $$ \begin{array}{rl} \displaystyle \max_{x_{1}, x_{2}, x_{3}} &-x_{1}-3x_{2}-2x_{3}\\ \text{s.t.} & x_{1} + x_{2} \leq 2 \\ &-x_{1}-x_{2} \leq -2 \\ &-2x_{1}+x_{2}-x_{3} \leq -3 \\ &x_{1}, x_{2} \geq 0 \\ &x_{3} \text{ is free} \end{array} \Rightarrow \begin{array}{rl} \displaystyle \max_{x_{1}, x_{2}, \color{red}{x_{3}^{+}, x_{3}^{-}}} &-x_{1}-3x_{2}- 2\color{red}{\left(x_{3}^{+}-x_{3}^{-} \right)}\\ \text{s.t.} & x_{1} + x_{2} \leq 2 \\ &-x_{1}-x_{2} \leq -2 \\ &-2x_{1}+x_{2}-\color{red}{\left(x_{3}^{+}-x_{3}^{-}\right)} \leq -3 \\ &x_{1}, x_{2}, \color{red}{x_{3}^{+}, x_{3}^{-}} \geq 0 \end{array} $$ # 練習(提出の必要はありません) | Exercise (no submission required) 輸送問題を標準最大化問題に変換しなさい． Convert the transportation problem to a standard maximization problem.