<a rel="license" href="http://creativecommons.org/licenses/by/4.0/"></a><br /><span xmlns:dct="http://purl.org/dc/terms/" property="dct:title"><b>Solving LP with Two Variables with Pyomo</b></span> by <a xmlns:cc="http://creativecommons.org/ns#" href="http://mate.unipv.it/gualandi" property="cc:attributionName" rel="cc:attributionURL">Stefano Gualandi</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.<br />Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://github.com/mathcoding/opt4ds" rel="dct:source">https://github.com/mathcoding/opt4ds</a>.

# 2. Solving LP model with Two Variables with PYOMO

In this notebook, we explain how to solve **Linear Programming** problems:
\begin{align}
\max \quad& c^T x \\
\mbox{s.t. } \quad & Ax \geq b \\
& x \geq 0
\end{align}

We begin with a very simple problem with only two positive variables.

## 2.1 Software Installation
If you are running this notebook in a Colab, you don't need to install anything else on your computer.

Otherwise, if you have installed the recommended Anaconda Python distribution, you have to run the following two commands:

1. To install the [Pyomo](http://www.pyomo.org/) optimization modeling language:

```
conda install -c conda-forge pyomo
```

2. To install the open source [GLPK](https://www.gnu.org/software/glpk/) solver:

```
conda install -c conda-forge glpk
```

3. (Optional) You can install some extra packages of Pyomo using the following command:

```
conda install -c conda-forge pyomo.extras
```

For details about the Pyomo installation, we refer to the official [Pyomo Documentation](https://pyomo.readthedocs.io/en/stable/).

The following lines are for running this notebook in a Google Colab:


```python
import shutil
import sys
import os.path

if not shutil.which("pyomo"):
    !pip install -q pyomo
    assert(shutil.which("pyomo"))

if not (shutil.which("glpk") or os.path.isfile("glpk")):
    if "google.colab" in sys.modules:
        !apt-get install -y -qq glpk-utils
    else:
        try:
            !conda install -c conda-forge glpk 
        except:
            pass
```

## 2.2 Example From the Slides
Consider the following example, which is solved graphically on the slide *Introduction to Linear Programming*.

We want to solve the following Linear Programming problem:
\begin{align}
\min \;\; & -x_1 - x_2 \\
\mbox{s.t. } \;\; 
& x_1 + 2x_2 \leq 3 & \\
& 2x_1 + x_2 \leq 3 & \\
& x_1 \geq 0 & \\
& x_2 \geq 0 & \\
\end{align}

Note that we have 
$c = \left[\begin{array}{c} -1 \\ -1 \end{array}\right]$, 
$A = \left[ \begin{array}{cc}1 & 2 \\ 2 & 1 \end{array} \right]$, and
$b = \left[\begin{array}{c} 3 \\ 3 \end{array}\right]$.



```python
from pyomo.environ import *
```


```python
model = ConcreteModel()

# declare decision variables
model.x1 = Var(domain=NonNegativeReals)
model.x2 = Var(domain=NonNegativeReals)

# declare objective
model.cost = Objective(
    expr = - model.x1 - model.x2,
    sense = minimize)

# declare constraints
model.cnstr1 = Constraint(expr = model.x1 + 2*model.x2 <= 3)
model.cnstr2 = Constraint(expr = 2*model.x1 + model.x2 <= 3)

# solve
sol = SolverFactory('glpk').solve(model)
```

To check the optimal value of the decision variables:


```python
print("x1 = {}, x2 = {}".format(model.x1(), model.x2()))
```

Note that in the previous example, the model variable are used as they were a function (with round parenthesis) to get their values.

Similirayl, in order to get the optimal solution value, you can type:


```python
print("f(x1,x2) = {}", model.cost())
```

## 2.3 Graphical Solution
In the following snippets, we show a graphical interpretation of the LP with two variables of the previous section. All the snippets are very similir, and they are executed to produce the plots inserted into the slides used during the lecture.


```python
from pylab import *
figure(figsize=(6, 6))
subplot(111, aspect='equal')
axis([0, 3.5, 0, 3.5])
xlabel('$x_1$')
ylabel('$x_2$')

# First constraint
x = array([0, 3])
y = 3/2 - 1/2*x
plot(x, y, 'g', lw=2)
fill_between([0, 3, 2], [1.5, 0, 0], [0, 0, 0], color='g', alpha=0.15)

t1 = annotate('$x_1 + 2x_2 \leq 3$', xy=(2,0.5), xytext=(2.5, 0.7),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='g'))
savefig("example16a.pdf", bbox_inches='tight')
```


```python
figure(figsize=(6, 6))
subplot(111, aspect='equal')
axis([0, 3.5, 0, 3.5])
xlabel('$x_1$')
ylabel('$x_2$')

# Second constraint
x = array([0, 1.5])
y = 3 - 2*x
plot(x, y, 'b', lw=2)
fill_between([0, 1.5, 100], [3, 0, 0], [0, 0, 0], color='b', alpha=0.15)

t2 = annotate('$2x_1 + x_2 \leq 3$', xy=(0.25,2.5), xytext=(0.7, 2.5),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='b'))
savefig("example16b.pdf", bbox_inches='tight')
```


```python
from pylab import *
figure(figsize=(6, 6))
subplot(111, aspect='equal')
axis([0, 3.5, 0, 3.5])
xlabel('$x_1$')
ylabel('$x_2$')

# First constraint
x = array([0, 3])
y = 3/2 - 1/2*x
plot(x, y, 'g', lw=2)
fill_between([0, 3, 2], [1.5, 0, 0], [0, 0, 0], color='g', alpha=0.15)

# Second constraint
x = array([0, 1.5])
y = 3 - 2*x
plot(x, y, 'b', lw=2)
fill_between([0, 1.5, 100], [3, 0, 0], [0, 0, 0], color='b', alpha=0.15)

annotate('$x_1 + 2x_2 \leq 3$', xy=(2,0.5), xytext=(2.5, 0.7),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='g'))

annotate('$2x_1 + x_2 \leq 3$', xy=(0.25,2.5), xytext=(0.7, 2.5),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='b'))

legend(['Constraint 1','Constraint 2'])
savefig("example16c.pdf", bbox_inches='tight')
```


```python
from pylab import *
figure(figsize=(6, 6))
subplot(111, aspect='equal')
axis([0, 3.5, 0, 3.5])
xlabel('$x_1$')
ylabel('$x_2$')

# First constraint
x = array([0, 3])
y = 3/2 - 1/2*x
plot(x, y, 'g', lw=2)
fill_between([0, 3, 2], [1.5, 0, 0], [0, 0, 0], color='g', alpha=0.15)

# Second constraint
x = array([0, 1.5])
y = 3 - 2*x
plot(x, y, 'b', lw=2)
fill_between([0, 1.5, 100], [3, 0, 0], [0, 0, 0], color='b', alpha=0.15)

t1 = annotate('$x_1 + 2x_2 \leq 3$', xy=(2,0.5), xytext=(2.5, 0.7),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='g'))

t2 = annotate('$2x_1 + x_2 \leq 3$', xy=(0.25,2.5), xytext=(0.7, 2.5),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='b'))

# Objective function
x = array([0, 4])
for p in linspace(0, 10, 21):
    y = p - x
    plot(x,y,'y--', color='red', alpha=0.3)

text(0.1,0.6,'Decreasing Cost')
annotate('', xy=(0.5, 0.5), xytext=(0, 0),
          arrowprops=dict(width=0.5, headwidth=5, color='r'))
savefig("example16d.pdf", bbox_inches='tight')
```


```python
from pylab import *
figure(figsize=(6, 6))
subplot(111, aspect='equal')
axis([0, 3.5, 0, 3.5])
xlabel('$x_1$')
ylabel('$x_2$')

# First constraint
x = array([0, 3])
y = 3/2 - 1/2*x
plot(x, y, 'g', lw=2)
fill_between([0, 3, 2], [1.5, 0, 0], [0, 0, 0], color='g', alpha=0.15)

# Second constraint
x = array([0, 1.5])
y = 3 - 2*x
plot(x, y, 'b', lw=2)
fill_between([0, 1.5, 100], [3, 0, 0], [0, 0, 0], color='b', alpha=0.15)

legend(['Constraint 1','Constraint 2'])

# Put some arrows
plot(1.5,0,'b.',ms=20)
annotate('$x_1$ only', xy=(1.5,0), xytext=(2, 0.1),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='r'))

annotate('$x_1 + 2x_2 \leq 3$', xy=(2,0.5), xytext=(2.5, 0.7),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='g'))

plot(0,1.5,'g.',ms=20)
annotate('$x_2$ only', xy=(0,1.5), xytext=(1.0, 2.0),
          arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='r'))

annotate('$2x_1 + x_2 \leq 3$', xy=(0.25,2.5), xytext=(0.7, 2.5),
         arrowprops=dict(shrink=0.1, width=2, headwidth=10, color='b'))

# Objective function
x = array([0, 4])
for p in linspace(0, 10, 21):
    y = p - x
    plot(x,y,'y--', color='red', alpha=0.3)

# Optimum
plot(1,1,'r.',ms=20)
annotate('Optimal Solution', xy=(1,1), xytext=(2,1.5),
          arrowprops=dict(shrink=.1, width=2, headwidth=10, color='r'))

text(0.1,0.6,'Decreasing Cost')
t3 = annotate('', xy=(0.5, 0.5), xytext=(0, 0),
          arrowprops=dict(width=0.5, headwidth=5, color='r'))
savefig("example16d.pdf", bbox_inches='tight')
```


```python

```

9aa0505b31a728aacfe4dd62f5759810cc52beb2
ipynb
Jupyter Notebook
aa2020/notebooks/LPwithTwoVariables.ipynb
gianlucacovini/opt4ds
c8927ad36cace51c501527b2f8e8e93857c80d95
MIT
2020-03-04T18:02:47.000Z
2022-02-27T17:40:09.000Z
aa2020/notebooks/LPwithTwoVariables.ipynb
gianlucacovini/opt4ds
c8927ad36cace51c501527b2f8e8e93857c80d95
MIT
2021-03-23T11:47:24.000Z
2021-03-28T12:23:21.000Z
aa2020/notebooks/LPwithTwoVariables.ipynb
mathcoding/opt4ds
42904fd56c18a83fd5ff6f068bbd20b055a40734
MIT
2020-03-12T23:41:21.000Z
2022-03-03T13:41:29.000Z
Qwen/Qwen-72B
1. YES
2. YES