Consider the following all-integer linear program.

Max	1x1	+	1x2
s.t.
	4x1	+	7x2	27
	1x1	+	6x2	18
	2x1	+	1x2	11
x1, x2 0 and integer

(a)

Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.

On the coordinate plane the horizontal axis is labeled x and the vertical axis is labeled x. A region bounded by a series of connected line segments and several points are on the graph.

• The line segments connect the approximate points (0, 5.5), (1, 5), (2.65, 2.12), and (3, 0).
• The region is above the horizontal axis, to the right of the vertical axis, and below the line segments.
• All ordered pairs with integer values in the region, on the series of connected line segments, but not on the horizontal nor vertical axes, are shown.

On the coordinate plane the horizontal axis is labeled x and the vertical axis is labeled x. A region bounded by a series of connected line segments and several points are on the graph.

• The line segments connect the approximate points (0, 3), (2.12, 2.65), (5, 1), and (5.5, 0).
• The region is above the horizontal axis, to the right of the vertical axis, and below the line segments.
• All ordered pairs with integer values in the region, on the series of connected line segments, but not on the horizontal nor vertical axes, are shown.

On the coordinate plane the horizontal axis is labeled x and the vertical axis is labeled x. A region bounded by a series of connected line segments and several points are on the graph.

• The line segments connect the approximate points (0, 3), (2.12, 2.65), (5, 1), and (5.5, 0).
• The region is above the horizontal axis, to the right of the vertical axis, and below the line segments.
• All ordered pairs with integer values in the region and on its boundaries are shown.

On the coordinate plane the horizontal axis is labeled x and the vertical axis is labeled x. A region bounded by a series of connected line segments and several points are on the graph.

• The line segments connect the approximate points (0, 5.5), (1, 5), (2.65, 2.12), and (3, 0).
• The region is above the horizontal axis, to the right of the vertical axis, and below the line segments.
• All ordered pairs with integer values in the region and on its boundaries are shown.

(b)

Solve the LP Relaxation of this problem.

at

(x₁, x₂) =

(c)

Find the optimal integer solution.

at

(x₁, x₂) =