# 선형계획법 Linear Programming




```python
import matplotlib.pyplot as plt
import numpy as np
import numpy.linalg as nl
import scipy.optimize as so


```

ref : 
* Wikipedia [link](https://en.wikipedia.org/wiki/Linear_programming)
* Stackoverflow [link](https://stackoverflow.com/questions/62571092/)
* Tips & Tricks on Linux, Matlab, vim, LaTex, etc [link](http://tipstrickshowtos.blogspot.com/2012/04/how-to-render-argmax-argmin-operator-in.html)



## Problem description<br>문제 설명



* Area of the farm 농장의 넓이 : $L = 10 (km^2)$
* Types of crops : wheat or rice<br>작물의 종류 : 밀 또는 쌀
* Available fertilizer 사용 가능한 비료의 양 : $F = 10 (kg)$
* Available pesticide 사용 가능한 살충제의 양 : $P = 5 (kg)$

|   | Wheat 밀 | rice 쌀 |
|:-----:|:-----:|:-----:|
| Needed Fertilizer per unit area $(kg/km^2)$<br>단위면적 당 필요 비료 양 $(kg/km^2)$ | $F_1$ | $F_2$ |
| Needed Pesticide per unit area $(kg/km^2)$<br>단위면적 당 필요 살충제 양 $(kg/km^2)$ | $P_1$ | $P_2$ |
| Selling price per unit area $(\$/km^2)$<br>단위면적 당 매출 $(\$/km^2)$ | $S_1$ | $S_2$ |
| Planting area $(km^2)$<br>재배 면적 $(km^2)$ | $x_1$ | $x_2$ |


* Under the constraints, what are the areas of wheat and rice maximizing the overall selling price?<br>제한조건 하에서 매출을 최대로 하는 밀과 쌀의 재배 면적?



$$
\underset{x_1, x_2}{\arg\max} \left(S_1 x_1 + S_2 x_2\right)
$$



subject to 제한조건



$$
\begin{align}
    x_1 + x_2 & \le L \\
    F_1 x_1 + F_2 x_2 & \le F \\
    P_1 x_1 + P_2 x_2 & \le P \\
    x_1, x_2 & \ge 0
\end{align}
$$



In matrix form 행렬 형태로는:



$$
\underset{x_1, x_2}{\arg\max} \begin{bmatrix} S_1 & S_2    \end{bmatrix}\begin{pmatrix} x_1 \\ x_2    \end{pmatrix}
$$



subject to 제한조건



$$
\begin{align}
    \begin{bmatrix}
        1 & 1 \\
        F_1 &  F_2 \\
        P_1 &  P_2 \\
    \end{bmatrix}
    \begin{pmatrix}
        x_1 \\
        x_2 
    \end{pmatrix} & \le 
    \begin{pmatrix}
        L \\
        F \\
        P
    \end{pmatrix} \\
    \begin{pmatrix}
        x_1 \\
        x_2 
    \end{pmatrix}& \ge 0
\end{align}
$$

## Parameters Example<br>매개변수 예




```python
L = 10


```


```python
F = 10
F1 = 2
F2 = 3


```


```python
P = 5
P1 = 2
P2 = 1


```


```python
S1 = 20
S2 = 25


```

## Visualization 시각화



$$
\begin{align}
    x_1 + x_2 & \le L \\
    F_1 x_1 + F_2 x_2 & \le F \\
    P_1 x_1 + P_2 x_2 & \le P \\
    x_1, x_2 & \ge 0
\end{align}
$$



$$
\begin{align}
    x_2 & \le -x_1 + L \\
    x_2 & \le -\frac{F_1}{F_2} x_1 + \frac{F}{F_2} \\
    x_2 & \le -\frac{P_1}{P_2} x_1 + \frac{P}{P_2} \\
    x_1 & \ge 0 \\
    x_2 & \ge 0
\end{align}
$$


```python
x1 = np.linspace(0, 2.5, 101)
x2 = np.linspace(0, 5, 101)
X1, X2 = np.meshgrid(x1, x2)

C = S1 * X1 + S2 * X2

C[X2 > (-F1 * X1 + F) / F2] = np.nan
C[X2 > (-P1 * X1 + P) / P2] = np.nan

plt.pcolor(X1, X2, C, shading="auto")
plt.xlabel("$x_1$")
plt.ylabel("$x_2$")

plt.title("$S_1 x_1 + S_2 x_2$")
plt.colorbar()

plt.grid(True)


```

## `scipy.optimize.linprog()`




```python
c_T = -np.array((S1, S2))


```


```python
A_ub = np.array(
    (
        (1, 1),
        (F1, F2),
        (P1, P2),
    )
)


```


```python
b_ub = np.array(
    ((L, F, P),)
).T


```


```python
bounds = (
    (0, None),
    (0, None),
)


```


```python
result = so.linprog(c_T, A_ub, b_ub, bounds=bounds)
result


```


```python

```

1959996af5a0d5bfc070ccdc055c50e9ab130197
ipynb
Jupyter Notebook
15_optimization/050_Linear_Programming.ipynb
kangwon-naver/nmisp
141f8148b3ce783d3df27ee0c9986f530cada8fb
BSD-3-Clause
2019-05-14T11:00:53.000Z
2020-08-27T01:04:29.000Z
15_optimization/050_Linear_Programming.ipynb
kangwon-naver/nmisp
141f8148b3ce783d3df27ee0c9986f530cada8fb
BSD-3-Clause
2018-07-12T06:06:21.000Z
2022-01-28T09:06:55.000Z
15_optimization/050_Linear_Programming.ipynb
kangwon-naver/nmisp
141f8148b3ce783d3df27ee0c9986f530cada8fb
BSD-3-Clause
2018-08-28T08:38:59.000Z
2020-09-02T03:40:47.000Z
Qwen/Qwen-72B
1. YES
2. YES