Lesson Solving linear optimization problems without LP-method by reduction to linear function

Source code of 'Solving linear optimization problems without LP-method by reduction to linear function'

This Lesson (Solving linear optimization problems without LP-method by reduction to linear function) was created by by ikleyn(52778)

: View Source, Show
About ikleyn:

<H2>Solving linear optimization problems without LP-method by reduction to linear function</H2>

<H3>Problem 1</H3>An oil refinery refines types &nbsp;A &nbsp;and &nbsp;B &nbsp;of crude oil and can refine as much as &nbsp;4000 &nbsp;barrels each week. 
Type &nbsp;A &nbsp;crude oil has &nbsp;2 kg of impurities per barrel, &nbsp;type &nbsp;B &nbsp;has &nbsp;3 kg of impurities per barrel,
and the refinery can handle no more than &nbsp;9000 kg of these impurities each week. 
How much of each type should be refined in order to maximize profits, &nbsp;if the profit is 
R25/barrel for type &nbsp;A &nbsp;and &nbsp;R30/barrel for type &nbsp;B?

<B>Solution</B>

<pre>
Let x be the amount of the oil type A to refine (in barrels).

Then the amount of oil type B to refine is  4000-x  barrels.

We want to maximize profit

P(x) = 25x + 30*(4000-x) = 25x + 120000 - 35x = 120000 - 5x.    (1)

under this restriction

2x + 3*(4000-x) =<= 9000,   or  2x + 12000 - 3x <= 9000,  or  x >= 3000.   (2)

+------------------------------------------------------+
    |   According to (1), we want to subtract from 120000  |
    |         the minimal possible value of 5x.            |
    |                                                      |
    |     According to (2), x must be at least 3000.       |
    +------------------------------------------------------+

So, it is logical to take for x the minimal possible value, which is 3000.

Thus, the <U>ANSWER</U> to the problem is  this:

+-----------------------------------------------------------------------+
    |   Under given restrictions, the optimal solution is                   |
    |                                                                       |
    |       x = 3000 barrels for oil type A                                 |
    |           and  4000-x = 4000-3000 = 1000 barrels of oil type B.       |
    |                                                                       |
    |   The profit is then  P = 25*3000 + 30*1000 = 75000 + 30000 = 105000. |
    +-----------------------------------------------------------------------+
</pre>

<H3>Problem 2</H3>The dean of Faculty of Management and Information Technology must plan the faculty’s course 
offerings for the first semester, &nbsp;2020/2021. &nbsp;Student demands make it necessary to offer 
at least &nbsp;30 &nbsp;undergraduate and &nbsp;20 &nbsp;graduate courses in the term. &nbsp;Faculty contracts 
also dictate that at least &nbsp;60 &nbsp;courses be offered in total. &nbsp;Each undergraduate course 
taught course the faculty an average of &nbsp;RM2,500 &nbsp;in faculty wages, &nbsp;and each graduate course 
costs &nbsp;RM3,000. &nbsp;Find the number of undergraduate and graduate courses should be taught 
in the first semester so that the total faculty salaries are kept to a minimum.

<B>Solution</B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Surely, this problem can be solved using Linear Programming method.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;But it also can be solved, &nbsp;using logical reasoning and common sense,

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;practically mentally, &nbsp;in your mind.

<pre>
Let U be the number of undergraduate courses, and G be the number of graduate courses.

First, notice that if the conditions "at least 30 U and at least 20 G" are satisfied
and we have MORE than 60 courses, than the total number of courses can be diminished
by 1 such way that we still will be in the feasible domain.

Indeed, if U >= 30 and G >= 20, and U + G > 60, it means that at least one number U or G
is greater than their corresponding lower boundaries, so this course can be eliminated.

Repeating this reasoning as many times as required, we will get the condition

U >= 30, G >= 20, U + G = 60

so the total number of courses is precisely 60. Eliminating excessive courses, we diminish
the total cost, so it is good, from the problem's point of view.

Now, if the number of undergraduate courses is U, then the number of undergraduate courses is U = 60-G.

The total cost is then  2500*U + 3000*G = 2500*(60 - G) + 3000*G = 150000 + 500*G,

and we want to make it as small as it is possible under restrictions.

From the last formula, it is clear that the total cost is minimum when the number of graduate 
courses G is at its lower bound G = 20.

Thus the optimal solution is G = 20 graduate courses and U = 60-20 = 40 undergraduate courses,
giving the minimum possible cost  40*2500 + 20*3000 = 100000 + 60000 = RM160,000.    <U>ANSWER</U>
</pre>

So, &nbsp;if the dean of Faculty of &nbsp;Management and &nbsp;Information &nbsp;Technology has a knack for logic,
he can solve this problem &nbsp;MENTALLY, &nbsp;without using the &nbsp;LP-method.

The idea is to assign as few of expensive courses as possible under restrictions,
and then to add as many of cheaper courses to get other restrictions.

My other additional lessons on &nbsp;Miscellaneous word problems &nbsp;(section 3) &nbsp;in this site are

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/More-complicated-problems-on-finding-number-of-elements-in-finite-subsets.lesson>More complicated problems on finding number of elements in finite subsets</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/Solving-problems-by-the-Backward-method.lesson>Solving problems by the Backward method</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/Minimax-problems-that-to-be-solved-MENTALLY-based-on-common-sense.lesson>Minimax linear problems to solve MENTALLY based on common sense</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/Solving-one-special-linear-minimax-problem-in-100-D-space.lesson>Solving one special linear minimax problem in 100-D space by the Linear Programming method</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/Miscellaneous-logical-problems.lesson>Miscellaneous logical problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/Upper-class-entertainment-Math-problems-for-all-ages.lesson>Upper class entertainment Math problems for all ages</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF=https://www.algebra.com/algebra/homework/word/misc/OVERVIEW-of-my-additional-lessons-on-Miscellaneous-word-problems-section-3.lesson>OVERVIEW of my additional lessons on Miscellaneous word problems, section 3</A>

Use this file/link &nbsp;<A HREF=https://www.algebra.com/algebra/homework/quadratic/lessons/ALGEBRA-I-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-I - YOUR ONLINE TEXTBOOK</A>&nbsp; to navigate over all topics and lessons of the online textbook &nbsp;ALGEBRA-I.

Use this file/link &nbsp;<A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A>&nbsp; to navigate over all topics and lessons of the online textbook &nbsp;ALGEBRA-II.