14.9 Exercises: Linear Optimization

Q1

Consider the following 4 constraints

  • Constraint A: \(X_1 + X_2 \leq 10\)
  • Constraint B: \(0.5X_1 + 2X_2 \leq 10\)
  • Constraint C: \(X_1 - 0.5X_2 \geq 12\)
  • Constraint D: \(X_2 \geq 7\)
  • Non-negativity constraints: \(X_1 \geq 0\), \(X_2 \geq 0\)

Assume the non-negativity constraints always hold. For each of the following sets of constraints, please indicate whether they are (i) Feasible, (ii) Infeasible, or (iii) Unbounded.

  1. A+B
  2. A+C
  3. A+D
  4. B+C
  5. B+D
  6. C+D
Q2

The examples we discussed in the earlier part of this chapter were all maximization problems (specifically, to maximize profit). In this question we shall explore minimisation.

  1. FunToys is famous for three types of toys: Cars, Animals, and Robots. Each year, near the holiday season, it receives large bulk orders for these items. To meet these orders, FunToys operates three small toy-making factories, A, B and C.
  • Factory A costs $1000 per day to operate, and can produce 30 cars, 20 animals and 30 robots per day.
  • Factory B costs $1200 per day to operate, and can produce 40 cars, 50 animals and 10 robots per day.
  • Factory C costs $1500 per day to operate, and can produce 50 cars, 40 animals and 15 robots per day.

This Christmas, FunToys is required to deliver 5000 cars, 3000 animals and 2500 robots. You are tasked with finding out what is the most cost-efficient way to meet the order. (In this question, please IGNORE integer requirements, i.e., just use fractional answers if/when they come up.)

Let us start by trying to formulate this as a optimisation problem.

  • First, write down what you want to minimize.
  • Second, write down your decision variables. What are you actually choosing?
  • Third, write your objective function in terms of your decision variables.
  • Fourth, write down the constraints: what are the contractual requirements you need to fulfill. What other constraints are there? Write them down in terms of your decision variables.
  • Summarize them nicely in a table.

  1. Write code to solve this optimisation problem. Report the optimal solution, and the value of the objective function at that solution. Interpret the solution: what do these numbers mean? (again, please ignore any integer requirements and just report fractional answers if they appear)

  2. What if we impose an additional constraint that FunToys only has 60 days to complete the order? (Note that we can run all three factories simultaneously). What happens now? Re-produce a new table summarizing the optimisation problem (including the existing and new constraints), and write R code to solve it. What is the new solution, and what is the objective function value?

  3. For the solution in (c), which of the constraints are binding, and which are non-binding?

  4. Using your solution in (c), print out the Shadow Prices. Interpret these values – make sure you can explain why each shadow price is zero or why it is positive/negative! Your answer from part (d) should also help you explain. (Note again, that we IGNORE integer requirements in this question, so your \(X\) variables can be fractional…)