# Graphical Method: Integer Programming

This section deals with the geometric representation of an integer programming problem.

To illustrate the concept of cutting plane method through graphical method, consider again the following problem.

## Example Graphical Method: Cutting Plane Method

Maximize z = x1 + 4x2

subject to
2x1 + 4x2 ≤ 7
5x1 + 3x2 ≤ 15

x1, x2 are integers ≥ 0

Solution.

First, solve the above problem by applying the simplex method.

After introducing slack variables, we have
2x1 + 4x2 + x3 = 7
or  x3 = 7 - 2x1 - 4x2 ....(i)
5x1 + 3x2 + x4 = 15
or  x4 = 15 - 5x1 - 3x2 ....(ii)

Gomory's constraint

- (1/2x1 - 3/4 x3) ≤ -3/4 ...(iii)

Substituting the value of x3 in equation (iii).
- 1/2x1 + 3/4 (7 -2x1 - 4x2) ≤ -3/4
-2x1 - 3x2 ≤ -6 ....(iv)

Gomory's constraint
-1/2x3 ≤ -1/2 ....(v)

Substituting the value of x3 in equation (v)
-1/2 (7 - 2x1 - 4x2) ≤ -1/2
x1 + 2x2 ≤ 3 ....(vi)

The inclusion of two cuts( -2x1 - 3x2 ≤ -6, x1 + 2x2 ≤ 3) give the new corner point A where x1 = 3, x2 = 0 and z = 3

Share and Recommend