Open in App
Log In Start studying!

Select your language

Suggested languages for you:

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

Unlock all solutions

Get unlimited access to millions of textbook solutions with Vaia Premium

Over 22 million students worldwide already upgrade their learning with Vaia!

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.

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
  • Access our smart AI features to upgrade your learning
Get Vaia Premium now
Access millions of textbook solutions in one place

Most popular questions from this chapter

Chapter 17

A marketing manager wishes to maximize the number of people exposed to the company's advertising. He may choose television commercials, which reach 20 million people per commercial, or magazine advertising, which reaches 10 million people per advertisement. Magazine advertisements cost \(\$ 40,000\) each while a television advertisement costs \(\$ 75,000\). The manager has a budget of \(\$ 2,000,000\) and must buy at least 20 magazine advertisements. How many units of each type of advertising should be purchased?

Chapter 17

Show through the simplex method and then graphically that the following linear program has no solution. Maximize \(\quad 2 \mathrm{x}+\mathrm{y}\) subject to $$ \begin{aligned} &-x+y \leq 1 \\ &x-2 y \leq 2 \end{aligned} $$ \(\mathrm{x}, \mathrm{y} \geq 0 .\)

Chapter 17

Solve the following game $$ \begin{array}{|l|l|l|l|l|} \hline & \text { B: } & \mathrm{B}_{1} & \mathrm{~B}_{2} & \mathrm{~B}_{3} \\ \hline \mathrm{A} & & & & \\ \hline \mathrm{A}_{1} & & 1 & 2 & 3 \\ \hline \mathrm{A}_{2} & & 0 & 3 & -1 \\ \hline \mathrm{A}_{3} & & -1 & -2 & 4 \\ \hline \end{array} $$

Chapter 17

Two players, \(\mathrm{A}\) and \(\mathrm{B}\), each call out one of the numbers 1 and 2 simultaneously. If they both call 1 , no payment is made. If they both call 2, B pays \(A \$ 3.00\). If \(A\) calls 1 and \(B\) calls \(2, B\) pays $A \$ 1.00\(. If A calls 2 and \)B\( calls 1, A pays \)B\( \)\$ 1.00 .$ What is the payoff matrix for this game? Is the game fair to both players?

Chapter 17

A businessman needs 5 cabinets, 12 desks, and 18 shelves cleaned out. He has two part time employees Sue and Janet. Sue can clean one cabinet, three desks and three shelves in one day, while Janet can clean one cabinet, two desks and 6 shelves in one day. Sue is paid \(\$ 25\) a day, and Janet is paid \(\$ 22\) a day. In order to minimize the cost how many days should Sue and Janet be employed?

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
Join over 22 million students in learning with our Vaia App Join over 22 million students in learning with our Vaia App

Recommended explanations on Math Textbooks