Category: Lucknow University BBA Notes

The North-West Corner Method is a basic heuristic algorithm used for solving transportation problems, a type of linear programming problem in operations research. The method gets its name from the fact that the first allocation of supply to demand is made in the north-west corner of the transportation table.

Steps involved in the North-West Corner Method:

1. Set up the transportation table: This involves creating a table with the supply at the top and the demand on the left side. Each cell in the table represents the cost of transporting one unit of the product from the supplier to the demand location.
2. Identify the north-west corner cell: Start by allocating the maximum possible amount to the first supply and demand location, which is the top-left cell of the table.
3. Allocate as much as possible to the cell: Allocate as much product as possible to this cell, up to the smaller of the supply and demand values.
4. Update the supply and demand: Subtract the allocated quantity from the supply and demand values for the respective rows and columns.
5. Move to the next cell: Move to the next cell in the same row or column that has not been allocated, and repeat steps 3 and 4.
6. Repeat the process: Continue the process until all cells in the table have been allocated.
7. Optimize the solution: Once all cells have been allocated, check whether the solution obtained is optimal. If it’s not optimal, make adjustments by repeating the process until the optimal solution is obtained.

The North-West Corner Method is a simple and easy-to-use algorithm. However, it does not guarantee an optimal solution, especially for large and complex transportation problems. Therefore, it is often used as a starting point for more advanced methods of solving transportation problems.

North West corner method example

Suppose a company has three factories that produce goods and four warehouses that distribute the goods. The supply and demand of the goods are given in the following table:

To apply the North-West Corner Method, we start with the top-left cell and allocate as much as possible. So, we allocate 3 units from Factory 1 to Warehouse 1.

Next, we move to the next cell in the same row and allocate as much as possible. So, we allocate 2 units from Factory 1 to Warehouse 2.

Now we move to the next row and allocate as much as possible to the next cell. We allocate 5 units from Factory 2 to Warehouse 2.

Then we move to the next row and allocate as much as possible to the next cell. We allocate 9 units from Factory 2 to Warehouse 3.

Then we move to the next row and allocate as much as possible to the next cell. We allocate 9 units from Factory 2 to Warehouse 3.

Next, we allocate 6 units from Factory 1 to Warehouse 4:

We continue to allocate in the same way until all demands are satisfied. The final allocation table is:

We can verify that the total cost of transportation for this allocation is:

3 x $1 + 2 x $3 + 7 x $2 + 6 x $2 + 5 x $3 + 4 x $2 + 9 x $1 + 3 x $2 + 5 x $3 + 7 x $4 = $156.

Thus, the North-West Corner Method provides us with an initial feasible solution to the transportation problem. However, we may need to apply the optimization techniques such as the MODI method to find the optimal solution.

After obtaining an initial feasible solution using one of the methods such as the North West Corner method or the Least Cost method, we need to check if the solution is optimal. This involves checking whether there exists any other feasible solution that has a lower total cost.

The optimality test can be performed using various methods such as the stepping stone method, the modified distribution method, or the Vogel’s approximation method. Here, we will discuss the stepping stone method.

The stepping stone method involves calculating the opportunity cost for each empty cell in the allocation table. The opportunity cost represents the amount by which the cost of an allocated cell would have to increase or decrease to make another allocation possible in the same row or column without violating the supply or demand constraints.

The steps involved in the stepping stone method are as follows:

1. Select an empty cell (i,j) in the allocation table.
2. Starting from the cell (i,j), draw a closed loop that includes only allocated cells.
3. Count the number of cells in the loop. If the count is odd, then the opportunity cost for cell (i,j) is the smallest cost among all the cells in the loop. If the count is even, then the opportunity cost for cell (i,j) is zero.
4. Repeat steps 1-3 for all empty cells in the allocation table to obtain the opportunity cost for each cell.
5. If all the opportunity costs are non-negative, then the current solution is optimal. Otherwise, select the cell with the most negative opportunity cost and perform an improvement move.

An improvement move involves adding or subtracting the opportunity cost from each cell in the closed loop and updating the allocation table accordingly. The process is repeated until an optimal solution is obtained.

Note that there may be multiple optimal solutions with the same total cost.

Optimality test examples

Let’s continue with the example from the previous question:

We will use the stepping stone method to check whether this solution is optimal.

Step 1: Select an empty cell. Let’s select cell (1,1).

Step 2: Draw a closed loop that includes only allocated cells starting from cell (1,1) and going right, then down, then left, and finally up to cell (1,1). The closed loop is shown in red in the table below.

Step 3: Count the number of cells in the loop. The loop has four cells, which is an even number. Therefore, the opportunity cost for cell (1,1) is zero.

Step 4: Repeat steps 1-3 for all other empty cells.

For cell (1,2), the loop goes down, left, up, and right to cell (1,2), and has an odd number of cells. The smallest cost among the cells in the loop is 2, which is the opportunity cost for cell (1,2).

For cell (1,4), the loop goes down, right, up, and left to cell (1,4), and has an odd number of cells. The smallest cost among the cells in the loop is 1, which is the opportunity cost for cell (1,4).

The corrected table after the optimality test using the stepping stone method is as follows:

Since all the opportunity costs are non-negative, the current solution is optimal. Therefore, the optimal allocation is:

• Allocate 50 units from F1 to W1
• Allocate 120 units from F2 to W2
• Allocate 120 units from F1 to W3
• Allocate 60 units from F2 to W4
• Allocate 100 units from F3 to W1
• Allocate 10 units from F3 to W4
• The total cost for this allocation is $7,900.

The stepping stone method is an iterative procedure used to improve an initial feasible solution for a transportation problem, in order to find the optimal solution. The method is based on the idea of moving from one feasible solution to another by making small changes in the allocation of goods from one cell to another, and then checking whether this change reduces the total transportation cost.

The stepping stone method involves the following steps:

1. Start with an initial feasible solution. This means that all supply and demand constraints are satisfied, and the total supply equals the total demand.
2. Identify any non-basic cells in the allocation table, and assign a value of zero to each of these cells. These cells are called “test cells”.
3. Construct a closed loop by starting from any test cell, and moving to adjacent cells (horizontally or vertically) that have positive allocations. Continue moving in this way until you reach the test cell that you started from, and close the loop.
4. Compute the opportunity cost for each test cell in the loop. The opportunity cost is the difference between the transportation cost of the current cell and the transportation costs of the cells in the loop that have positive allocations.
5. If all the opportunity costs are non-negative, then the current solution is optimal, and the algorithm terminates. Otherwise, select the test cell with the smallest opportunity cost, and increase its allocation by the minimum amount necessary to make one of the cells in the loop unoccupied, while keeping all supply and demand constraints satisfied. Set the allocation of the cell that becomes unoccupied to zero, and repeat the procedure from step 2.

By repeating steps 2 to 5, the stepping stone method gradually moves from the initial feasible solution to the optimal solution, by improving the allocation of goods in the cells of the allocation table.

Note that in the stepping stone method, the allocations are changed in a way that preserves the total supply and demand, and satisfies the non-negativity constraints of the problem. This ensures that the resulting solution remains feasible, and only improves the objective function value.

Stepping stone method examples

Sure, here is an example of the stepping stone method applied to a transportation problem:

Suppose we have a company that manufactures products in three factories (F1, F2, F3) and ships them to four warehouses (W1, W2, W3, W4). The transportation costs per unit are given in the following table:

The supply and demand for each factory and warehouse are given by:

• F1 has a supply of 120 units
• F2 has a supply of 180 units
• F3 has a supply of 110 units
• W1 has a demand of 50 units
• W2 has a demand of 120 units
• W3 has a demand of 180 units
• W4 has a demand of 70 units

To find the optimal solution, we can start with an initial feasible solution. For example, we can allocate 50 units from F1 to W1, 120 units from F2 to W2, 60 units from F2 to W4, and 110 units from F3 to W3. This allocation satisfies the supply and demand constraints, and the total supply equals the total demand. The allocation table is:

We can now apply the stepping stone method to improve this initial solution. We start by identifying the test cells, which are the cells with zero allocation: cell (1,2), cell (1,3), and cell (3,1). We then construct a closed loop by starting from cell (1,2), and moving to cell (2,2), cell (2,4), cell (1,4), cell (3,4), cell (3,3), and back to cell (1,2). The loop has an even number of cells, so we need to compute the opportunity cost for each test cell.

For cell (1,2), the loop goes right, up, left, and down to cell (1,2), and has an even number of cells. Therefore, the opportunity cost for cell (1,2) is zero.

For cell (1,3), the loop goes down, right, up, and left to cell (1,3), and has an odd number of cells. The smallest cost among the cells in the loop is 2, which is the opportunity cost for cell (1,3).

For cell (3,1), the loop goes right, up, left, down, right, and up to cell (3,1), and has an odd number of cells. The smallest cost among the cells in the loop is 6, which is the opportunity cost for cell (3,1).

To increase the allocation for cell (1,3), we need to find a way to increase the flow of units through this cell while maintaining feasibility. We can do this by using the stepping stone method again to find a new feasible solution with an improved objective function value.

To do this, we start by adding a flow of 2 units to cell (1,3), which will increase the allocation for this cell to 2 units. This will also decrease the available supply for F1 to 48 units and increase the demand for W3 to 182 units.

Next, we identify the test cells for the new allocation table, which are cells (1,2), (2,2), (2,4), and (3,1). We construct a closed loop by starting from cell (1,2), and moving to cell (2,2), cell (2,4), cell (1,4), cell (3,4), cell (3,3), and back to cell (1,2). The loop has an even number of cells, so we need to compute the opportunity cost for each test cell.

For cell (1,2), the loop goes right, up, left, and down to cell (1,2), and has an even number of cells. Therefore, the opportunity cost for cell (1,2) is zero.

For cell (2,2), the loop goes left, down, right, and up to cell (2,2), and has an even number of cells. Therefore, the opportunity cost for cell (2,2) is zero.

For cell (2,4), the loop goes up, left, down, and right to cell (2,4), and has an even number of cells. Therefore, the opportunity cost for cell (2,4) is zero.

For cell (3,1), the loop goes right, up, left, down, right, and up to cell (3,1), and has an odd number of cells. The smallest cost among the cells in the loop is 6, which is the opportunity cost for cell (3,1).

The cell with the smallest opportunity cost is cell (3,1), with an opportunity cost of 6. We can increase its allocation by 6 units, which will increase the allocation for cell (2,2) by 2 units, and decrease the allocation for cell (2,4) by 2 units. This new allocation table is:

We can now repeat the process of identifying the test cells, constructing a closed loop, and computing the opportunity costs to continue improving the solution until we reach an optimal solution.

The Hungarian method is a popular algorithm used to solve assignment problems, which involve assigning a set of agents to a set of tasks with given costs, such that each agent is assigned to exactly one task and each task is assigned to exactly one agent, while minimizing the total cost of the assignments.

The Hungarian method involves the following steps:

1. Create a cost matrix: Create an n x n matrix representing the costs of assigning each agent to each task, where n is the number of agents and tasks.
2. Subtract the smallest cost in each row from all the costs in that row, and subtract the smallest cost in each column from all the costs in that column.
3. Draw the minimum number of horizontal or vertical lines to cover all the zeros in the matrix. If the number of lines equals n, then an optimal assignment has been found. If not, proceed to step 4.
4. Determine the smallest uncovered element in the matrix, and subtract it from all uncovered elements. Then, add it to all elements at the intersection of two lines.
5. Repeat steps 3 and 4 until an optimal assignment has been found.
6. Assign the agents to the tasks based on the lines. If an agent is assigned to a task covered by a vertical line, or a task is assigned to an agent covered by a horizontal line, the assignment is optimal.
7. If there are any unassigned agents or tasks, return to step 2 and continue until all agents and tasks are assigned.

Here is an example of the Hungarian method in action:

Suppose we have the following cost matrix representing the costs of assigning three agents to three tasks:

Step 1: Create a cost matrix.

Step 2: Subtract the smallest cost in each row from all the costs in that row, and subtract the smallest cost in each column from all the costs in that column.

Step 3: Draw the minimum number of horizontal or vertical lines to cover all the zeros in the matrix. In this case, we can cover all the zeros with two horizontal lines (through rows A2 and A3).

Step 4: Determine the smallest uncovered element in the matrix, which is 2. Subtract it from all uncovered elements, and add it to all elements at the intersection of two lines.

Step 5: Repeat steps 3 and 4 until an optimal assignment has been found.

• We can cover all the zeros in the matrix with two horizontal lines, but we still need to cover one more cell to have a complete assignment.
• The uncovered cell with the smallest value is (A2, T2) with a cost of 0.
• We can draw a vertical line through column T2 to cover cell (A2, T2).

• Now we can cover all the zeros in the matrix with two lines. The covered cells correspond to an optimal assignment:

• The optimal assignment is:

  • Agent 1 is assigned to Task 2 with a cost of 0.
  • Agent 2 is assigned to Task 1 with a cost of 2.

  • Agent 3 is assigned to Task 3 with a cost of 5.

Game theory is a branch of mathematics that studies strategic decision-making in situations where the outcome depends on the actions of multiple players. It provides a framework for analyzing and understanding the behavior of individuals or groups who are interacting in a strategic environment.

In game theory, a “game” is a formal mathematical representation of a strategic situation. A game consists of:

• Players: The individuals or groups who are making decisions.
• Actions: The choices available to each player.
• Payoffs: The outcomes or rewards associated with each possible combination of actions.

There are two main types of games in game theory:

1. Non-cooperative games: In non-cooperative games, the players act independently, without any explicit communication or cooperation. Each player chooses their actions based on their own interests, without regard to the interests of the other players. Examples of non-cooperative games include the prisoner’s dilemma and the game of chicken.
2. Cooperative games: In cooperative games, the players can communicate and form alliances or agreements. The players work together to achieve a common goal and share the rewards accordingly. Examples of cooperative games include bargaining games and coalition formation games.

Game theory provides several tools and concepts for analyzing games and predicting the behavior of the players. Some of the key concepts in game theory include:

• Nash equilibrium: A Nash equilibrium is a set of actions, one for each player, such that no player can improve their payoff by unilaterally changing their action, assuming the other players’ actions remain unchanged.
• Dominant strategy: A dominant strategy is a player’s best response to any possible action of the other players, regardless of what they do.
• Pareto efficiency: A game is said to be Pareto efficient if there is no other outcome that would make all players better off without making any player worse off.

Game theory has applications in economics, political science, psychology, and other fields. It is used to model and analyze a wide range of strategic situations, such as market competition, international relations, and social behavior.

Game Theory Uses

Game theory has a wide range of applications in various fields, including:

1. Economics: Game theory is extensively used in economics to study market competition, bargaining, and pricing strategies. It helps to understand the behavior of firms and consumers in markets, and to predict how changes in market conditions can affect market outcomes.
2. Political Science: Game theory is used in political science to study strategic interactions among political actors, such as voters, candidates, and interest groups. It helps to analyze election outcomes, lobbying, and other political processes.
3. Psychology: Game theory is used in psychology to study decision-making and social behavior. It helps to understand how people make choices in social situations and how they interact with each other.
4. Biology: Game theory is used in biology to study evolutionary dynamics and the behavior of organisms in social and ecological contexts. It helps to understand the evolution of cooperation, competition, and other social behaviors in animals and humans.
5. Computer Science: Game theory is used in computer science to study artificial intelligence, machine learning, and algorithms. It helps to develop algorithms that can make optimal decisions in strategic situations.
6. Military Strategy: Game theory is used in military strategy to study conflicts and the behavior of opposing forces. It helps to analyze military tactics and to develop optimal strategies for different situations.

In game theory, a saddle point is a point in a game matrix where the minimum value in a row is equal to the maximum value in the corresponding column. If a game matrix has a saddle point, it can help simplify the analysis of the game and identify the equilibrium strategies of the players.

Here is an example of a game with a saddle point:

Consider a two-player game in which Player A can choose between two pure strategies, A1 and A2, and Player B can choose between two pure strategies, B1 and B2. The game matrix is as follows:

In this matrix, the minimum value in the first row is 2, which corresponds to the maximum value in the first column. This is a saddle point, and it indicates that Player A should choose A1 and Player B should choose B1 to achieve the equilibrium outcome.

To see why, consider the following:

• If Player A chooses A1, Player B’s best response is to choose B1, which gives them a payoff of 2.
• If Player A chooses A2, Player B’s best response is to choose B2, which gives them a payoff of 3.
• If Player B chooses B1, Player A’s best response is to choose A1, which gives them a payoff of 2.
• If Player B chooses B2, Player A’s best response is to choose A1, which gives them a payoff of 4.

Thus, the equilibrium outcome of this game is (A1, B1), with payoffs of (2, 2). The presence of the saddle point in the game matrix simplifies the analysis of the game and allows us to identify the equilibrium outcome without having to consider more complex strategies.

A saddle point in game theory refers to a strategy combination in a game where each player’s best response is the same strategy regardless of what the other player does. In other words, it’s a point in the payoff matrix where both players have a unique optimal strategy. However, not all games have a saddle point equilibrium.

Here are some examples of games that do not have a saddle point:

1. Matching Pennies: In this game, each player has a coin and can choose to show either heads or tails. The payoff matrix is as follows:

2. There is no saddle point in this game because there is no single strategy combination where both players have a unique best response.
3. Prisoner’s Dilemma: In this game, two players are arrested for a crime and are given the choice of whether to cooperate or defect. The payoff matrix is as follows:

4. There is no saddle point in this game because each player’s best response depends on what the other player does, so there is no single strategy combination where both players have a unique best response.
5. Chicken: In this game, two drivers are racing towards each other and must decide whether to swerve or stay on course. The payoff matrix is as follows:

6. There is no saddle point in this game because each player’s best response depends on what the other player does, so there is no single strategy combination where both players have a unique best response.

In each of these games, finding a Nash equilibrium requires the use of mixed strategies, as no pure strategy Nash equilibrium exists.

Mixed strategies are a key concept in game theory that refers to a situation where a player chooses to play more than one strategy with a certain probability distribution. In other words, instead of playing a single strategy every time, the player selects different strategies randomly based on a probability distribution.

Mixed strategies are used in game theory to find the equilibrium of a game when no pure strategy Nash equilibrium exists. A Nash equilibrium is a set of strategies where no player can improve their payoff by changing their strategy unilaterally. In some games, however, there may not be a Nash equilibrium in pure strategies, which means that each player has a dominant strategy to play. In such cases, mixed strategies are used to find an equilibrium.

To find a mixed strategy equilibrium, players assign a probability distribution over the available strategies, which must satisfy certain conditions. The probabilities should sum up to one, and each strategy should have a non-negative probability. The expected payoff for each player under this probability distribution is then calculated, and the Nash equilibrium is found when no player has an incentive to change their strategy.

Mixed strategies are used in many different types of games, such as the famous Prisoner’s Dilemma and Battle of the Sexes. They provide a useful tool for analyzing games where players have incomplete information or where there are multiple equilibria.

Mixed strategies Types with examples

There are two main types of mixed strategies that are commonly used in game theory: symmetric and asymmetric mixed strategies.

1. Symmetric Mixed Strategies: In symmetric mixed strategies, all players use the same probability distribution over the strategies. In other words, players have the same strategy set and they randomize over those strategies in the same way. This is often used in games where players have identical strategies and payoffs.

Example: The classic example of a game that uses symmetric mixed strategies is the Matching Pennies game. In this game, two players each have a penny and choose to show either the heads or tails side. The payoff depends on whether the two pennies match or not. Each player randomizes over their choices with equal probability, so the probability of matching is 1/2.

2. Asymmetric Mixed Strategies: In asymmetric mixed strategies, players use different probability distributions over their strategies. This is often used in games where players have different strategies and payoffs.

Example: Consider the game of Rock-Paper-Scissors. In this game, each player can choose to play either rock, paper, or scissors. Each choice wins against one choice and loses against another, and ties with itself. If both players play pure strategies, there is no Nash equilibrium. However, if each player randomly chooses each option with equal probability, then there is a mixed strategy Nash equilibrium.

In asymmetric mixed strategies, players use different probability distributions over their strategies, so each player has a different optimal mix of strategies. For example, if Player 1 chooses rock, paper, and scissors with probabilities 1/2, 1/3, and 1/6, respectively, then Player 2’s optimal mix of strategies is to choose rock, paper, and scissors with probabilities 1/3, 1/3, and 1/3, respectively.

In game theory, a pure strategy is a specific, predetermined choice of action that a player will take in a game. It represents the player’s complete plan of action, given all possible scenarios and the choices available to them.

For example, in the game of rock-paper-scissors, a player could use a pure strategy of always playing “rock.” This means that no matter what the opponent plays, the player will always play “rock” as their predetermined choice.

In a game with multiple players, each player can have their own set of pure strategies. The combination of all players’ pure strategies determines the possible outcomes of the game.

The use of pure strategies is often used as a simplifying assumption in game theory, as it allows for straightforward analysis of the game’s equilibrium outcomes. However, in many real-world situations, players may use mixed strategies, which involve a randomized choice of actions with certain probabilities, rather than predetermined, fixed actions.

Here is an example of pure strategies in game theory:

Consider a simple game where two players, Alice and Bob, each have the choice to either cooperate or defect. If both players cooperate, they each receive a payoff of 3. If both players defect, they each receive a payoff of 1. If one player cooperates and the other defects, the defector receives a payoff of 4 and the cooperator receives a payoff of 0.

To analyze this game, we can consider the possible pure strategies for each player:

Alice’s pure strategies: Cooperate or Defect

Bob’s pure strategies: Cooperate or Defect

There are four possible outcomes of the game, depending on the choices of Alice and Bob:

• Both players cooperate: Payoffs = (3, 3)
• Alice cooperates, Bob defects: Payoffs = (0, 4)
• Alice defects, Bob cooperates: Payoffs = (4, 0)
• Both players defect: Payoffs = (1, 1)

To find the equilibrium outcome of the game, we can use the concept of Nash equilibrium. A Nash equilibrium is a set of strategies where no player can unilaterally improve their payoff given the other player’s strategy.

In this game, the only Nash equilibrium is for both players to defect. If Alice chooses to cooperate, Bob has an incentive to defect and receive a higher payoff. Similarly, if Bob chooses to cooperate, Alice has an incentive to defect and receive a higher payoff.

Thus, the Nash equilibrium outcome of the game is (Defect, Defect), with payoffs of (1, 1). This is the only outcome that satisfies the criteria of Nash equilibrium, where neither player can improve their payoff by changing their strategy, given the other player’s strategy.

The rule of dominance is a decision-making principle in game theory that suggests that a strategy can be eliminated from consideration if it is always dominated by another strategy, meaning that it always yields a worse outcome regardless of the other player’s strategy.

To apply the rule of dominance, a player evaluates each of their strategies based on the payoffs that they would receive for all possible strategies that the other player could play. If one strategy always yields a worse outcome than another strategy, it can be eliminated from consideration as it is dominated.

For example, consider a game between two players, Alice and Bob, in which Alice can choose between two pure strategies, A1 and A2, and Bob can choose between two pure strategies, B1 and B2. The game matrix is as follows:

To apply the rule of dominance, Alice evaluates her strategies based on Bob’s possible strategies:

• If Bob plays B1, Alice’s payoffs for each of her strategies are 3 for A1 and 2 for A2. Therefore, A2 is dominated by A1 and can be eliminated from consideration.
• If Bob plays B2, Alice’s payoffs for each of her strategies are 1 for A1 and 2 for A2. Therefore, A1 is dominated by A2 and can be eliminated from consideration.

Thus, applying the rule of dominance results in the elimination of A2 and the conclusion that Alice should choose A1 if Bob plays B1 and A2 if Bob plays B2.

The rule of dominance is a useful tool in game theory as it can simplify the analysis of a game by reducing the number of strategies that need to be considered. However, it should be used with caution as it may not always identify the correct equilibrium outcome.