Course MBA – 2ndSemester
Subject: Operations Research
Assignment MB0048 – Set2
Q1. Explain how to transform an unbalanced transportation problem into a balanced transportation problem where the demand of warehouses is satisfied by the supply of factories.
Ans:-
2. Explain how the profit maximization transportation problem into a Balanced transportation problem where the demand of warehouses is Satisfied by the supply of factories.
A fictive corporation A has a contract to supply motors for all tractors produced
by a fictive corporation B. Corporation B manufactures the tractors at four
locations around Central Europe: Prague, Warsaw, Budapest and Vienna. Plans
call for the following numbers of tractors to be produced at each location:
Prague 9 000
Warsaw 12 000
Budapest 9 000
Corporation A has three plants that can produce the motors. The plants and
production capacities are
Hamburg 8 000
Munich 7 000
Leipzig 10 000
Dresden 5 000
Due to varying production and transportation costs, the profit earns on each motor
depends on where they were produced and where they were shipped. The
following transportation table (Table 7.9) gives the accounting department
estimates of the euro profit per unit (motor).
"Highest - Profit Assignment"
Applying the Stepping Stone method (modified for maximization purposes) to the
initial solution we can see that no other transportation schedule can increase the
profit and so the Highest – Profit initial allocation is also an optimal solution of
this transportation problem.
Stepping Stone Method
Step 1: Pick any empty cell and identify the closed path leading to that cell. A
closed path consists of horizontal and vertical lines leading from an empty cell
back to itself (If assignments have been made correctly, the matrix has only one
closed path for each empty cell.) In the closed path there can only be one empty
cell that we are examining. The 90-degree turns must therefore occur at those
places that meet this requirement. Two closed paths are identified. Closed path a
is required to evaluate empty cell A-E; closed path b is required to evaluate empty
cell A-F
Step 2: Move one unit into the empty cell from a filled cell at a corner of the
closed path and modify the remaining filled cells at the other comers of the closed
path to reflect this move. (More than one unit could be used to test the desirability
of a shift. However, since the problem is linear, if it is desirable to shift one unit, it
is desirable to shift more than one, and vice versa.) Modifying entails adding to
and subtracting from filled cells in such a way that supply and demand constraints
are not violated. This requires that one unit always be subtracted in a given row or
column for each unit added to that row or column. Thus, the following additions
and subtractions would be required :
For the path a:
• Add one unit to A-E (the empty cell).
• Subtract one unit from A-H.
• Add one unit to C-H.
• Subtract one unit from C-E.
For the path b,
• Add one unit to A-F (the empty cell).
• Subtract one unit from A-H.
• Add one unit to C-H.
• Subtract one unit from C-G.
• Add one unit to D-G.
• Subtract one unit from D-F.
Step 3: Determine desirability of the move. This is easily done by (1) summing
the cost values for the cell to which a unit has been added, (2) summing the cost
values of the cells from which a unit has been subtracted, and (3) taking the
difference between the two sums to determine if there is a cost reduction. If the
cost is reduced by making the move, as many units as possible should be shifted
out of the evaluated filled cells into the empty cell. If the cost is increased, no
move should be made and the empty cell should be crossed.
For cell A-E, the pluses and minuses are
3. Illustrate graphically the following special cases of Linear programming problems:
i) Multiple optimal solutions, ii) No feasible solution, iii) Unbounded problem
Ans:- Solving a LPP with 2 decision variables x1 and x2 through graphical representation is easy. Consider x1 x2 – the plane, where you plot the solution space enclosed by the constraints. The solution space is a convex set bounded by a polygon; since a linear function attains extreme (maximum or minimum) values only on the boundary of the region. You can consider the vertices of the polygon and find the value of the objective function in these vertices. Compare the vertices of the objective function at these vertices to obtain the optimal solution of the problem.
Working rule
The method of solving a LPP on the basis of the above analysis is known as the graphical method. The working rule for the method is as follows.
Step 1: Write down the equations by replacing the inequality symbols by the equality symbols in the given constraints.
Step 2: Plot the straight lines represented by the equations obtained in step I.
Step 3: Identify the convex polygon region relevant to the problem. Decide on which side of the line, the half-plane is located.
Step 4: Determine the vertices of the polygon and find the values of the given objective function Z at each of these vertices. Identify the greatest and least of these values. These are respectively the maximum and minimum value of Z.
Step 5: Identify the values of (x1, x2) which correspond to the desired extreme value of Z. This is an optimal solution of the problem
We can analyse linear programming with 2 decision variables graphically.
Example
Let’s look at the following illustration.
Maximise Z = 700 x1+500 x2
Subject to 4x1+3x2 210
2x1+x2 90
and x1 0, x2 0
Let the horizontal axis represent x1 and the vertical axis x2. First, draw the line 4x1 + 3x2 = 210, (by replacing the inequality symbols by the equality) which meets the x1-axis at the point A (52.50, 0) (put x2 = 0 and solve for x1 in 4x1 + 3x2 = 210) and the x2 – axis at the point B (0, 70) (put x1 = 0 in 4x1 + 3x2 = 210 and solve for x2).
| Suppose a linear programming problem has an unbounded feasible solution space. If the set of all values of the objective function at different feasible solutions is not bounded above (respectively, bounded below), and if the problem is a maximisation (respectively, minimisation) problem, then we say that the given problem has an unbounded solution |
Q4: 4. How would you deal with the Assignment problems, where a) the objective function is to be maximized?
b) Some Assignments are prohibited?
Ans:- Let’s say there are „n‟ jobs in a factory having „n‟ machines to process the jobs. A job i (=1… n), when processed by machine j (=1… n) is assumed to incur a cost Cij. The assignment is to be made in such a way that each job can associate with one and only one machine. You can then determine an assignment of jobs to the machines to minimise the overall cost.
The cost data is given as a matrix where rows correspond to jobs and columns to machines and there are as many rows as the number of columns. The number of jobs and number of machines should be equal.
Assignment becomes a problem because each job requires different skills and the capacity or efficiency of each person with respect to these jobs can be different. This gives rise to cost differences. If each person is able to do all jobs with same efficiency then all costs will be the same and each job can be assigned to any person. When assignment is a problem it becomes a typical optimization problem. Therefore, you can compare an assignment problem to a transportation problem. The cost element is given and is a square matrix and requirement at each destination is one and availability at each origin is also one.
Additionally, you have number of origins,
Which equal the number of destinations. Therefore, the total demand is equal to the total supply. There is only one assignment in each row and each column. However if you compare this to a transportation problem, you will find that a general transportation problem does not have the above mentioned limitations. These limitations are peculiar to assignment problems only.
An assignment problem can be either balanced or unbalanced. Let’s first focus on a balanced assignment problem. A balanced assignment problem is one where the number of rows = the number of columns (comparable to a balanced transportation problem where total demand =total supply).
Balanced assignment problem: No. of rows = No. of columns
A:- the objective function is to be maximized :-
Some assignment problems are phrased in terms of maximizing the profit or effectiveness or payoff of an assignment of people to tasks or of jobs to machines. You cannot apply the Hungarian method to such maximization problems. Therefore, you need to reduce it to a minimization problem.
It is easy to obtain an equivalent minimization problem by converting every number in the table to an opportunity loss. To do so, you need to subtract every value from the highest value of the matrix and then proceed as usual
You will notice that minimizing the opportunity loss produces the same assignment solution as the original maximization problem.
B:- b Some Assignments are prohibited
Infeasible assignments
It is sometimes possible that a particular person is incapable of doing certain work or a specific a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the infeasible assignment can be avoided. This can be achieved by assigning a very high cost (say ∞ or M) to the cells where assignments are prohibited, thereby, restricting the entry of this pair of job – machine or resource – activity into the final solution. After inserting a high value at the cell we need to apply Hungarian method to solve the problem.
5. “Simulation is an especially valuable tool in a situation where the mathematics
needed to describe a system realistically is too complex to yield analytical solutions”.
Elucidate.
Ans: Simulation is an especially valuable tool in a situation where the mathematics needed to describe a system realistically is too complex to yield analytical solutions”. Elucidate.
Simulation is the imitation of some real thing, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system. Simulation is used in many contexts, such as simulation of technology for performance optimization, safety engineering, testing, training,education, and video games. Training simulators include flight simulators for training aircraft pilots. Simulation is also used for scientific modeling of natural systems or human systems in order to gain insight into their functioning. Simulation can be used to show the eventual real effects of alternative conditions and courses of action. Simulation is also used when the real system cannot be engaged, because it may not be accessible, or it may be dangerous or unacceptable to engage, or it is being designed but not yet built, or it may simply not exist. Simulation can be used when the problem is too
complex for analytical solution and too dangerous for actual experimentation. Key issues in simulation include acquisition of valid source information about the relevant selection of key characteristics and behaviours, the use of simplifying approximations and assumptions within the simulation, and fidelity and validity of the simulation outcomes.
6. Describe Gomory’s method of solving an all-integer programming problem.
Ans :An optimum solution to an IPP is obtained by using the simplex method, ignoring the restriction of integral values. In the optimum solution, if all the variables have integer values, the current solution will be the required optimum integer solution.
Otherwise, the given IPP is modified by inserting a new constraint called Gomory’s constraint or secondary constraint. This constraint represents necessary conditions for integrability and eliminates some non-integer solution without losing any integral solution. On addition of the secondary constraint, the problem is solved using dual simplex method to obtain an optimum integral solution. If all the values of the variables in the solution are integers, then an optimum inter-solution is obtained, or else a new constraint is added to the modified LPP and the procedure is repeated till the optimum solution is derived. An optimum integer solution will be reached eventually after introducing enough new constraints to eliminate all the superior non-integer solutions. The construction of additional constraints, called secondary or Gomory’s constraints is important and needs special attention.
Construction of Gomory’s constraints
Consider a LPP or an optimum non–integer basic feasible solution. With the usual notations, let the solution be displayed in the following simplex.
The optimum basic feasible solution is given by
xB = [x2, x3 ] = [y10, y20]; max z = y00
Since xB is a non-integer solution, we can assume that y10 is fractional. The constraint equation is
y10 = y11 x1 + y12 x2 + y13 x3+ y14 x4 0xx4 1
It reduces to
y10 = y11 x1 + x2 + y14 x4 _____ (1) 0xx4 1
Because x2 and x3 are basic variables (which implies that y12 = 1 and y13 = 0). The above equation can be rewritten as
x2 = y10 - y11 x1 - y14 x4
This is a linear combination of non-basic variables.
Now, since y10 0 the fractional part of y10 must also be non-negative. You can split each of yij in (1) into an integral part Iij , and a non-negative fractional part, f1j for j = 0,1,2,3,4. After the breakup (1) above, you can write it as:
I10 + f10 = (I11 + f11) x2 + (I14 + f14) x4
Or
f10 - f11 x2 - f14 x4 = x2 + I11 x1 + I14x4 - I10 _
If you compare (1) and (2), you will see that if you add an additional constraint in such a way that the left-hand side of (2) is an integer; then you will be forcing the non-integer y10 towards an integer.
The desired Gomory’s constraint is
f10 – f11 x1 – f11 x4 ≤ 0
It is possible to have f10 – f11 x1 – f11 x4 = h where h > 0 is an integer. Then f10 = h + f11 x1 + f14 x4 is greater than one. This contradicts that 0 < fij < 1 for j = 0, 1, 2, 3, 4.
Thus Gomory’s constraint is
10 sla 4 ,1j j ij 4 , 1j 10 j ij 4 , 1j j ig f ) 1(G x f or f x . f or f x f 10 Where Gsla (1) is a slack variable in the above first Gomory’s constraint
The additional constraint to be included in the given LPP is towards obtaining an optimum all integer solution. After adding the constraint, the optimum simplex table looks like given below.
Since – f10 is negative, the optimal solution is unfeasible. Thus the dual simplex method is to be applied for obtaining an optimum feasible solution. After obtaining this solution, the above referred procedure is applied for constructing second Gomory’s constraint. The process is to be continued till all the integer solution has been obtained.
No comments:
Post a Comment