3
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Here's an open-source software that is very useful for exactly this: padowan.dk $\endgroup$ Commented Jan 31, 2016 at 14:52
  • $\begingroup$ That's helpful but I need to know how to draw the graph by hand. I mean I have to show the whole process. $\endgroup$ Commented Jan 31, 2016 at 15:05
  • $\begingroup$ Also you should know that given your problem definition $(x_1, x_2) = (0, 250)$ is indeed NOT a valid solution, by the constraint $x_1 > 0$. As $0 > 0$ is false, had your constrained been $x_1 \geq 0$ it would have been a valid solution. $\endgroup$ Commented Jan 31, 2016 at 15:47
  • $\begingroup$ It should have been >= but someone edited it, now it's correct. $\endgroup$ Commented Jan 31, 2016 at 16:05
  • $\begingroup$ Yes, I just checked the history, it appears Subhadeep Dey was a bit too fast in the type-setting. $\endgroup$ Commented Jan 31, 2016 at 16:19

1 Answer 1

Reset to default
2
$\begingroup$

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;

Wolfram Alpha plotting

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):

Wolfram Alpha plotting

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

Wolfram Alpha plotting

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

$\endgroup$
2
  • $\begingroup$ Thanks, I know how to do that, but how can I find the optimal integer solution from this graph? $\endgroup$ Commented Jan 31, 2016 at 15:33
  • $\begingroup$ The coordinates for last defined point you get from 'shoving' the maximization line 'up' is the optimal solution point. Giving the linearity of your maximization function, it'll always be on an intersection between two constraints. In this case the $x_2 = 250-\frac{5x_1}{14}$ and $x_1 > 0$. $\endgroup$ Commented Jan 31, 2016 at 15:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.