Linear Programming

Key Questions

  • Answer:

    2 common constraints are the non-negative constraints:
    #x>=0# and #y>=0#

    The main constraints will depend on each individual question.

    Explanation:

    The constraints are usually some kind of inequality such as time spent in a manufacturing department, or total cost allowed, etc.

  • Answer:

    For 2 dimensional problems, graph the corresponding equations of all the constraint inequalities and find the region in which all the constraints are satisfied simultaneously.

    Explanation:

    Assuming it is a linear programming problem with 2 choice variables, you consider all the constraint equations and inequalities and then draw the graph of the corresponding equalities. These will then be straight line graphs.
    Then you go back to the actual inequalities again and see is y bigger than or less than the graph you have drawn and shade the appropriate area.

    The feasibility region is then the region where all constraint equations are satisfied. It may be bounded or unbounded.

    The optimum solution to the linear programming problem (if there is one) occurs at the corner point of the feasibility region.

    If the linear programming problem has more than 2 choice variables, then you cannot draw the feasibility region and will have to use the Simplex Algorithm (involving matrix linear algebra) to solve it.

    Let me know if you need more help, and if you have an actual problem with actual figures, please post it then I will show you how to find its feasible region and solve the problem for you. :)

  • Answer:

    The maximum and minimum values are found at the vertices.

    Explanation:

    In general, a linear programming graph will give you a polygon which contains all the possible combinations of the quantities involved.

    The maximum and minimum values are found at the vertices, or if the vertices are not on whole numbers, then at the points INSIDE the polygon which are CLOSEST to the vertices.

    Which vertex you will use will depend on the question asked.
    It is a good idea to calculate an answer from several vertices to be sure of choosing the correct one.

Questions