Solve the problem-using the lexicographic tie-breaking

Question

Q1. Consider the linear programming problem minimize

 z = c^Tx

subject to Ax = b

x ≥ 0.

Let a1, . . . , am be the artificial variables, and suppose that at the end of phase 1 a basic feasible solution to the problem has been found (no artificial variables are in the basis). Prove that, in the final phase-1 basis, the reduced costs are zero for the original variables x1, . . . , xn and are one for the artificial variables.

Q2. The following is the final basic solution for phase 1 in a linear programming problem, where a1 and a2 are the artificial variables for the two constraints:

basic	x1	x2	x3	x4	x5	a1	a2	rhs
-z'	0	a	0	0	b	c	1	d
	-2	0	4	1	0	0	-2	1
	e	f	g	0	h	i	1	J

Find conditions on the parameters a, b, c, d, e, f, g, h, i, and j such that the following statements are true. You need not mention those parameters that can take on arbitrary positive or negative values. You should attempt to find the most general conditions possible.

(i) A basic feasible solution to the original problem has been found.

(ii) The problem is infeasible.

(iii) The problem is feasible but some artificial variables are still in the basis. However, by performing update operations a basic feasible solution to the original problem can be found.

(iv) The problem is feasible but it has a redundant constraint.

(v) For the case a = 4, b = 1, c = 0, d = 0, e = 0, f = -4, g = 0, h = -1, i = 1, and j = 0, determine whether the system is feasible. If so, find an initial basic solution for phase 2. Assume that the objective is to minimize z = x₁ + x₄.

[Note: The value of 1 in row 2, col. 7 (i.e., the col. for a2 ) of the constraints in the final tableau for Phase I. That value should be 0, not 1].

Q3. Solve the problem

minimize  z = -4x₁ - 2x₂ - 8x₃

subject to 2x₁ - x₂ + 3x₃ ≤ 30

                   x₁ + 2x₂ + 4x₃ = 40                                         

                  x₁, x₂, x₃ ≥ 0,                    

Using the lexicographic tie-breaking procedure

Q4.  Solve the problem

minimize  z = 5x₁ + 3x₂ _ 2x₃

subject to 4x₁ + 5x₂ + 2x₃ + x₄ ≤ 20

                   3x₁ + 4x₂ - x₃ + x₄ ≤ 30

                  x₁, x₂, x₃, x₄ ≥ 0,                              

Using revised simplex method.