1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Programming Exam Question

  1. Aug 8, 2013 #1
    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:


    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≥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. jcsd
  3. Aug 8, 2013 #2


    User Avatar
    2017 Award

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted