Transportation Algorithm for Minimization Problem, MODI Method, LPP Solution, Assignment Help

MODI Method - Transportation Algorithm for Minimization Problem

Transportation Algorithm for Minimization Problem (MODI Method)

Step 1

Make the transportation table entering the origin capacities a_i, the cost c_ij and destination requirement b_j

Step 2

Determine an initial basic feasible solution by vogel's technique or by any of the known method.

Step 3

For all the basic variables x_ij, solve the system of equations u_i + v_j = c_ij, for all i, j for which cell (i, j) is in the basis, starting at first with some u_i = 0, compute the values of u_i and v_j on the transportation table

Step 4

Calculate the cost differences d_ij = c_ij - ( u_i + v_j ) for all the non-basic cells

Step 5

Apply optimality test by testing the sign of each d_ij

If all d_ij ≥ 0, the present basic feasible solution is optimal or best
If at least one d_ij < 0, choose the variable x_rs (most negative) to enter the basis.
Solution under test is not optimal if any of the d_ij is negative and subsequent improvement is needed by repeating the above procedure.

Step 6

Assume the variable x_rs enter the basis. Assign an unknown quantity ? to the cell (r, s). Then make a loop that begins and ends at the cell (r, s) and links some of the basic cells. The amount ? is added to and subtracted from the transition cells of the loop in such a way that the availabilities and necessities remain fulfilled.

Step 7

Allocate the largest possible value to the ? in such a manner that the value of at least one basic variable comes out to be zero and the other basic variables remain non-negative. The basic cell whose allotment has been made zero will leave the basis.

Step 8

Now, go back to step 3 and repeat the process until an optimal solution is achieved.

Worked Examples

Illustration 1

Determine an optimal solution

	W₁	W₂	W₃	W₄	Availability
F₁	19	30	50	10	7
F₂	70	30	40	60	9
F₃	40	8	70	20	18
Requirement	5	8	7	14

Answer

1. Put vogel's approximation method for determining the initial basic feasible solution

	W₁	W₂	W₃	W₄	Availability	Penalty
F₁	5(19)	(30)	(50)	2(10)	X	X
F₂	(70)	(30)	7(40)	2(60)	X	X
F₃	(40)	8(8)	(70)	10(20)	X	X
Requirement	X	X	X	X
Penalty	X	X	X	X

Minimum transportation cost comes out to be 5 (19) + 2 (10) + 7 (40) + 2 (60) + 8 (8) + 10 (20) = Rs. 779

2. Test for Non-degeneracy

The initial fundamental feasible solution has m + n - 1 i.e. 3 + 4 - 1 = 6 allocations in independent positions. Therefore optimality test is fulfilled.

3. Computation of u_i and v_j : - u_i + v_j = c_ij

					u_i
	(19)			(10)	u₁= -10
			(40)	(60)	u₂= 40
		(8)		(20)	u₃= 0
v_j	v₁= 29	v₂= 8	v₃= 0	v₄= 20

Allocate a 'u' value to zero. (Convenient rule is to choose the u_i, which has the maximum number of allocations in its row)

Assume u₃ = 0, then

u₃ + v₄= 20 which means 0 + v₄ = 20, so v₄= 20

u₂ + v₄= 60 which means u₂ + 20 = 60, so u₂ = 40

u₁ + v₄= 10 which means u₁ + 20 = 10, so u₁ = -10

u₂ + v₃= 40 which means 40 + v₃ = 40, so v₃ = 0

u₃ + v₂= 8 which means 0 + v₂ = 8, so v₂= 8

u₁ + v₁= 19 which means -10 + v₁= 19, so v₁ = 29

4. Computation of cost differences for non basic cells d_ij = c_ij - ( u_i + v_j )

c_ij			u_i + v_j
	(30)	(50)		-2	-10
(70)	(30)		69	48
(40)		(70)	29		0

d_ij = c_ij - ( u_i + v_j )
	32	60
1	-18
11		70

5. Doing Optimality test

d_ij < 0 i.e. d₂₂ = -18

so x₂₂ is entering the basis

6. Creation of loop and allotment of unknown quantity ?

We assign ? to the cell (2, 2). Reallocation is done by transferring the maximum possible amount ? in the marked cell. The value of ? is achieved by equating to zero to the corners of the closed loop. That is min (8-?, 2-?) = 0 which gives ? = 2. Hence x₂₄ is outgoing as it turns out to be zero.

5 (19)			2 (10)
	2 (30)	7 (40)
	6 (8)		12 (20)

Minimum transportation cost comes out to be 5 (19) + 2 (10) + 2 (30) + 7 (40) + 6 (8) + 12 (20) = Rs. 743

7. Enhanced Solution

					u_i
	(19)			(10)	u₁= -10
		(30)	(40)		u₂= 22
		(8)		(20)	u₃= 0
v_j	v₁= 29	v₂= 8	v₃= 18	v₄= 20

c_ij				u_i + v_j
	(30)	(50)			-2	8
(70)			(60)	51			42
(40)		(70)		29		18

d_ij = c_ij - ( u_i + v_j )
	32	42
19			18
11		52

As d_ij > 0, an optimal solution is achieved with minimal cost of Rs.743

Have a Question? (oR Write a Review)

Write atleast 100 words!!

Related Writing Services!

Unified Approach to OOA

www.tutorsglobe.com offers Unified Approach to OOA homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.

Carbohydrates-physical properties and functions

Carbohydrates-physical properties and functions tutorial all along with the key concepts of Categorization of carbohydrates, Functions of carbohydrates, Physical property of carbohydrates and Stereochemistry of carbohydrates

Insulation Materials

insulation materials - leathroid paper, nomex, triflexil (collective flexible insulating material that is insulation class f (155 °c) material conforms to iec 626-1.)

Kinds of Business Ownership Exist

the specific form of business ownership has significant implications for accounting purposes and so it is helpful to be clear about the major kinds of ownership that can take place.

Sculpture

Avail the best Sculpture Assignment Help and put a full stop to sleepless nights at low prices and score A++ easily!!

Supply

tutorsglobe.com supply assignment help-homework help by online demand and supply tutors

Environmental Impact of Chemical Industry

TutorsGlobe.com Environmental Impact of Chemical Industry Assignment Help-Homework Help by Online Access Chemistry Tutors

Ferrites

ferrites tutorial all along with the key concepts of magnetic resonance, nuclear magnetic resonance, ferromagnetic resonance, antiferromagnetic resonance

Economic Importance of Plants

the fibres are acquired from the surface of seeds. hibiscus cannabinus (deccan hemp) yields bast fibres which are employed for making ropes.

Conductor Materials

pure copper is one of the finest conductors of electricity and the conductivity of it is extremely sensitive to impurities, pure aluminium comprises silvery colour and polish. it presents high resistance to corrosion.

Natural Products

www.tutorsglobe.com offers natural products homework help, natural products assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.

Whole Coil Winding

total number of coils =24/4= 6; coils per phase =12/3= 4; number of coils of groups per phase = 3 x 2 = 6

Types of Cost Reports

Routine reports are submitted to dissimilar levels of management according to a fixed time schedule. Special reports are needed for special purposes. The reason of obtaining such type of reports, and the time limit in which such type of reports are to be submitted, has to be particularly and clearly laid down.

Least Squares Fitting-Noisy Data

Theory and lecture notes of Least Squares Fitting-Noisy Data all along with the key concepts of functions and data, Traffic flow model, Linear least squares, Drag coefficients. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Least Squares Fitting-Noisy Data.

Arithmetic Sequences

Theory and lecture notes of Arithmetic Sequences all along with the key concepts of arithmetic sequences, Partial Sum of an Arithmetic Sequence, Common Difference and General Term of Arithmetic Sequences. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Arithmetic Sequences.

1958221

Questions
Asked

3689

Tutors

1442138

Questions
Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment