0.4 Linear programming: a geometric approach  (Page 3/3)

The answer is yes.

For example, in the above problem, we substituted the points (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0), in the objective function $P=\text{20}x+\text{30}y$ , and we got the values $0, $180, $190, $160, $120, respectively. Sometimes that is not the most efficient way of finding the optimum solution.

To determine the largest $P$ , we graph $P=\text{20}x+\text{30}y$ for any value $P$ of our choice. Let us say, we choose $P=\text{60}$ . We graph $\text{20}x+\text{30}y=\text{60}$ . Now we move the line parallel to itself, that is, keeping the same slope at all times. Since we are moving the line parallel to itself, the slope is kept the same, and the only thing that is changing is the $P$ . As we move away from the origin, the value of $P$ increases. The largest value of $P$ is realized when the line touches the last corner point. The figure below shows the movements of the line, and the optimum solution is achieved at the point (2, 5). In maximization problems, as the line is being moved away from the origin, this optimum point is the farthest critical point.

We summarize:

Minimization applications

Minimization linear programming problems are solved in much the same way as the maximization problems. For the standard minimization linear programming problem, the constraints are of the form $\text{ax}+\text{by}\ge c$ , as opposed to the form for the standard maximization problem. As a result, the feasible solution extends indefinitely to the upper right of the first quadrant, and is unbounded. But that is not a concern, since in order to minimize the objective function, the line associated with the objective function is moved towards the origin, and the critical point that minimizes the function is closest to the origin.

However, one should be aware that in the case of an unbounded feasibility region, the possibility of no optimal solution exists.

Professor Symons wishes to employ two students, John and Mary, to grade the homework papers for his classes. John can mark 20 papers per hour and charges $5 per hour, and Mary can mark 30 papers per hour and charges $8 per hour. Each student must be employed at least one hour a week to justify their employment. If Mr. Symons has at least 110 homework papers to be marked each week, how many hours per week should he employ each student to minimize his cost?

We choose the variables as follows:

Let $x=\text{The number of hours per week John is employed}\text{.}$

and $y=\text{The number of hours per week Mary is employed}\text{.}$

The objective function is

$C=\mathrm{5x}+\mathrm{8y}$

The fact that each student must work at least one hour each week results in the following two constraints:

$x\ge 1$

$y\ge 1$

Since John can grade 20 papers per hour and Mary 30 papers per hour, and there are at least 110 papers to be graded per week, we get

$\text{20}x+\text{30}y\ge \text{110}$

The fact that x and y are non-negative, we get

$x\ge 0$ , and $y\ge 0$ .

The problem has been formulated as follows.

Minimize $C=\mathrm{5x}+\mathrm{8y}$

Subject to: $x\ge 1$

$y\ge 1$

$\text{20}x+\text{30}y\ge \text{110}$

$x\ge 0;y\ge 0$

To solve the problem, we graph the constraints as follows:

Again, we have shaded the feasibility region, where all constraints are satisfied.

Since the extreme value of the objective function always takes place at the vertices of the feasibility region, we identify the two critical points, (1, 3) and (4, 1). To minimize cost, we will substitute these points in the objective function to see which point gives us the minimum cost each week. The results are listed below.

Critical Points	Income
(1,3)	$5(1)+8(3)=\$\text{29}$
(4,1)	$5(4)+8(1)=\$\text{28}$

The point (4, 1) gives the least cost, and that cost is $28. Therefore, we conclude that Professor Symons should employ John 4 hours a week, and Mary 1 hour a week at a cost of $28 per week.

Got questions? Get instant answers now!

Got questions? Get instant answers now!

Professor Hamer is on a low cholesterol diet. During lunch at the college cafeteria, he always chooses between two meals, Pasta or Tofu. The table below lists the amount of protein, carbohydrates, and vitamins each meal provides along with the amount of cholesterol he is trying to minimize. Mr. Hamer needs at least 200 grams of protein, 960 grams of carbohydrates, and 40 grams of vitamins for lunch each month. Over this time period, how many days should he have the Pasta meal, and how many days the Tofu meal so that he gets the adequate amount of protein, carbohydrates, and vitamins and at the same time minimizes his cholesterol intake?

	Pasta	Tofu
Protein	8g	16g
Carbohydrates	60g	40g
Vitamin C	2g	2g
Cholesterol	60mg	50mg

We choose the variables as follows.

Let x = The number of days Mr. Hamer eats Pasta.

and y = The number of days Mr. Hamer eats Tofu.

Since he is trying to minimize his cholesterol intake, our objective function represents the total amount of cholesterol C provided by both meals.

$C=60x+50y$

The constraint associated with the total amount of protein provided by both meals is as follows:

$8x+16y\ge 200$

Similarly, the two constraints associated with the total amount of carbohydrates and vitamins are obtained, and they are

$60x+40y\ge 960$

$2x+2y\ge 40$

The constraints that state that x and y are non-negative are

$x\ge 0,\text{and}y\ge 0$

We summarize all information as follows:

Minimize $C=60x+50y$

Subject to: $8x+16y\ge 200$

$60x+40y\ge 960$

$2x+2y\ge 40$

$x\ge 0;y\ge 0$

To solve the problem, we graph the constraints as follows.

Again, we have shaded the unbounded feasibility region, where all constraints are satisfied.

To minimize the objective function, we find the vertices of the feasibility region. These vertices are (0, 24), (8, 12), (15, 5) and (25, 0). To minimize cholesterol, we will substitute these points in the objective function to see which point gives us the smallest value. The results are listed below.

Critical Points	Income
(0,24)	$\text{60}(0)+\text{50}(\text{24})=\text{1200}$
(8,12)	$\text{60}(8)+\text{50}(\text{12})=\text{1080}$
(15,5)	$\text{60}(\text{15})+\text{50}(5)=\text{1150}$
(25,0)	$\text{60}(\text{25})+\text{50}(0)=\text{1500}$

The point (8, 12) gives the least cholesterol, which is 1080 mg. This states that for every 20 meals, Professor Hamer should eat Pasta 8 days, and Tofu 12 days.

Got questions? Get instant answers now!

Although the method of solving minimization problems is similar to that of the maximization problems, we still feel that we should summarize the steps involved.