Suggested languages for you:

Americas

Europe

Problem 397

# Find a solution to the following problem by solving its dual: Minimize $$\quad 9 \mathrm{x}_{1}+12 \mathrm{x}_{2}+15 \mathrm{x}_{3}$$ subject to \begin{aligned} &2 \mathrm{x}_{1}+2 \mathrm{x}_{2}+\mathrm{x}_{3} \geq 10 \\ &2 \mathrm{x}_{1}+3 \mathrm{x}_{2}+\mathrm{x}_{3} \geq 12 \\ &\mathrm{x}_{1}+\mathrm{x}_{2}+5 \mathrm{x}_{3} \geq 14 \\ &\mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 0, \mathrm{x}_{3} \geq 0 \end{aligned}

Expert verified
The dual of the given linear programming problem is: Maximize $$W=-10y_1 -12y_2 -14y_3$$ Subject to: $$-2y_1-2y_2-y_3 \geq -9$$ $$-2y_1-3y_2-y_3 \geq -12$$ $$-y_1-y_2-5y_3 \geq -15$$ $$y_1 \geq 0, y_2 \geq 0, y_3 \geq 0$$ Upon solving the dual problem, we can find the optimal solution for the original problem (i.e., $$x_1, x_2, x_3$$).
See the step by step solution

## Step 1: Write LPP in standard form

First, we need to rewrite the given problem in the standard form by multiplying inequality constraints with -1 to change them into the less-than constraints: Minimize $$Z=9x_1+12x_2+15x_3$$ Subject to: $$-2x_1-2x_2-x_3 \leq -10$$ $$-2x_1-3x_2-x_3 \leq -12$$ $$-x_1-x_2-5x_3 \leq -14$$ $$x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$$

## Step 2: Obtain the dual LPP

To obtain the dual LPP, we will follow the mentioned rules: - Interchange the roles of coefficients and right-hand side constants - Interchange the roles of constraints and objective function Denote $$y_1, y_2, y_3$$ as the dual variables. The dual LPP is: Maximize $$W=-10y_1 -12y_2 -14y_3$$ Subject to: $$-2y_1-2y_2-y_3 \geq -9$$ $$-2y_1-3y_2-y_3 \geq -12$$ $$-y_1-y_2-5y_3 \geq -15$$ $$y_1 \geq 0, y_2 \geq 0, y_3 \geq 0$$

## Step 3: Solve the dual LPP

Now we solve the dual LPP using any suitable linear programming method (e.g., Graphical Method, Simplex Method). It is generally easier to solve the dual than the original problem. Here, the objective function is of maximization type and constraints are still of the greater-than type. We will rewrite the dual LPP into its dual (i.e., back into the primal form). This would mean the objective function would be of minimization type and constraints will be less-than: Minimize $$W=-10y_1 -12y_2 -14y_3$$ Subject to: $$2y_1+2y_2+y_3 \leq 9$$ $$2y_1+3y_2+y_3 \leq 12$$ $$y_1+y_2+5y_3 \leq 15$$ $$y_1 \geq 0, y_2 \geq 0, y_3 \geq 0$$ Now, since the primal problem has a solution, by duality theorem, the dual also has a feasible solution set. Solve the above problem using any suitable linear programming method. After solving the dual LPP, we will get the solution for y-values (i.e., $$y_1, y_2, y_3$$). Finally, using the dual solution, we can find the solution to the original problem (i.e., $$x_1, x_2, x_3$$) by substituting the y-values into the constraints of the original problem.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features

## Join over 22 million students in learning with our Vaia App

The first learning app that truly has everything you need to ace your exams in one place.

• Flashcards & Quizzes
• AI Study Assistant
• Smart Note-Taking
• Mock-Exams
• Study Planner