Optimization-LinearProgramming-Python

>> Linear programming:¶

One of the Optimization topics is Linear Programming. In this category of optimization problems, both the cost function and all the restrictions are linear.

Linear programming (LP) is one of the simplest ways to perform optimization. We can solve some very complex optimization problems by making a few simplifying assumptions. As an analyst one is bound to come across applications and problems to be solved by Linear Programming.

It is a simple technique where we depict complex relationships through linear functions and then find the optimum points. The real relationships might be much more complex – but we can simplify them to linear relationships.

It could be a breakthrough method while solving optimization problems. One can use it to find Minimum cost expenditure, maximum profit gained, shortest path to travel, etc.

Simple Example:¶

Here I am providing a simple example to illustrate solving a simple LP optimization problem.

Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:

x + 2y <= 14,

3x - y >= 0,

x - y <= 2

Here we need to find optimum (Max/Min) solution for the Objective Function: z = 3x + 4y. First of all, we will convert constraints equations into more simpler way:

Now we will plot graph for these constraint equations.

The soltuion lies in the bounded (feasible) region. And the optimal solution is @ either of these corners.

Its tabular repsentation to find the corner points.

Solution for these corner points:

(2, 6): z = 3(2) + 4(6) = 6 + 24 = 30

(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34

(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15

Then the maximum of z = 34 occurs at (6, 4),

and the minimum of z = –15 occurs at (–1, –3).

>> Common terminologies used in Linear Programming¶

Decision Variables: The decision variables are the variables which will decide my output. They represent my ultimate solution. To solve any problem, we first need to identify the decision variables. For the above example, the total number of units for A and B denoted by X & Y respectively are my decision variables.

Objective Function: It is defined as the objective of making decisions. In the above example, the company wishes to increase the total profit represented by Z. So, profit is my objective function.

Constraints: The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables. In the above example, the limit on the availability of resources Milk and Choco are my constraints.

Non-negativity restriction: For all linear programs, the decision variables should always take non-negative values. Which means the values for decision variables should be greater than or equal to 0.

>> Solving LP problems:¶

There are many ways to solve a LP problem; like:- solving it throgh converting it to Standard Form, Graphical Method. Out of which, Graphical Method is most popular method.

Additionally, we have multiple libraries for python that can help us soving a LP problem. viz.

1.) scipy.optimize.minimize

2.) scipy.optimize.linprog

3.) PuLP

4.) Analyzing graphs through plotting with Matplotlib

..... And there must be few other methods also.

>> Circumstances in which we apply LP technique to solve our daily analytics operation¶

we use LP technique to solve the optimiziation cases:

When we want to get best outcome (such as maximum profit or lowest cost) in a mathematical model; considering whose requirements are represented by "linear relationships" .

When its objective function can be represented through a linear function . and subject to subject to linear equality and linear inequality constraints.

->It can be applied in following application indaily analytics operations:

1. Manufacturing industries use linear programming for analyzing their supply chain operations. Their motive is to maximize efficiency with minimum operation cost.

2. Linear programming is also used in organized retail for shelf space optimization. Since the number of products in the market have increased in leaps and bounds, it is important to understand what does the customer want.

3. Optimization is also used for optimizing Delivery Routes. This is an extension of the popular traveling salesman problem.

4. Optimizations is also used in Machine Learning. Supervised Learning works on the fundamental of linear programming.
5. There are many more applications of linear programming in real-world like applied by Shareholders, Sports, Stock Markets, etc.

Question:¶

> A car company produces 2 models, model A and model B. Long-term projections indicate an expected demand of at least 100 model A cars and 80 model B cars each day. Because of limitations on production capacity, no more than 200 model A cars and 170 model B cars can be made daily. To satisfy a shipping contract, a total of at least 200 cars much be shipped each day. If each model A car sold results in a $2000 loss, but each model B car produces a $5000 profit, how many of each type should be made daily to maximize net profits?

car models - A & B

*demand: A >= 100 ; B >= 80

*produce: A <= 200 ; B <= 170

So, we can conclude that: 200 >= A >= 100 and 170 >= B >= 80

*Shipping: A + B >= 200

*objective function: ( z = 5000B - 2000A )

visualization of the problem:¶

The solution lies in the feasible region( green region) ------¶

In [9]:

import matplotlib.pyplot 
from matplotlib.pyplot import *
import numpy
from numpy import arange
figure()
A = arange(-100, 220, 10)
B = arange(-100, 220, 10)
# constraint equation
B1 = 200.0 - A
xlim = (-100, 220)
ylim= (-100, 220)
hlines(0, -100, 220, color = 'k')
vlines(0, -100, 220, color = 'k')
grid(True)
xlabel('X-axis')
ylabel('Y-axis')
#Plotting graph
plot(A, B1, color = 'b')
axhline(y = 80, color = 'r')
axhline(y = 170, color = 'm')
axvline(x = 200, color = 'b')
axvline(x = 100, color = 'g')
title('objective function: z = 5000B - 2000A with following constarints')
legend(['A+B>=200','200>=A>=100','170>=B>=80'])
# get the co-ordinates of intersection points by mere visualisation
A = [200.0,100.0, 100.0, 120.0,200.0]
B = [170.0, 170.0, 100.0, 80.0, 80.0]
fill(A,B,'g+')
show()
#Getting Solution
checker = 0
for i,j in zip(A,B):
print('\n calculating for point: A = {0:f} and B = {1:f}' .format(i,j))
print('solution for z = ', 5000j-2000i)
if(checker <= (5000j-2000i)):
checker = (5000j-2000i)
X,Y = i,j
print('\n the maximum profit z = ${0:f} @ A = {1:f} and B = {2:f}' .format(checker,X,Y))

Output::::::::::::

Solving using library PULP:¶

In [6]:

from pulp import *
# declare your variables
A = LpVariable("A", 100, 200)   # 100 <= A <= 200
B = LpVariable("B", 80, 170) # 80 <= B <= 170
# defines the problem: optimization - Maximization
prob = LpProblem("problem", LpMaximize)
# defines the constraints
prob += A + B >=200
prob += A<=200
prob += A>=100
prob += B>=80
prob += B<=170
# defines the objective function to maximize
prob += 5000B-2000A
# solve the problem
status = prob.solve()
print('printing status of the LP problem: ', LpStatus[status])
# print the results A = 100, B = 170
print('Value of model A car: ', value(A))
print('Value of model B car: ', value(B))
print('the optimal solution or say maximum profit: $', value(prob.objective))

Output::::::::::::

printing status of the LP problem:  Optimal
Value of model A car:  100.0
Value of model B car:  170.0
the optimal solution or say maximum profit: $ 650000.0

Solving using Scipy Library:¶

In [11]:

import numpy as np
from scipy.optimize import minimize
#defining our Objective function
def objective(x):
A = x[0]
B = x[1]
#since we are finding Max result using Minimizer. So returned the negative value.
return -(5000B-2000A)
def constraint(x):
return x[0]+x[1]-200
#boundations
b1 = [100, 200]     #bounds on A: 200 >= A >= 100
b2 = [80, 170]      #bounds on B: 170 >= B >= 80
bnds = (b1,b2)
#defining Inequality type of constraint.
con = {'type': 'ineq', 'fun': constraint}
# passing any guess value for A and B into minimize fuinction.
Xguess = [100,100]
#Predicting Maximization values for the objective function by seeding guess value Xguess; boundations included..
sol = minimize(objective, Xguess, method = 'SLSQP', options={'disp':True}, bounds = bnds, constraints = con)
print('About solution from Optimize.minnimize: \n' ,sol)
#assigning values to desired results.
profit = -sol.fun   #converting back to positive answer
CarA = sol.x[0]     # number of car A models
CarB = sol.x[1]     # number of car B models
###################################################################
print ('\n\n\nPrinting the Results: \n\n\n')
print('maximum Profit Gained: $', profit)
print('\n Number of Model A Cars: ',CarA)
print('\n Number of Model B Cars: ',CarB)

Output::::::::::::

Positive directional derivative for linesearch    (Exit mode 8)
            Current function value: -650000.0
            Iterations: 7
            Function evaluations: 12
            Gradient evaluations: 3
About solution from Optimize.minnimize: 
      fun: -650000.0
     jac: array([ 2000., -5000.])
 message: 'Positive directional derivative for linesearch'
    nfev: 12
     nit: 7
    njev: 3
  status: 8
 success: False
       x: array([ 100.,  170.])



Printing the Results: 



maximum Profit Gained: $ 650000.0

 Number of Model A Cars:  100.0

 Number of Model B Cars:  170.0