Solving integer programming problem using the graphical method

Question

I have an integer programming problem I need to solve using the graphical method.

Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ 5x_1 + 4x_2 &\le 2200 \end{align}$$ $$x_1,x_2 \ge 0$$

The optimal solution is known and it's $(0,250)$. The problem is that I need to draw the graph by hand and I don't know how to do it properly when the numbers are quite big.

Thanks!

Answer 1

Here's how I usually solve these kinds of problems graphically:

• Start out by drawing a cartesian 2-dimensional coordinate system ($(x_1, x_2)$ in your case).

• Draw your limits as lines; i.e. by isolating $x_2 = \ldots$ and plotting the lines (scale the $x_1$- and $x_2$-axises according to your needs).

• These lines will confine an area, this is your solution space; i.e. the area which contains your of your valid solutions.

Now for finding the optimal solution;

The maximization function can be seen as just another 'line', i.e. by isolating $x_2 = \ldots$

• Draw this line into the 'limits' graph, as relationship between $x_1$ and $x_2$ of the maximization function is 'encoded' in the slope of the line. The optimum value can be found by simply 'shoving' the line 'up' until only a single point of the line is within the area of valid solutions.

Example:

Isolating your constraints for $x_2$ yields: $$\begin{align} 4x_1 + 5x_2 \le 2000 \quad\Rightarrow\quad x_2 \leq 400 - \frac{4x_1}{5} \\ 2.5x_1 + 7x_2 \le 1750 \quad\Rightarrow\quad x_2 \leq 250 - \frac{5x_1}{14} \\ 5x_1 + 4x_2 \le 2200 \quad\Rightarrow\quad x_2 \leq 550 - \frac{5x_1}{4} \end{align}$$ Plotting these yields;

Where the area below the graph, but with $x_1, x_2 > 0$ is the solution space.

We can see that the blue line ($x_2 \leq 400 - \frac{4x_1}{5}$) is superfluous for defining the solution space, and thus leave it out.

Your maximization function isolated for $x_2$ yields: $$ 55x_1 + 500x_2 = 0 \\ \Downarrow \\ x_2 = -\frac{11x_1}{100} $$

Adding this to the plot, yields the following graph (new blue line = maximization function):

Now 'shoving' this maximization function line 'up' yields the following;

At this point the line cannot be 'shoved' further 'up', without entirely leaving the solution space.