Linear Programming

Question 1

formulating a problem:

Answer 1

• define variables
• find the constraints
• find the objective function

Question 2

shade the…

Answer 2

unwanted region

Question 3

find the optimal solution

Answer 3

draw an objective line and move is parallel, the last vertex to be crossed is the optimal solution.

Question 4

branch and bound method

Answer 4

1. calculate the optimised solution (not an integer, UB)
2. truncate the x and y values and calculate the profit from this (LB)
3. branch on the variable that was truncated the most (branch with values either side and signs to reflect this)
4. solve the original problem with the new constraint from the branch
5. reject the solution is the LB is less than the original truncated lower bound
6. repeat the branching up to 3 times

Question 5

minimise problems branch and bound

Answer 5

round up the non-integer value

Question 6

Simplex for minimise

Answer 6

multiply profit by -1
for conditions:
if (expression ≥ constant) multiply through by -1
if (expression ≤ constant) leave it as it is

Question 7

Setting up the simplex table

Answer 7

1. rearrange profit so P - (expression) = 0
2. write constraints each with their own slack
3. write the table:
   - rows and the profit+constraints
   - columns are the variables, slack variables and constants (RHS)

Question 8

Simplex method

Answer 8

1. choose the most negative value in the profit row. This column is the pivot
2. Complete ratio tests for constraint row:
   - RHS/value in pivot column
   the lowest non negative, non zero value is the pivot row
3. determine what you need to divide/multiply the pivot element by to make it 1. complete this operation to the whole row.
4. determine row operations so the value in the pivot column is zero by adding/ subtracting multiples of the new pivot row.
5. repeat

Question 9

ratio test

Answer 9

RHS/value in pivot column

the lowest non negative, non zero value is the pivot row

Question 10

pivot row

Answer 10

the lowest non negative, non zero value from the ratio test is the pivot row

Question 11

pivot column

Answer 11

the most negative value in the profit row

Question 12

When does simplex stop

Answer 12

when non of the values in the pivot row are negative

Question 13

reading off results from a simplex tableu

Answer 13

If the column for a variable has all 0s and 1s read of the RHS value where the 1 is.
If the column has other numbers variable = 0