7 - Simplex algorithm

Question 1

What are slack variables used for?

Answer 1

They are added to variable inequalities to turn them into equations. They are also non-negative.

Question 2

What is the function of the simplex algorithm?

Answer 2

Determines whether a vertex is optimal, and which vertex should be moved to next.

Question 3

Describe the use of the one-way simplex algorithm to maximise.

Answer 3

1. Draw table, Basic volumn on left, one column of each variable, value column, row operation column, R value column
   One row for each constraint and one row for objective function.
2. Find most negative entry in objective row and label this column as pivot
3. Divide value column by term in pivot column to get R value
4. Select smallest R value to make that term (smallest R value and pivot column) the pivot
5. Divide pivot row by pivot and chnage basic variable on left to variable at top of column
6. use new pivot row to make the pivot colummn 0 in all other rows
7. repeat steps 2-6 until there are no negative numbers in objective function
8. now optimal

Question 4

What are surplus variables?

Answer 4

used to turn greater than inequalities into equations by subtracting a surplus variable and adding an articficial variable

Question 5

how to carry out two stage simplex

Answer 5

1. use artifical +surplus variables
2. let I = sum of artificial;s
3. replace I with normal variables
4. find I +- all variables = a constant value
5. use simplex as normal
6. if sum of artificals = 0, then use this solution to start the second iteration of simplex
7. if != 0, no feasible solution to original problem

Question 6

big M

Answer 6

1. use slack for >=
2. use surplus + artificials for <=
3. for each artifical, subtract M(a1 + a2 +a3) from objectiev
4. write artificals in terms of normal variables
5. simplex like normal

M is abitrily large