Linear Programming: Modeling and Optimization

Posted on May 13, 2024 in Law & Jurisprudence

Process to Model a Linear Programming Problem

  1. Determine and define the target (either maximize or minimize).
  2. Develop a list of choices.
  3. Define the decision variables (X1, X2, …, Xn).
  4. Develop a list of restrictions that affect them.
  5. Define the objective function, e.g.: Max Z: 40X1 + 50X2

Limitations, Requirements, and Restrictions

Restrictions should establish limitations on the availability of resources and the need to comply with the commitments for the period.

  • Capacity Constraints and/or Resource Availability: These are limits due to system limitations in terms of the amount of equipment, space, funding, raw materials, and manpower available. An example would be the constraint that refers to the land available for crops. These constraints are expressed as limitations or inequalities of type (≤). What we deal with a resource cannot be greater than what we have available.
  • Restrictions on Market: There are limits (lower, upper, or both) on the amount of product that can be sold or used. For example, the maximum and historical minimum sales for a product. The latter would be a requirement or inequality of type (≥), because if there is a committed amount of product sales, you cannot decide to produce less than that amount because you could not fulfill your delivery commitments. The former is a constraint or inequality of type (≤) because you should not produce more product than you have historically been able to sell each season.
  • Restrictions on Quality or Composition of a Mixture: These restrictions limit the mixture of ingredients that usually define the quality of the resulting products. These restrictions can be limitations (≤), requirements (≥), or more restrictive requirements of the type (=).
  • Restrictions of Production Technology or Material Balance: These are constraints that define the output of a process as a function of the inputs, often with waste or yield loss. These restrictions, as above, may also be limitations (≤), requirements (≥), or more restrictive requirements of the type (=), depending on the process being modeled.
  • Restrictions of Definition: These restrictions define a variable as a function of others. Often these restrictions come from accounting definitions or balancing materials, such as the relationship between the quantity of a product, which must be equal to what was sold plus what was left over in inventory. These restrictions are usually requirements of the type (=).

Characterization of the Optimal Solution

a) Types of Constraints

  • Active Constraints: These are defined directly by the location of the optimum.
  • Non-Active Constraints: These are not directly involved in determining the optimum location.
  • Redundant Constraints: These are non-active constraints that do not participate directly or even in determining the boundaries of the feasible solution zone.

b) Constraint Shadow Price

The shadow price of a constraint is a quantitative measure of how each constraint influences a system in which the optimal value of the objective function is neither better nor worse. There are two equivalent definitions for the shadow price:

  • Definition No. 1: The rate of IMPROVEMENT experienced by the optimal value of the objective function for each unit that INCREASES the free term of a constraint.
  • Definition No. 2: The rate of DETERIORATION experienced by the optimal value of the objective function for each unit that DECREASES the free term of a constraint.

These two definitions are made on the basis that the shadow price is positive. Normally, the shadow price of a constraint of type (≤), which is active, is always positive.

When the shadow price of a constraint is negative, which normally happens with restrictions of the type required (≥), the effect on the objective function is contrary to the definition: When you increase the free term, it worsens, and when you decrease it, it improves.

c) Ranges of Values for Constraint Shadow Price

  • The shadow price of an active constraint will be non-negative (≥ 0) if the restriction is a limitation (≤).
  • The shadow price of an active constraint is not positive (≤ 0) if the restriction is a requirement of type (≥).
  • The shadow price of an active constraint will be positive, negative, or equal to 0 if the restriction is a requirement of the type (=); this will depend on each model.
  • The shadow price of a non-active constraint is always zero.

d) Range of Validity of Constraint Shadow Price

  • The value of the shadow price of a constraint is valid only for increases or decreases in its free end to such values that do not cause any of the active constraints of the original optimal solution to stop being active.
  • The objective function will improve its value (increase if maximizing, decrease if minimizing) when increasing the value of the free term of an active constraint that is a limitation.
  • The objective function will worsen its value (decrease if maximizing, increase if minimizing) when diminishing the value of the free term of an active constraint that is a limitation.
  • The objective function will improve its value (increase if maximizing, decrease if minimizing) when diminishing the value of the free term of an active constraint that is a requirement such as “greater than or equal to.”
  • The objective function will worsen its value (decrease if maximizing, increase if minimizing) when increasing the value of the free term of an active constraint that is a requirement such as “greater than or equal to.”
  • The objective function will retain its value (not change) when you increase or decrease the value of the free term of an active restriction of any kind.