Lesson Minimax linear problems to solve MENTALLY based on common sense

Minimax linear problems to solve MENTALLY based on common sense

Problem 1

The seed of potatoes ($20/acre) is cheaper than the seed of corn ($60/acre).

The profit per acre of potatoes ($150) is greater than the profit per acre of corn ($50). 


It makes it clear that the most aggressive strategy should be applied, which is 
to plant the potatoes as much as possible.


There are enough money to buy the potatoes seed for 70 acres: 70*20 = 1400 dollars.


So, the optimal strategy is to plant 70 acres of potatoes and do not plant the corn, at all.


ANSWER.  The farmer should plant 70 acres of potatoes  and do not plant the corn, at all.  
         The profit is 70*150 = 10500 dollars.

Problem 2

Seed for crop B is twice as expensive as seed for crop A, but gives the profit which is more than twice as big

as the profit of crop A (compare  270/120 = 2.25  with  40/20 = 2 !).


    +---------------------------------------------------------------+
    |   THEREFORE, it is clear, that the most aggressive strategy   |
    |   is to sow as much area with crop B as possible.             |
    +---------------------------------------------------------------+


The possible area to sow with crop B, within the budget, is  1400/40 = 35 acres.


So, the most profitable solution is to sow 35 acres with crop B and do not sow crop A, at all.


The expected profit is then  35*270 = 9450 dollars, and it is maximal possible profit at given conditions.

Problem 3

From the condition, it is clear that as many as possible production should be made at

the plant A, since it is more ecologically clean, and the rest can be (and should be) made

at the plane B.


ANSWER.  30 tons at plant A and the rest 20 tons at plant B.

Problem 4

The right strategy is the most aggressive strategy to maximize profit:



    It is to produce and cell as many as possible product units, what bring the maximum profit, and then

    add to it as many as possible less profitable units, to be and to remain in the frame of given restrictions.



Following this strategy, the company should produce 300 units of DELUXE and 400-300 = 100 units of TURBO.


It will have then the maximum profit of  300 * P6000 + 100 * P1000 = P 1,900,000.    ANSWER

Problem 5

Tala wants to earn maximum money.


For it, she should work at the greater hour salary as long as possible: as long as the restrictions do allow.


The restrictions allow her to work 20-6 = 14 hours at the rate of 10 JOD per hour.

The remaining 6 hours she wants to work at the rate of 8 JOD per hour.



It is the solution and the ANSWER to the problem:


    At given conditions, the maximum earning is  14*10 + 6*8 = 188 JOD.

    It is achieved at 14 hours working at 10 JOD per hour and 6 hours working at 8 JOD per hour.

Problem 6

As you read the problem, you see that each Jumbo biscuit requires more flour than 
each Regular biscuit, but provides lesser profit than Regular biscuit.


It means that the most aggressive strategy should work, when the company produces
Regular biscuits ONLY and does not produce Jumbo biscuits, at all.


It is so OBVIOUS, that I will not spend my and your time for explanations.


And since we just chose the strategy, we simply need to divide 600 oz by 1 to get
the number of possible Regular biscuits: it is 600/1 = 600.


But at this point, other restriction turns on: the number of biscuits can not 
be greater than 400.


    +---------------------------------------------------------------+
    |     Thus the optimal solution/answer is as follows:           |
    |                                                               |
    |  400 Regular biscuits should be produced; no Jumbo biscuits;  |
    |     optimal (maximum) profit is  400*0.12 = 48 dollars.       |
    +---------------------------------------------------------------+

Problem 7

The solution for maximum profit is OBVIOUS: apply the most aggressive strategy 
and make as many A-beds as possible under given restrictions, i.e. 50 A-beds (since they create the maximum profit)
and complement it by 30 B-beds, making them as many as possible, still remaining
under the given restrictions. 

    So, the answer in this case is (50 A and 30 B).

Problem 8

Sophia wants to minimize her spending, still satisfying all constraints.

Let's apply the most economic strategy.


Sophia should take as much cheep items (sodas) as possible (24 cans), 
and then complement it with an appropriate number of more expensive items (popcorn bags).

So, she needs 60-24 = 36 popcorn bags.


Her spending will be  $2*36 + $1*24 = $96,
and, obviously, it is the minimum spending.


Notice that this solution satisfies all the constraints.

Problem 9

We want maximize the number of apples and sandwiches (more precisely, the sum of them),
satisfying the other given constraints.


Let's apply the most aggressive strategy.


We will take as much apples as possible (30 apples), since they take only 1 unit of space, each.
Then we complement it with an appropriate number of sandwiches, which is  


     = 15  (the remaining space divided by 2).


So, the solution is 30 apples and 15 sandwiches, which gives the total of 30 + 15 = 45 items.


Notice that this solution satisfies all the constraints.

Problem 10

We want maximize the number of flowers in the garden (= maximize the sum of tulips and roses),
satisfying the imposed constraints.


Let's apply the most aggressive strategy.


Since the number of roses should be greater than or equal to the number of tulips,
we will take as much pairs (rose, tulip) as possible. Let the number of pairs be  p >= 0.

Each such pair requires 2+3 = 5 square feet of the garden area.

Then we will complement the pairs with separate roses. Let "r" be the numbers of separate roses.


Now the restriction regarding the area is

    5p + 3r <= 30  square feet.


The pairs will provide that the number of roses is not less than the number of tulips;
and each pair provides 2 flowers; so we are interested to maximize p and minimize  r >= 0.


Thus, in this inequality, we want to have integer r as small as possible, 
and due to this, to have p as great as possible.


Take r = 0.  Then  p = 30/5 = 6.


So, the optimal solution under given restriction is to plant 6 roses and 6 tulips.


Thus, the solution is 6 roses and 6 tulips, which gives the total of 6 + 6 = 12 flowers.


Notice that this solution satisfies all the constraints.

Problem 11

First, let's organize the given info into this TABLE. m-hours stands for machine-hours.


        one product                  one product 
        of wire roop #1              of wire roop #2

         3 machine                    3 machine
        19 coils of wires            14 coils of wires
         3 m-hours production         4 m-hours production       

        sold for PhP 64500 each      sold for PhP 10500 each

    Resources: 2006 coils of wires
          and   315 machine-hours.


Let six machines be A, B, C, D, E and F. So, we have two triples of machines ABC and DEF.
The rate of making money is

    three machines making product #1:   = 1131.579 of PhP per coil per hour.

    three machines making product #2:   =  187.5   of PhP per coil per hour.

It makes it clear that the most aggressive strategy is THIS


   +-------------------------------------------------------------------------------------------+
   |  3 machine (A,B,C) work as long as possible and produce as many wire roop #1 as possible. |
   |    (To produce one product #1, they consume 19 coils and 3 m-hours).                      |
   |                                                                                           |
   |  3 machine (D,E,F) work as long as possible and produce as many wire roop #1 as possible. |
   |    (To produce one product #1, they consume 19 coils and 3 m-hours).                      |
   +-------------------------------------------------------------------------------------------+


    Thus, doing this way, 6 machines produce 2 products #1 and consume 19+19 = 38 coils and 3+3 = 6 m-hours.

    Which resource will run out first - machine-hours or coils ?

          coils:   2006/38 = 52 + 30/38     ( <<<---===  division with the remainder )

          m-hours:  315/6  = 52 1/2         ( <<<---===  division with the remainder )

    Thus, coils of wires will run out first.


      +--------------------------------------------------------------------------------+
      |   Let's call this cycle "consuming 3+3 = 6 m-hours, 6 machines produce         |
      |                          2 products #1 and consume 19+19 = 38 coils of wires"  |
      |   as "one basic cycle".                                                        |
      +--------------------------------------------------------------------------------+


    Thus we found out that the "basic cycle" can be repeated (cycled) 52 times.


    After that, the remaining resources are 30 coils of wires and 315 - 6*52 = 315 - 312 = 3 m-hours.


    With these remaining resources, we can (and we will) run only 3 machines ABC to produce one #1 product.
    

    They will spend 19 coils of wire and 3 m-hours.


    The remaining resource is 30-19 = 11 coils, and the time is just used ion full.
    


    The final conclusion and the ANSWER is that we run two triples of the machines 

    only to produce 2*52 + 1 = 105 of products #1; we do not make product #2, at all.

    The earning of this strategy is  105*64500 = 6772500 dollars.

    The remaining unused resource is 2006 - 19*105 = 11 coils of wires; the time is used in full.

Problem 12

To present information in compact form, I prepared this table 


      T       A         B         L          E


             Texas    Lone    Lariat    To purchase
  
    felt       3      3.80      4          470

    cowboy     4      3.50      3.60       370

    maximum   370     463       185



Now imagine that you are aggressive buyer/seller, who wants to get maximum profit.


You look at the table, and you see that among felt hats, you will get maximum profit of $4/hat from Lariat.
So you take as many felt hats as possible from Lariat: 185.

    After that, you still need 470-185 = 285 felt hats.


You look at the Table again, and you see that next the most profitable felt hat is from Lone at $3.80 -
so you buy these 285 felt hats from Lone: the Lone's restriction of 463 hats allows you to do it.


    At this point, you completed with felt hats and provided a profit of 185*4 + 285*3.80 = 1823 dollars.

    Next, we will work/analyze/buy cowboy hats.



You look at the table again, and you see that among cowboy hats, you will get maximum profit of $4/hat from Texas.
So you take as many cowboy hats as possible from Texas: 370.

    After that, you just completed with the cowboy hats and provided your profit of 370*4 = 1480 dollars.


RESUME: you buy 185 felt hats from Lariat and 285 felt hats from Lone;

        you buy 370 cowboy hats from Texas.

        Doing this way, you provide total profit of 1823 + 1480 = 3303 dollars, and it is maximum possible 
            (OPTIMUM) profit under imposed conditions.

Problem 13

The feasible domain for this problem is a quadrilateral in QI
    under straight line  4x +  y = 16      (1)
and under straight line   x + 2y =  9.     (2)


It has vertices A = (0,0), 

                B = (0,4.5)       ( y-intercept of line (2) )

                C = (,)    ( intersection of lines (1) and (2) )

                D = (4,0)         ( x-intercept of line (1) )


Next, the objective function increases as x increases and decreases as y increases.


     +------------------------------------------------------+
     |  THEREFORE, the objective function has the maximum   |
     |         in the feasibility quadrilateral             |
     |     when x is the maximum and y is the minimum.      |
     +------------------------------------------------------+


This point is, OBVIOUSLY, point D, where  (x,y) = (4,0)  and  P(x,y) = 3x-y = 3*12 - 0 = 12.


ANSWER.  The maximum point is (4,0) with the objective function value of 12.

Problem 14

                    To Pulsar Factories
                      City A  City B
From TMA Location  I    $5     $5
From TMA Location II    $8     $8

Since the shipping cost per unit from Location  I to A and to B is the same $5,  and 

since the shipping cost per unit from Location II to A and to B is the same $8,



it MEANS that the most reasonable strategy is 

    (1)  to ship as many TVs as possible from Location I (5800)
         for cheaper shipping price to cities A and B,

    (2)  and then to ship the rest of TVs from Location II (2900 + 4000 - 5800 = 6900 - 5800 = 1100)
         for more expensive shipping price to cities A and B.



How these quantities 5800 from Location I  and 1100 from Location II will be distributed 
between the cities A and B, does not matter for the total shipping cost.


Such strategy provides the minimum total shipping cost.

Problem 15

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.

Problem 16

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.


So, 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 17

To find the maximum number of ad exposures, let's formulate the problem in terms 
of objective function and constraints.  


Let x be the number of newspaper ads and y be the number of radio ads. 


The objective function is 

    P = 5700*x + 6700*y.       (1)

It is the number of possible expositions, and we want to maximize it.


The constraints are: 

    190*x + 590*y ≤ 14830 (the budget),     (2)

    x ≤ 24 (newspaper ad limit), y ≤ 32 (radio ad limit),     (3)

    x ≥ 0, y ≥ 0 (non-negativity).     (4)


Now it is presented as a typical Linear Programming problem. But it can be easily solved MENTALLY
using "the most aggressive" logical strategy/methodology.


From expression (1) for the objective function, we see that the contribution of each single newspaper ad
(in terms of the number of potential expositions, 5700) is comparable with (or distinct insignificantly from) 
the contribution of each single radio ad (6700).


But each newspaper ad is much cheaper ($190) than each radio ad ($590). So, it is clear that 
the most profitable strategy is  to make as many newspaper ads as possible (x=24), and then
to spend the rest of the budget for the radio ads. 


Thus the most effective solution is to make 24 newspaper ads, spending 24*190 = 4560 dollars for it.

The rest of the budget is then  $14830 - $4560 = #10270.

This amount can be / (should be) spent for radio ads.

It provides the number of radio ads  y =  = 17.40678,
and we should round this decimal number to the closest lesser integer number, which is y = 17.


So, the answer to the problem's question is THIS:

    24 newspaper ads and 17 radio ads provide the greatest possible number of expositions (~ potential customers),
    which is then  5700*24 + 6700*17 = 250700.

Post-solution note

Problem 18

Indeed, after reading the post, it should be clear that the winning strategy 
is the most aggressive strategy making SO MANY small boxes as possible,
until the restrictions allow do it; and when the restriction on small boxes
is reached, then to switch making large boxes, until the restrictions on 
large boxes is reached.


It is so, because the profit of each small box is greater than the profit of each
large box (R42 against R14), while each small box requires less amount of 
material than each large box (0.8 sq. m against 1.4 sq. m).


So, it is OBVIOUS that to produce small boxes is more profitable.


The other restrictions (total wood and total working time) do not give a preference to any 
sort of production, and the limitation on the numbers of small boxes and large boxes (like
the warehouse space limitation and the demand) are in favor of small boxes.


So, following to this idea, as many of small boxes should be produced, making 30 small boxes.
(limited by the demand). 

It will require 0.8*30 = 24 sq.m of wood, leaving 42-24 = 18 sq.m of wood for large boxes
and will require 0.5*30 = 15 hours of labor, leaving 24-15 = 9 hours for large boxes.


Now we determine the number of large boxes.  The limitations are

    18/1.4 = 12.86 for wood;

    9/0.5 = 19 from labor hours;
  
    20 from the warehouse space limitations.


So, for large boxes the number is 12.


The maximum profit is 30*42 + 12*14 = 1428 monetary units.


ANSWER.  The optimal strategy is to make 30 small boxes and 12 large boxes,

         making the maximum possible profit of R1428.