Given the Following All-Integer Linear Program

question 16

Essay

Given the following all-integer linear program:
MAX 3x₁ + 2x₂
s.t.3x₁ + x₂ < 9
x₁ + 3x₂ < 7
-x₁ + x₂ < 1
x₁,x₂ > 0 and integer
a Solve the problem as a linear program ignoring the integer constraints.Show that the optimal solution to the linear program gives fractional values for both x₁ and x₂.
b.What is the solution obtained by rounding fractions greater than of equal to 1/2 to the next larger number? Show that this solution is not a feasible solution.
c.What is the solution obtained by rounding down all fractions? Is it feasible?
d.Enumerate all points in the linear programming feasible region in which both x₁ and x₂ are integers,and show that the feasible solution obtained in (c)is not optimal and that in fact the optimal integer is not obtained by any form of rounding.

---

Definitions:

Scripting Language

A programming language used to automate the execution of tasks that could alternatively be executed one-by-one by a human operator.

Floating-Point

A method of representing real numbers in a way that can accommodate a wide range of values by using a fraction, an exponent, and a base, typically used in computing to process complex calculations.

Integer

A whole number, including zero and negative numbers.

Perspective

A particular attitude towards or way of regarding something; a point of view, often influencing how situations are perceived.