Chapter 17: Chapter 17

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} $$

Short Answer

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 by step solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Recommended explanations on Math Textbooks

Select your language

Chapter 17: Chapter 17

Short Answer

Step by step solution

Unlock all solutions

Step 1: Write LPP in standard form

Step 2: Obtain the dual LPP

Step 3: Solve the dual LPP

Access millions of textbook solutions in one place

Most popular questions from this chapter

More chapters from the book ‘Linear Algebra’

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8

Chapter 9

Chapter 10

Chapter 11

Chapter 12

Chapter 13

Chapter 14

Chapter 15

Chapter 16

Chapter 18

Chapter 19

Chapter 20

Chapter 21

Chapter 22

Chapter 23

Chapter 24

Join over 22 million students in learning with our Vaia App

Recommended explanations on Math Textbooks

Mechanics Maths

Probability and Statistics

Calculus

Statistics

Geometry

Pure Maths