|
Question 1023709: Hi, Would you please be able to help me. I need to understand the formula to add into a graphing tool for the following problem:
A minibus operator is contracted to transport 50 Olympians from the Olympic Village to the Athletic Stadium. He has three type A minibuses and four type B minibuses available. A type A minibus carries 15 people and a type B minibus carries 10 people. Only five drivers are available. It costs $100 to operate a type A minibus and $80 to operate a type B minibus. He wishes to minimise the costs involved to transport the 50 Olympians.
I've completed the following:
Variables: Let x represent type A mini bus; Let y represent type B mini bus; Let c represent the minimum cost.
Constraints:
x <= 3 (At most 3 type A mini buses available)
y <= 4 (At most 4 type B mini buses available)
x + y = 5 (Limit on number of drivers)
15x + 10y = 50 (Limit on number of passengers who can be carried in both mini buses)
Objective Function: C = 100x + 80y
Graphs - I've set the Axis to x: -1 to 10 and y: -1 to 10 and entered the above relations and constraints but don't know how to enter the formula to determine the minimum cost and I don't understand how corner points work.
Thank you so much for any help you can offer.
Chris
Found 2 solutions by Theo, solver91311:
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! you did pretty good in setting up the problem.
x + y = 5 should be x + y <= 5, since it is possible that the constraints can be satisfied with less than 5 driver.
15x + 10y = 50 can also be3 15x + 10y >= 50 since there is no restriction that says exactly 50 olympians need to be carried.
x has to be >= 0 and y has to be >= 0.
these constraints are usually there but not always specified.
the constraint equations that you need to graph are:
x <= 3
y <= 4
x + y <= 5 which is modeled as y <= 5 - x.
15x + 10y >= 50 which is modeled as y >= (50 - 15x) / 10
x >= 0
y >= 0
you graph the equality portion and then you shade the inequality portion as required.
your graphed equations would look like this.
the shaded area represents your region of feasibility.
it is on or above the line x = 0 and on or to the right of the line y = 0.
it is on or to the left of the line x = 3 and on or below the line y = 4.
it is on or below the line y = 5 - x.
it is on or above the line y = (50 - 15x) / 10.
the corner points of the region of feasibility are:
intersection of the line y = (50 - 15x) / 10 and y = 4 = (2/3,4).
intersection of the line y = 5-x and y = 4 = (1,4).
intersection of the line x = 3 and y = 5-x = (3,2).
intersection of the line x = 3 and y = (50 - 15x) / 10 = (3,1/2).
as can be seen on the graph, those are the corner points of your region of feasibility.
now that you've found the region of feasbility, all that is left to do is to analyze the objective function at those intersection points.
your objective function should be maximum or minimum at those intersection points.
the constraint equations also need to be satisfied at those corner points if you graphed correctly.
the added wrinkle is that not all of the corner points are integers, and your solution needs to be integers.
you can't rent a fraction of a bus.
let's look at the points in turn.
the points are (2/3,4), (1,4), (3,2), (3,1/2).
the point (2/3,4) is not possible.
it either has to be (0,4) or (1,4).
(0,4) won't do because then you can only carry 40 olympians.
the point would have to be (1,4).
(1,4) can carry 15 + 40 = 55 olympians.
that's more than enough so the constraints of carrying are satisfied.
it also satisfies all the other constraints since you have 5 or less drivers x is between 0 and 3, and y is between 0 and 4.
so (1,4) is a valid intersection point.
(1,4) also happens to be another intersection point on the graph, so we'll just use that and forget about (2/3,4).
(3,2) is a valid point on the graph.
it carries 3 * 15 + 2 * 10 = 65 olympians.
that satisfies the requirement that 50 or more olympians be carried.
the point doesn't make much sense since it's more type B buses than needed, but it is a valid point because it does satisfy all the requirements.
x is between 0 and 3 and y is between 0 and 4 and it is on or below the line y = 5-x and it is on or above the line y = (50-15x)/10.
so it's another valid point that satisfies all the constraints.
the last point is (3,1/2).
since you can't have 1/2 a bus, then we can round that up or down.
down doesn't make sense since only 45 olympians can be carried.
1 makes more sense, so we'll go with (3,1).
(3,1) satisfies all the constraints so it's a valid point.
we have 3 valid points of intersection, otherwise known as the corner points of the feabibility region.
they are (1,4), (3,2), (3,1).
what's left is to evaluate the objective function at these corner points.
at (1,4), the cost is 100 * 1 + 80 * 4 = 420
at (3,2), the cost is 300 + 160 = 560.
at (3,1), the cost is 300 + 80 = 380.
the minimum cost is at (3,1).
that's when they rent 3 type A buses and 1 type B bus.
they will carry 55 olympians which is greater than or equal to 50.
you can pick any other point within the feasibility region and it will not be less than 380 in cost.
at least that's the theory.
unfortunately, the point (2,2) is in the feasibility region, but it is not one of the corner points.
the cost would be 2 * 100 + 2 * 80 = 360.
50 olympians can be carried.
only 4 drivers are required.
why this was not one of the corner points is beyond me.
it is on the line y = (50 - 15x) / 10, however, and it does satisfy all the other constraint, so it is definitely in the feasibility region.
it does appear to be the minimum cost solution even though it's not on one of the corner points.
this is something you might want to bring up with your instructor.
i can't explain it.
the method that i showed you is correct, however, despite that wrinkle.
the only change i would make is to have 15x + 10y = 50 rather than 15x + 10y >= 50.
this would force the solution to be on the line.
the feasibility region would have to be on the line only.
the region of feasibility would just be on the line.
the point (2,2) is still not on a corner of the feasibility region since the only corner points would now be (2/3,4) and (3,1/2).
bottom line is i have no idea what the instructor was trying to show you with this problem.
talk to him / her about it.
see what he or she says.
let me know what the answer is if you do get an answer.
this problem is not the usual type of problem.
most of the time they work out and the solution is at the corner points.
it doesn't appear to be so with this problem.
i don't see anything in here that would make (2,2) a corner point, even though (2,2) is cheaper (360 versus 380) and it does carry 50 olympians (2*15 + 2*10 = 50), and it does require 5 or less drivers (4 actually).
it's possible i did something wrong, but i'll be damned if i can see it, and i have done many of these in the past successfully.
Answer by solver91311(24713)  (Show Source):
You can put this solution on YOUR website!
The general idea is to graph all of the inequalities and the area where they ALL overlap is called the "feasibility area". Any ordered pair in the feasibility area will satisfy ALL of the constraints, and, if there is an optimum solution, it will be one of the feasibility area polygon vertices (what you called corner points).
The problem with graphing all of the inequalities as they are written is that it gets difficult to tell exactly where they all overlap. To mitigate this difficulty I graph the inequalities in the OPPOSITE sense which results in the feasibility polygon having no shading; therefore much easier to see.
The constraint inequalities that you have are all correct except for two of them. Yes, it is indeed true that you are contracting to haul 50 people, but this constraint needs to be couched as an inequality that says you have contracted to haul AT LEAST 50 passengers. Also, since the MOST drivers you can have is 5, you need 
You also need to constrain both  and  to the positive integers. You can't have a negative number of either type of bus, nor can you have a fractional number of buses of either type. Hence, your constraints are:
Now, when you go to graph these constraints, just flip the inequality symbol over. I graphed all but the last constraint in the first diagram and then added the last one in the other figure.
_1.jpg)
Note the white quadrilateral that is formed. This is your feasibility polygon. Any points wholly within or on the boundaries of this polygon that have INTEGER coefficients are feasible solutions. Constraining the solutions to the integers changes the rules about where to find the optimum solution. In this case, you actually have four feasible points.
You did state the Objective Function correctly. All you need to do is substitute the and values of each of the four points into the objective function and do the arithmetic. Since your objective is to minimize your objective function value, choose the point that gives you the smallest value of the objective function.
John
My calculator said it, I believe it, that settles it
|
|
|
| |
