Gentle Introduction to Linear Programming
Tags: python, datascience, programming, computerscience
Published: 2021-11-15 22:50:00

<!-- wp:separator -->
<hr class="wp-block-separator"/>
<!-- /wp:separator -->

<!-- wp:paragraph -->
<p>First, let’s talk about a Linear Equation. A linear equation consists of variables, the only restriction is that each variable can have a power of 1. I.e there can be no variable with a power of 2 or greater.</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*crjno_3nbSGaVR-Ssst0aQ.png" alt=""/><figcaption>Image By&nbsp;Author</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Linear Programming consists of two parts. The objective function is a linear equation and a set of constraints. The objective function or the linear equation will either have to be maximized or minimized.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Eg: Consider a bookseller has 3 types of books (Physics, Chemistry, and Biology). The Physics Book makes a profit of 10\$, Chemistry makes a profit of 5\$ and Biology makes a profit of 2\$. If we wanted to write a equation for the total profit it would look something like below</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*jgKPIuzU7n0g5-pjwVWKyw.png" alt=""/><figcaption>Image by&nbsp;Author</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>We would need to maximize the above equation. Right now it doesn’t have any constraints therefore the value for the variables has no upper bounds. However, in real life, there will be constraints. In the above example, constraints could be the number of books the bookseller has in stock. If the Book Seller has 5 Physics books available, 3 Chemistry Books available, and 10 Biology Books available, our problem would look like below</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*lpagvH8k3qd78i8-WbxTyQ.png" alt=""/><figcaption>Image by&nbsp;Author</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>The above is a simple case and can be solved without the need to use Python. However, in the real world, the Formulation of the Problems is very complex in nature. We will look at some of these in the next chapter.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Some applications of Linear Programming are listed below</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>Supply Chain</li><li>Scheduling Problems</li><li>Delivery Route Problems</li><li>Manufacturing Problems</li><li>&nbsp;Diet Plan Optimization</li><li>Production Planning</li><li>Transportation</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>As the problems become more complex, it becomes harder to solve the problem without the help of a solver. A solver is a software that basically accepts the problem formulation(variables, objectives, and constraints) as inputs and returns the solution.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><a href="https://coin-or.github.io/pulp/index.html" rel="noreferrer noopener" target="_blank">PuLP</a> is an open-source software written in Python. It helps you to formulate problems such as the bookseller problem. It is free and supports free open-source solvers as well. For an introduction to PuLP, refer to my below article</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><a href="https://www.realpythonproject.com/basic-linear-programming-in-python-with-pulp/" target="_blank" rel="noreferrer noopener"><strong>Basic Linear Programming in Python with PuLP</strong><br></a><a href="https://towardsdatascience.com/basic-linear-programming-in-python-with-pulp-d398d144802b"></a></p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":3} -->
<h3>Plotting the Feasible Region Using&nbsp;Python</h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>In some cases a linear problem doesn’t have an objective function, it simply has a set of constraints, and the solution which satisfies all the constraints is required.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"linkDestination":"custom"} -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/0*wSTsFxsQ_lAmKjfH" alt=""/><figcaption>The image is taken from&nbsp;<a href="https://medium.com/p/d398d144802b" target="_blank" rel="noreferrer noopener">here</a></figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Given a set of constraints, a feasible region is the solution space or the set of values that satisfy all the constraints. In the above picture, the various lines are the constraints related to Car A (X-Axis) and Car B (Y-Axis) and the green shaded area is the feasible region. Any Coordinate within the green shaded region, eg: (1,2), (2,2), etc will satisfy all the constraints.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Consider the following set of constraints</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*1IIvrFduP6kqf-yq0FK5nA.png" alt=""/><figcaption>Image By&nbsp;Author</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Let’s try to plot the feasible region for the above constraints. First, install NumPy and matplotlib</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">pip3 install numpy, matplotlib</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>Below is the code for plotting the </p>
<!-- /wp:paragraph -->

<!-- wp:code -->
<pre class="wp-block-code"><code lang="python" class="language-python">x = np.linspace(0, 50, 1000)
y = np.linspace(0, 50, 1000)

'''
Draw Vertical Line
'''
plt.axvline(10, color='b', label=r'X &lt;=10')
plt.axvline(0, color='b', label=r'X &gt;=0')

'''
Draw Horizontal Line
'''
plt.axhline(2, color='r', label='Y &gt;= 2') 
plt.axhline(10, color='r', label='Y &lt;= 10') 

'''
X+Y&gt;=12
'''
plt.plot(x, 12-x, label='X+Y&gt;=12',color='b')

'''
X+Y&lt;=15
'''
plt.plot(x, 15-x, label=r'X+Y&lt;=15',color='yellow') # constraint 4

plt.xlim((0, 20))
plt.ylim((0, 20))
plt.show()</code></pre>
<!-- /wp:code -->

<!-- wp:paragraph -->
<p>This the plot</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*wRySNlDpnwH-4vF8qqPy_Q.png" alt=""/><figcaption>Lines Plotted</figcaption></figure>
<!-- /wp:image -->

<!-- wp:heading {"level":4} -->
<h4>Letting Matplotlib Calculate the Feasible&nbsp;region</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>The following code will calculate the feasible region for the above </p>
<!-- /wp:paragraph -->

<!-- wp:code -->
<pre class="wp-block-code"><code lang="python" class="language-python">x,y = np.meshgrid(np.linspace(0, 50, 1000),np.linspace(0, 50, 1000))
plt.imshow( 
        (
            (x&gt;=0)&amp;(x&lt;=10)&amp;(y&gt;=2)&amp;(y&lt;=15-x)&amp;(y&gt;=12-x)&amp;(y&lt;=10)
        ).astype(int) , 
        extent=(0,50,0,50),
        origin="lower", 
        cmap="Reds", 
        alpha = 0.3);</code></pre>
<!-- /wp:code -->

<!-- wp:paragraph -->
<p>You will need to put this before we plot any of the lines. This will ensure that the lines are drawn on top of the feasible region. This method was taken from <a href="https://stackoverflow.com/questions/57017444/how-to-visualize-feasible-region-for-linear-programming-with-arbitrary-inequali" rel="noreferrer noopener" target="_blank">this stack overflow answer</a></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Below is the Feasible Region</p>
<!-- /wp:paragraph -->

<!-- wp:image -->
<figure class="wp-block-image"><img src="https://cdn-images-1.medium.com/max/1600/1*wS8dXDZ78LoEZivqLmXDgA.png" alt=""/><figcaption>Feasible Region&nbsp;Plot</figcaption></figure>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>All the points in this feasible region satisfy all the constraints.&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":3} -->
<h3>Conclusion</h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>I hope this article served as a good introduction to Linear Programming</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>You can check out the following articles related to Linear Programming</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><meta charset="utf-8"><a href="https://www.realpythonproject.com/basic-linear-programming-in-python-with-pulp/" target="_blank" rel="noreferrer noopener"><strong>Basic Linear Programming in Python with PuLP</strong></a></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><a href="https://www.realpythonproject.com/how-to-solve-a-sudoku-puzzle-using-python-and-linear-programming/" target="_blank" rel="noreferrer noopener">How To Solve A Sudoku Puzzle Using Python And Linear Programming</a></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><a href="https://www.realpythonproject.com/how-to-balance-chemical-equations-in-python-using-constraint-optimization-pulp/" target="_blank" rel="noreferrer noopener">How to Balance Chemical Equations in Python using Constraint Optimization (PuLP)</a></p>
<!-- /wp:paragraph -->

<!-- wp:separator -->
<hr class="wp-block-separator"/>
<!-- /wp:separator -->

<!-- wp:paragraph -->
<p>Connect with on <a href="https://www.linkedin.com/in/rahulbanerjee2699/" rel="noreferrer noopener" target="_blank">LinkedIn</a>, <a href="https://twitter.com/rahulbanerjee99" rel="noreferrer noopener" target="_blank">Twitter</a>.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>If you like my articles and would like to support me, please consider using my <a href="https://rahul1999.medium.com/membership" rel="noreferrer noopener" target="_blank">Referral link</a> to sign up for a Medium Membership. You will be able to access all articles behind the paywall. If you use my referral, I will get a part of your monthly subscription at no extra cost for you.</p>
<!-- /wp:paragraph -->