2 | review linear programming, metabolic model Flashcards
s.t. meaning
subject to
What is our goal with constraint based modelling?
What mathematical method can be used to achieve this goal?
Goal:
- what amounts of limited resources needed to achieve a certain goal (of objectives)?
- finding the best (=optimal) solution for the above
Mathematical method:
Mathematical programming → algorithms to find optimal solutions.
- different ‘flavors’ of mathematical programming
- simplest is linear programming: only linear mathematical functions used in model
Assumptions for an LP standard form
Assume that there are 𝑛 decision variables (modelling resources, competing activities, etc.):
𝑥1, 𝑥2, …, 𝑥𝑛
Let these variables be subjected to 𝑚 (inequality) constraints:
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ⋯ + 𝑎2𝑛𝑥𝑛 ≤ 𝑏2
…
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ⋯ + 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚
all 𝒙𝒋 ≥ 𝟎, 1 ≤ 𝑗 ≤ 𝑛
We want to maximize an objective - a linear function of the variables
𝑧 = 𝑐1𝑥1 +𝑐2𝑥2 + ⋯ +𝑐𝑛𝑥𝑛
LP standard form?
max 𝑧 = ∑1≤𝑖≤𝑛𝑐𝑖𝑥𝑖
s.t.
∑1≤𝑗≤𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 for 1 ≤ 𝑖 ≤ 𝑚
𝑥𝑗 ≥ 0, 1 ≤ 𝑗 ≤ 𝑛
Steps to develop an LP model?
- Specify the decision variables
- Determine objective of problem, describe it by criterion function in terms of decision variables.
- Determine constraints (resource limits, demand, etc.)
- Solve the LP problem using an algorithm (e.g., graphical method, simplex method)….. Do analysis → selection of values for decision variables, optimizing criterion function, while satisfying all constraints
What is a criterion function?
Product Mix Problem:
Two products: I / II
Storage (m2): 4 / 5
Raw material (kg/unit): 5 / 3
Production rate (unit/hr): 60 / 30
Selling price (euro/unit): 13 / 11
The total available storage space is 1500 m2
The total amount of raw material is 1575 kg
Maximum 7 hrs can be used for production
Write down the LP model!
max 𝑧 = 13𝑥1 + 11𝑥2
s.t.
4𝑥1 + 5𝑥2 ≤ 1500
5𝑥1 + 3𝑥2 ≤ 1575
𝑥1 + 2𝑥2 ≤ 420
𝑥1 ≥ 0
𝑥2 ≥ 0
Graphically, what does an inequality define? How do you check this?
An inequality defines a half-plane (area bounded by a straight line)
To check which half: enter any point to the inequality and see if it’s true - if so it’s this side.
LP - feasible region?
Feasible region or feasible solution space:
comprises all points (𝑥1, 𝑥2) that satisfies all constraints (recall the solution of linear equalities and intersection)
The area containing all possible solutions that satisfy the constraints.
Formed by intersecting half-planes of inequalities.
Hence, the optimal solution must lie in this region!
LP - Three types of points in a feasibility region?
Interior points: Inside the feasible region but not on boundaries.
Boundary points: On the constraints’ lines.
Extreme points: Vertices (corners) of the feasible region—optimal solutions always occur here!
LP - how to find the optimal solution graphically?
Check each exteme point for the best value.
LP - multiple solutions?
An LP problem can have multiple solutions
This is the case when the objective is parallel to one of the constraints – infinitely many optimal solutions
The Simplex Method - when is it needed?
requirements?
More than two decision variables –> graphical method is not tractable.
The Simplex method is not used to examine all feasible solutions.
It deals only with a small and unique set of feasible solutions
- the set of extreme points (vertex points)
- of the convex feasible region
- that contains the optimal solution.
The Simplex Method
convex feasible region?
A feasible region is convex if the line connecting any two points in the region is fully contained in the region!
What are the main steps of the Simplex Method - described graphically?
- Locate an extreme point of the feasible region.
- Examine each boundary edge intersecting at this point to see whether movement along any edge increases the value of the objective function.
- If the value of the objective function increases along any edge, move along this edge to the adjacent extreme point. If several edges indicate improvement, the edge providing the greatest rate of increase is selected.
- Repeat steps 2 and 3 until movement along any edge no longer increases the value of the objective function.
What are the main steps of the Simplex Method?
- Convert inequalities to equalities using slack variables.
- Set up the initial simplex tableau.
- Choose the entering variable (most negative coefficient in the objective function).
- Choose the leaving variable (smallest positive ratio of RHS to pivot column).
- Update the tableau and repeat until optimal solution is found.
Simplex method: basic variable?
Basic variable is a variable isolated in a constraint that can be set to the right-hand side of that constraint.
All other variables are non-basic
Simplex method - basic feasible solution?
x<sub<1</sub>, … xn = 0
s<sub<1</sub>, … sn = amount of resource available
The Simplex method is not used to examine all ______ solutions. It deals only with a small and unique set of ______ solutions the set of ______ points of the ______ ______ region that contains the ______ ______.
The Simplex method is not used to examine all feasible solutions. It deals only with a small and unique set of feasible solutions the set of extreme (vertex) points of the convex feasible region that contains the optimal solution
What is a slack variable?
- A variable added to inequality constraints to convert them into equalities.
- Example: 4x1 + 5x2 ≤ 1500 becomes 4x1 + 5x2 + s1 = 1500, where s1 ≥ 0.
Where does the optimal solution occur in the Simplex Method?
- Always at an extreme point (corner) of the feasible region.
How is a basic feasible solution constructed in the Simplex method?
- Set all non-basic variables to zero.
- Solve the system to find the values of the basic variables from the right-hand side.
What is a basic feasible solution?
- A solution that satisfies all constraints and non-negativity.
- Some variables (basic) take positive values; others (non-basic) are set to zero.
- The number of basic variables equals the number of constraints.
What are basic and non-basic variables?
- Basic variables: Variables that can take positive values in the current solution.
- Non-basic variables: Variables currently set to zero.
How do we increase the value of z in the Simplex method?
- Look at the first row (objective function row).
- If a variable has a negative coefficient, increasing its value increases z.
What does it mean if all coefficients in the objective function row are non-negative?
- The current solution is optimal.
- No variable can be increased to improve z.
What are minimization LP problems?
- Instead of maximizing, we minimize a cost function:
min z = c1x1 + c2x2 + … + cnxn - Solved using the same Simplex Method, but the entering variable is the most positive coefficient in row 1.
What are equality constraints in LP problems?
- Instead of ≤ or ≥, the constraint is an exact equality:
Σ aijxj = bi - Requires artificial variables to solve with Simplex.
What are integer and mixed-integer LP problems?
- Integer LP: All decision variables must be whole numbers (e.g., number of cars produced).
- Mixed-Integer LP: Only some variables must be integers.
- Zero-One LP: Decision variables are either 0 or 1 (e.g., choosing between projects).
- Simplex Method cannot be used for these problems—other algorithms are needed.
