2 | review linear programming, metabolic model

Question 1

s.t. meaning

Answer 1

subject to

Question 2

Linear programming?

Answer 2

In many practical situations, we are interested in finding the best (= optimal) solution that determines how much of some limited resources are to be used to achieve a given goal (of objectives).

Mathematical programming provides algorithms to find optimal solutions.

Mathematical programming has different flavors The simplest is linear programming requires that all mathematical functions used in the model are linear

Question 3

LP standard form?

Answer 3

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

s.t.

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

𝑥_𝑗 ≥ 0, 1 ≤ 𝑗 ≤ 𝑛

Question 4

Steps to develop an LP model?

Answer 4

1. Specify the decision variables
2. Determine the objective of the problem and describe it by a criterion function in terms of the decision variables.
3. Find out the constraints.
4. Do the analysis which should lead to the selection of values for the decision variables that optimize the criterion function while satisfying all the constraints imposed on the problem.

Question 5

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!

Answer 5

max 𝑧 = 13𝑥₁ + 11𝑥₂

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

Question 7

Graphically, what does an inequality define? How do you check this?

Answer 7

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.

Question 8

LP - feasible region?

Answer 8

Feasible region or feasible solution space:

comprises all points (𝑥₁, 𝑥₂) that satisfies all constraints (recall the solution of linear equalities and intersection)

Hence, the optimal solution must lie in this region!

Question 9

LP - Three types of points in a feasibility region?

Answer 9

interior points are points in the feasibility region that do not lie on the lines determining the feasibility region

boundary points are points in the feasibility region that lie on the lines determining the feasibility region

extreme points are points in the feasibility region that are the ends of the segments determining the feasibility region

Question 10

LP - how to find the optimal solution graphically?

Answer 10

Check each exteme point for the best value.

Question 11

LP - multiple solutions?

Answer 11

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

Question 12

The Simplex Method - when is it needed?

requirements?

Answer 12

When there are more than two decision variables the 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.

Question 13

The Simplex Method

convex feasible region?

Answer 13

A feasible region is convex if the line connecting any two points in the region is fully contained in the region!

Question 14

The Simplex Method

Steps?

Answer 14

1. Locate an extreme point of the feasible region.
2. Examine each boundary edge intersecting at this point to see whether movement along any edge increases the value of the objective function.
3. 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.
4. Repeat steps 2 and 3 until movement along any edge no longer increases the value of the objective function.

Question 15

Simplex method: basic variable?

Answer 15

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

Question 15

Simplex method - basic feasible solution?

Answer 15

x<sub<1</sub>, … x_n = 0

s<sub<1</sub>, … s_n = amount of resource available