Optimization

More content to come soon!

Linear Programming

Deals with finding the max or min of a linear function (objective function is subject to linear constraints). For example, how do you maximize profits selling different products with limited resources?

Example 1: Resource Allocation Problem

Producing n different products, maximize profit to not exhausting our n different resources.

Decision Variable

= number of unit of product j to be produced

This is the decision variable (unknown to be determined from the solution of the model).

= denote the profit (utility per unit of product j) then = total profit from producing units of product j.

total profit from all products

Objective Function

Objective to be achieved by the system as a mathematical function of the system decision variables (DV). It is usually maximizing profit or minimizing cost for example.

= the amount of resource i needed to produce 1 unit of product j

= amount of resource i needed to make units of product j

This is the total amount of resource i used or needed.

Functional Constraints

Functional contraints are limitations imposed on the variable to satisfy the restriction of the model system expressed as a math function of the system DV.

We usually assume that . This is called the non-negativity constraint.

Summary

Find so as to maximize subject to , i = 1, … m and j = 1, …, n and where n is the number of decision variables, and m is he number of contraints.

Canonical Form of Linear Programming

Maximization

) subject to and

Minimization

) subject to and

General Mathematic Form

Find X so as to max f(x) subject to

  1. Forumlating the Model

  2. Solving the Model

  3. Intrepreting the Model

Assumptions of L. P.

  1. Divisibility a) Proportionality (assumption about both objective function and functional contraints). This means that for each item of product j, both the profit contribution and the amount of each resource i consumed are strictly proportional to the number of units of .

b) Continuity: Variables are continious numbers, meaning we can produce not just interget (whole number) amounts of each product. Mathematically this is representedby

  1. Additivity Both the equation for the value to minimize or maximize are sums, and the contraints are linear as well

Linear Programming has 3 basic components:

  1. Decision variables (solution of model)
  2. Objective function (min or mix) with a goal (maximize profit, minimize cost)
  3. Constraints

Further Reading:

History of Linear Programming

Optimization - February 19, 2015 - Andrew Andrade