Get this book -> Problems on Array: For Interviews and Competitive Programming

Mathematical Programming is used to find the best or optimal solution to a problem that requires a decision or set of decisions about how best to use a set of limited resources to achieve a state goal of objectives.

**Linear programming** requires that all the mathematical functions in the model be linear functions. We have solved linear programming problems in Python using **cvxpy library**.

# Mathematical formulation

Decision variables: X_{1}, X_{2}, X_{3}, .... X_{n}

Objective function or linear function: Z

# Library used

Here, we use the library, `cvxpy`

to find the solution of the linear programming problem(lpp).

To install this library, use the following command:

```
pip3 install cvxpy
```

To include it in our code, use

```
import cvxpy as cp
import numpy as np
```

# EXAMPLE 1

## Problem

Here, we solve the following LPP:

Maximise: z = x_{1} + x_{2}

Subject to

- 4 x
_{1}+ 3 x_{2}<= 12 - -3 x
_{1}+ 4 x_{2}<= 12 - 0 <= x
_{1}, x_{2}<= 2

The expected solution is

- z = 3.5
- x
_{1}= 1.5 - x
_{2}= 2

## CODE

### Step 1: First define the number of variables that would be used

For example, if only two x_{i}s would be used,

```
x = cp.Variable(shape=(2,1), name="x")
```

This line creates a column matrix of dimensions `2 x 1`

(in a general case, if `n`

is the number of linear programming variables, then a column matrix of dimensions `n x 1`

should be made.)

### Step 2: Define the constraints

Here the constraints are as follows

x_{1} |
x_{2} |
Inequality | Constraint |
---|---|---|---|

4 | 3 | <= | 12 |

-3 | 4 | <= | 12 |

All values of x lie between 0 and 2 both inclusive.

```
A = np.array([[4,3],[-3,4]])
constraints = [cp.matmul(A, x) <= 12, x<=2, x>=0]
```

The above lines first make a `2 x 2`

matrix (as described in the table above). Since both of their constraints are the same, we can define the constraint in a single line, by making the matrix `<=`

12.

Multiple constraints on both the variables can be defined using `x`

as a general variable.

For defining multiple single lined distinct constraints, use the following format:

```
A x <= B
```

Where `<=`

can be replaced by any other inequality symbol.

Here A is a square matrix of dimensions `n x n`

where n is the number of varibles in the linear programming problem, x is as defined in the previous step, and B is a column matrix of dimensions `n x 1`

.

For example, for defining the following constraints, use the following snippet: (n = 3)

x_{1} |
x_{2} |
x_{3} |
Inequality | Constraint |
---|---|---|---|---|

4 | 3 | 2 | <= | 12 |

-3 | 4 | 2 | <= | -10 |

-2 | 3 | 1 | <= | 14 |

```
A = np.array([[4,3,2],[-3,4,2],[-2,3,1]])
B = np.array([[12],[-10],[14]])
constraints = [cp.matmul(A, x) <= B, x<=2, x>=0]
```

### Step 3: Define the objective function

Here the objective function is z = x_{1} + x_{2}

```
objective = cp.Maximize(cp.sum(x, axis=0))
```

For an objective function z = 3 x_{1} + 4 x_{2}, define a new 1 dimensional array containing the different parameters in the objective function as follows:

```
r = np.array([3,4])
objective = cp.Maximize(cp.matmul(r, x))
```

### Step 4: Define the problem and then solve it

The problem is defined by the objective function and the constraints.

```
problem = cp.Problem(objective, constraints)
solution = problem.solve()
```

### Step 5: Print the maximised objective funstion, and the x values

```
print(solution)
print(x.value)
```

Here, solution contains the value of the objective function, and x.value is the column matrix, containing the values of x_{i}.

## Final code

```
import cvxpy as cp
import numpy as np
x = cp.Variable(shape=(2,1), name="x")
A = np.array([[4,3],[-3,4]])
constraints = [cp.matmul(A, x) <= 12, x<=2, x>=0]
objective = cp.Maximize(cp.sum(x, axis=0))
problem = cp.Problem(objective, constraints)
solution = problem.solve()
print(solution)
print(x.value)
```

## Output of the code

```
3.4999999999296327
[[1.5]
[2. ]]
```

Here the first line denotes the solution while the next two lines denote the values of the two parameters.

# EXAMPLE 2

## Problem

Here, we solve the following LPP:

Minimize: z = 4 x_{1} + 2 x_{2}

Subject to

- 4 x
_{1}+ 3 x_{2}<= 12 - -3 x
_{1}+ 6 x_{2}<= 10 - x
_{1}>= 1 - 0 <= x
_{1}, x_{2}<= 5

The expected solution is

- z = 4.00
- x
_{1}= 1.00 - x
_{2}= 0.00

## Code

```
import cvxpy as cp
import numpy as np
x = cp.Variable(shape=(2,1), name="x")
A1 = np.array([[4,3],[-3,6]])
A2 = np.array([1,0])
B = np.array([[12],[10]])
constraints = [cp.matmul(A1, x) <= B, cp.matmul(A2, x) >= 1, x<=5, x>=0]
r = np.array([4,2])
objective = cp.Minimize(cp.matmul(r, x))
problem = cp.Problem(objective, constraints)
solution = problem.solve()
print(solution)
print(x.value)
```

## Output of the code

```
3.9999999998494915
[[1.0000000e+00]
[7.7046817e-11]]
```

With this article at OpenGenus, you must have the complete idea of solving Linear Programming problems in Python. Enjoy.