Home

Optimization Problem:

A dietician recommends a patient to take exercise for 2 hours/day. It is assumed that swimming burns 320 cal/hr and walking consumes 200 cal/hr. The dietician recommends minimum 10 minutes extra walk than swimming and also that extra walking time should not exceed 25 minutes. Determine the duration in minutes the patient should walk and swim per day so that maximum calories are burnt.

Solution:

Assume x minutes of walk and y minutes of swimming per day.

Hence objective function is z = 320x/60 + 200y/60 which is to be maximized.

Constraints are x + y <= 120 minutes

And 10 <= x – y <= 25

The extreme conditions are x + y = 120, x – y = 10 and x – y = 25

Analytically, solving 2 equations at a time simultaneously as below;

x + y = 120, x – y = 10 x = 65 and y = 55

x + y = 120, x – y = 25 x = 72.5 and y = 47.5

z1 = 320*65/60 + 200*55/60 = 530

z2 = 320*72.5/60 + 200*47.5/60 = 545

Hence solution corresponding to z2 is optimum solution

Graphical solution is as follows

Problem: A farmer has 1000acres of land on which he can grow corn, wheat and soyabean. An acre of wheat costs Rs. 120 for preparation, requires 10 man days and yields a profit of Rs. 40. Each acre of corn costs Rs. 100 for preparation, requires 7 man days of work and yields a profit of Rs. 30. An acre of soyabean costs Rs. 70 for preparation, requires 8 man days and yields a profit of Rs. 20. If farmer has Rs. 1,00,000 for preparation and can count on 8000 man days of work how many acres should be allocated to each crop to maximize tha profit?

Solution: First convert the description into mathematical model by making a table.

	Wheat	Corn	Soyabean	Availability
Let acres allotted be	x1	x2	x3	1000
Hence cost of preparation will be	120x1	100x2	70x3	1,00,000
Man days required	10x1	7x2	8x3	8000
Profit	40x1	30x2	20x3	To be maximized

Thus Objective function is maximization of z = 40x1 + 30x2 + 20x3

With constraints that x1 + x2 + x3 <= 1000

10x1 + 7x2 + 8x3 <= 8000

12x1 + 10x2 + 7x3 <= 10000

The standard for of mathematical system is as below

Maximization of z = 40x1 + 30x2 + 20x3 + 0s1 + 0s2 + 0s3

Subject to x1 + x2 + x3 + s1= 1000

10x1 + 7x2 + 8x3 + s2 = 8000

12x1 + 10x2 + 7x3 + s3 = 10000

		Cj	40	30	20	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
s1	0	1000	1	1	1	1	0	0
s2	0	8000	10	7	8	0	1	0
s3	0	10000	12	10	7	0	0	1
Z=	0	Zj	0	0	0	0	0	0
		Zj-Cj	-40	-30	-10	0	0	0

Key column is x1		(Xb/x1)1=	1000	(Xb/x1)2=	800	(Xb/x1)3=	833.3333
Key row is s2, So s2 replaced by x1				Pivotal element is =		10
Hence R2/10 then R1-R2 and R3-12R2

		Cj	40	30	20	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
s1	0	200	0	0.3	0.2	1	-0.1	0
x1	40	800	1	0.7	0.8	0	0.1	0
s3	0	400	0	1.6	-2.6	0	-1.2	1
Z=	32000	Zj	40	28	32	0	4	0
		Zj-Cj	0	-2	12	0	4	0

Key column is x2		(Xb/x2)1=	666.6667	(Xb/x2)2=	1142.857	(Xb/x2)3=	250
Key row is s3, So s3 replaced by x2				Pivotal element is =		1.6
Hence R3/1.6 then R1-0.3R3 and R2-0.7R3

		Cj	40	30	20	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
s1	0	125	0	0	0.6875	1	0.125	-0.1875
x1	40	625	1	0	1.9375	0	0.625	-0.4375
x2	30	250	0	1	-1.625	0	-0.75	0.625
Z=	32500	Zj	40	30	28.75	0	2.5	1.25
		Zj-Cj	0	0	8.75	0	2.5	1.25

As all (Zj-Cj) are positive iterative process ends here
Solution is x1 = 625 and x2 = 250 (x3 remains = 0)

Problem: Maximize the function z = 25x1 + 9x2 + 10x3 subjected to following three conditions using simplex method

12x1 + 3x2 + 4x3 <= 300

6x1 + 4x2 + x3 <= 225

3x1 + x2 + 2x3 <=100

And x1, x2, x3 >= 0

Solution: Express the mathematical model in standard for as below,

Maximize z = 25x1 + 9x2 + 10x3 + 0s1 + 0s2 + 0s3

Subject to 12x1 + 3x2 + 4x3 + s1 = 300

6x1 + 4x2 + x3 +s2 = 225

3x1 + x2 + 2x3 + s3 =100

		Cj	25	9	10	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
s1	0	300	12	3	4	1	0	0
s2	0	225	6	4	1	0	1	0
s3	0	100	3	1	2	0	0	1
Z=	0	Zj	0	0	0	0	0	0
		Zj-Cj	-25	-9	-10	0	0	0

Key column is x1		(Xb/x1)1=	25	(Xb/x1)2=	37.5	(Xb/x1)3=	33.33333
Key row is s1, So s1 replaced by x1				Pivotal element is =		12
Hence R1/12 then R2-6R1 and R3-3R1

		Cj	25	9	10	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
x1	25	25	1	0.25	0.333333	0.083333	0	0
s2	0	75	0	2.5	-1	-0.5	1	0
s3	0	25	0	0.25	1	-0.25	0	1
Z=	625	Zj	25	6.25	8.333333	2.083333	0	0
		Zj-Cj	0	-2.75	-10	2.083333	0	0

Key column is x3		(Xb/x3)1=	75	(Xb/x3)2=	-75	(Xb/x3)3=	25
Key row is s3, So s3 replaced by x3				Pivotal element is =		1
Hence R1-0.333333R3 and R2+R3

		Cj	25	9	10	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
x1	25	16.66667	1	0.166667	0	0.166667	0	-0.33333
s2	0	100	0	2.75	0	-0.75	1	1
x3	10	25	0	0.25	1	-0.25	0	1
Z=	612.5	Zj	25	6.666667	10	1.666667	0	1.666667
		Zj-Cj	0	-2.33333	0	1.666667	0	1.666667

Key column is x2		(Xb/x2)1=	100	(Xb/x2)2=	36.36364	(Xb/x2)3=	100
Key row is s2, So s2 replaced by x2				Pivotal element is =		2.75
Hence R2/2.75 then R1-0.1666667R2 and R3-0.25R2


		Cj	25	9	10	0	0	0
BV	Cb	Xb	x1	x2	x3	s1	s2	s3
x1	25	10.60606	1	0	0	0.212121	-0.06061	-0.39394
x2	9	36.36364	0	1	0	-0.27273	0.363636	0.363636
x3	10	15.90909	0	0	1	-0.18182	-0.09091	0.909091
Z=	751.5152	Zj	25	19	10	1.030303	0.848485	2.515152
		Zj-Cj	0	10	0	1.030303	0.848485	2.515152

Hence solution is x1 = 10.60606, x2 = 36.363636 and x3 = 15.90909

Problem: An industry produces two products A & B. Product A is sold at Rs. 50/- and B is sold at Rs. 12/- per piece. Each product passes through three different processes. Data for duration for these processes is given below

Process	Hours required		Available hrs/month
	Product A	Product B
I	75	15	1000
II	100	30	1500
III	45	10	750

Determine the quantity of products to be produced so as to maximize the sale.

Solution: The mathematical model will be;

To maximize z = 50x1 + 12 x2

With constraints that 75x1 + 15x2 <= 1000

100x1 + 30x2 <= 1500

45x1 + 10x2 <= 750

The standard form is z = 50x1 + 12 x2 + 0s1 + 0s2

Subject to 75x1 + 15x2 + s1 = 1000

100x1 + 30x2 + s2 = 1500

45x1 + 10x2 + s3 = 750

		Cj	50	12	0	0	0
BV	Cb	Xb	x1	x2	s1	s2	s3
s1	0	1000	75	15	1	0	0
s2	0	1500	100	30	0	1	0
s3	0	750	45	10	0	0	1
Z=	0	Zj	0	0	0	0	0
		Zj-Cj	-50	-12	0	0	0

Key column is x1		(Xb/x1)1=	13.33333	(Xb/x1)2=	15	(Xb/x1)3=	16.66667
Key row is s1, So s1 replaced by x1				Pivotal element is =		75
Hence R1/75 then R2-100R1 and R3-45R1

		Cj	50	12	0	0	0
BV	Cb	Xb	x1	x2	s1	s2	s3
x1	50	13.33333	1	0.2	0.013333	0	0
s2	0	166.6667	0	10	-1.33333	1	0
s3	0	150	0	1	-0.6	0	1
Z=	666.6667	Zj	50	10	0.666667	0	0
		Zj-Cj	0	-2	0.666667	0	0

Key column is x2		(Xb/x2)1=	66.66667	(Xb/x2)2=	16.66667	(Xb/x2)3=	150
Key row is s2, So s2 replaced by x2				Pivotal element is =		10
Hence R2/10 then R1-0.2R2 and R3-R2



		Cj	50	12	0	0	0
BV	Cb	Xb	x1	x2	s1	s2	s3
x1	50	10	1	0	0.04	-0.02	0
x2	12	16.66667	0	1	-0.13333	0.1	0
s3	0	133.3333	0	0	-0.46667	-0.1	1
Z=	700	Zj	50	12	0.4	0.2	0
		Zj-Cj	0	0	0.4	0.2	0

Hence Solution is x1 = 10, x2 = 16.6667 and s3 = 133.3333
z = 50x1 + 12x2 + 0s3
Thus s3 = 133.3333 is meaningless
Thus optimum solution is x1 = 10 and x2 = 16.666667

Problem: Maximize z = 2x1 + x2 – 3x3 + 5x4

Subject to x1 + 7x2 + 3x3 + 7x4 <=46

3x1 – x2 + x3 + 2x4 <=8

2x1 + 3x2 – x3 + x4 <= 10

And x1, x2, x3, x4 >= 0

Solution: Standard for of the system is,

Maximize z = 2x1 + x2 – 3x3 + 5x4 + 0s1 + 0s2 + 0s3

Subject to x1 + 7x2 + 3x3 + 7x4 + s1 =46

3x1 – x2 + x3 + 2x4 + s2 =8

2x1 + 3x2 – x3 + x4 + s3 = 10

		Cj	2	1	-3	5	0	0	0
BV	Cb	Xb	x1	x2	x3	x4	s1	s2	s3
s1	0	46	1	7	3	7	1	0	0
s2	0	8	3	-1	1	2	0	1	0
s3	0	10	2	3	-1	1	0	0	1
Z=	0	Zj	0	0	0	0	0	0	0
		Zj-Cj	-2	-1	3	-5	0	0	0

Key column is x4		(Xb/x4)1=	6.571429	(Xb/x4)2=	4	(Xb/x4)3=	10
Key row is s2, So s2 replaced by x4				Pivotal element is =		2
Hence R2/2 then R1-7R2 and R3-R2

		Cj	2	1	-3	5	0	0	0
BV	Cb	Xb	x1	x2	x3	x4	s1	s2	s3
s1	0	18	-9.5	10.5	-0.5	0	1	-3.5	0
x4	5	4	1.5	-0.5	0.5	1	0	0.5	0
s3	0	6	0.5	3.5	-1.5	0	0	-0.5	1
Z=	20	Zj	7.5	-2.5	2.5	5	0	2.5	0
		Zj-Cj	5.5	-3.5	5.5	0	0	2.5	0

Key column is x2		(Xb/x2)1=	1.714286	(Xb/x2)2=	-8	(Xb/x2)3=	1.714286
As (Xb/x2)1 = (Xb/x2)3, both the rows are equally eligible to become key row.
Here we may consider any one of the two row as key row.
taking key row as s1, So s1 replaced by x2				Pivotal element is =		10.5
Hence R1/10.5 then R2+0.5R1 and R3-3.5R1

		Cj	2	1	-3	5	0	0	0
BV	Cb	Xb	x1	x2	x3	x4	s1	s2	s3
x2	1	1.714286	-0.90476	1	-0.04762	0	0.095238	-0.33333	0
x4	5	4.857143	1.047619	0	0.47619	1	0.047619	0.333333	0
s3	0	0	3.666667	0	-1.33333	0	-0.33333	0.666667	1
Z=	26	Zj	4.333333	1	2.333333	5	0.333333	1.333333	0
		Zj-Cj	2.333333	0	5.333333	0	0.333333	1.333333	0

As all (Zj-Cj) are positive iterative process ends here
Solution is x2 = 1.714286 and x4 = 4.857143 (x1 and x3 remain = 0)

Problem: Minimize z = x2 – 3x3 + 2x5

Subject to x1 + 3x2 – x3 + 2x5 = 7

-2x2 + 4x3 + x4 = 12

-4x2 + 3x3 + 8x5 + x6 = 10

And x1, x2, x3, x4, x5, x6 >=0

Solution: It is observed that coefficients of x1, x4 and x6 in objective function are = 0. Also their coefficients in constraint equation are two times zero and one time 1. Further the constraints do not have inequality signs. Hence it may be assumed that x1, x4 and x6 are surplice variables (s–variables). Therefore standard form is

Maximize z = –x2 + 3x3 – 2x5 + 0x1 + 0x4 + 0x6

Subject to x1 + 3x2 – x3 + 2x5 = 7

–2x2 + 4x3 + x4 = 12

–4x2 + 3x3 + 8x5 + x6 = 10

		Cj	0	-1	3	0	-2	0
BV	Cb	Xb	x1	x2	x3	x4	x5	x6
x1	0	7	1	3	-1	0	2	0
x4	0	12	0	-2	4	1	0	0
x6	0	10	0	-4	3	0	8	1
Z=	0	Zj	0	0	0	0	0	0
		Zj-Cj	0	1	-3	0	2	0

Key column is x3		(Xb/x3)1=	-7	(Xb/x3)2=	3	(Xb/x3)3=	3.333333
Key row is x4, So x4 replaced by x3				Pivotal element is =		4
Hence R2/4 then R1+R2 and R3-3R2

		Cj	0	-1	3	0	-2	0
BV	Cb	Xb	x1	x2	x3	x4	x5	x6
x1	0	10	1	2.5	0	0.25	2	0
x3	3	3	0	-0.5	1	0.25	0	0
x6	0	1	0	-2.5	0	-0.75	8	1
Z=	9	Zj	0	-1.5	3	0.75	0	0
		Zj-Cj	0	-0.5	0	0.75	2	0

Key column is x2		(Xb/x2)1=	4	(Xb/x2)2=	-6	(Xb/x2)3=	-0.4
Key row is x1, So x1 replaced by x2				Pivotal element is =		2.5
Hence R1/2.5 then R2+0.5R1 and R3+2.5R1

		Cj	0	-1	3	0	-2	0
BV	Cb	Xb	x1	x2	x3	x4	x5	x6
x2	-1	4	0.4	1	0	0.1	0.8	0
x3	3	5	0.2	0	1	0.3	0.4	0
x6	0	11	1	0	0	-0.5	10	1
Z=	11	Zj	0.2	-1	3	0.8	0.4	0
		Zj-Cj	0.2	0	0	0.8	2.4	0

As all (Zj-Cj) are positive iterative process ends here
Solution is x2 = 4, x3 = 5 and x6 = 11 (x1and x4 become zero and x5 remains = 0)
As coefficient of x6 in objective function is zero x6 = 11 has no meaning;
Therefore solution is x2 = 4, x3 = 5 and x5 = 0

Hosted by www.Geocities.ws