Operation Research

Section - A

 

1-Discuss about the principle of simplex method. Also define non basic variable and artificial variables.

The simplex method is a widely used algorithm for solving linear programming problems. Linear programming is a method used to optimize a linear objective function subject to constraints represented by linear equations or inequalities. The simplex method is based on the principle of iteratively improving the current solution by moving to an adjacent solution that has a better objective value.

The simplex method begins with an initial feasible solution and then repeatedly moves to an adjacent feasible solution until it reaches an optimal solution. The method uses a set of non-basic variables and a set of basic variables. 

Non-basic variables are the variables that are not currently part of the basis and are used to represent the objective function and the constraints. Basic variables are the variables that are currently part of the basis and are used to represent the current solution.

In each iteration of the simplex method, an entering non-basic variable is chosen and a leaving basic variable is chosen. The entering non-basic variable is the variable that will be added to the basis and the leaving basic variable is the variable that will be removed from the basis. This change in the basis results in an improvement in the objective value.

Artificial variables are a special type of non-basic variable that are used to represent constraints in the problem. They are introduced when there are constraints that are less than or equal to zero. They are used to represent the slack in the constraints, and are set to zero in the final solution. Artificial variables are used when the constraints are not in a standard form.

In summary, the simplex method is an algorithm used to solve linear programming problems by iteratively moving to an adjacent feasible solution that has a better objective value. It uses the principle of non-basic and basic variables. Non-basic variables are the variables that are not currently part of the basis and are used to represent the objective function and the constraints. Basic variables are the variables that are currently part of the basis and are used to represent the current solution. Artificial variables are a special type of non-basic variables that are used to represent constraints in the problem and are set to zero in the final solution.

 

2-What is a game problem? How do we solve these problems using LPP technique? Give example.

A game problem, also known as a non-cooperative game, is a mathematical model of a strategic situation in which multiple players make decisions simultaneously and independently to achieve their own objectives. Game theory is the branch of mathematics that studies such strategic situations and provides tools for analyzing and solving game problems.

Linear programming (LP) is a technique that can be used to solve some types of game problems. A LP problem is a problem in which the objective function and the constraints are linear. LP can be used to solve game problems by modeling the problem as a LP and then solving it using the simplex method or other LP algorithms.

For example, consider a game problem in which two companies, A and B, are competing to sell a product. Company A can produce the product at a cost of $10 per unit, while company B can produce the product at a cost of $8 per unit. The market demand for the product is 100 units, and the companies can sell the product for $15 per unit.

We can model this game problem as a LP problem with the following objective function and constraints:

Objective function: Maximize Z = 15x1 + 15x2 (x1 is the number of units sold by company A, x2 is the number of units sold by company B)

Constraints: x1 + x2 <= 100 (market demand) x1 >= 0 (x1 is non-negative) x2 >= 0 (x2 is non-negative) 10x1 <= 150 (company A's production cost) 8x2 <= 160 (company B's production cost)

The LP problem can then be solved using the simplex method or other LP algorithms to find the optimal solution, which represents the best strategy for each company.

In summary, A game problem is a mathematical model of a strategic situation in which multiple players make decisions simultaneously and independently to achieve their own objectives. Linear programming is a technique that can be used to solve some types of game problems by modeling the problem as a LP and then solving it using the simplex method or other LP algorithms.

 3-What do you mean by LPP? Discuss geometric properties of LPP.

LPP stands for Linear Programming Problem, which is a mathematical optimization problem that involves maximizing or minimizing a linear objective function subject to a set of linear constraints. The goal of an LPP is to find the values of the decision variables that optimize the objective function while satisfying all of the constraints.

Geometric properties of LPP refer to the way in which the constraints and the objective function of the problem can be represented graphically. In two-dimensional LPP, the constraints are represented by straight lines and the feasible region is the set of all points that satisfy all the constraints. The objective function is represented by a straight line that is parallel to one of the axes and the optimal solution is the point on the feasible region that is closest to this line.

In three-dimensional LPP, the constraints are represented by planes and the feasible region is the set of all points that satisfy all the constraints. The objective function is represented by a plane that is parallel to one of the coordinate planes and the optimal solution is the point on the feasible region that is closest to this plane.

It's worth noting that the feasible region of an LPP is a convex set, which means that any line segment connecting any two points in the feasible region is also entirely contained within the feasible region. This property is important because it guarantees that there is only one optimal solution to the LPP and that this solution can be found by moving from any feasible point along the objective function to the optimal solution.

In summary, LPP stands for Linear Programming Problem, which is a mathematical optimization problem that involves maximizing or minimizing a linear objective function subject to a set of linear constraints. Geometric properties of LPP refers to the way in which the constraints and the objective function of the problem can be represented graphically, where the feasible region is a convex set and the optimal solution is the point on the feasible region that is closest to the objective function.

 Section - B

1-Discuss in brief about the Hungarian method.

The Hungarian method is an algorithm used to solve the assignment problem, which is a type of linear programming problem where the goal is to assign a set of tasks to a set of workers in such a way that the total cost of the assignments is minimized.

The Hungarian method is based on the concept of a "reduced cost matrix," which is a matrix that is derived from the original cost matrix of the problem. The reduced cost matrix is obtained by subtracting the minimum element of each row from every element in that row, and then subtracting the minimum element of each column from every element in that column.

The Hungarian method then proceeds through a series of steps to find a complete set of optimal assignments:

1.      Starting with the reduced cost matrix, the algorithm looks for a zero element in the matrix that is not covered by any previously selected row or column. If it finds one, it assigns the task to the worker, and marks the row and column of the zero as covered.

2.      If there are no uncovered zeroes, it looks for the smallest non-zero element in the matrix and subtracts it from every uncovered element, and then adds it to every element that lies in the intersection of an uncovered row and an uncovered column. This is done to ensure that the reduced cost matrix remains valid.

3.      Repeat the above steps until all tasks are assigned.

The Hungarian method guarantees that a complete set of optimal assignments is found and also it is efficient and easy to implement. It is widely used in many fields such as logistics, scheduling, and image processing.

In summary, The Hungarian method is an algorithm used to solve the assignment problem, which is a type of linear programming problem where the goal is to assign a set of tasks to a set of workers in such a way that the total cost of the assignments is minimized. It guarantees a complete set of optimal assignments, is efficient and easy to implement and widely used in many fields.

 

2-What is a dual problem? How do we get a dual of given primal?

A dual problem is a related problem to a given primal problem in linear programming. The primal problem is the original problem that we want to solve, while the dual problem is a transformed version of the primal problem that can be used to gain additional insights or to solve the primal problem using different methods.

The primal problem is defined by an objective function and a set of constraints. The dual problem is obtained by interchanging the role of the objective function and the constraints in the primal problem. More specifically, the objective function in the primal problem becomes the constraints in the dual problem, and the constraints in the primal problem become the objective function in the dual problem.

The process of obtaining the dual problem from the primal problem is called duality. To get the dual of a given primal problem, we need to follow these steps:

1.      Write the primal problem in standard form: Maximize Z = c1x1 + c2x2 + ... + cnxn subject to: a11x1 + a12x2 + ... + a1nxn <= b1 a21x1 + a22x2 + ... + a2nxn <= b2 ... am1x1 + am2x2 + ... + amnxn <= bm x1, x2, ..., xn >= 0

2.      Introduce a set of new variables y1, y2, ..., ym, called the dual variables, which will be used as the objective function in the dual problem.

3.      Write the constraints in the primal problem as equalities: a11x1 + a12x2 + ... + a1nxn + y1 = b1 a21x1 + a22x2 + ... + a2nxn + y2 = b2 ... am1x1 + am2x2 + ... + amnxn + ym = bm

4.      Write the objective function of the primal problem as a minimization problem: Minimize Z* = b1y1 + b2y2 + ... + bmym

5.      Replace the original variables x1, x2, ..., xn with the non-negativity constraints x1, x2, ..., xn >= 0

6.      The resulting problem is the dual problem.

It's worth noting that while the primal and dual problem are related, they are not equivalent. A solution to the primal problem does not imply a solution to the dual problem, and vice versa. However, under certain conditions, the optimal values of the primal and the dual problem will be equal, known as weak and strong duality.

In summary, A dual problem is a related problem to a given primal problem in linear programming. The process of obtaining the dual problem from the primal problem is called duality, which is done by interchanging the role of the objective function and the constraints in the primal problem, introducing a set of new variables called the dual variables and replacing the original variables with non-negativity constraints. The primal and dual problem are related but not equivalent, however they have equal optimal values under certain conditions.

 

3-State and prove reduction theorem for assignment problems.

The reduction theorem for assignment problems states that any square assignment problem, which is an assignment problem where the number of tasks is equal to the number of agents, can be transformed into a square transportation problem and vice versa.

The proof of the reduction theorem for assignment problems can be broken down into two parts:

1.      From an assignment problem to a transportation problem: Given an assignment problem with a cost matrix C = [c(i,j)] where c(i,j) is the cost of assigning task i to agent j, we can construct a transportation problem as follows:

·         Introduce a new set of dummy sources, one for each task, and a new set of dummy destinations, one for each agent.

·         For each task i, set the supply at the dummy source i to 1.

·         For each agent j, set the demand at the dummy destination j to 1.

·         Set the transportation cost from dummy source i to dummy destination j to be equal to the cost of assigning task i to agent j, c(i,j)

2.      From a transportation problem to an assignment problem: Given a transportation problem with a cost matrix C' = [c'(i,j)] where c'(i,j) is the cost of transporting one unit of goods from source i to destination j, we can construct an assignment problem as follows:

·         Set the cost of assigning task i to agent j to be equal to the cost of transporting one unit of goods from source i to destination j, c'(i,j)

·         Set the number of tasks to be equal to the number of sources and the number of agents to be equal to the number of destinations.

This theorem is helpful in solving assignment problems using linear programming techniques. The reduction theorem allows us to solve an assignment problem using transportation problem techniques, and vice versa, which can lead to faster and more efficient solutions.

In summary, the reduction theorem for assignment problems states that any square assignment problem can be transformed into a square transportation problem and vice versa. The theorem can be proved by showing that the cost matrix of an assignment problem can be converted into a transportation problem and vice versa. The theorem is useful as it allows solving assignment problems using linear programming techniques, which can lead to faster and more efficient solutions.

 

4-Give the basic assumptions of Two-Person Sum-Zero Game.

 

 

Two-Person Sum-Zero Game is a mathematical model of a strategic situation in which two players make decisions simultaneously and independently in order to achieve their own objectives. The basic assumptions of a Two-Person Sum-Zero Game are:

1.      Two players: The game involves two players, who are referred to as player 1 and player 2.

2.      Complete information: Both players have complete knowledge of the rules of the game and the payoffs associated with each possible outcome.

3.      Simultaneous decision making: Both players make their decisions simultaneously and independently of each other.

4.      Pure strategies: Each player has a set of pure strategies, which are the specific actions that they can take. The players must choose one of these strategies and cannot mix or combine them.

5.      Finite number of strategies: The number of pure strategies available to each player is finite.

6.      Payoffs are real numbers: The payoffs associated with each outcome of the game are real numbers.

7.      Sum-zero property: The sum of the payoffs for the two players is always zero. In other words, if one player wins, the other player loses by the same amount.

8.      Non-cooperative: The game is non-cooperative, meaning that the players do not have any binding agreements, and they cannot make side-payments or enforce any kind of binding contract.

In summary, The basic assumptions of a Two-Person Sum-Zero Game are: two players, complete information, simultaneous decision making, pure strategies, finite number of strategies.

----------------------------------------------------------------------------------------------------------

Please reads the answers carefully if any error please show in the comment. This answers are not responsible for any objection. All the answers of Assignment are above of the paragraph. If you like the answer, please comment and follow for more also If any suggestion please comment or E-mail me. 

 Thank You!