Perform the Fourier-Motzkin elimination to find a feasible region and optimum solution

Question

Consider the following linear programming problem:

min 50x1 + 80x2

subj 2x1 + 8x2 ≤ 5

6x1 + 5x2 ≤ 10

x1 ≥ 0

x2 ≥ 0

(a) Is this problem feasible? (Hint: Use the Fourier-Motzkin elimination to check if the polyhedron defined by the constraints is nonempty).

(b) Convert the problem into standard form and then Identify a basic solution for this problem by considering A1, A2 as your basic columns. (Hint form the Basis matrix B and then solve BxB = b in terms of xB). Check to see if the solution you found is a basic feasible solution?

(c) Find the optimum cost of this linear programming problem using the Fourier-Motzkin elimination.

Answer 1

min 50x1+80x2

subject to

quadrant 1

2x1+8x2 </= 5

6x1+5x2</=10

graph them

it's a linear programming problem

test the corners of the polygon, quadrilateral, if any

for minimum you want the lower left corner (0,0)

smallest objective function is 0

solution is feasible, it's zero

max is 2650/19= 139.4736842, if that's what you really wanted, mixing up min with max