Management Science Recall Questions

Management Science Recall Questions

Linear Programming, Integer Programming, Graph Theory, Decision Analysis
Ready to Publish
Ready to Publish
Publish on
Mar 17, 2021
Hide Page Cover
Hide Page Cover
View Table of contents

1 - Intro

What is a model?
A simplified version of the real world
What are the three different types of Models?
notion image
How does a break even analysis work?
Find the point where revenue equals costs
What are fixed costs / varible costs?
When do we have underagre costs when overrage costs?
  • Demand < Q (ordered) β†’ Overrage
  • Demand > Q (ordered) β†’ Underage
What are the most common management science techniques?
notion image
Difference between probabilistic techniques and mathematical models?
  • Probabilistic = Uncertain outcomes of solutions, there is a certain probability that another solutions is the outcome than the one we expect.
  • Mathematical = Deterministic solutions, as we assume to know each outcome / solution with certaincy.

2 - Linear Programming

Intro and Graphical solving

What are decision variables?
Mathematical variables that represent levels of activity of a firm. E.g. production quantitites
Are decision variables part of every model?
No. There are models that don't have to do with any decision variables
What is an objective function?
The objective of a firm in relation to the decision variables. Either min or maximazation
What are (model) contraints?
Restrictions in the firms production process. E.g limited ressources, labor, capital, time,...
What are non-negativity contraints?
A constraint that restricts that a decision or slack variable becomes negative.
When is a solution called feasible? How can you test, if a solution is feasible?
If the combination of variables that results does not violate any of the contraints.
What is the basic feasible solution?
The value "z" equals to after you set all the non basic varibales equal to 0.
An optimal solution is always feasible?
A LP can have 3 solutions?
No, it can have one, infinite or an unbounded amount of solutions
A basic solution is always feasible?
Yes, this is a variable combination that needs to be feasible in order to be called basic.
To what kind of models is the graphical solving method of linear programs restricted?
Programms with only two decision variables
What are the steps of graphically solving a linear program?
  1. Plot the contrainst in the graph and shade the feasible area
      • As those are linear functions, we can graph them by finding two points that are on the line
      • Find two points by first setting e.g x1 = 0, then x2 = 0 and solving for the other variable respectively
  1. Locate point of optimal feasible solution
      • Draw objective function for arbitrary profit (z) value. Set the objective function = something random.
      • Solve for x2 and shift around the objective function, to see which point in the graph has optimal intersection
  1. Find optimal x1 and x2 values
      • Once you now where in the graph the optimal solution is, e.g intersection x1 and x2, you can find that point by setting both equations equal to each other and solving for both variables.
What are extreme points?
The corner points of the feasible region. One of those corners will likely be the optimal feasible solution.
What are the different special cases for solutions of a linear program?
  1. Multiple (infinite) optimal solutions (alternate optimal solution)
      • Objective function is parallel to one of the contrainst
      • Notation with lambda
        • notion image
          notion image
  1. Unbouded optimal solution
      • The solution space is not closed in by the contraints.
      • The OF can shift endless towards a certain direction
  1. Empty Optimal solution / infeasible
      • No solution will satisfy all of the contraints
What are slack varibles and what are they used for?
  • A variable with is added or subtracted from a contraint to turn an inequality into an equality
  • It represents the unused resources in a certain contraint based on a certain basis mix of variables
  • If is there nothing produced of any variable, we are in the origin. Here the value of the slack variable is equal to the amount of available e.g ressources.
How does the standart / normal form of a linar program look like?
  1. Maximazation problem β†’ Max objective function
  1. Constraints are equalities
  1. All variables are non-negative
  1. The RHS of the contraints are non-negative
What is the difference between the optimal solution of a maximazation vs a minimization problem?
  • Maxi β†’ Optimal point is the farthest from the origin. OF shifts away from origin
  • Mini β†’ Optimal point is the closest to the origin. OF shifts towards the origin
What are surplus varibales and what are then used for?
  • A positive variable that is subtracted from the contraint to neutralize β‰₯ situations.
  • The surplus variable shows the excess return above the minimum requirement of each contraint based on a certain decision variable solution.
What are 2 requirements for linear programs to be solveable?
  1. Proportionaliity β†’ Slope is constant
  1. Divisible β†’ Variables can't be restricted to integers

Computer Solution and Sensitivity Analysis

What is the simplex algorithm?
Procedure involving mathematical steps to solve linear programming problems. We only change one varibale at the time and determine new feasible solutions with each step
How does the cannonical normal form look like and how is it different from the normal form?
notion image
What kind of variable do we have if the constraint is of the form x1 + x2 = 3?
An artificial Mx3 Variable.
  • OF looks as follows: x1 + x2 + Mx3
  • Constraint x1+ x2 + Mx3 = 3
What are the steps of solving an LP with the simplex algorithm?
notion image
notion image
The selection of the pivot row in the simplex uses non-negativity contraints?
Yes, as we are dividing the RHS of the constraints by the pivot column elements to see which one is restriciting the non-negativity constraint.
When do we stop with another interation of the simplex?
As soon as all the elements in the optimal function row are positive. There are only subtractions in the objective function left. No change of variables would increase the OF Value anymore.
What is the basis?
Set of all basic variables
What is the basic solution?
Set of all varibales. Basic and Non-basic
The coefficients of the basic variables in the objective functions are always zero.
Yes, basic variables always have a coefficient of 0 in the OF.
What are and how can you see the different special cases of LP solutions in the simplex tableau?
No feasible solution
Infinite amount of solutions
  • A non-basic variable has 0 as a coefficient.
Unbound feasible solution
  • In the final tableau there is still a negative number left, but there is no element in the column which this can be divided through.
  • If you solve the OF row for Z, you will see that this variable can be enlarged limitless without violating any of the contraints
    • notion image
Primal degeneration (3 intersections)
  • A basic variable has the value 0
An LP has an infinite number of solutions if there are no positive values in the pivot column.
Wrong, in this case the solution is unbounded
What effect does an additional input on the RHS of any contraint have, if the corresponding slack variable is not in the final OF?
  • Non-Binding variable
  • There is no effect, as there is no variable that could change in the OF
    • β‡’ No shadow price
      notion image
What effect occures, if the corresponding slack variable is indeed in the final OF?
  • Binding Variable
  1. Reformulate the OF for Z
  1. You will need to insert this variable - 1 e.g. instead of the current variable in the OF.
  1. Then you multiply the coefficient of that variable with the the and will see that there will be a positive number resulting. Negative coefficient * (-1)
    1. β‡’ This number is called shadow price.
      • The smaller this number, the fewer the costs that occur or fall away due to a change of the available e.g ressources.
      notion image
  1. You can test the effect of changing the input on the RHS by just one on any of the other equations in the final tableau.
    1. notion image
What effect on the optimal solution does it have, if you decrease the available ressources of a contraint by 10, whose slack variable has a value of 20 with the optimal solution obtained?
  • There is no effect on optimal solution, as the current optimal solution leads to surplus of 20 in the corresponding contraint. The ressources available in e.g a certain production step, based on the production quantities that are optimal, are not fully used. There are 20 additional units
  • Now if we reduce the available capacity by 10, this won't change anything, as there is still a slack of 10 in this specific contraint.
  • If we would reduce by a total of 20 or more, then the optimal basic solution must need to change, as the current optimal solution would violate the respective contraint.
What are reduced costs?
In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution
  • Often related to non-basic variables. We want to find out by how much the corresponding profit or cost margin of the corresponding variable needs to change, so that it would make sense to increase it from 0 to 1.
notion image
What is sensitivity analysis?
The analysis of the effect which a change of a certain parameter in e.g a production has on the optimal solution.
What is the sensitivity range?
Finding the range of values a certain parameter can take on without changing the first optained optimal solution.
  • If we are testing the sensitivity of OF coefficients, we are basically testing by how much we can change the slope of the OF so that the optimal intersection point remains optimal.
What are the types of sensitivity analysis?
Change in objective function coefficients
  • Change in coefficient could e.g be a change in the profit margin of a good.
  • Also changing coefficients changes the slope of the OF line. Increasing coefficients, makes the line steeper
Steps of finding this range graphically
  1. Write a βˆ† in front of the coefficient of the starting OF.
    1. notion image
  1. Determine whether the choosen decision variable is a basic or non-basic variable
  1. If basic, then look at the row corresponding to the variable and reformulate it, so that the variable is isolated
    1. notion image
      If non-basic variable in final tableau, e.g x4 above, just add +βˆ† to the reformulated OF. There is no need to reformulate any equalities before, as there are no functions to reformulate.
  1. Multiply the whole equality with βˆ†.
  1. Add βˆ†variable to the final OF. Reformulate the equation and group together corresponding variables
  1. Factor the variables of the non-basic constraints, so that you only have (βˆ† + numer) left.
    1. notion image
  1. Recall that the solution OF only remains optimal, as long as the coefficients in the tableau remain positive. Thus set this βˆ† + ... β‰₯ 0 and solve for βˆ†
  1. As there are likely more than one non-basic variable, you will have multiple results for βˆ†
  1. Determine your upper bound βˆ† and lower bound βˆ†
  1. Add the upper and lower bound to the coefficient of the decision variable choosen in the beginning β‡’ You will get the range by which e.g the profit margin can change.
    1. notion image
What are the steps of finding the sensitivity using the mathematical model?
  1. If Xs is a basic variable in the final tabeau (x β‰  0)
    1. Chose the corresponding row to the variable in the final tableau
    2. Create the Sets .
        • J is the set containing all nonbasic (x = 0) variables from the row we chose.
    3. Determine βˆ† max (upper bound) with:
      1. notion image
        • Upper βˆ† is ∞, if the is empty
    4. Determine βˆ† min (lower bound) with:
      1. notion image
        • Lower bound is ∞ if is empty.
    5. Add the values for βˆ† to the corresponding coefficient of the variable we chose in the starting objective function and state in what interval range the coefficient can change.
      1. notion image
  1. Xs is a nonbasic variable in the final objective function (x = 0)
    1. We determine the value for delta that we can add to the corresponding nonbasic variable in the starting objective function just by using the condition:
      1. notion image
        • As long as βˆ† is smaller than the gamma, the optimal solution will remain the same
          • y represents the coefficients of the objective function in the final tableau. s will determine which variable we need to look at and what the corresponding coefficient in the objective function is
Change of the RHS of the contraints
  • Change in e.g the available material or time
  • Shifting the whole line of the contraint to the right or left without changing the optimal solution
Graphical solution
  1. CASE 1: Varible is non-basic in final tableau
    1. Add βˆ† to the RHS of the corresponding constraint
    2. Subtract it and find the corresponding slack variable (which now is )
      1. notion image
    3. Exchange with the corresponding variable in the OF.
    4. Recall that the other non-basic variables are 0, thus you are left with
      1. notion image
    5. Make use of the non-negativity constraint, and recall that x3 β‰₯ 0. Thus set the whole equation β‰₯ 0 and solve for βˆ†.
      1. notion image
    6. This is a lower bound as the number is negative. Now we need to add this negative number to RHS of the corresponding constraint in the start LP.
      1. notion image
    7. We can lower the available ressources down to 58 without affecting the optimal solution.
Mathematical solution
  1. Add βˆ† to RHS and find corresponding slack variable
  1. Find the Column corresponding to this variable in the final tableau
  1. Set up I+, I- and I0 (Here x4)
    1. notion image
  1. Find the upper and lower bound of the RHS using the following formula
    1. notion image
  1. Add βˆ† to the RHS to the get sensitivity interval (bi = RHS)
    1. notion image
Changing the value of an input parameter leads always to a new optimal base.
If the shadow price of a resource is zero, then additional units of the resource will improve the optimal solution.
Wrong, only if the shadow price is postive, there will be a benefit by adding an additional ressource.
If the coefficient of an optimal non-basic variable in the objective function is reduced then the optimal value of the objective function is increased.
No, a change in the coeffient of a NBV does not necessarily lead to a change in the OF value

3 - Integer Programming

What are the three types of integer programs?
  1. Total integer program
      • All variables are integers
  1. 0-1 program (binary program)
      • All variables are either 0 or 1
  1. Mixed integer program
      • Some variables are integer but not all
      • E.g warehouse-location problem
In an binary program what does x1 + x2 ≀ 1 mean?
  • Contingency contraint
  • Also mutually exclusive contraint
  • Either or relationship between x1 and x2
  • Only one of both can be produced. However also non of the two can be produced.
What changes if x1 + x2 = 1? How do you call such a constraint?
  • Multiple-choice constraint
  • You need to choose either x1 or x2, but only one of them
  • Here there is no option to not produce either one of them
How do you call a constraint of the type x1 ≀ x2?
  • Conditional constraint / (also contigent?)
  • The existance of the good behind x1 does depend on x2
  • Only if x2 is e.g 1 (or choosen), x1 can be 1 as well
  • If x2 is 0 (or not choosen) x1 can only be 0 as well.
What changes if you have x1 = x2?
  • Corequisite constraint
  • If one good is produced, the other one needs to be produced as well
  • Both need to equal the same value
State the decision variables, OF, and constraints of a normal knapsack problem
notion image
What are the steps of solving this problem with the heuristic approach and rounding?
  1. Calcualte the utility/weight ratio of each entry in the table.
    1. notion image
  1. Sort according to highest ratio
    1. notion image
  1. Set up a new table and start adding each item, starting with the highest u/w ratio while keeping track of total weight.
  1. Once the weight constraint would be violated, don't add a complete unit of the item, but calcualte the fraction of the item that would still fit in the bag without violating the weight contraint. β‡’ continous solution
    1. notion image
      • Get the fraction amount by using cross multiplication
  1. Get a feasible solution by rounding down (diskret solution) = not optimal
What are the properties of this approach?
Maximization Problem
  1. For optimal solution, relaxation of integer LP is required
  1. Optimal solution is upper bound of Problem. There will be no higher value for OF than the relaxed solution
  1. Integer optimal solutoin will have lower value
  1. Feasible solution is gained by rounding down
Minimization problem
  1. Optimal solution, relaxation is also used
  1. Optimal solution is lower bound (the closest to the origin). No other solution will be closer than the relaxed one β‡’ Lower bound.
  1. Feasible solution is gained by rounding up (moving away from the origin).
  1. Optimal solution will have higher value
What is complete ennumeration?
  • Approach of obtaining the optimal solution of a binary LP by ennumerating each decision variable of the problem from left to right
  • We start with x1 and turn only it's value to 1, while all the others are 0. Then we turn x1 into 0 and instead turn x2 into 1
    • notion image
  • Write down the OF value for each step and choose the one with the highest value
  • Problem here: A loooot of branches that you need to create.
  • If binary program: branches, where n is the number of decision variables.
What is the branch and bound procedure?
  • Alternative to complete ennumeration.
    • incomplete ennumeration (only relevant solutions)
    • Breaking down the main problem (root) into easier to solve sub-problems (nodes)
    • Solve a relaxation of the integer problem
    • The union of the subsequent subproblems of the root should have the same solution space as the preceding problem
      • notion image
What is branching?
  • The creation of relaxed subproblems, that are easier to solve, because we can e.g apply the heurisitic approach of the knapsack to find the set of variables
What is are lower bound and upper bound of a subproblem?
notion image
  • For the root problem, upper bound is the result of relaxation
  • The lower bound would be the result of (if maximization problem) rounding down the non-integer variable.
What conditions do we use in order to decide whether to keep on branching a subproblem or fathome it?
  1. If the solution is not feasible, fathome the SP
      • Test feasibility by plugging in the solutions for the varibales into the contrainst.
  1. If the optimal value before any rounding is already lower (maxi problem) or higher (mini problem) than the best known feasible solution, fathome it
  1. The SP has a feasible solution in which all variables are integers, stop
      • If the resulting LP solution has better value than currently best know, update Z
  1. Only if the solution is non-integer, feasible, and has an OF value that is better than the currently best know feasible solution, keep branching
What is the kandidate list?
  • A set containing all the SP's that sill need to be branched.
    • notion image
What are the different rules that can be used to determine the order of the creation of the subproblems?
  1. FIFO (first in first out) β†’ "oldest problem"
      • The oldest problem which was added to the candidates list is solved first.
      • As the decision tree will growth in width, this approach is also called breath first search
        • notion image

  1. LIFO (last in first out) β†’ "youngest problem"
      • The problem that was added last to the kandidates list is branched first
      • In many cases multiple subproblems are created from one root problem.
        • In such cases we need an additinoal criteria e.g the tibreaker rule to decide which of the simultaneuously created ones is choosen
        • Tibreaker rule could be: "choose the SP with the largest (index) number"
      • As the tree grows vertically on the right side, this approach is also called depth-first-search
        • notion image
  1. Maximum Upper bound (MUB) / Minimu Lower Bound (MLB)
      • Maximization problem
        • We branch those SP's first which have the greates Upper Bound
      • Minimization problem
        • We branch those SP's first which have the smallest lower bound
What is a truncated branch and bound procedure
  • Additional criteria to futher decrease amount of Sp's that needs to be created.
  • Allow spread around the currently best know upper / lower bound by a certain percentage or βˆ†
  • If the upper / lower bound we get by solving a LP deviates by the percentage allowed, we also don't need to consider this SP anymore
    • notion image
What is the tradeoff in a warehouse location problem?
Lower shipping costs and thus higher fixed costs for building the warehouses or higher shipping costs and thus lower fixed costs because you build less.
How does the decision variables, OF, and Constraints of a warehouse-location problem look like?
notion image
If you don't want to know the amount of goods that is shipped on each route, but the percentage of the full demand that is shipped on each route, how do you need to change the model?
  1. xij repesents now a number between 0 and 1, which is the percentage that is shipped on each route.
  1. xij is now multiplied with the total shipping costs that will occur on a certain route. So total unit shipping costs * the total demand on the route.
    1. notion image
What is the fix and optimize approach?
  • if you have 5 warehouses and 6 customers, there are in total total variable combinations possible. Solving that with siplex will take forever
  • We approach the problem from the warehouse locations. This we unly have possiblities, which is less work
  • We then choose the combinations of y-locations which results in the lowest cost
    • notion image
  • To calculate total costs, we:
      1. Sum the fixed costs of construction of each of the warehouse locations β‡’ Amount of fixed costs
      1. Calculate the shipping costs by looking at the total costs table in the rows corresponding to the warehouses we decided to build.
          • Here it only makes sense to choose for each customers 1-6 the location entry which has the smallest cost value
            • notion image
      1. Summing fixed costs and shipping costs will give you the total costs

4 - Graph Theory / Network Flow

What is a network? What is a network flow?
An arrangement of paths connected at various points, through which items move
The network flow describes the flow of those items through the network.
What is a digraph?
notion image
  • This graph shows you the direction form start to end point.
What is special about node 1 and 5?
Node 1 is the start node, only arcs are going away from it. β‡’ Origin, supply node or source
Node 5 is the end node, only arcs going into the node.
β‡’ destination, demand node or sink.
  • Different names depending on the problem we are considering.
    • For transportation problems origin and destination could be used.
What are weights?
  • Values on the arcs of a graph
    • Kilometers
    • Amount shipped
    • Costs
    • ...
  • We denote them by using i,j where i is the starting note and j the ending node.
    • notion image
β‡’ If a directed graph also has weights next to the nodes and arcs, we also add "c" into the graph definition.
notion image
What is an undirected graph?
  • A graph in which there is no clear direction given
  • The connection between the nodes are called edges here not arcs anymore.
  • We denote an undirected graph and with bracketes []
  • We can also have weights on the edges, which are also denoted by cij.
    • notion image
What is a cycle?
A graph in which there is a connection which allows us to cycle back to the origin or demand in a undirected graph
What is a path?
A sequence from the n'th node to the n'th+1 up to the k'th end node, where k > 1.
The end node of a path is the starting node of the next path, except of the destination node. There the graph ends and we have reached the node k.
What are the two ways of denoting paths?
  1. List of the nodes
  1. List of the arcs (in the big set of the path, we here have subsets with the starting and ending node)
notion image
In a undirected graph the edges (i,j) and (j,i) are the same?
Yes, becuase the direction in which we go on the graph is not specified
In a directed graph the arcs i,j and j,i are the same?
No, the direction between i and j is fixed and we cannot arbitrarly switch the direction
A node in a path can have exactly two immediate predecessors?
No, in a path any node will only have one immediate predecessor. This node will have the shortest path (weight) to the node we are looking at.
A node on a path can have two successors?

Shortest Path Problem

What is the goal of the shortest route problem?
Shortest distance between starting node and destination node. Based on weights on the edges or arcs. Decide to only use those edges or arcs between two nodes that have the shortest distance between them.
What is the mathematical model for the shortest path and how do the conservation of flow constraints look like?
  1. Decision Variables
    1. notion image
      • xij is only 1 if the corresponding arc is the shortest of all possible other arcs in this position.
      • i and j are all the nodes we have, i is the nodes where we are coming from and j the node we are going to
      • The set (i,j) are all the arcs we have.
  1. Objective Function
    1. notion image
      • We sum up the weights of all the arcs which we decided are the minimal
      • Now without constraints we would set all xij = 0, but that would not lead to a feasible solution
  1. Constraints
"Conservation of flow"
  1. There need to be at least one arc "k" which is leaving the start node s. However we can only guarantee to get the optimal solution if we only choose one of those arcs "k", thus we get the following constraint:
    1. notion image
  1. If there is an arc entering a node, and this node is not the destination, there needs to be at least one arc which is leaving the node.
      • If xij = 1, then there is an arc entering the j'th node. Thus the sum of all arcs "k" which are leaving node j, need to be 1. There must be exactly 1 arc leaving.
        • notion image
          notion image
  1. If there is an arc entering node j from node i, there must also be an arc which had entered node i before.
    1. notion image
      notion image
  1. There should only be one exact arc of all the arcs entering the destination node, which we should choose. Thus the sum of all the ones entering must be 1, which means that only one incoming arc is chosen.
    1. notion image
What are immediate predecessors and immediate successors?
notion image
What is the dikstra algorithm, how does it work and what are prerequisits?
notion image
Initialization of the algorithm
notion image
  • Insert only the start node into the set M.
  • Set the distance of all other nodes besiders the starting node to ∞
    • notion image
  • In table form:
    • notion image
Iteration (code) β†’ Determining the shortest path
notion image
How many interations do you need to run with the dikstra and what is the problem with that?
You need to run as many iterations as there are nodes, thus you need to update / draw the table every time you insert or delete nodes into / from M.
What is the floyd-warshall algorithm, how does it work and does it have any prerequisits?
notion image
Initialization of the two matrices
notion image
notion image
  • The squared boxes are the nodes which can be reached form each of the starting nodes on the left.
How does the iteration work?
  • We introduce and intermediate node "v"
  • If the distance from the i'th node to the j'th node is greater than the distance if we use the node v in between, we update the graph.
  • Just look at the graph, there you can see if it makes sense to have a node in between.
notion image
During the floyd-wahrshall algorithm, the values on the diagonal are never updated?
No, there are entered during the initiation of the algorithm. The diagonal only consists of those nodes which have

Minimum Spanning Tree Problem

When are two nodes connected? What do you call it if the whole network of nodes is connected?
Two nodes are connected if there is at least one path in between them
If every pair of nodes is connected, then the network is connected
What is a spanning tree?
If there a n nodes in a network, a spanning tree is a subset of n-1 edges which connects all nodes
There are no cycles in the graph, so there can be no path which has the same starting and ending node.
What is the Kruskal Algorithm and how does it work?
  • obtaining the minimum spanning tree without disconnected nodes but also without any cycles.
  1. We determine or have given a table with different connections (edges) btween nodes
    1. notion image
  1. We sort the edges based on the non-decreasing costs principle, so that the ones with the smalles weight are in the first position. If two edges have the same weight, sort based on the smaller i value. If this is equal, then sort based on the smaller j value.
    1. notion image
  1. Initialze the Set A' to empty. This set will hold all the edges which contribute to a minimum spanning tree.
  1. Start all the way on the left in the table.
      • Add the edge (2,5) to the set A'
      • Keep track of the costs. In this case 2
      • Cancel the column 1
  1. Continue adding edges moving from the left to the right
      • Do not add any edges which would cause a cycle to occur. E.g (2,4)
        • notion image
      • In our case we stop at (3,5) because now the graph is connected and we also have n-1 edges compared to the nodes.
        • notion image

Maximum Flow Problem

What is the goal of the maximum flow problem?
determine the maximum possible flow through a directed graph with a source and a destination and given capacities on each arc
What are the components of a graph in the maximum flow problem?
notion image
How does the mathematical model look like and what are the conservation of flow criteria?
notion image
What is a semiwalk?
  • Basically a path (or sequence of nodes, that are connected), where the direction of the arcs is negleged
What is a cut?
  • A imaginary line cutting throught the arcs of a network and thus separating the source node from the destination node
  • The set of all nodes V, gets separated into and
What is the capacity of a cut?
  • The sum of the maximum capacities kappa of the arcs where node i is element of set Vs and node j is element of set Vq.
    • notion image
What does the max-flow min-cut theorem say?
  • In a network with single source and single destination node, the maximum flow in that network can be obtained determining the value of the minimum cut capacity
    • The cut where the sum of the capacities on the arcs is the smallest
    • Each cut capacity obtained on the way of finding the optimal one is a new upper bound.
      • notion image
What is the Ford Fulkerson Algorithm and how does it work?
  • This algoritm allows us to find the maximum flow in a network without using the simplex.
  1. Find / come up with any feasible flow. Value on the arcs.
    1. notion image
  1. Find new semiwalks always starting in source node s, trying to improve the amount of flow in the network
    1. notion image
      notion image
What is a transportation problem?
What is a transshipment model?
A transportation problem including intermediate nodes between the source and destination nodes.

5 - Decision Analysis

What are the different decision making scenarios and criteria?
notion image
What are the components of a decision matrix?
notion image
When do we call an alternative efficient and what does an alternative do, if is not efficient?
notion image
For each decision problem there exists a dominant decision alternative?
No, not neccesarly, as all decision alternatives ai could have the same outcomes.
What is a reduced decision matrix?
Matrix only containing efficient alterantives
In what scenarios can we apply decision rules?
  • We can apply decision rules, if:
    • single decision maker
    • one criterium
    • randomly acting opponent
    • If there is uncertaincy (risk) only probablities of each outcome given
What are the different decision rules?
notion image
A decision alternative with a large regret in a specific scenario is a good decision alternative.
No, a large regret is not very good, as the alternatives
What do you need to be aware of, if the decision matrix entries show the costs and not the profits?
If the decision matrix contains the costs for certain outcomes, the best outcome is the one with the lowest costs
The expected outcome always has to be maximized in order to obtain the optimal solution?
No, a decision problem could also have the objective to minimize costs. Then the best outcome would the min expected outcome
What are the characteristics of decision making under risk (also compared to certainty and uncertainty)?
  • We have n different scenarios given, thus we know what can possible happen
  • For each of those scenarios, we have a certain probability of occurance given
  • Summing up all inidividual probabilties of each scneario, the result needs to be 1 (or 100%)
  • The decision matrix gets another row above of the scenarios, holding the probabilities
    • notion image
What is a lottery and how do we decide between the different lotteries?
  • Each decision alternative can be written as a lottery, which is bascially a vector holding the probability and the corresponding outcome realted to the specific alternative. L1 = lottery of alternative 1
  • The amount of "branches" depends on the amount of scenarios that can be capitalized.
    • notion image
A lottery has always at least two possible outcomes.
No, a lottery can also have just one outcome.
What is the problem with using the expected outcome decision making?
The expected outcome does not always reflect what the best alternative in reality would be.
  • Recall coin flip example, where coin can be flipped unlimted times or you can choose 50€ instantly.
  • Flipping unlimited times will yield unlimited expected outcome, however the chance of loosing everything along the way is much higher.
What are the properties of a utility function that is used for decision making using expected utility and what is the formula of EU?
notion image
What are the three realtionships between two alterantives regarding the expected utility?
notion image
What are three utility function types and what risk attitude do they represent?
  1. Linear utility function β†’ Risk neutral
    1. notion image
  1. Convex utility function (exponent > 1) β†’ Risk seeking
    1. notion image
  1. Concarve utility function (exponent 0 < x < 1) β†’ Risk averse
    1. notion image
What method can you use to derive a utility function with the help of the decision maker?
The certain equivalent method
notion image
  • The lottery in 2. is the certain equivalent lottery
What do you do with the utility function?
Insert the outcomes of the initial decision matrix and turn it into the utility matrix.
With those new entries you can then calculate the expected utility of each alternative and then choose the one with the highest expected utility.
What is the risk premium?
notion image
notion image
How can we determine the risk attitude of the decision maker?
  • With the arrow pratt measure
    • We need an utility function that is at least twice differentiable and whose first derivative is not 0.
    • Then we can use the following formula to differentiate between three different risk attitudes.
      • notion image
      notion image
How does the mΓΌ-sigma method work?
  1. Set up:
    1. notion image
      sigma tells us, if there are large differences between the outcomes (scenarios) of a certain choosen alternative. If there is a wide spread around the expected outcome.
      β‡’ Row 1: Here we have the max outcome and the min outcome, thus a high variance. In contrast Row 2 has more similar values.
  1. Apply the preference value
    1. notion image
What is a preference value formula for risk neutral decision makers?
notion image
β†’ preference value is simply the mean or expected value of the row. Then choose the highest.
Same for risk adverse?
notion image
β†’ We are putting more weight on the mean, while also trying to make those alternatives with high variance as small as possible.
We multiply the variance without the square. Simply multiply 2* √sigma value.
Same for risk seeking?
notion image
β†’ Here the decision maker is likely to choose the decision which includes a high variance, because we add it to the mean.
What are the characteristics of a sequence of decisions?
notion image
What are the properties of a decision tree?
notion image
With a decision tree dependent decisions can be modeled.
yes, decision tree is specifically made for depended decisions.
After a circle node there are always exactly two branches.
No, there can be many branches going out of a circle node. This node represents the occurance of an unknown event. There can be many unknown events after a decision is made.
How do we compare and decide between the different branches in a decision tree?
Using the Rollback Procedure:
notion image
  • Calculate the expected value always at the round nodes.
    • notion image
      notion image
What is the value of perfect information?
  • Creating a testmarket in which both the positive and negative result provide us with 100% accuracy that:
      1. In case of a positive result in the testmarket, the product is guaranteed to sell
      1. In case of a negative result in the testmarket, the product is guaranteed to not sell.
      β‡’ In both cases we can fully rely on the testmarket.
  • Now there is the question how much you would need to pay in order to create such a certain testmarket.
  • In our example
    • For a testmarket providing perfect information, you:
        1. First calculate the expected outcome (profit) of a perfect testmarket
        1. Determine X (representing the costs of launching that testmarket) by setting up a equation. After X is subtracted, the value needs to be greater than the alternative of launching directly.
          1. notion image
            β‡’ 60.000€ is what we could pay, if the testmarket would provide optimal information
How would a sensitivity analysis in our example work and what is our goal with that?
"How large must the (success after pos. market test) probability p be, so that the test market is chosen over the direct introduction." Or
How accurate must the outcome (so success) of a positive test market be, so that we benefit?
notion image
β†’ "For what value of p, will the EV[testmarket] be β‰₯ 120.000?
Result: p = 0,875
β†’ With a success probability of 0,875 the decision maker will chose the testmarket over direct introduction.
What is the problem with the making your decision based on the expected outcome here?
  • The branch with the highest expected outcome might also have a very high possiblity of making a huge loss.
  • If you introduce without a testmarket, you can e.g have a 45% likelyhood of loosing 100.000€
  • If you however choose to have a testmarket, you can
      1. Loose 130.000€ with a chance of 0.6 * 0.15 = 0.09
      1. Loose 30.000€ with a chance of 0.4 (neg. result β†’ no introduction)
β‡’ So if we look at: How likely is it to make a loss? You will probably choose to not go into the market without testing.
How does the expected utility approach work in case of decision trees?
  1. Move (by adding or subtracting) all values on the edges all the way to the right. β†’ There can be no values other then percentages on the edges.
    1. notion image
  1. Determine the utility function of the decision maker based on the best outcome e+ and the worst outcome e-
      • We assume that the decision maker is risk adverse, so wants to minimize the chance of loosing a lot of money.
      • Also the utility of 1 is achieved for an outcome of 300.000 and utility of 0 for an outcome of -100.000
        • notion image
  1. Transform all the outcomes on the right into utility values
    1. notion image
      notion image
  1. Calculate EU[all outcomes] using the roll back procedure
    1. notion image
      notion image
      notion image
      β‡’ EU[testmarket] = 0.68
      notion image
  1. Result
      • Choosing the testmarket will have the highest expected utility .
What is multicriteria decision making?
  • A company wants to introduce one or more products and also wants to make sure that different attibutes are met
  • Those attributes can be good quality and fast shipping e.g
  • Could also be low prices and good quality
A normalization of the outcomes is required to determine an optimal decision in case of multiple criteria.
Yes, the outcomes of the matrix need to be of comparable value in order to multiply them with the goal weights.
  • Below you can't compare test and number, thus you need to bring both into similar format
notion image
How does the decision matrix under multicriteria decision making look like?
notion image
What method can be used to determine the best decision in this scenario?
Scoring Model
notion image
notion image
notion image
notion image
β‡’ Here alternative 2 choosen
What is the objective of a sensitivity analysis in context of MC decision making?
notion image