We summarize the steps of the Dual Simplex Algorithm. Consider the linear progra

Question

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

Explanation / Answer

EXPLANATION

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

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

ar1X1 + ar2X2 + ar3X3 + ....... + arnXn = br, where X1, X2, Xn 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 ar1, ar2, ......, arn are positive. Thus, each of ar1X1, ar2X2, ar3X3, ....... ,arnXn are positive or rather non-negative, and hence (ar1X1 + ar2X2 + ar3X3 + ....... + arnXn) must be non-negative which obviously cannot be equal to a negative number. So, 'arj 0 for all j and br < 0' is not compatible. => there is no feasible solution.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.