04_Linear Programming

Question 1

What is an extreme point in a LP

Answer 1

• 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

Question 2

Standard Form of an LP

4 items

Answer 2

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

Question 3

When do you introduce Slack Variable and when Surplus Variable?

When transforming LP into standard form

Answer 3

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

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

Question 4

In which order to transform into Standard form?

Answer 4

1. Maximize Objective Function
2. Nonnegativity Constraint
3. Are all constraints stated as equalities?
4. Is RHS nonnegative?
5. Isolate variables in each constraint

Question 5

What is the Intuition of the Simplex Method

Answer 5

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

Question 6

Basic Variable in Simplex Algorithm

Answer 6

• extreme point
• decide whether to pivot to next extreme point or whether optimal solution has been found

Question 7

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

2 Methods

Answer 7

• Big-M Method
• Two Phase Method

Question 8

An optimal solution of a linear program is always a…

Answer 8

corner point of the feasible region

Question 9

Gauß-Jordan Algorithm

Graphical Solution of LP

Answer 9

• 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

Question 10

What is the Basis in an LP in canonical form?

Answer 10

• set of all basic variables

Question 11

What is a Basic Variable

Answer 11

• variable that appears with +1 in one constraint and 0 in all other constaraints including objective function
• # of BV = # of equations / constraints / m

Question 12

When is a basic solution optimal

Answer 12

• when non basic variables in objective function are < = 0

Question 13

Change of the basis

Pivot Step

Answer 13

• 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

Question 14

When to stop pivoting?

simplex method

Answer 14

• when optimal solution is found
• or simplex shows objective function is unbounded of feasible region (unbounded solution)

Question 15

What to do when > =

Answer 15

• introduce negative surplus variable
• introduce artifical variable
• to avoid artifical variable in the Basis multiply artifical varible with -M in objective function

Question 16

What to do when Minimization in objective function

Answer 16

• multiply with -1

Question 17

n
Examples of n

Answer 17

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

Question 18

Big M Method
Avoid these Errors in Calculation

Answer 18

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

Question 19

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

Answer 19

• Tableu is optimal
• but LP is infeasible