Discussion
Consider the following linear programming problem :
Maximize \(z = 5x_{1} + 2x_{2} + 3x_{3} - x_{4} + x_{5}\)
Subject to : \(x_{1} + 2x_{2} + 2x_{3} + x_{4} = 8\)
\(3x_{1} + 4x_{2} + x_{3} + x_{5} = 7\)
\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \ge 0\)
What will be the basic feasible solution after iteration 1 ?
Answer: A
After the first iteration the solution is \(x_{3} = 4\), \(x_{5} = 3\), the rest 0, with \(z = 15\).
\(x_{4}\) and \(x_{5}\) each appear in only one constraint with coefficient 1, so they form the starting basis: \(x_{4} = 8\), \(x_{5} = 7\), \(z = -8 + 7 = -1\). With basic costs \((-1, 1)\), the values \(z_{j} - c_{j}\) are:
\[ \begin{aligned} x_{1} &: (-1 + 3) - 5 = -3 \\ x_{2} &: (-2 + 4) - 2 = 0 \\ x_{3} &: (-2 + 1) - 3 = -4 \end{aligned} \]
The most negative is \(x_{3}\), so it enters. Ratios are \(8/2 = 4\) and \(7/1 = 7\), so \(x_{4}\) leaves and \(x_{3} = 4\). Then \(x_{5} = 7 - 4 = 3\), and
\[ z = 3(4) + 3 = 15 \]
The solution with \(x_{1} = 1, x_{2} = 2, x_{3} = 1\) is not a basic solution (three non-zero variables with two constraints), and the problem is feasible, as the starting basis shows.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development