04_Linear Programming Flashcards

1
Q

What is an extreme point in a LP

A
  • an extreme point in an LP with n decision variables is defined by the intersection of n of the m>n hyperplanes
  • if we have m hyperplanes and n <= m variables, the # of possibele extreme points is

m = number of constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Standard Form of an LP

4 items

A
  1. All variables are nonnegative
  2. Constraints except non-negativity constraints of variables are stated as equalities
  3. RHS of each constraint is nonnegative
  4. For each constraint, except non-negativity constraint we have a variable with coefficient of 1 in that constraint and coefficients of 0 in all other constraints and in the objective function
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

When do you introduce Slack Variable and when Surplus Variable?

When transforming LP into standard form

A

Slack Variable
- when <= in constraint
- sj > 0
- positive

Surplus Variable
- when >= in constraint
- sj > 0
- negative

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In which order to transform into Standard form?

A
  1. Maximize Objective Function
  2. Nonnegativity Constraint
  3. Are all constraints stated as equalities?
  4. Is RHS nonnegative?
  5. Isolate variables in each constraint
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the Intuition of the Simplex Method

A

PROCEDURE (PIVOT STEPS):
- Given an extreme point, determine whether there exists a better neighbor or not
a. “No”: Stop, you’re at an optimal extreme point or there exists none
b. “Yes”: Go to a better one

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Basic Variable in Simplex Algorithm

A
  • extreme point
  • decide whether to pivot to next extreme point or whether optimal solution has been found
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What to do when variables aren’t isolated in standard form?
How do you solve for an optimal solution

2 Methods

A
  • Big-M Method
  • Two Phase Method
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

An optimal solution of a linear program is always a…

A

corner point of the feasible region

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Gauß-Jordan Algorithm

Graphical Solution of LP

A
  • allows to solve a set of m linear equations with m variables
  • applies elementary row operations to obtain identity matrix for LHS
  • elementary row operations: multiply rows by constant, adding and subtratcting multiples of rows from each other
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the Basis in an LP in canonical form?

A
  • set of all basic variables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a Basic Variable

A
  • variable that appears with +1 in one constraint and 0 in all other constaraints including objective function
  • # of BV = # of equations / constraints / m
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

When is a basic solution optimal

A
  • when non basic variables in objective function are < = 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Change of the basis

Pivot Step

A
  • occurs when moving from one basic feasible solution to another
  • by removing one former BV from the basis and introducin one former non basic variable to the basis
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When to stop pivoting?

simplex method

A
  • when optimal solution is found
  • or simplex shows objective function is unbounded of feasible region (unbounded solution)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What to do when > =

A
  • introduce negative surplus variable
  • introduce artifical variable
  • to avoid artifical variable in the Basis multiply artifical varible with -M in objective function
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What to do when Minimization in objective function

A
  • multiply with -1
17
Q

n
Examples of n

A

# of variables
- decision variables
- slack variables
- surplus variables
- artifical variables

18
Q

Big M Method
Avoid these Errors in Calculation

A
  • when dividing RHS / Coefficient : if RHS = 0 than this is the smallest -> select row accordingly
  • however **if coefficient = 0 -> then unbound **
19
Q

What happens when artificial variable has 0 coefficient in objective function but is still in the basis, while all NBV coefficients are smaller or equal 0 in the objective function?

Big-M Method

A
  • Tableu is optimal
  • but LP is infeasible
20
Q
A