Linear/Integer Programming

Question 1

How to put a LP problem in standard form?

Answer 1

1. Objective from min to max (*-1)
2. <Slack (+) / >Surplus (-)
3. Constraints RHS to positives (*-1)

Eg:
min z = -50x_1 + 100x_2 to max z = 50x_1 - 100x_2
x_1 + 2x_2 >= 7 to x_1 + 2x_2 - s_1 = 7
x_1 + 2x_2 <= -7 to -x_1 - 2x_2 + s_2 = 7

Question 2

Put this into a Simplex tableau:
Max 2x_1 + 3x_2 + s_1 + s_2 + s_3
S.t. x_1 + s_1 = 30
x_1 + 2x_2 + s_2 = 54
x_2 + s_3 = 20

Answer 2

Basics | z| x_1| x_2| s_1| s_2|s_3| sol
z |1| -2 |-3 |0 |0 |0 |0
s_1 |0| 1 |0 |1 |0 |0 |30
s_2 |0| 1 |2 |0 |1 |0 |54
s_3 |0| 0 |1 |0 |0 |1 |20

Question 3

7 steps to solving Simplex

Answer 3

1. Pivot column (most negative in obj row)
2. Ratio (sol ÷ pivot column)
3. Pivot row (smallest positive number)
4. Pivot number (intersect)
5. Re-write tableau (column var replaces row var)
6. Row operations (pivot # = 1, pivot column = 0)
7. Repeat (until no negatives in obj row)

Question 4

Decision variable definition

Answer 4

The unknown quantities you’re solving for eg: tonnes of silk paint and matt paint.

x_i

Question 5

Coefficients definition

Answer 5

The weight or cost associated with each decision variable eg: £40 profit per tonne of matt paint.

40x_1

Question 6

3 things needed in a LIP problem?

Answer 6

Decision variables - x_i

Linear objective function - c_1x_1+…+c_nx_n

Constraints - a_1x1+…+a_2x_2 =>< b

Question 7

Basic solution

Answer 7

The number of ways that the system of linear equations can be solved without yielding a contradictory result.

Basic solutions aren’t necessarily feasible (don’t meet non-negativity constraint)

n! / m!*(n-m)!

Question 8

Basic variable definition

Answer 8

Variable IS NOT 0 in a basic solution

Question 9

Non-basic variable

Answer 9

Variable is 0 in a basic solution

Question 10

Basic feasible solution

Answer 10

Solution that meets the non-negativity constraints.

Question 11

What is the solution to this Simplex tableau:

Basics | z| x_1| x_2| s_1| s_2|s_3 | sol
z |1| 0 | 0 |1/2 |0 |3/2 |96
s_2 |0| 0 | 0 |1/2 |1 |-1/2|8
x_1 |0| 1 | 0 |1 |0 |0 |30
x_2 |0| 0 | 1 |-1/2|0 |1/2 |12

Answer 11

Z = 96
X_1 = 30
X_2 = 12

Or c_130 + c_212 = 96

8 slack on constraint 2 (s_2)