# Linear Programming - Help please!

• May 15th 2006, 04:23 AM
LilDragonfly
An orchadist has 10 hectares of land available for growing Fuji apples and Nashi pears. She estimates that each hectare of apples will cost $5000 to establish, and each hectare of pears will cost$20 000 to establish. She is not able to spend more than $100 000 on establishing the orchard. It is also estimated that the profit per hectare from apples will be$4000 and the profit per hectare from pears will be $8000. What is the maximum profit the orchardist can expect? How many hectares of Fuji apples and Nashi pears should she plant to achieve this? Please show your working clearly, with an explanation for the reason behind the answer you give. Thank you for your help. • May 15th 2006, 05:58 AM ticbol Quote: Originally Posted by LilDragonfly An orchadist has 10 hectares of land available for growing Fuji apples and Nashi pears. She estimates that each hectare of apples will cost$5000 to establish, and each hectare of pears will cost $20 000 to establish. She is not able to spend more than$100 000 on establishing the orchard.

It is also estimated that the profit per hectare from apples will be $4000 and the profit per hectare from pears will be$8000. What is the maximum profit the orchardist can expect? How many hectares of Fuji apples and Nashi pears should she plant to achieve this? Please show your working clearly, with an explanation for the reason behind the answer you give.

There are two decision variables:
hectares of apples, A
hectares of pears, P

The constraints are:
A +P <= 10 ----------------------(1)

5000A +20,000P <= 100,000
Divide both sides by 5000,
A +4P <= 20 ----------------------(2)

Non-negative, non-zero constraints:
A > 0 ------------------------------(3)
P > 0 ---------------------------(4)

The objective function is
Profit = 4000A +8000P -----------***

Now, plot the inequalities (1), (2), (3) and (4) on the same (A,P) cartesian or rectangular coordinate axes.
Get the intersection points of the 4 inequalities. Since A or P cannot be zero, then the intersection of (1) and (2) , being the only intersection point left, should determine the optimum (maximum here) profit.

The intersection of (1) and (2):
Consider them as equations only.
(2) minus (1),
3P = 10
So, P = 10/3
And, using (1), A = 10 -P = 10 -(10/3) = 20/3
Therefore, the intersection of (1) and (2), and at the same time the only effective corner of the feasible/solution region, is (20/3, 10/3).
Plugging that into the objective function,
Profit = 4000A +8000P
Maximum profit = 4000(20/3) +8000(10/3) = 160,000/3 = \$53,333.33 ----------answer.
To achieve that, the orchardist should plant (6 and 2/3) hectares of apples and (3 and 1/3) hectares of pears. ------------------answer.
• May 15th 2006, 06:14 AM
CaptainBlack
Quote:

Originally Posted by ticbol
Non-negative, non-zero constraints:
A > 0 ------------------------------(3)
P > 0 ---------------------------(4)

Non-negativity constraints are (there is no stipulation that they are non-zero
as far as I can see):

$
A \ge 0$
,
$
P \ge 0$

Quote:

Get the intersection points of the 4 inequalities. Since A or P cannot be zero, then the intersection of (1) and (2) , being the only intersection point left, should determine the optimum (maximum here) profit.
We will need to consider the casses where $A$ and/or $P$ are zero, unless
you determine that these cannot correspond to the optimum by other means.

(this will not change the answer as the point you give is in fact the minimum
as we know :) )

RonL
• May 15th 2006, 12:23 PM
ticbol
Quote:

Originally Posted by CaptainBlack
Non-negativity constraints are (there is no stipulation that they are non-zero
as far as I can see):

$
A \ge 0$
,
$
P \ge 0$

We will need to consider the casses where $A$ and/or $P$ are zero, unless
you determine that these cannot correspond to the optimum by other means.

(this will not change the answer as the point you give is in fact the minimum
as we know :) )

RonL

The question says Apples and Pears are to be raised, not Apples or Pears, or not Apples and/or Pears. That was or is very easy to understand. :)
So, A or P cannot be zero.
• May 15th 2006, 01:45 PM
CaptainBlack
Quote:

Originally Posted by ticbol
The question says Apples and Pears are to be raised, not Apples or Pears, or not Apples and/or Pears. That was or is very easy to understand. :)
So, A or P cannot be zero.

No it actually says "An orchadist has 10 hectares of land available for
growing Fuji apples and Nashi pears"

Which if you wish to interpret it as both apples and pears must be grown
you are welcome. We can overlook the fact that this is an exercise in
linear programming, which usually requires the feasible region to be closed
(among other things) to guarantee that a solution exists.

RonL
• May 15th 2006, 02:36 PM
ThePerfectHacker
Maybe this will help,
• May 15th 2006, 02:45 PM
ticbol
Quote:

Originally Posted by CaptainBlack
No it actually says "An orchadist has 10 hectares of land available for
growing Fuji apples and Nashi pears"

Which if you wish to interpret it as both apples and pears must be grown
you are welcome. We can overlook the fact that this is an exercise in
linear programming, which usually requires the feasible region to be closed
(among other things) to guarantee that a solution exists.

RonL

No, I do not wish that. That is what it really is. That was very EASY to understand.

The feasible region must be closed to guarantee that a solution exists?
That is new to me, to say it mildly.
• May 15th 2006, 02:54 PM
ThePerfectHacker
Quote:

Originally Posted by ticbol
The feasible region must be closed to guarantee that a solution exists?

I believe so.

If the feasible region is not closed, then IF the optimized solution exists then it must be on the endpoints. This does not means that it does indeed exists.
• May 15th 2006, 03:03 PM
ticbol
Quote:

Originally Posted by ThePerfectHacker
I believe so.

If the feasible region is not closed, then IF the optimized solution exists then it must be on the endpoints. This does not means that it does indeed exists.

Then I can safely say, if you wish to believe that.

Now, a question, what if the feasible region extends to infinity, and that the optimum is a minimum?
Have you not encountered those in linear programming yet? There are garozillions of them, I wish to believe.

Wait, did I understand really your,
"If the feasible region is not closed, then IF the optimized solution exists then it must be on the endpoints. This does not means that it does indeed exists."
You mean the optimum is at the endpoints? At the points on the axes?
Not at corners of the feasible region away from the axes? An optimum does not exist?
Now, you lost me there.
• May 15th 2006, 03:05 PM
ThePerfectHacker
Quote:

Originally Posted by ticbol
Then I can safely say, if you wish to believe that.

Now, a question, what if the feasible region extends to infinity, and that the optimum is a minimum?
Have you not encountered those in linear programming yet? There are garozillions of them, I wish to believe.

I belive max/min follow the same rules in linear programming. I am not an expert, a noob rather in this field. I am sure CaptainBlack will have the answers.
• May 18th 2006, 05:56 AM
CaptainBlack
Standard formulation of the Linear Programming problem from Wikipedia attached.

The constraints are usualy expressed as $\le$ or $\ge$ to ensure that the solution algorithms
can find a solution in the feasible region.

An example of a psedo LP problem without a solution (if I have done this right) is:

Maximise:

$
P(x,y)=4000x+1000y
$

Subject to the constraints:

$
x+y\le10
$

$
x+4y \le 20
$

$
x>0, y>0
$

RonL
• May 18th 2006, 06:01 AM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
I belive max/min follow the same rules in linear programming. I am not an expert, a noob rather in this field. I am sure CaptainBlack will have the answers.

A minimization problem can always be rewritten as a maximization problem
by replacing the objective function $O(\rm{X})$ by a new objective
function $O'(\mathrm{X}) =- O (\rm{X})$.

RonL
• May 18th 2006, 06:14 AM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
No it actually says "An orchadist has 10 hectares of land available for
growing Fuji apples and Nashi pears"
a solution exists.

RonL

The orchadist has 10 hectares available for growing apples and pears. This
means in this context that apples and/or pears can be grown on this land,
but the orchadist is not obliged to grow any of either. The only thing that
make the orchadist grow anything on this land is the desire to maximize
profit.

RonL
• May 18th 2006, 06:50 AM
ticbol
Quote:

Originally Posted by CaptainBlack
The orchadist has 10 hectares available for growing apples and pears. This
means in this context that apples and/or pears can be grown on this land,
but the orchadist is not obliged to grow any of either. The only thing that
make the orchadist grow anything on this land is the desire to maximize
profit.

RonL

That is another problem, not the original problem.