Module 3 - Allocating scarce resource (Part 1) Flashcards
How to formulate a LP
- Identify decision variables
- Write out objective function
- Write out constraints
- Write the LP
Identify Decision variables?
Decision variables represent what has to be decided
How many products to produce/buy/consume?
Each decision variable is written as an unknown, usually x. Find the variable by looking at problem.
Step 2: find objective function
What should be optimized in the linear program.
Maximize or minimize?
Minimize cost, maximize profit, maximize revenue
Data:
Step 3: Write out constraints
What is restricting the objective?
A resource can only be used for a certain number of hours
Step 4: Write the LP
What is a feasible solution?
A set of values when they satisfies all the constraints (including non-negativity)
What is an optimal solution?
A set of values satisfy all the constraints (including non-negativity) AND gives the best value of the objective function.
What is called the best value of the objective function?
Optimal objective function value.
There can be more than one optimal solution and sometimes ther is no optimal solution.
How do we call an feasible solution that attains a value that could be a bit lower than the optimal objetive function. (goal is to maximize)
We say that it is a** lower bound** on the optimal objective function value of the LP.
How do we call an feasible solution that attains a value that could be a bit lower than the optimal objetive function. (goal is to minimize)
an** upper bound **on the optimal objective function value
Key taaways
Formulating a Linear Program (LP):
- Decision variables.
- Objective function.
- Constraints.
* Feasible solutions versus optimal solutions.
* Very useful tool to guide decision making:
- Large scale problems.
- Very large number of applications
