Simplex

Question 1

How do you know if a solution isn’t feasible when using big M method?

Answer 1

If an artificial variable isn’t 0

(Artificial variables must = 0, and are non negative so should all be 0)

Question 2

What does simplex meth allow you to do

Answer 2

Determine which vertex on the edge of the feasible is optimal.

Decide which adjacent vertex you should move to to increase the value of the objective function

Question 3

Borders of feasible region represent?
Vertices of feasible region represent?

Answer 3

Borders when a variable = 0 (slack or basic)
Vertex where 2 variables = 0 (intersection of borders)

Question 4

Things of note

Answer 4

Define constraints explicitly, ie x represents a number of, or grams of etc

Don’t forger non negativity constraint, + write down slack variables are slack variables

For algebraic meth - show that starting solution (0,0,0..) isn’t optimal

Question 5

Finding integer solutions strat

Answer 5

Draw optimal point, then draw a box around to deduce which integer points would be around it

Question 6

Meaning of basic variable column in simplex

Answer 6

Values aren’t initially at 0 - slack variables initially here
as you start at (0,0,0) a basic variable is a non zero variable

Question 7

What does it mean if all theta values are negative or zero

Answer 7

this relates geometrically to an unbounded region so no optimal solution can be found

Question 8

Meaning of slack variable

Answer 8

Accounts for whats “left” after x and y - makes up for it basically

Question 9

2 stage simplex explanation

Answer 9

The simplex method we just looked at only works when all the constraints, other than the non-negativity conditions, are ≤ constraints. These are converted into equations using slack variables and the method involves starting at the origin as the basic feasible solution and improving this solution systematically.

Problems that include ≥ constraints, have no obvious basic feasible solution, since the origin is not in the feasible region. You could convert the inequality 𝑥 + 3𝑦 ≥ 10 into an equation by subtracting a variable, s, giving

𝑥 + 3𝑦 – 𝑠 = 10 where 𝑠 ≥ 0

s is a surplus variable. This doesn’t solve the problem of using the simplex method with 𝑥 and 𝑦 as non-basic variables. This would require 𝑥 = 𝑦 = 0, giving –𝑠 = 10, which makes s negative. To avoid this problem, a new type of variable called an artificial variable is introduced

𝑥 + 3𝑦 – 𝑠 + 𝑎 = 10 where 𝑠, 𝑎 ≥ 0
Define a new objective function to minimise the sum of all the artificial variables
Use the simplex method to solve this problem
If the minimum sum of the artificial values is 0 then the solution found is a basic feasible solution of the original problem, which is then the starting point for the second stage. Use the simplex method again to solve this problem.
If the minimum sum of the artificial variables is not 0 then the original problem has no feasible solution.

Question 10

Big M meth + what is M

Answer 10

Introduce a slack variable for each constraint of the form ≤
Introduce a surplus variable and an artificial variable for each constraint of the form ≥.
For each artificial variable 𝑎1, 𝑎2,𝑎3,… Subtract 𝑀(𝑎1+𝑎2+𝑎3+…)from the objective function where 𝑀 is an arbitrarily large number.
Eliminate the artificial variables from your objective function so that the variables remaining in your objective function are non-basic variables.
Formulate an initial tableau, and apply the simplex method in the normal way.

M is an arbitrarily large number’ is the exact phrase which is required by this question

Question 11

Minimising using big M

Answer 11

Change objective to neg first, then use big M to maximise neg