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$
  • $\begingroup$ Here's an open-source software that is very useful for exactly this: padowan.dk $\endgroup$ – Math1000 Jan 31 '16 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$ – Boris Jan 31 '16 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$ – Skeen Jan 31 '16 at 15:47
  • $\begingroup$ It should have been >= but someone edited it, now it's correct. $\endgroup$ – Boris Jan 31 '16 at 16:05
  • $\begingroup$ Yes, I just checked the history, it appears Subhadeep Dey was a bit too fast in the type-setting. $\endgroup$ – Skeen Jan 31 '16 at 16:19
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$
  • $\begingroup$ Thanks, I know how to do that, but how can I find the optimal integer solution from this graph? $\endgroup$ – Boris Jan 31 '16 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$ – Skeen Jan 31 '16 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.