2 | review linear programming, metabolic model Flashcards by Stevie Davies

s.t. meaning

subject to

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

Assumptions for an LP standard form

Assume that there are 𝑛 decision variables (modelling resources, competing activities, etc.):

𝑥₁, 𝑥₂, …, 𝑥_𝑛

Let these variables be subjected to 𝑚 (inequality) constraints:

𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ + ⋯ + 𝑎_1𝑛𝑥_𝑛 ≤ 𝑏₁
𝑎₂₁𝑥₁ + 𝑎₂₂𝑥₂ + ⋯ + 𝑎_2𝑛𝑥_𝑛 ≤ 𝑏₂
…
𝑎_𝑚1𝑥₁ + 𝑎_𝑚2𝑥₂ + ⋯ + 𝑎_𝑚𝑛𝑥_𝑛 ≤ 𝑏_𝑚

all 𝒙_𝒋 ≥ 𝟎, 1 ≤ 𝑗 ≤ 𝑛

We want to maximize an objective - a linear function of the variables

𝑧 = 𝑐₁𝑥₁ +𝑐₂𝑥₂ + ⋯ +𝑐_𝑛𝑥_𝑛

How well did you know this?

Not at all

Perfectly

LP standard form?

max 𝑧 = ∑_{1≤𝑖≤𝑛}𝑐_𝑖𝑥_𝑖

s.t.

∑_{1≤𝑗≤𝑛}𝑎_𝑖𝑗𝑥_𝑗 ≤ 𝑏_𝑖 for 1 ≤ 𝑖 ≤ 𝑚

𝑥_𝑗 ≥ 0, 1 ≤ 𝑗 ≤ 𝑛

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

What is a criterion function?

How well did you know this?

Not at all

Perfectly

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𝑥₁ + 11𝑥₂

s.t.
4𝑥₁ + 5𝑥₂ ≤ 1500
5𝑥₁ + 3𝑥₂ ≤ 1575
𝑥₁ + 2𝑥₂ ≤ 420
𝑥₁ ≥ 0
𝑥₂ ≥ 0

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

LP - feasible region?

Feasible region or feasible solution space:

comprises all points (𝑥₁, 𝑥₂) 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!

How well did you know this?

Not at all

Perfectly

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!

How well did you know this?

Not at all

Perfectly

LP - how to find the optimal solution graphically?

Check each exteme point for the best value.

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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!

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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>, … x_n = 0

s<sub<1</sub>, … s_n = 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: 4x₁ + 5x₂ ≤ 1500 becomes 4x₁ + 5x₂ + s₁ = 1500, where s₁ ≥ 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 = c₁x₁ + c₂x₂ + ... + c_nx_n * 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: Σ a_ijx_j = b_i * 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.