Week 1

Question 1

What is the objective function?

Answer 1

The function we want to maximize/minimize

Question 2

What is the decision variable?

Answer 2

The variable we can change to meet out goals

Question 3

What is an LP-problem?

Answer 3

A linear optimization problem, it an problem in the form,

• max f(x)*
• g_i(x)* ≤ b, i = 1, …, m

in f, g: Rⁿ –> R

Question 4

What is Seperability?

Answer 4

Each function is the sum of terms in which each term is a function of one of the variables only. e.g.

Σ_j=1ⁿ f_j(x_j)

Question 5

What is proportionality?

Answer 5

The value of the function is proportional with the value of earch of the variables. Thus, any increate of 1 unit of a given variable gives a constant cange in function, value, independent of the value of the variable.

Question 6

What is divisibility?

Answer 6

All variables may take any values in R. Typically, they will attain fractional values.

Question 7

What is the form of a linear problem in the objective function?

Answer 7

Σ_j=1ⁿc_jx_j

Question 8

How to create a linear problem?

Answer 8

1. First create the function to maximize
2. Write the constraints, note: be sure to watch for x ≥ 0

Question 9

How to resolve fractions in a linear problem? For example

1800 (x₁/(x₁ + x₂)) + 3800 (x₁/(x₁ + x₂) ≤ 3000

Answer 9

1. Multiply both by (x₁+x₂)
2. Then rewrite s.t. the variables are on the left and a number is on the right.

Question 10

How to rewrite a min(…) function to a linear function?

Answer 10

Create a variable z for which holds:

• z* ≤ …
• z* ≤ …

…

Question 11

When is a set convex?

Answer 11

A set is convex iff. x, y ∊ C and for all λ ∊ [0, 1] then the point

z = λx + (1 - λ) ∊ C

Question 12

What is a halfspace?

Answer 12

H = {x ∊ ℝⁿ : h^Tx ≤ 𝛅 }, this is convex

Question 13

What is a hyperplane?

Answer 13

H = { x∊ℝⁿ : h^Tx = 𝛅 }

Question 14

What is a basic feasible solution?

Answer 14

Any feasible point that is determined by n linearly independent bounding hyperplanes.

Question 15

What is the skeleton of a polyhedron?

Answer 15

The extreme points and the edges together

Question 16

What is an edge?

Answer 16

The segment of the line beween two neighbouring extrem points.

Question 17

What is the definition of an extreme point?

Answer 17

A point in the polyhedron which cannot be rewritten as a convex combination of two other points.

Question 18

What is the definiton of a vertex?

Answer 18

The only intersection point of the polyhedron with some hyperplane

Question 19

When does a system have a unique solution?

Answer 19

Let x^* be an element of ℝⁿ and let I = {i: a_i^Tx^* = b_i} the set of indices of constraints that hold with equaltity at x^*. Then the following are equilvalent:

1. There exists n vectors in the set {a_i: i∊ I}, which are linearly independent
2. The span of the vectors a_i, i ∊ I, is all of ℝⁿ can be expressed as a linear combination of the vectors a_i, i ∊ I.
3. The system of equations a_i^Tx = b_i, i∊I, has a unique solution.

Question 20

When is a solution a basic feasible solution?

Answer 20

For a non-empty polyhedron P, the following 3 statements are equivalent:

a. x^* ∈ P is an extreme point of P,
b. x^* is a basic feasible solution
c. x^* is a vertex

Question 21

When does a extreme point exist?

Answer 21

Given a non-empty polyhedron P = {x ∈ Rⁿ |a^T_i x ≥ b_i , i = 1, . . . , m}, then the following statements are equivalent:

a) P has at least one extreme point;
b) P doesnotcontainaline;i.e.,does not exist x∈P,d !=0 ∈ Rⁿ,∀λ∈R: x+λd∈P;c) There exist n vectors out of the family of a₁, . . . , a_m which are linearly independent.

Question 22

When does an LP problem have a extreme point?

Answer 22

If the feasible polyhydron contains at least one extreme point, and for which an optimal solution exists, there is always an extere point that is an optimal solution.