# Homework Help: Linear Programming Exam Question

1. Aug 8, 2013

### elyttle

1. The problem statement, all variables and given/known data
Here is the stated problem:

MSA computer corporation manufactures two computer system. Alpha 4 and Beta 5. The firm employs five technicians working 160 hours per month. Management insists on no overtime next month (less than or equal to 160 hours).20 hours labour is required for an Alpha 4, and 25 hours labour required for a Beta 5. MSA wants to see at least 10 Alpha 4s, and 15 Beta 5s produced in the next month. Alpha 4s cost 1200 euro, Beta 5s cost 1800 euro. Determine the number of each to be produced in order to minimize costs.

1)Formulate the above L.P.P

2)Put it into canonical form and show that the origin is not a feasible point.

3)Using two artificial variable x6 and x7 solve the above L.P.P using the two stage simplex algorithm.

3. The attempt at a solution

I have parts 1) and 2) done

z=monthly costs
x1=No of alpha 4 systems
x2=No of beta 5 systems

Alpha 4 costs 1200 euro, Beta 5 costs 1800 euro, so the objective function is

z=1200x1 + 1800x2

5 technicians work 160 hours so there are 800 hours total available. Alpha 4 takes 20 hours and beta 5 takes 25 hours, We also want at least 10 Alpha 4s and 15 Beta 5's. SO our contraint equations are:

20x1+25x2≤800
x1≥10
x2≥15

and our non-negative contraints, x1≥0 and x2≥0

So the full L.P.P is...

Minimize z=1200x1 + 1800x2

subject to 20x1+25x2≤800
x1≥10
x2≥15

x1≥0 , x2≥0

To put the L.P.P in canonical form we introduce slack variables and change the objective function to maximize, so canonical form is

Maximize z= -1200x1 - 1800x2

subject to 20x1+25x2 + x3 = 800
x1 - x4 = 10
x2 - x5 = 15

x1≥0 , x2≥0 , x3≥0 , x4≥0 , x5≥0

The origin is clearly not a feasible point because at x1 = 0 and x2 = 0, x3 = 800, x4 = -10, x5 = -15

Negative values are present so the origin is not feasible.

Im getting stuck now because I don't know how to introduce the artificial variables x6 and x7, do we not need at least three artificial variables, one for each constraint, if not which constraints should I add the artificial variables to? A little help would be much appreciated.

2. Aug 8, 2013

### Staff: Mentor

I don't understand the question, or the question is pointless. Clearly the workers have to produce 10 Alpha 4s and 15 Beta 5s. After that, each additional computer leads to more costs, so we just stop building computers. No overtime has to be paid and the minimal amount of computers was built, so all constraints are satisfied and costs are minimal.

Shortly afterwards, the manufacturer will go bankrupt, as producing anything seems to generate a negative income.
Are we supposed to maximize costs (with the implication that more produced computers will also give more revenue when they are sold)? That would lead to something to calculate.

Why don't you introduce variables for x1-10 and x1-15 and similarly for the costs? That simplifies the problem.