More content to come soon!
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.
= 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 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 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.
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
) subject to and
) subject to and
General Mathematic Form
Find X so as to max f(x) subject to
Forumlating the Model
Solving the Model
Intrepreting the Model
Assumptions of L. P.
- 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
- 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:
- Decision variables (solution of model)
- Objective function (min or mix) with a goal (maximize profit, minimize cost)
History of Linear Programming