2022年度交通社会システム論 Report #5 解答例

--- lang: ja tags: MTNS-2022, lecture, linear programming --- # 2022年度交通社会システム論 Report #5 解答例 [ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022) このページへは以下のURLからアクセスできます： <code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch09-answer</code> </div> # 課題下記の2財4人からなる割当問題に対して，以下を答えよ． Suppose the following 2-item and 4-buyer assignment and answer the questions: 1. 等価な線形計画問題の主問題および双対問題を書き下せ Write down the primal and dual of the equivalent linear programming. 2. 主問題および双対問題の最適解が相補性条件を満足することを示せ． Show that the primal/dual optimal solutions satisfy the complementarity condition. ||買手1 Buyer 1|買手2 Buyer 2|買手3 Buyer 3|買手4 Buyer 4|供給量 supply| |---|---|---|---|---|---| |財 (item) $A$|100|50|90|120|1| |財 (item) $B$|80|50|40|90|2| ## 主問題 | Primal Problem $$\begin{align} \max_{\mathbf{x}} \quad &100x_{A1}+80x_{B1}+50x_{A2}+50x_{B2}+90x_{A3}+40x_{B3}+120x_{A4}+90x_{B4}\\ \text{s.t.} \quad & x_{A1} + x_{B1} \leq 1\\& x_{A2} + x_{B2} \leq 1\\& x_{A3} + x_{B3} \leq 1\\& x_{A4} + x_{B4} \leq 1\\& x_{A1} + x_{A2} + x_{A3} + x_{A4} \leq 1\\& x_{B1} + x_{B2} + x_{B3} + x_{B4} \leq 2\\& x_{A1}, x_{B1}, x_{A2}, x_{B2}, x_{A3}, x_{B3}, x_{A4}, x_{B4} \geq 0 \end{align}$$ ## 双対問題 | Dual Problem $$\begin{align} \min_{\mathbf{p}, \mathbf{\pi}} \quad& \pi_{1} + \pi_{2} + \pi_{3} + \pi_{4} + p_{A} + 2p_{B}\\ \text{s.t.} \quad & \pi_{1} + p_{A} \geq 100\\& \pi_{1} + p_{B} \geq 80\\& \pi_{2} + p_{A} \geq 50\\& \pi_{2} + p_{B} \geq 50\\& \pi_{3} + p_{A} \geq 90\\& \pi_{3} + p_{B} \geq 40\\& \pi_{4} + p_{A} \geq 120\\& \pi_{4} + p_{B} \geq 90\\& \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4}, p_{A}, p_{B} \geq 0 \end{align}$$ ## 最適解 | Optimal Solution 主問題の最適解は$x_{B1} = x_{A3} = x_{B4} = 1$で，最適値は260. The primal optimal solution is $x_{B1} = x_{A3} = x_{B4} = 1$ and the corresponding optimal value is 260. ||買手1 Buyer 1|買手2 Buyer 2|買手3 Buyer 3|買手4 Buyer 4|供給量 supply| |---|---|---|---|---|---| |財 (item) $A$|100|50|**90**|120|1| |財 (item) $B$|**80**|50|40|**90**|2| 双対問題の最適解は$(p_{A}, p_{B} | \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4})=(80, 50|30, 0, 10, 40)$． The dual optimal solution is $(p_{A}, p_{B} | \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4})=(80, 50|30, 0, 10, 40)$．これらの解が主/双対実行可能であることは明らか．相補性条件を書き下せば， It is obvious that these solutions are primal/dual feasible, respectively. The complementarity condition can be written down as $$ \begin{align} x_{A1} &\left\{\pi_{1}+p_{A}-100\right\} &&= 0\cdot\left(30+80-100\right)&&=0\\ x_{B1} &\left\{\pi_{1}+p_{B}-80\right\} &&= 1\cdot\left(30+50-80\right)&&=0\\ x_{A2} &\left\{\pi_{2}+p_{A}-50\right\} &&= 0\cdot\left(0+80-50\right)&&=0\\ x_{B2} &\left\{\pi_{2}+p_{B}-50\right\} &&= 0\cdot\left(0+50-50\right)&&=0\\ x_{A3} &\left\{\pi_{3}+p_{A}-90\right\} &&= 1\cdot\left(10+80-90\right)&&=0\\ x_{B3} &\left\{\pi_{3}+p_{B}-40\right\} &&= 0\cdot\left(10+50-40\right)&&=0\\ x_{A4} &\left\{\pi_{4}+p_{A}-120\right\} &&= 0\cdot\left(40+80-120\right)&&=0\\ x_{B4} &\left\{\pi_{4}+p_{B}-90\right\} &&= 1\cdot\left(40+50-90\right)&&=0\\ \pi_{1} & \left\{1-x_{A1}-x_{B1}\right\} &&=30 \cdot\left(1-0-1\right)&&= 0\\ \pi_{2} & \left\{1-x_{A2}-x_{B2}\right\} &&=0 \cdot\left(1-0-0\right)&&= 0\\ \pi_{3} & \left\{1-x_{A3}-x_{B3}\right\} &&=10 \cdot\left(1-1-0\right)&&= 0\\ \pi_{4} & \left\{1-x_{A4}-x_{B4}\right\} &&=40 \cdot\left(1-0-1\right)&&= 0\\ p_{A} &\left\{1 - x_{A1}-x_{A2}-x_{A3}-x_{A4}\right\} &&= 80\cdot\left(1-0-0-1-0\right) &&=0\\ p_{B} &\left\{2 - x_{B1}-x_{B2}-x_{B3}-x_{B4}\right\} &&= 50\cdot\left(2-1-0-0-1\right) &&=0\\ \end{align}$$ ちなみに，価格が10円づつ高く各買手の最大利得が10円づつ低い解: Note that the following solution with the higher prices by 10 JPY and the lower maximum payoff by JPY $$(p_{A}, p_{B} | \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4}) = (90, 60|20, 0, 0, 30) $$も双対実行可能で目的関数値が is also dual feasible, while its objective function is $$20+40+90+2\times60=260 $$となることから，これもまた双対問題の最適解である（より正確には，0〜10円の範囲で価格と最大利得をシフトさせた解は全て最適解）． Thus this is also dual optimal solution. (More precisely, the shifted-solutions in the range of $[0,10]$ are all optimal.) このように，線形計画問題の**最適解は複数存在することがある**（第8回講義で紹介したように主問題でも配分の仕方が複数通りあることがある）が，**最適値は常に唯一**である． As shown in this example, a linear programming problem might have multiple optimal solutions (the primal problem might have multiple optimal assignments as shown in Lecture #8) though, the optimal value is unique.