Lesson Solving some linear minimax problems in 3D space
Algebra
->
Customizable Word Problem Solvers
->
Misc
-> Lesson Solving some linear minimax problems in 3D space
Log On
Ad:
Over 600 Algebra Word Problems at edhelper.com
Word Problems: Miscellaneous Word Problems
Word
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Solving some linear minimax problems in 3D space'
This Lesson (Solving some linear minimax problems in 3D space)
was created by by
ikleyn(52780)
:
View Source
,
Show
About ikleyn
:
<H2>Solving some linear minimax problems in 3D space</H2> <H3>Problem 1</H3>Minimize C = 2x + 3y + 4z subject to restrictions <pre> 4x + 2y + z = 10 x + y - z = 5 x >= 0, y >= 0, z >= 0. </pre> <U>Solution</U> <pre> The idea of the solution is <U>THIS</U> : 1) Two restrictions are equations of planes in 3D space. These planes are not parallel -- hence, they have non-empty intersection. Their intersection is a straight line, and the first step is to present this straight line in a <U>parametric form</U> x = f(z), y = g(z) of the coordinate z. 2) Having it, we can present the objective function C = 2x + 3y + 4z as a linear function of only one single variable z C = C(x,y,z) = C(z) = 2*f(z) + 3*g(z) + z. Then it should be easy to find the minimum of the function C(z). </pre> Below is the implementation of this idea. <pre> To express x as a function of z, write the given restrictions in the form 4x + 2y = 10 - z (1) x + y = 5 + z (2) Eliminate "y". For it, multiply eq(2) by 2 (both sides). Keep eq(1) as is. You will get 4x + 2y = 10 - z (3) 2x + 2y = 10 + 2z (4) Subtract eq(4) from eq(3). You will get 2x = = -3z, or x = -1.5z. Thus I got "x" as this function of z : x = f(z) = -1.5z. (5) To express y as a function of z, use the restrictions in the form (1), (2) again. Eliminate "x". For it, multiply eq(2) by 4 (both sides). Keep eq(1) as is. You will get 4x + 2y = 10 - z (6) 4x + 4y = 20 + 4z (7) Subtract eq(6) from eq(7). You will get 2y = = 10 + 5z, or y = 2.5z + 5. Thus I got "y" as this function of z : y = g(z) = 2.5z + 5. (8) Now the objective function C = 2x + 3y + 4z on the straigh line (5), (8) becomes C = 2*(-1.5z) + 3*(2.5z + 5) + 4z = -3z + 7.5z + 15 + 4z = 8.5z + 15. In the first octant, this function INCREAZES as z increases; so, it it OBVIOUS that the objective function on the straight line gets the minimum at z= 0, and this minimum iz equal to 8.5*0 + 15 = 15. As the last step, we can determine the x- and y- coordinates of the minimal point. They are x = -1.5*0 = 0 and y = 2.5*0 + 5 = 5. <U>ANSWER</U>. Under given restrictions, the objective function gets it minimum at the point (x,y,z) = (0,5,0), and the minimum value is 15. </pre> <H3>Problem 2</H3>One gram of soybean meal provides at least 2.5 units of vitamins and 5 calories. One gram of meat byproducts provides at least 4.5 units of vitamins and 3 calories. One gram of grain provides at least 5 units of vitamins and 10 calories. If a gram of soybean meal costs 6 cents, a gram of meat byproducts 7 cents, and a gram of grain 9 cents, what mixture of these three ingredients will provide at least 48 units of vitamins and 54 calories per serving at minimum cost? What will be the minimum​ cost? <B>Solution</B> <pre> Let X = the mass of soybean meal consumed (in grams); Y = the mass of meat; Z = the mass of grain. The objective function to minimize is the cost C(X,Y,Z) = 6*X + 7*Y + 9*Z cents. (1) The constraints are 2.5*X + 4.5*Y + 5*Z >= 48 units of vitamins, (2) 5*X + 3*Y + 10*Z >= 54 calories. (3) Other constraints are X >= 0; Y>= 0, and Z >= 0. (4) Now, a remarkable fact is that the solution to this minimax problem can be obtained ANALYTICALLY. Constraints (2) and (3) represent two planes in 3D: 2.5*X + 4.5*Y + 5*Z = 48 (5) 5*X + 3*Y + 10*Z = 54 (6) These planes are not parallel -- hence, their intersection is a straight line. The idea is to present this straight line in a parametric form - then the solution of the minimax problem on this straight line will be easy. Multiply equation (5) by 2 (both sides) and then subtract equation (6) from the obtained equation. You will get 3Y - 9Y = 54 - 2*48, or -6Y = -42. Hence, Y = 7. (7) Thus we found that the intersection of two planes (5) and (6) is a straight line, which lies on the plane Y = 7. Subctitute Y =7 into equations (5) and (6). You will get then 2.5*X + 4.5*7 + 5Z = 48 (5') 5*X + 3*7 + 10Z = 54, (6') or, collecting all constant terms on the right side 2.5*X + 5Z = 16.5, (5'') 5*X + 10*Z = 33, (6'') Equations (5'') and (6'') are DEPENDENT (which is OBVIOUS). Hence, two equations (5'') and (6'') represent THE SAME plane. So, our straight line is the intersection of planes (7) and (6''). Now, from equation (6''), X = 6.6 - 2Z. Thus our stright line in parametric form is X = 6.6 - 2Z, Y = 7. (8) Substitute (8) into the objective function (1). You will get C(X,Y,Z) = 6*X + 7*Y + 9*Z = 6*(6.6 - 2Z) + 7*7 + 9*Z = 39.6 - 12Z + 49 + 9Z = -3Z + 88.6. (9) Thus, on our line the objective function is presented as the linear function (9) of Z. We see that when Z increases from 0 to positive values, the function (9) decreases. But Z can increase only till X = 6.6 - 2Z is >= 0 (is non-negative). Hence, the linear function (9) has the minimum at Z = 6.6/2 = 3.3. Then X = 6.6 - 2*3.3 = 0, according to (8). Thus we just obtained the solution to our minimax problem: The minimum solution point is X= 0; Y= 7 and Z= 3.3 and the mimimum cost is -3*Z + 88.6 = -3*3.3 + 88.6 = 78.7. <U>ANSWER</U>. The minimum cost is 78.70 cents and it is achieved at this diet: 0 gram of soybean meal; 7 gram of meat, and 3.3 gram of grain. </pre> My other additional lessons on Miscellaneous word problems in this site are - <A HREF=https://www.algebra.com/algebra/homework/word/misc/I-do-not-have-enough-savings-now.lesson>I do not have enough savings now</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/In-a-jar-all-but-6-are-red-marbles.lesson>In a jar, all but 6 are red marbles</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/How-many-boys-and-how-many-girls-are-there-in-a-family.lesson>How many boys and how many girls are there in a family ?</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/What-is--the-last-digit-of-the-number-a%5En-.lesson>What is the last digit of the number a^n ?</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Find-the-last-three-digits-of-these-numbers-.lesson>Find the last three digits of these numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/What-are-the-two-last-digits-of-the-number-3%5E123%2B7%5E123%2B9%5E123.lesson>What are the last two digits of the number 3^123 + 7^123 + 9^123 ?</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Really-complicated-logic-problem.lesson>Advanced logical problems</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Prove-that-if-a-b-and-c-are-the-sides-of-a-triangle-.lesson>Prove that if a, b, and c are the sides of a triangle, then so are sqrt(a), sqrt(b) and sqrt(c)</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Calculus-optimization-problems-for-shapes-in-2D-plane.lesson>Calculus optimization problems for shapes in 2D plane</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Calculus-optimization-problems.lesson>Calculus optimization problems for 3D shapes</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Solving-one-non-linear-minimax-problem-in-3D-space.lesson>Solving one non-linear minimax problems in 3D space</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Solving-linear-minimax-problem-in-three-unknowns-by-the-simplex-method.lesson>Solving linear minimax problem in three unknowns by the simplex method</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/The-pigeonhole-principle-problems.lesson>The "pigeonhole principle" problems</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/In-the-worst-case.lesson>In the worst case</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Page-numbers-on-the-left-and-right-facing-pages-of-an-opened-book.lesson>Page numbers on the left and right facing pages of an opened book</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Selected-problems-on-counting-elements-in-subsets-of-a-given-finite-set.lesson>Selected problems on counting elements in subsets of a given finite set</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/How-many-numbers-from-1-to-300-are-divisible-by-X.lesson>How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ?</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Nice-problems-to-setup-them-using-Venn-diagram.lesson>Nice problems to setup them using Venn diagram</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Wrapping-a-gift.lesson>Wrapping a gift</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/In-preparation-for-Halloween-.lesson>In preparation for Halloween</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Nice-entertaiment-problems-related-to-divisibility-numbers.lesson>Nice entertainment problems related to divisibility property</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Stars-and-bars-method-for-Combinatorics-problems.lesson>Stars and bars method for Combinatorics problems</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Olimpiad-level-Math-problem-on-caves-and-bats.lesson>Math Olympiad level problem on caves and bats</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Math-Olympiad-level-problem-on-caught-fishes.lesson>Math Olympiad level problem on caught fishes</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Math-Olympiad-level-problem-on-pigeonhole-principle.lesson>Math Olympiad level problem on pigeonhole principle</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/Math-Olympiad-level-problem-on-placing-books-in-bookcase.lesson>Math Olympiad level problem on placing books in bookcase</A> - <A HREF=https://www.algebra.com/algebra/homework/word/misc/OVERVIEW-of-additional-lessons-on-Miscellaneous-word-problems.lesson>OVERVIEW of additional lessons on Miscellaneous word problems</A> Use this file/link <A HREF=https://www.algebra.com/algebra/homework/quadratic/lessons/ALGEBRA-I-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-I - YOUR ONLINE TEXTBOOK</A> to navigate over all topics and lessons of the online textbook ALGEBRA-I. Use this file/link <A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A> to navigate over all topics and lessons of the online textbook ALGEBRA-II.
