CSC 445/545: Fall 2014 Assignment #1


Due beginning of class, Fri. Sept. 19, 2014
Late submissions accepted with 10% penalty until Tues. Sept. 23 at 12:30pm.
Instructions for all assignments:
  1. Draw boxes for your marks on the top of the first page of your submission. Place a 0 in the corresponding box for any questions you omit. For this assignment:
    Question 1 2 3 4 5 6 7
    Marks 0 0 0 0 0 0 0
  2. Questions should be in order.
  3. Show your work unless otherwise stated.
  4. Please put your name (last name underlined) and full student number on all submissions.

    For questions 1 and 2: Formulate the problem as a linear programming problem. It does not have to be stated in standard form. Make sure you explain the meaning of all of your variables.

  1. [10] A prison is trying to decide what to feed its prisoners. They would like to offer some combination of milk, beans, and grapefruit. Their goal is to minimize cost, subject to meeting the minimum nutritional requirements imposed by law. The cost and nutritional content of each food, along with the minimum nutritional requirements are shown below.

    Food Milk (liters) Beans (cups) Grapefruit Minimum Daily Requirement
    Niacin (mg) 3.2 4.9 0.8 13.0
    Thiamin (mg) 1.12 1.3 0.19 1.5
    Vitamin C (mg) 32.0 0.0 93.0 45.0
    Cost ($) 2.00 0.30 0.35

  2. [10] A gold processor has two sources of gold ore, source A and source B. In order to keep his plant running, at least three tons of ore must be processed each day. Ore from source A costs $20 per ton to process, and ore from source B costs $10 per ton to process. Costs must be kept to less than $80 per day. Moreover, Federal Regulations require that the amount of ore from source B cannot exceed twice the amount of ore from source A. If ore from source A yields 2 oz. of gold per ton, and ore from source B yields 3 oz. of gold per ton, how many tons of ore from both sources must be processed each day to maximize the amount of gold extracted subject to the above constraints?
  3. (a) [8] Convert this linear programming problem into an equivalent problem that is stated in standard form:
    Minimize 2 x 1 - x 2
    subject to
    x 1 + x 2 = 5
    x 1 <= 8
    x 2 >= -2
    x 1 >= 0

    Side note: One way to convert this to standard for is to use a substitution that uses the equation
    x 2 >= -2
    to get the non-negativity constraint for x2 This question would have better tested the learning objectives if students were forced to apply the tactic described in class using x' and x".
    (b) [2] Incorrect wording (this solution is not optimal): The optimal solution to this problem has x1= 7 and x2 = -2. What values do your standard form variables take on for this solution?

    Please change this question to: One feasible solution to this problem has x1= 7 and x2 = -2. What values do your standard form variables take on for this solution?

  4. [10] Find necessary and sufficient conditions for the numbers s and t to make the LP problem:
    Maximize x1 + x2
    subject to
    s x1 + t x2 <= 10
    x1, x2 >= 0
    (a) have an optimal solution,
    (b) be infeasible,
    (c) be unbounded.
    Justify your answers.
    You must solve the remaining problems by hand. Show the calculations required in detail. You may use your program to check the answer, but it should be clear that you know how to the the algebraic manipulations required for pivoting by hand. You will not get credit for these questions unless you show all your work.

  5. [20] Solve this problem by the Simplex method:
    Maximize 5 x1 + 6 x2 + 9 x3 + 8 x4
    subject to
    1 x1 + 2 x2 + 3 x3 + 1 x4 <= 5
    1 x1 + 1 x2 + 2 x3 + 3 x4 <= 3
    x1, x2, x3, x4 >= 0
    When you have a choice of entering variable, use the smallest subscript rule (of the variables in the z row with strictly positive coefficients, select the one which has the smallest subscript to enter).
  6. [20] Redo the previous question. When you have a choice of entering variable, use the largest coefficient rule (of the variables in the z row with strictly positive coefficients, select the one which has the largest coefficient to enter).
  7. [20] Solve the following problem using the maximum increase rule (the entering variable is chosen to result in a maximum increase to the objective function at each step). Indicate the increase to the ojective function that occurs with each possible choice of entering variable at each step.
    Maximize 4 x1 + 2 x2 + 3 x3
    subject to
    0 x1 + 1 x2 + 0 x3 <= 30
    2 x1 + 0 x2 + 1 x3 <= 10
    x1, x2, x3 >= 0