Interactive Graphic Method

Try me

Introduction

In this notebook, you can experiment with the graphic representation of a linear programming problem. The objective is to gain understanding on the graphic method, how constraints affect the boundaries of the feasibility region and why the solution to a problem is always at a vertex of the feasibility region. In this notebook you will be able to change the objective variable and add or remove constraints to experiment and reflect on these questions.

Requirements

This script uses Numpy, Matplotlib, and Ipywidgets. They are provided off-the-shelf in Colabs. Otherwise, run the following cell to install in your Kernel:

!pip install numpy
!pip install matplotlib
!pip install ipywidgets

Problem model

The problem model is taken from the Making weapons problem. You can find the solution here: (Making weapons)

\(\max z = 40x_{1} + 5x_{2}\)

s.t.

\(x_{1} + 0.5x_{2} \leq 125\) (Beskar constraint)

\(x_{1} + x_{2} \leq 225\) (Tungsten constraint)

\(3x_{1} + x_{2} \leq 300\) (Titanium constraint)

\(x_{2} \geq 100\) (Demand constraint)

The code cell below allows you to add the constraints one by one to see how to modify the feasibility region. The slider allows to modify the objective variable z to find the optimal value in each case. Remember, the optimal value will be always the highest value of z where the objective function intersects with the feasibility region.

Solution with the graphical method

#Import the numpy and pyplot libraries, we set the aliases np and plt so that it is easier to use
import numpy as np
import matplotlib.pyplot as plt
import ipywidgets as widgets
from ipywidgets import interactive
#We set the mode inline of matplotlib to get the result at the output of the cell code
%matplotlib inline

#Construct lines, in our coordinate system x represents our decision variable x1 and y represents our decision variable x2
x=np.linspace(0,300,2000) #2000 numbers from 0 to 100



y1=(125-x)/0.5 # Beskar constraint
y3=225-x       # Tungsten constraint
y4=100+x*0     # Demand constraint
y5=300-3*x     # Titanium constraint


#1. Interactive plot
def show_solution(z, beskar_constraint, tungsten_constraint, titanium_constraint, demand_constraint):
    y_min=x*0         # absolute min: non negativity constraint
    y_max = 250 + 0*x   # A very high maximum value
    plt.figure(1) #Create a figure
    # 1. Check if we need to add constraints and recalculate max and min
    if beskar_constraint:
        plt.plot(x,y1,label=r'$x_{1}+0.5x_{2}\leq125$')
        y_max = np.minimum(y1, y_max)

    if tungsten_constraint:
        plt.plot(x,y3,label=r'$x_{1}+x_{2}\leq225$')
        y_max = np.minimum(y3, y_max)

    if titanium_constraint:
        plt.plot(x,y5,label=r'$3x_{1}+x_{2}\leq300$')
        y_max = np.minimum(y5, y_max)

    if demand_constraint:
        plt.plot(x,y4,label=r'$x_{2}\geq100$')
        y_min = y4

    # 2. Adjust axis
    plt.xlim((0,150))
    plt.ylim((0,250))
    plt.xlabel((r'$x_{1}$'))
    plt.ylabel((r'$x_{2}$'))

    # 3. fill between max and min
    plt.fill_between(x, y_max, y_min, where=y_max>y_min, color='grey', alpha=0.5)

    # 4. Plot objective function
    obj_func= (z - 40*x)/5 # we clear the x2 with the value of z
    plt.plot(x, obj_func, label=r'$z = 40*x_1 + 5*x_2$')

    # 5. Plot legend
    plt.legend(bbox_to_anchor=(1.05,1), loc=2, borderaxespad=0.)
    plt.show()

interactive_plot = interactive(show_solution, z=(0,6000,10), beskar_constraint = False, tungsten_constraint = False, titanium_constraint = False, demand_constraint = False)
output = interactive_plot.children[-1]
output.layout.height = '350px'
interactive_plot