Decision 2

supply

The capacity of each of the supply points (or sources) - the quantity of goods that can be produced at each factory or held at each warehouse.

demand

The amount required at each of the demand points (or destinations) - the quantity of goods that are needed at each shop or by each customer.

transportation algorithm

north-west corner method

what to do if total supply > total demand

add a dummy demand point

what to do if If total supply < total demand

add a dummy supply point

demand or supply dummy

In each case the demand or supply at the dummy is chosen so that total demand is equal to total supply, and the transportation costs to/from the dummy location are all zero.

when is a solution degenrate

In a feasible solution to a transportation problem with m rows and columns, if the number of cells used is less than n + m - 1, then the solution is degenerate. This will happen when an entry, other than the last, is made that satisfies the supply for a given row, and at the same time satisfies the demand for a given column. The algorithm requires that n + m - 1 cells are used in every solution, so a zero needs to be placed in a currently unused cell.

hwo to find shadow costs

improvement index

The improvement index in sending a unit from a source P to a demand point Qis found by subtracting the source cost S(P) and destination cost D(Q) from the stated cost of transporting one unit along that route C(PQ): Improvement index for PQ = 1pQ = C(PQ) - S(P) - D(Q) The route with the most negative improvement index will be introduced into the solution. The cell corresponding to the value with the most negative improvement index becomes the entering cell (or entering square or entering route) and the route it replaces is referred to as the exiting cell (or exiting square or exiting route).there are two equal potential entering cells you may choose either. Similarly, if there are two equal exiting cells, you may select either. Π If there are no negative improvement indices the solution is optimal.

stepping stone method

exiting cell

One entry that has been reduced to 0 by the steppingstone method is called the exiting cell, and should be left blank in the improved solution.

linear programming for transortation roblems

sully constraints linear rogramming

<-

linear rogramming demand constraints

>-

why cant you apply simplex to transportation problems

as >- constraints so no basic feasible solution

how to reduce cost matrix

• subtract the least value in each row from each element of that row

• using the new matrix subtract the least valye in each column from each element in that column

the Hungarian algorithm

how to solve allocation problem which is not n x n

introduce dummy rows or dummy columns with zero entries

how to maximise in allocation roblem

make everything negative then do row reduction and column reduction

what to do if incomplete data in Hungarian algorithm

you can enter a large value into the matrix at the appropriate place.

how to set out linear rogrammign of allocaiton rovblem

what to do wehn maximisation and incomlete data

relace with small number

when is a vertex a source in flows and networks

if all arcs connect are directed away

when is a vertex a sink in flows and netwroks

if all arcs connected are directed towards

2 conidtions in flows and netwoeks

• feasibility - flow along each arc must not exceed the capacity of that arc

• conservation- total flow into vertex=total flow out of vertex

what do we call an arc with flow equal to capacity

saturated

value of flow d

sum of all flows along all arcs leaving source vertex or entering sink vertex

cut

set of arc whose removal seperates the network into two parts

capacity of a cut

sum of the capacities of the arcs flowing to the sink

arcs flowing out of cut

contribute zero to capacity of cut

forward arrow labelling

amount by which the flow can be increased by

backward arrow labelling

amount in which the flow in arc can be reduced

when is the flow maximal

equal to value of minimu cut

what does minimum cut pass through

saturated arcs directed from source to sink

empty arcs directed from sink to source

what do the numbers represent in capacitated directed network

first number represent lower capacity and second number represents upper capacity

what does it mean if the maximum total flow into a vertex is equal to minimum total flow out of that vertex

arcs into that vertex are at their upper capacities

arcs out of that vertex are at their lower capacities

what does it mean if the minimum total flow into a vertex is equal to maximum total flow out of that vertex

arcs into that vertex are at their lower capacities

arcs out of that vertex are at their upper capacities

capacity of a cut in a netwrok with lower capacities

sum of the upper capacities crossing from the source to sink minus the sums of the lower capacities crossing the cut from sink to the source

what must supersource be

arcs leading from supersource to each source must have capacity and flow equal to total capacity and total flow leaving that source

what must supersink be

arcs leading from each sink to the supersink must have capacity and flow equal to the total capacity and total flow arriving at that sink

capacities on supersource

Each arc from the supersource to a source must have a lower capacity equal to the sum of the lower capacities of the arcs leaving the source and an upper capacity equal to the sum of the upper capacities of the arcs leaving the source.

capacities on supersink

Each arc from a sink to the supersink must have a lower capacity equal to the sum of the lower capacities of the arcs entering the sink and an upper capacity equal to the sum of the upper capacities of the arcs entering the sink.

what to do if a node has restricted capacity

it may be replaced by two nodes joined by an arc of that capacity. Flow problems for the network can then be solved in the usual way.

what to do if node is blocked

the node and any arcs linked directly to it may be removed from the network.

stage when finding optimal solutions to network problems using dynamic programming

The route from the initial state (S say) to the final state (T say) is made up of a sequence of moves. Each move is a stage. The stage tells you how 'far' you are from the destination vertex.

state when finding optimal solutions to network problems using dynamic programming

This is the vertex that you are considering at each point.

action when finding optimal solutions to network problems using dynamic programming

This is the directed arc from one state to the next. In selecting an arc you are considering what happens if you do that action.

destination when finding optimal solutions to network problems using dynamic programming

This is the vertex you arrive at having taken the action.

value when finding optimal solutions to network problems using dynamic programming

This is the sum of the weights on the arcs used in a sequence of actions.

how to do dynamic programming for network problems

In dynamic programming you work backwards from T in a series of stages.

• The vertices immediately before T are examined. These are the stage 1 vertices. The best route from these to T is noted.

Then move back a stage, away from t and towards S, to the stage 2 vertices. Routes from these vertices must pass through one of the stage 1 vertices to get to T. Use this to help you find the optimal route from each stage 2 vertex to T.

Then move back a stage and repeat the process, until you reach S.

The principle of optimality is used at each stage. The current optimal paths are developed using the paths found in the previous stage.

minimax route

A minimax route is one in which the maximum value of the individual arcs used is as small as possible.

how to do minimax route

find max of each action and select minimum of these actions for each state

maximin orute

A maximin route is one in which the minimum value of the individual arcs used is as large as possible.

how to do maximim route

find min of each action and select max of these actions for each state

stage when finiding otimal solution to roblems in a table

A time interval or an option being considered.

state when finiding otimal solution to roblems in a table

The value of a resource available from a previous stage.

action when finiding otimal solution to roblems in a table

The amount of the resource used in the current stage.

destination when finiding otimal solution to roblems in a table

The value of the resource passed to the next stage.

value when finiding otimal solution to roblems in a table

he numerical value of the quantity to be optimised.

2 person game

only 2 parties can play

what does a player do to play safe

each player looks for the worst that could happen if they make each choice in turn

the player then picks the choice that results in the least worst option

pure strategy

strategy in which a player always makes the same choice

zero sum game

the 2 entries in each cell in the pay-off matrix add up to zero

play safe strategies for player 1

row containing row maximin

playsafe strategy for B

column containing column minimax

row maximin

• maximum of the minimum values in each row

• find the min valye for each row and choose the largest of these

column minimax

• minimum of the maximum value in each column

• find the maximum value for each column and choose the smallest of these

when is there stable solution

row ,maximin =column minimax

saddle point

value which is the smallest in its row and largest in its column

hwat it means if stable solution

• must occur when both players adopt their play safe strrategies

• value of the game to player a is eqaul to the row maximin

• value of the game to B is equal to the negative of the column minimax

when can a row be deleted

If every entry in row p is greater than the corresponding entry in row 4 then you can say that row p dominates row q. In this case, row q may be deleted as it would never be chosen.

when can a column be deleted

if every entry in column r is less than the corresponding entry in column s then you can say that column r dominates column s. in this case column s may be deleted as t would never be chosen.

what is the optimal mixed strategy for a

The optimal mixed strategy for player A is the mixed strategy that maximises the minimum expected pay-off for all possible actions by player B.

how to find optinmal mixed strategy for player with 2 choices in 2 x n or n x 2 game

set the probability of one choice as p, so that the probability of the other choice is 1 - p. Find the expected winnings in terms of p. Draw a graph showing the expected winnings as straight lines. Choose the intersection point that maximises the minimum winnings.

what is the value to b if vale to a a is v

-v

where is optimal solution on graph when more than 2 lines game theory

highest point of intersection with no lines udnerenah

how to formulate game as linear rogrammin roblem

Transform the game by adding n to each value so that all of the values are non-negative. Define the decision variables. Watch out YoWrite (the value of the new game, with added) and set the objective to maximise V. Write down the constraints.

order of a recurrence relation

difference between the highest and lowest subscripts in the relation

first order recurrence relation

un can be given as a function of n and un-1 only

how can a first order linear recurrence relation b ewritten

when is a first order linear recurrence relation homogenous

g(n) = 0

how to solve un =aun-1

un=c(a^n)

how to solve un = un-1 + g(n)

how to solve recurrence relation un=aun-1 + g(n)

• Find the complementary function (C.F.), which is the general solution to the associated homogeneous recurrence relation = aun-1

• Choose an appropriate form for a particular solution (P.S.) then substitute into the original recurrence relation to find the values of any coefficients.

• The general solution is un = C.F. + P.S.= ca^n + P.S.

• Use the initial condition to find the value of the arbitrary constant.

particular solution when solving aun-1 + g(n) when g(n) is p with a ≠ 1

λ

particular solution when solving aun-1 + g(n) when g(n) is pn + q with a ≠ 1

λn + μ

particular solution when solving aun-1 + g(n) when g(n) is kp^n with p ≠ a

λp^n

particular solution when solving aun-1 + g(n) when g(n) is ka^n with

λna^n

particular solution when solving aun-1 + g(n) when g(n) is p with a = 1

λn

particular solution when solving aun-1 + g(n) when g(n) is pn+q with a = 1

λn² + μn

second order linear recurrence relation form

when is a second order linear recurrence relation homogfenous

g(n)=0

if un = f(n) and un=g(n) are particular solution ti a linear recurrence relation what eles is a solution

how to find solution to second order order homegenous linear recurrence relation of form un=aun-1 +bun-2

r² -ar -b =0

form of un if 2 real roots of second order homogenous auxilliary

form of un if repeated root of second order homogenous auxilliary

form of un if comlex roots of second order homogenous auxilliary

how to solve recurrence relation un=aun-1 +bun-2 +g(n)

particular solution when solving aun-1 + bun-2 +g(n) when g(n) is j