Question

Randall grew up in Ohio but now lives in California. He knows that snow sucks and makes driving a nightmare. His father, Douglas, owns a specialty cars dealership chain in Ohio. Douglas knows that it is very hard to sell sports cars in the winter. So, they see a business opportunity where they can ship and sell Corvettes from Ohio to California in the winter. They can make a profit of $3,000 per car sold. This year Doug has 57 Corvettes in his Columbus store, 55 in Cincinnati store, and 20 in his Cleveland store. Randall is able to broker deals with California dealers: VetteMax will buy 25, BlingRide is committed to 30, Americana signs a contract for 20, and BoyToys will buy 45.

The associated shipping costs are as follows:

$	VetteMax	BlingRide	Americana	BoyToys
Columbus	560	744	777	480
Cincinnati	704	810	604	570
Cleveland	801	890	502	703

a. How many Corvettes does BoyToys get from Columbus?

b.What is the total shipping cost?

c.What is their NET profit?

Answer 1

a.) BoyToys get 32 Corvettes from Columbus

b.) Total Shipping cost is 71360

c.) A total of 120 Corvettes are shipped and each gives a profit of $3000, thus net profit = $3000 * 120 = $360000

First we find a basic feasible solution using Voggel's Approximation method, also then optimal solution using MODI method

TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4
Problem Table is

	VetteMax	BlingeRide	Americana	BoyToys		Supply
Columbus	570	744	777	480		57
Cincinnati	704	810	604	570		55
Cleveland	801	890	502	703		20
Demand	25	30	20	45

Here Total Demand = 120 is less than Total Supply = 132. So We add a dummy demand constraint with 0 unit cost and with allocation 12.
Now, The modified table is

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply
Columbus	570	744	777	480	0		57
Cincinnati	704	810	604	570	0		55
Cleveland	801	890	502	703	0		20
Demand	25	30	20	45	12

Table-1

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570	744	777	480	0		57	480=480-0
Cincinnati	704	810	604	570	0		55	570=570-0
Cleveland	801	890	502	703	0		20	502=502-0
Demand	25	30	20	45	12
Column Penalty	134=704-570	66=810-744	102=604-502	90=570-480	0=0-0

The maximum penalty, 570, occurs in row Cincinnati.

The minimum cij in this row is c25 = 0.

The maximum allocation in this cell is min(55,12) = 12.
It satisfy demand of Ddummy and adjust the supply of Cincinnati from 55 to 43 (55 - 12 = 43).

Table-2

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570	744	777	480	0		57	90=570-480
Cincinnati	704	810	604	570	0(12)		43	34=604-570
Cleveland	801	890	502	703	0		20	201=703-502
Demand	25	30	20	45	0
Column Penalty	134=704-570	66=810-744	102=604-502	90=570-480	--

The maximum penalty, 201, occurs in row Cleveland.

The minimum cij in this row is c33 = 502.

The maximum allocation in this cell is min(20,20) = 20.
It satisfy supply of Cleveland and demand of Americana.

Table-3

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570	744	777	480	0		57	90=570-480
Cincinnati	704	810	604	570	0(12)		43	134=704-570
Cleveland	801	890	502(20)	703	0		0	--
Demand	25	30	0	45	0
Column Penalty	134=704-570	66=810-744	--	90=570-480	--

The maximum penalty, 134, occurs in row Cincinnati.

The minimum cij in this row is c24 = 570.

The maximum allocation in this cell is min(43,45) = 43.
It satisfy supply of Cincinnati and adjust the demand of BoyToys from 45 to 2 (45 - 43 = 2).

Table-4

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570	744	777	480	0		57	90=570-480
Cincinnati	704	810	604	570(43)	0(12)		0	--
Cleveland	801	890	502(20)	703	0		0	--
Demand	25	30	0	2	0
Column Penalty	570	744	--	480	--

The maximum penalty, 744, occurs in column BlingeRide.

The minimum cij in this column is c12 = 744.

The maximum allocation in this cell is min(57,30) = 30.
It satisfy demand of BlingeRide and adjust the supply of Columbus from 57 to 27 (57 - 30 = 27).

Table-5

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570	744(30)	777	480	0		27	90=570-480
Cincinnati	704	810	604	570(43)	0(12)		0	--
Cleveland	801	890	502(20)	703	0		0	--
Demand	25	0	0	2	0
Column Penalty	570	--	--	480	--

The maximum penalty, 570, occurs in column VetteMax.

The minimum cij in this column is c11 = 570.

The maximum allocation in this cell is min(27,25) = 25.
It satisfy demand of VetteMax and adjust the supply of Columbus from 27 to 2 (27 - 25 = 2).

Table-6

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570(25)	744(30)	777	480	0		2	480
Cincinnati	704	810	604	570(43)	0(12)		0	--
Cleveland	801	890	502(20)	703	0		0	--
Demand	0	0	0	2	0
Column Penalty	--	--	--	480	--

The maximum penalty, 480, occurs in row Columbus.

The minimum cij in this row is c14 = 480.

The maximum allocation in this cell is min(2,2) = 2.
It satisfy supply of Columbus and demand of BoyToys.


Initial feasible solution is

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	Row Penalty
Columbus	570(25)	744(30)	777	480(2)	0		57	480 | 90 | 90 | 90 | 90 | 480 |
Cincinnati	704	810	604	570(43)	0(12)		55	570 | 34 | 134 | -- | -- | -- |
Cleveland	801	890	502(20)	703	0		20	502 | 201 | -- | -- | -- | -- |
Demand	25	30	20	45	12
Column Penalty	134 134 134 570 570 --	66 66 66 744 -- --	102 102 -- -- -- --	90 90 90 480 480 480	0 -- -- -- -- --

The minimum total transportation cost =570×25+744×30+480×2+570×43+0×12+502×20=72080

Here, the number of allocated cells = 6, which is one less than to m + n - 1 = 3 + 5 - 1 = 7
∴ This solution is degenerate

To resolve degeneracy, we make use of an artifical quantity(d).
The quantity d is assigned to that unoccupied cell, which has the minimum transportation cost.

The quantity d is assigned to CincinnatiAmericana, which has the minimum transportation cost = 604.

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply
Columbus	570 (25)	744 (30)	777	480 (2)	0		57
Cincinnati	704	810	604 (d)	570 (43)	0 (12)		55
Cleveland	801	890	502 (20)	703	0		20
Demand	25	30	20	45	12

Optimality test using modi method...
Allocation Table is

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply
Columbus	570 (25)	744 (30)	777	480 (2)	0		57
Cincinnati	704	810	604 (d)	570 (43)	0 (12)		55
Cleveland	801	890	502 (20)	703	0		20
Demand	25	30	20	45	12

Iteration-1 of optimality test
1. Find ui and vj for all occupied cells(i,j), where cij=ui+vj

1. Substituting, u1=0, we get

2.c11=u1+v1⇒v1=c11-u1⇒v1=570-0⇒v1=570

3.c12=u1+v2⇒v2=c12-u1⇒v2=744-0⇒v2=744

4.c14=u1+v4⇒v4=c14-u1⇒v4=480-0⇒v4=480

5.c24=u2+v4⇒u2=c24-v4⇒u2=570-480⇒u2=90

6.c23=u2+v3⇒v3=c23-u2⇒v3=604-90⇒v3=514

7.c33=u3+v3⇒u3=c33-v3⇒u3=502-514⇒u3=-12

8.c25=u2+v5⇒v5=c25-u2⇒v5=0-90⇒v5=-90

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	ui
Columbus	570 (25)	744 (30)	777	480 (2)	0		57	u1=0
Cincinnati	704	810	604 (d)	570 (43)	0 (12)		55	u2=90
Cleveland	801	890	502 (20)	703	0		20	u3=-12
Demand	25	30	20	45	12
vj	v1=570	v2=744	v3=514	v4=480	v5=-90

2. Find dij for all unoccupied cells(i,j), where dij=cij-(ui+vj)

1.d13=c13-(u1+v3)=777-(0+514)=263

2.d15=c15-(u1+v5)=0-(0-90)=90

3.d21=c21-(u2+v1)=704-(90+570)=44

4.d22=c22-(u2+v2)=810-(90+744)=-24

5.d31=c31-(u3+v1)=801-(-12+570)=243

6.d32=c32-(u3+v2)=890-(-12+744)=158

7.d34=c34-(u3+v4)=703-(-12+480)=235

8.d35=c35-(u3+v5)=0-(-12-90)=102

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	ui
Columbus	570 (25)	744 (30)	777 [263]	480 (2)	0 [90]		57	u1=0
Cincinnati	704 [44]	810 [-24]	604 (d)	570 (43)	0 (12)		55	u2=90
Cleveland	801 [243]	890 [158]	502 (20)	703 [235]	0 [102]		20	u3=-12
Demand	25	30	20	45	12
vj	v1=570	v2=744	v3=514	v4=480	v5=-90

3. Now choose the minimum negative value from all dij (opportunity cost) = d22 = [-24]

and draw a closed path from CincinnatiBlingeRide.

Closed path is CincinnatiBlingeRide→CincinnatiBoyToys→ColumbusBoyToys→ColumbusBlingeRide

Closed path and plus/minus sign allocation...

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	ui
Columbus	570 (25)	744 (30) (-)	777 [263]	480 (2) (+)	0 [90]		57	u1=0
Cincinnati	704 [44]	810 [-24] (+)	604 (d)	570 (43) (-)	0 (12)		55	u2=90
Cleveland	801 [243]	890 [158]	502 (20)	703 [235]	0 [102]		20	u3=-12
Demand	25	30	20	45	12
vj	v1=570	v2=744	v3=514	v4=480	v5=-90

4. Minimum allocated value among all negative position (-) on closed path = 30
Substract 30 from all (-) and Add it to all (+)

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply
Columbus	570 (25)	744	777	480 (32)	0		57
Cincinnati	704	810 (30)	604 (d)	570 (13)	0 (12)		55
Cleveland	801	890	502 (20)	703	0		20
Demand	25	30	20	45	12

5. Repeat the step 1 to 4, until an optimal solution is obtained.

Iteration-2 of optimality test
1. Find ui and vj for all occupied cells(i,j), where cij=ui+vj

1. Substituting, u2=0, we get

2.c22=u2+v2⇒v2=c22-u2⇒v2=810-0⇒v2=810

3.c23=u2+v3⇒v3=c23-u2⇒v3=604-0⇒v3=604

4.c33=u3+v3⇒u3=c33-v3⇒u3=502-604⇒u3=-102

5.c24=u2+v4⇒v4=c24-u2⇒v4=570-0⇒v4=570

6.c14=u1+v4⇒u1=c14-v4⇒u1=480-570⇒u1=-90

7.c11=u1+v1⇒v1=c11-u1⇒v1=570+90⇒v1=660

8.c25=u2+v5⇒v5=c25-u2⇒v5=0-0⇒v5=0

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	ui
Columbus	570 (25)	744	777	480 (32)	0		57	u1=-90
Cincinnati	704	810 (30)	604 (d)	570 (13)	0 (12)		55	u2=0
Cleveland	801	890	502 (20)	703	0		20	u3=-102
Demand	25	30	20	45	12
vj	v1=660	v2=810	v3=604	v4=570	v5=0

2. Find dij for all unoccupied cells(i,j), where dij=cij-(ui+vj)

1.d12=c12-(u1+v2)=744-(-90+810)=24

2.d13=c13-(u1+v3)=777-(-90+604)=263

3.d15=c15-(u1+v5)=0-(-90+0)=90

4.d21=c21-(u2+v1)=704-(0+660)=44

5.d31=c31-(u3+v1)=801-(-102+660)=243

6.d32=c32-(u3+v2)=890-(-102+810)=182

7.d34=c34-(u3+v4)=703-(-102+570)=235

8.d35=c35-(u3+v5)=0-(-102+0)=102

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply	ui
Columbus	570 (25)	744 [24]	777 [263]	480 (32)	0 [90]		57	u1=-90
Cincinnati	704 [44]	810 (30)	604 (d)	570 (13)	0 (12)		55	u2=0
Cleveland	801 [243]	890 [182]	502 (20)	703 [235]	0 [102]		20	u3=-102
Demand	25	30	20	45	12
vj	v1=660	v2=810	v3=604	v4=570	v5=0

Since all dij≥0.

So final optimal solution is arrived.

	VetteMax	BlingeRide	Americana	BoyToys	Ddummy		Supply
Columbus	570 (25)	744	777	480 (32)	0		57
Cincinnati	704	810 (30)	604 (d)	570 (13)	0 (12)		55
Cleveland	801	890	502 (20)	703	0		20
Demand	25	30	20	45	12

The minimum total transportation cost =570×25+480×32+810×30+570×13+0×12+502×20=71360