We summarize the steps of the Dual Simplex Algorithm Conside

We summarize the steps of the Dual Simplex Algorithm. Consider the linear programming problem of minimizing z = c middot X - z_0 subject to AX = b, X greaterthanorequalto 0 (with b not necessarily greaterthanorequalto 0). Assume that The system of constraints is in canonical form with a specified set of basic variables. The objective function z is expressed in terms of the nonbasic variables only, and the corresponding coefficients C_j are all nonnegative. If all b_i greaterthanorequalto 0, the minimum value of the objective function has been attained (Theorem 3.4.1 applies). If there exists an r such that b_r

Solution

EXPLANATION

Let us understand the condition \'if there exists an r such that arj 0 for all j and b_r < 0\'

We are looking at the rth constraint equation, which in expanded form would be

a_r1X₁ + a_r2X₂ + a_r3X₃ + ....... + a_rnX_n = b_r, where X₁, X₂, X_n are the variables whose value we are trying to determine. By the negativity condition, stated right at the top of the problem, X 0, and further, we are given under condition (2) that all a_r1, a_r2, ......, a_rn are positive. Thus, each of a_r1X_1, a_r2X_2, a_r3X_3, ....... ,a_rnX_n are positive or rather non-negative, and hence (a_r1X₁ + a_r2X₂ + a_r3X₃ + ....... + a_rnX_n) must be non-negative which obviously cannot be equal to a negative number. So, \'arj 0 for all j and b_r < 0\' is not compatible. => there is no feasible solution.