Unit 5: Liner Programming Problems (LPP)

Unit 5: Liner Programming Problems (LPP)
Properties of LPP
(i) All problems seek to maximise or minimise some quantity, usually profit or cost. This
property is referred to as objective function of an LP problem.
(ii) The presence of restrictions or constraints that limit the degree to which the objective
can be pursued.
(iii) There must be alternative courses of action to choose from.
(iv) The objective function and constraints in LPP must be expressed in terms of linear
equations or inequalities.
Assumptions of LPP
(i) The assumption that condition of certainty exists, i.e., numbers in objective function and
constraints are known with certainty and do not change during the study period.
(ii) The assumption that proportionality exists in the objective function and constraints. This
means that if production of one unit of a product uses 5 hours of a scarce resource, then
making 10 units of the product uses 50 hours (i.e., 5 x 10) of the resource.
(iii) The assumption (technical) dealing with additivity meaning that the total of all activities
equals the sum of the individual activities. For example, if product A yields a profit of Rs.
10 per unit and product B yields Rs. 20 per unit and if one number each of these two
products are produced, then the total profit is the sum of the profits from product A and
B. i.e.,Rs. 10 + Rs. 20 = Rs. 30.
(iv) The divisibility assumption that solutions need not be in whole numbers (integers) and
can take any fractional value. If a fraction of a product cannot be produced, the problem
becomes an integer programming problem. –
(v) The assumption that all answers or variables are non-negative. Negative quantities of
physical entities (variables) have no meaning because negative numbers of products
cannot be produced.
Advantages of Linear Programming

(i) Provides an optimal solution(s).
(ii) Fast determination of the solution if a computer is used.
(iii) Finds solutions to a wide variety of problems which can be formulated with LP.
(iv) Finds solutions to problems with a very large or infinite number of possible solutions.
(v) Provides a natural sensitivity analysis.
Limitations of Linear Programming

Limitations Due to Assumptions
The major assumptions are:
(i) Certainty: It is assumed that all the data in the LP are known with certainty.
(ii) Linear objective function: This means that per unit cost, price and profit are assumed to
be unaffected by changes in production methods or quantities produced or sold.
(iii) Linear constraints: The linearity assumptions in LP are reflected in additivity,
independence and proportionality.
(a) Additivity: It is assumed that the total utilization of each resource is determined by
adding together that portion of the resource required for the production of each of
the various products or activities.
(b) Independence: Complete independence of coefficients is assumed both among
activities and among resources.
(c) Proportionality: It is assumed that the objective function and constraints must be
linear as a requirement of proportionality. This means that the amount of resources
used and the resulting value of the objective function will be proportional to the
value of the decision variables.
(iv) Non-negativity: Negative activity levels or negative production are not permissible.
(v) Divisibility: Variables are classified as continuous or discrete. In LP, it is assumed that the
unknown variables x1, x2, .... are continuous, i.e., they can take any fractional values
(divisibility assumption).
Game Theory
• Game is defined as an activity between two or more persons involving activities by each
person according to a set of rules, at the end of which each person receives some
benefit or satisfaction or suffers loss.
• Game theory is a body of knowledge which is concerned with the study of decision-
making in situations where two or more rational opponents are involved under
conditions of competition and conflicting interests.
• Competitive situation is called a game.
• Game represents conflict between two or more parties.
• Game is defined as an activity between two or more persons involving activities by each
person according to a set of rules, at the end of which each person receives some
benefit or satisfaction or suffers loss.
• Main objective in the theory of games is to determine the rules of rational behaviour in
the game situations, in which outcomes are dependent on the actions of the
interdependent players.
• Each player definitely has number of possible outcomes with different values to them
All competitive situations having the following properties are termed as game:
1. There are a finite number of competitors or players.
2. For each of the competitors, there are a number of possible courses of action or
strategies.
3. The interest of each other is conflicting in nature.
4. A play occurs when each player chooses one of his courses of action.
5. Every combination of course of action determined an outcome, which results in a
gain to each player. (Loss is considered as negative gain)
Game Models
On the basis of number of players
2 – Players → Two-person game
More than two players → n person game
On the basis of sum of gains and losses
Zero Sum game or constant sum game - If in a game the gains to one player are exactly equal to
the losses to another player, then the sum of the gains and losses equals to zero
If the gain of one player ≠ losses of another player: Non zero sum game.
On the basis of number of strategies –
Finite: Game is finite if each player has the option of choosing from only a finite number of
strategies. Otherwise: Infinite
Terms to know:
Pay off – is the outcome of playing the game.
A pay off matrix is a table showing the amounts received by the player named at the left hand
side after all possible plays of the game. The player named at the top of the table makes the
payment.
Value of a game - The expected outcome per play when players follow their best or optimal
strategy.
Strategy - It is the list of all possible actions (moves or course of action) that he will take for
every outcome that might arise.
Two types of strategies
1. Pure strategy:
➢ If a player knows exactly what the other player is going to do, a deterministic situation is
obtained
➢ Objective of the players is to maximize gains
➢ A pure strategy is usually represented by a number with which the course of action is
associated
2. Mixed strategy:
➢ When both the players are guessing as to which course of action is to be selected on a
particular occasion, a probabilistic situation is obtained and the objective function is to
maximize the expected gain
➢ The mixed strategy is a selection among pure strategies with fixed probabilities
Optimal strategy - The particular strategy by which a player optimizes his gains or losses
without knowing the competitor’s strategies is called optimal strategy.
If the value of the game is zero, then the game is called as Fair game, otherwise the game is
strictly determinable
Pure strategies (MINIMAX & MAXIMIN Principles) Games with saddle point:
1. For player A minimum value in each row represents the least gain if A chooses a particular
strategy. These are written in the matrix by row minima. Then A selects the strategy that gives
largest gain among the row minimum values. The choice of player A is maximin principle and
the corresponding gain is maxmin value of the game.
2. For player B, who is assumed to be a loser, the maximum value in each column represents
the maximum loss if B chooses a particular strategy. They are column maxima. B has to select
a strategy that minimizes the maximum loss. This choice of player b is called the minimax
principle and the corresponding loss is minimax value of the game.
We use Algebraic method when there is no saddle point.
Player B
a11 a12
Player A a21 a22
(A plays strategy a1 with probability x and plays strategy a2 with probability 1- x)
(B plays strategy b1 with probability y and plays strategy b2 with probability 1- y)

A game is said to be fair game, if minimax = maximin value and both equal to zero.
Said to be strictly determinable if minimax = maximin and both equals to value of the game.
Rules to determine saddle point:
• Find minimum pay-off in each row

• Select the largest of the minimum pay-offs
• This is maximin strategy of the maximizing player
• Find maximum pay-off in each column
• Select the smallest of these pay-offs
• This is minimax strategy of the minimizing player
• If the maximin and minimax strategies have equal pay-offs, the game has a saddle point
NOTE:
• A game can have more than one saddle point, resulting in multiple optimal strategies
• If the game has no saddle point, the players have to play mixed strategies
• If value of the game, v = 0, it is called a fair game
• If v > 0, the game favors maximizing player and if v < 0, it favors minimizing player
Rules of Dominance
For player B, if each element in a column say Cr, is greater than or equal to the corresponding
element in another column say Cs, then the column Cr is dominated by the column Cs. So
delete column Cr from the pay- off matrix.
i.e., player B will lose more by choosing strategy Cr than by choosing strategy for column Cs.
2. For player A, if each element in a row Rr, is less than or equal to the corresponding element
in another row Rs, then the row Rr is dominated by row Rs. So delete row Rr from the pay off
matrix.
i.e., player A will never use the strategy corresponding to Rr because he will gain less for
choosing such strategy.
3. Dominance need not be based on the superiority of pure strategies only. A given strategy can
be dominated if it is inferior to an average of two or more other strategies.
Pay off matrix is a profit matrix for player A and loss matrix for player B.
Procedure to solve a case graphically:
➢ Check for saddle point

➢ If no saddle point, reduce the matrix using dominance rule
➢ Assign the probabilities and obtain payoff function and expected gain
➢ Plot on a graph sheet using a suitable scale
➢ Find the feasible region and the point corresponding to the matrix size
➢ Obtain the payoff matrix from the graph
➢ Solve the matrix algebraically
Schematic representation of method of solution of two- person zero- sum games

Unit 5: Liner Programming Problems (LPP)

Uploaded by

Copyright:

Available Formats

Unit 5: Liner Programming Problems (LPP)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 5: Liner Programming Problems (LPP)

Uploaded by

Copyright:

Available Formats

Unit 5: Liner Programming Problems (LPP)

Advantages of Linear Programming

Limitations of Linear Programming

On the basis of sum of gains and losses

On the basis of number of strategies –

Pay off – is the outcome of playing the game.

Two types of strategies

➢ Objective of the players is to maximize gains

We use Algebraic method when there is no saddle point.

Player A a21 a22

(A plays strategy a1 with probability x and plays strategy a2 with probability 1- x)

(B plays strategy b1 with probability y and plays strategy b2 with probability 1- y)

Rules to determine saddle point:

• Find minimum pay-off in each row

Procedure to solve a case graphically:

➢ Check for saddle point

Schematic representation of method of solution of two- person zero- sum games

You might also like