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

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

Problem 1

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 ANSWER 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. |
    +-----------------------------------------------------------------------+

Problem 2

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.    ANSWER