Maths: Decision 2 (D2)
Linear programming
The simplex algorithm:
- This section uses the following example question:
Maximise P = x + 0.8y,
subject to x + y ≤ 1000
2x + y ≤ 1500
3x + 2y ≤ 2400
Formulation:
- First, create slack variables in place of the inequalities. These can represent any number including zero
x + y + s1 = 1000
2x + y + s2 = 1500
3x + 2y + s3 = 2400 - The objective function also needs to be rearranged so that it is equal to zero:
P = x + 0.8y ⇒ P - x - 0.8y = 0 - Now construct the tableau and fill out the initial values:
P x y s1 s2 s3 RHS 1 -1 -.8 0 0 0 0 0 1 1 1 0 0 1000 0 2 1 0 1 0 1500 0 3 2 0 0 1 2400
Solving:
- First, pick a column (other than RHS) which is negative. In this example, x would be the most logical choice
- Circle this column and divide the RHS by each element in this column:
- 1000 ÷ 1 = 1000
- 1500 ÷ 2 = 750
- 2400 ÷ 3 = 800
- If the element in the pivot column is negative, ignore this for the ratio test, it cannot be a pivot element - Circle the value of x with the smallest non-negative answer to this ratio test - here is is the 2 (because 750 is smaller than 800 and 1000). This number is called the pivot and the column is called the pivot column. Exclude the objective row in the ratio test, an item on this row should not be used as a pivot element
- Draw a horizontal divider below the tableau and start filling out the pivot row on this one (leave gaps for other rows). Divide each value in the pivot row by the pivot element (so that the pivot element becomes 1). This is shown below:
P x y s1 s2 s3 RHS 1 -1 -.8 0 0 0 0 0 1 1 1 0 0 1000 0 2 1 0 1 0 1500 0 3 2 0 0 1 2400 0 1 0.5 0 0.5 0 750 - Now, make all values in the pivot column 0. Do this by combining multples of the pivot by the values in each row
- For example, for the top row, the -1 needs to be made equal to 0
- By adding 1 × the pivot row element in that column, this x value can be made equal to zero
- Repeat this same operation for the rest of the row, to get P = 1, y = -0.3, s1 = 0, s2 = 0.5, s3 = 0, RHS = 750
- This is now put into the tableau and repeated for each of the other rows:P x y s1 s2 s3 RHS 1 -1 -0.8 0 0 0 0 0 1 1 1 0 0 1000 0 2 1 0 1 0 1500 0 3 2 0 0 1 2400 1 0 -0.3 0 0.5 0 750 0 0 0.5 1 -0.5 0 250 0 1 0.5 0 0.5 0 750 0 0 0.5 0 -1.5 1 150 - This is not yet solved - there are still negative numbers on the top row. Therefore, this process must be repeated (starting from selecting a new pivot) until the top row only contains positive numbers
- The final tableau is shown below:
P x y s1 s2 s3 RHS 1 -1 -0.8 0 0 0 0 0 1 1 1 0 0 1000 0 2 1 0 1 0 1500 0 3 2 0 0 1 2400 1 0 -0.3 0 0.5 0 750 0 0 0.5 1 -0.5 0 250 0 1 0.5 0 0.5 0 750 0 0 0.5 0 -1.5 1 150 1 0 0 0 -0.4 0.6 840 0 0 0 1 1 -1 100 0 1 0 0 2 -1 600 0 0 1 0 -3 2 300 1 0 0 0.4 0 0.2 880 0 0 0 1 1 -1 100 0 1 0 -2 0 1 400 0 0 1 3 0 -1 600 - Finally, the solutions can be read off the final tableau
- If a column only contains 0s and 1s (a basic variable), it will be on the RHS column in the location of the 1. Otherwise, it will have a value of zero (a non-basic variable)
- Because the P column only contains 0s and 1s, it will be in the RHS column. The 1 is in the first row so its value is the RHS value from the top row - 880
- The x column also only contains 0s and 1s, so its value is 400 (the 1 is in the 3rd row)
- Similarly, y is equal to 600 (4th row)
- s1 contains some numbers that are not 0s or 1s. Therefore, its value must be zero
- s2, however, must be 600
- s3 is also 0
The two-stage simplex algorithm (for problems involving ≥):
- Maximise P = x + 0.8y,
subject to x + y ≤ 1000
2x + y ≤ 1500
3x + 2y ≤ 2400
x + y ≥ 800
Formulation:
- Slack variables:
x + y + s1 = 1000
2x + y + s2 = 1500
3x + 2y + s3 = 2400
For the last constraint, x + y - s4 = 800. However, s4 will be -1, so an artificial variable is required; x + y - s4 + a1 = 800 - Another objective is needed, A
- Let A be equal to the sum of artificial variables, in this case 1
- Now substitute A for a1 (etc) to get the new objective, A + x + y - s4 = 800 - Therefore, the starting tableau is
A I x y s1 s2 s3 s4 a1 RHS 1 0 1 1 0 0 0 -1 0 800 0 1 -1 -0.8 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1000 0 0 2 1 0 1 0 0 0 1500 0 0 3 2 0 0 1 0 0 2400 0 0 1 1 0 0 0 -1 1 800
Solving:
- In a two-stage simplex, the most positive element must be selected from the top row for the pivot column. Therefore, it must be x or y. We'll choose x for this example
- The ratio test is used like with the standard simplex algorithm, and the smallest is row 4 (1500 ÷ 2 = 750). As usual, this row is divided by two and the rest of the tableau is also transformed in the same way to get the below:
A I x y s1 s2 s3 s4 a1 RHS 1 0 1 1 0 0 0 -1 0 800 0 1 -1 -0.8 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1000 0 0 2 1 0 1 0 0 0 1500 0 0 3 2 0 0 1 0 0 2400 0 0 1 1 0 0 0 -1 1 800 1 0 0 0.5 0 -0.5 0 -1 0 50 0 1 0 -0.3 0 0.5 0 0 0 750 0 0 0 0.5 1 -0.5 0 0 0 250 0 0 1 0.5 0 0.5 0 0 0 750 0 0 0 0.5 0 -1.5 1 0 0 150 0 0 0 0.5 0 -0.5 0 -1 1 50 - The y coefficient is still negative though, so further pivots are possible. The current solution at this stage is actually infeasible - it does not satisfy all of the constraints
- Once all values in the first objective row are negative (excluding A), a feasible solution has been reached, but not the optimal solution
- Now, the first row, A column and artificial variable columns can be removed, to reach the tableau shown below:
I x y s1 s2 s3 s4 RHS 1 0 0 0 0.2 0 -0.6 780 0 0 0 1 0 0 1 200 0 1 0 0 1 0 1 700 0 0 0 0 -1 1 1 100 0 0 1 0 -1 0 -2 100 - Finally, use the standard simplex algorithm to remove all negative numbers from the top row. After this, the optimal vertex will be found and can be read off as usual
The big M method (also for problems involving ≥):
- Maximise P = x + 0.8y,
- Instead of introducing a new objective like in the two-stage simplex, it is modified with an M
- The M represents a very large number
- P = x + 0.8y - Ma1
x + y - s4 + a1 = 800 ⇒ a1 = 800 - x - y + s4
P = x + 0.8y - M(800 - x - y + s4)
P = x + 0.8y - 800M + Mx + My - Ms4
P = (1 + M)x + (0.8 + M)y - Ms4 - 800M
P - (1 + M)x - (0.8y + M)y + Ms4 = 800M - Construct a tableau:
P x y s1 s2 s3 s4 a1 RHS 1 -(1 + M) -(0.8 + M) 0 0 0 M 0 -800M 0 1 1 1 0 0 0 0 1000 0 2 1 0 1 0 0 0 1500 0 3 2 0 0 1 0 0 2400 0 1 1 0 0 0 -1 1 800 - Since M is large and positive, -(1 + M) and -(0.8 + M) are both negative
- After the required number of pivots, only the a1 column will contain M
- Finally, delete the a1 column and finish by using the standard simplex algorithm
subject to x + y ≤ 1000
2x + y ≤ 1500
3x + 2y ≤ 2400
Therefore:
x + y ≥ 800
x + y + s1 = 1000
2x + y + s2 = 1500
3x + 2y + s3 = 2400
x + y - s4 + a1 = 800
Equality constraints:
- If a constraint is, for example, x + y = 100, this can be dealt with by creating two constraints:
x + y ≤ 100 and x + y ≥ 100 - The big M method is generally easier for equality constraints than the two-stage simplex
Networks
Floyd's algorithm:
- Floyd's algorithm can be used to find the shortest path between any two vertices
- Vertices must be numbered and not marked with letters
- This algorithm has a cubic complexity (the same as applying Dijkstra's algoritm for each vertex individually)
- Two matrices are needed; a distance/weight matrix and a route matrix
- The distance matrix gives the distance from any start vertex to a destination vertex
- The original distance matrix should only contain the lengths for arcs directly connecting vertices
- Pairs of vertices with no direct connection are marked with infinite length (or a dash)
- The route matrix lists the route to get from a start node (y-axis) to a destination node (x-axis)
- Initially, the route matrix is like below (but possibly with more/less rows and columns depending on the number of vertices:
ROUTE MATRIX1 2 3 4 1 1 2 3 4 2 1 2 3 4 3 1 2 3 4 4 1 2 3 4
- For example, to get from vertex 2 to vertex 4, look for column 4 on row 2. In this case, it's a 4, which is the required destination vertex. If this was not a 4, the next step would be to repeat the process with the 4th row
Floyd′s algorithm example:
- First, highlight the first row and column. Start a new distance matrix and fill out this row and column in the new matrix
- For each other space in the new matrix, add the numbers in the first row/column to the left and above that element. For example, for (2, 2), add 7+7. If it is smaller than the existing value in that element, replace and circle/mark it. 7+7=14 is smaller than the infinity currently in that spot, so replace it with 14
- Once this is complete, create a new route matrix. In the locations of the changed values in the distance matrix, write the value of the element in the same row and 1st column (because it's the first iteration) of the route matrix. The completed first iteration is shown below with changed elements in bold
DISTANCE MATRIX 1 2 3 4 5 1 - 7 3 5 - 2 7 14 3 12 1 3 3 3 6 8 6 4 5 12 8 10 3 5 - 1 6 3 - ROUTE MATRIX 1 2 3 4 5 1 1 2 3 4 5 2 1 1 3 1 5 3 1 2 1 1 5 4 1 1 1 1 5 5 1 2 3 4 5 - For the second iteration, highlight the second row and column and continue as before. Once the nth iteration is reached (where n is the number of vertices), stop. The below matrices show the result of the final (5th) iteration:
DISTANCE MATRIX 1 2 3 4 5 1 6 6 3 5 7 2 6 2 3 4 1 3 3 3 6 7 4 4 5 4 7 6 3 5 7 1 4 3 2 ROUTE MATRIX 1 2 3 4 5 1 3 3 3 4 3 2 3 5 3 5 5 3 1 2 1 2 2 4 1 5 5 5 5 5 2 2 2 4 2 - The final distance matrix shows the distances between any two points. For example, the distance from vertex 3 to vertex 4 is 7
- The route matrix shows how to follow these routes. To get from 3 to 4, find the 3rd row and 4th column, 2. Now find the 2nd row and 4th column, 5. Finally find the 5th row and 4th column, 4. Therefore, the route from vertex 3 to vertex 4 is 3→2→5→4
- This can be confirmed by drawing the network
| 1 | 2 | 3 | 4 | 5 | |
| 1 | - | 7 | 3 | 5 | - |
| 2 | 7 | - | 3 | - | 1 |
| 3 | 3 | 3 | - | - | 6 |
| 4 | 5 | - | - | - | 3 |
| 5 | - | 1 | 6 | 3 | - |
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 1 | 2 | 3 | 4 | 5 |
| 3 | 1 | 2 | 3 | 4 | 5 |
| 4 | 1 | 2 | 3 | 4 | 5 |
| 5 | 1 | 2 | 3 | 4 | 5 |
The travelling salesperson problem:
- Travelling salesperson algorithms find the shortest way to travel through every vertex at least once in a round trip
- Trying every combination for the optimal solution is not feasible, since the number of possible tours is (n-1)!/2 where n is the number of vertices
- The practical problem can be converted into the classical problem by replacing the network by a complete network of shortest distances
Solving a travelling salesperson problem:
- The lower bound, L is less than or equal to the length of the shortest tour
- To find the lower bound, do the following for every vertex of the complete network
- Remove the vertex
- Complete a minimum connector of the remaining vertices (see the algorithms in D1)
- Add in the two shortest deleted arcs
- After finding values for each deleted vertex, the lower bound will be the largest of these - The upper bound is greater than or equal to the length of the shortest tour
- To find the upper bound, use the nearest neighbour algorithm:
- Start at an arbitrary vertex
- From the vertices not already in the sequence, find the nearest vertex (pick one if there is a tie)
- Repeat the previous step until all vertices are connected, then add in the shortest route to get to the starting vertex
- This can be used for an upper bound
The Chinese postperson problem - route inspection:
- In this problem, every vertex and arc must be visited
- An odd node has an odd number of arcs connected to it
- An even node has an even number of arcs connected to it
- All networks have an even number of odd nodes
- A traversable/Eulerian network can be drawn without removing the pen from the paper or tracing the same arc twice
- A network is only traversable if:
- It has 0 odd nodes to finish and start at the same node
- It has 2 odd nodes to finish and start at different nodes - Therefore, if a network has no odd nodes, the minimum distance is simply the sum of all arc lengths
- Otherwise, the method is as follows:
- Locate all odd nodes (there will be an even number of these)
- Pair these nodes so that the sum of the distances between these nodes is as short as possible
- The arcs connecting these must be traversed twice. This can be visualised by drawing an extra arc by each one
- Find the total distance by summing all arc lengths, including the extra ones between the pairings
Complexity:
- The number of possible pairings is shown below for some numbers of odd nodes:
- 2 odd nodes: 1 pairing
- 4 odd nodes: 3 pairings
- 6 odd nodes: 15 pairings
- 8 odd nodes: 105 pairings
- 10 odd nodes: 945 - This can be written as:
Which is the same asn - 1 × n - 3 × n - 5 ...; for example, with 10 odd nodes, 9 × 7 × 5 × 3 × 1 = 945 - This is called factorial complexity. Because the number of pairings is very high for large networks, a heuristic algorithm may be best, which won't always guarantee the optimal solution
Logic
Notation:
- NOT (negation): ~
p ~p 0 1 1 0 - AND: (conjunction): ∧
p q p ∧ q 0 0 0 0 1 0 1 0 0 1 1 1 - OR: (disjunction): ∨
p q p ∨ q 0 0 0 0 1 1 1 0 1 1 1 1 - Equivalence: ⇔
p q p ⇔ q 0 0 1 0 1 0 1 0 0 1 1 1 - Implication: ⇒
p q p ⇒ q 0 0 1 0 1 1 1 0 0 1 1 1 - Sufficiency: ⇐
p q p ⇐ q 0 0 1 0 1 0 1 0 1 1 1 1
Proofs:
- If a proposition is always true, with every combination of input values, it is called a tautology
- To prove that two statements are equivalent, either construct two truth tables and compare the end values, or create a nested truth table and check that every value in the ⇔ column is a 1
Boolean algebra rules:
- Identity:
- p ∧ 1 = p
- p ∧ 0 = 0
- p ∨ 0 = p
- p ∨ 1 = 1 - Associative:
- (p ∨ q) ∨ r = p ∨ (q ∨ r)
- (p ∧ q) ∧ r = p ∧ (q ∧ r) - Commutative:
- p ∨ q = q ∨ p
- p ∧ q = q ∧ p - Distributive:
- p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
- p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) - De Morgan's rules:
- ~(p ∨ q) = ~p ∧ ~q
- ~(p ∧ q) = ~p ∨ ~q - Complement:
- p ∨ ~p = 1
- p ∧ ~p = 0 - Absorption:
- p ∧ p = p
- p ∨ p = p
- p ∧ (p ∨ q) = p
- p ∨ (p ∧ q) = p
Logic gates:
- NAND is the same as an AND gate followed by a NOT gate
- NOR is the same as an OR gate followed by a NOT gate
- NAND and NOR gates are universal; combinations can be used to make all other types of gate
Decision trees
Decision trees:
- Rectangles (decision nodes) represent stages where a choice must be made
- Triangles represent outcomes and the final value if this outcome if reached should be written next to them
- Circles (chance nodes) denote stages where change determines the outcome
- Expected monetary value (EMV) can be calculated by summing chance of each outcome multiplied by its end value
- This should be written in the chance nodes - For every decision node, cross (use double perpendicular lines) every path which has a lower monetary value than the highest, and write the highest inside the decision node
- Utility can be used to compare outcomes taking into account wealth of the decision maker
-utility = √wealthis an example of a utility function, although this varies depending on the decision maker
- It is always an increasing function, but generally with the gradient decreasing as wealth increases