FW853--Topic 12. Linear Programming

  1. Begin with goal of linear programming-help make Aoptimal@ decisions. Very pertinent to natural resource management, trouble is getting problem formulated as a LP problem
  2. Linear Programs are typically a static model (i.e., not following the time trajectory of a system). Easiest way to explain is through an example
  3. Example from Dykstra
  4. General outline-you own 1200 acres of land, and have $142,500 to invest. Your land is most suited for tree farming or raising cattle. You want to decide what is the best mix of trees and cattle to maximize your income.
  5. Notice-the 1200 acres and $142,500 are fixed amounts, but the amount of land and money to allocate to cattle and trees is not. These are the DECISION VARIABLES. Here we will denote X1=# steer, and X2=# of 1000 tree lots
  6. More information-
  7. Cattle require 1 acre per animal, and cost $75
  8. Trees require 1 acre per 500, and cost $300/lot of 1000
  9. Annual returns are $9/steer, and $10 per acre
  10. Develop Objective Function
  11. ($9 / steer) * X1 = $ from cattle
  12. ($10/acre of trees) * (2 acres/lot of trees) * X2 = $ from trees
  13. Objective Function Z = 9X1 + 20X2 (See Graph)
  14. Constraints
  15. Since only have 1200 acres, and each steer requires 1 acre, and each lot of 1000 trees requires 2 acres, X1 + 2X2  1200
  16. The coefficients on the Left Hand Side (LHS) of the inequality are called technological coefficients
  17. Similarly, since only have $142,500, and each steer costs $75 and each 1000 trees costs $300, then 75X1 + 300X2  142500
  18. Another Aconstraint@ is that can not have negative numbers of cattle or trees. Therefore, X10 and X2 0
  19. Note-can plot constraints and see FEASIBLE REGIONS. Even though you don=t have objective function at this point, you can still do feasibility analysis
  20. Graphical solution-Notice that optimal solution occurs along an edge, or at a vertex of the feasible region. For this example, Z=$11,500
  21. Assumptions
  22. Linearity-strict linearity

(1)no constants (also meaning no fixed costs),

(2)no squared terms (but if a term is x2 or ln(x) throughout, and it has linear coefficients throughout, then it could be treated as any other variable)

(3)No interaction terms (e.g., x1x2)

  1. Divisibility-in example, cows only come in whole units, so this assumption would not be met.
  2. Non-negativity- note that if a term is only negative, then it=s opposite (e.g., -x1) would satisfy non-negativity
  3. Deterministic
  1. Sensitivity Analysis-Note that if you change coefficients anywhere in the model, it may or may not change the optimal decision
  2. Objective function-lets say that the price of beef has changed. Question is then, should I change cattle production, and by how much? Another way to look at this is, how much does the price of beef have to change for me to change my decision? This is called RANGING ANALYSIS. Note that changes in coefficients in objective function result in changes in slopes of lines representing objective function.
  3. Technological Coefficients-What if you had 1201 acres rather than 1200.
  4. This Arelaxes@ the constraint. If go through analysis, you would find new optimal point with new Z. In this case, 1 more acre would result in a Z of 11,508 rather than 11,500 for a gain of $8.
  5. This gain is called Ashadow price@, Aimputed value@, or Aimputed cost@ of the constraint. Note that this has the interpretation that you should be willing to pay $8 per acre to buy more land to increase your profit.
  6. Note that at some point, more land doesn=t help you. In linear programming terminology, the constraint is no longer binding. At this point, it=s shadow price drops to 0. Can do ranging analysis to find out how much land you would have to buy before land was no longer the binding constraint.
  7. Finding solutions-Simplex method
  8. Developed by Dantzig in 1947
  9. Simplex is a geometrical shape: in 2-d it is a triangle, in 3-d a tetrahedron, etc. Method is named the simplex method since it is related

References

Dykstra, Dennis P. 1984. Mathematical programming for natural resource management. McGraw-Hill Book Company. New York, New York. 318 p.