Optimization Problems With Simplex And Lagrange Methods

1. Solve the following problem using the simplex method.
Maximise p = 4 x + 6 y + 3 z
Subjected to the following constraints:
(N+1) x + 4 y + 3 z ≤ 12
4 x + 3 y + 2 z ≤ 10
2 x + 4 y + z ≤ 8
x≥ 0, y≥ 0 and z≥ 0
2. By using the Lagrange multiplier method, find the dimensions of a rectangular box of volume V = 1000 × (N+1)2 cm3 for which the total length of the 12 edges is minimum.
3. Consider the function f(x) = x4 – 14x3 + (N+51) x2 - 70x
Use the golden section search technique to find the value of x that minimises f over the range 0 ≤ x ≤ 2. Locate the x value within an interval of 15% uncertainty of the initial search interval. Present your answer in a tabular format.
4. A manufacturing company produces two types of products, Product A and Product B. The various restrictions, requirements and unit profits are shown below. By using the analytical linear programming method determine how many of Product A and Product B should be produced to maximise the profit. Present your answer in a tabular format.
† Individual assignment
Profit Raw Material Electricity Labour
Product A 3 5 1 1
Product B 4 2 1 2
Amount available ---- 31 + N 10

As given in question,

Maximize p = 4x + 6y + 3z subject to

6x + 4y + 3z <= 12

4x + 3y +2z <= 10

2w + 4y + z <= 8

x>=0

y>=0

z>=0

Suppose s­­_1, s_2, s_3, s_4, s_{5 and s6}  are the slack variable, the above equation can be tabulated as follows

Table	#1
x	y	z	s1	s2	s3	s4	s5	s6	p
6	4	3	1	0	0	0	0	0	0	12
4	3	2	0	1	0	0	0	0	0	10
2	4	1	0	0	1	0	0	0	0	8
4	6	3	0	0	0	0	0	0	0

 

Further row and column operation can be done as follows

Tableau	#1
x	y	z	s1	s2	s3	s4	s5	s6	p
6	4	3	1	0	0	0	0	0	0	12
4	3	2	0	1	0	0	0	0	0	10
0	4	1	0	0	1	0	0	0	0	8
1	0	0	0	0	0	-1	0	0	0	0
0	1	0	0	0	0	0	-1	0	0	0
0	0	1	0	0	0	0	0	-1	0	0
-4	-6	-3	0	0	0	0	0	0	1	0

 

Tableau	#2
x	y	z	s1	s2	s3	s4	s5	s6	p
6	4	3	1	0	0	0	0	0	0	12
4	3	2	0	1	0	0	0	0	0	10
0	4	1	0	0	1	0	0	0	0	8
-1	0	0	0	0	0	1	0	0	0	0
0	1	0	0	0	0	0	-1	0	0	0
0	0	1	0	0	0	0	0	-1	0	0
-4	-6	-3	0	0	0	0	0	0	1	0

 

Tableau	#3
x	y	z	s1	s2	s3	s4	s5	s6	p
6	4	3	1	0	0	0	0	0	0	12
4	3	2	0	1	0	0	0	0	0	10
0	4	1	0	0	1	0	0	0	0	8
-1	0	0	0	0	0	1	0	0	0	0
0	-1	0	0	0	0	0	1	0	0	0
0	0	1	0	0	0	0	0	-1	0	0
-4	-6	-3	0	0	0	0	0	0	1	0

 

Tableau	#4
x	y	z	s1	s2	s3	s4	s5	s6	p
6	4	3	1	0	0	0	0	0	0	12
4	3	2	0	1	0	0	0	0	0	10
0	4	1	0	0	1	0	0	0	0	8
-1	0	0	0	0	0	1	0	0	0	0
0	-1	0	0	0	0	0	1	0	0	0
0	0	-1	0	0	0	0	0	1	0	0
-4	-6	-3	0	0	0	0	0	0	1	0

 

Tableau	#5
x	y	z	s1	s2	s3	s4	s5	s6	p
6	0	2	1	0	-1	0	0	0	0	4
4	0	1.3	0	1	-0.75	0	0	0	0	4
0	1	0.25	0	0	0.25	0	0	0	0	2
-1	0	0	0	0	0	1	0	0	0	0
0	0	0.25	0	0	0.25	0	1	0	0	2
0	0	-1	0	0	0	0	0	1	0	0
-4	0	-1.5	0	0	1.5	0	0	0	1	12

 

Tableau	#6
x	y	z	s1	s2	s3	s4	s5	s6	p
1	0	0.33	0.17	0	-0.17	0	0	0	0	0.67
0	0	-0.083	-0.67	1	-0.083	0	0	0	0	1.3
0	1	0.25	0	0	0.25	0	0	0	0	2
0	0	0.33	0.17	0	-0.17	1	0	0	0	0.67
0	0	0.25	0	0	0.25	0	1	0	0	2
0	0	-1	0	0	0	0	0	1	0	0
0	0	-0.17	0.67	0	0.83	0	0	0	1	15

 

Table	#7
x	y	z	s1	s2	s3	s4	s5	s6	p
3	0	1	0.5	0	-0.5	0	0	0	0	2
0.25	0	0	-0.63	1	-0.12	0	0	0	0	1.5
-0.75	1	0	-0.13	0	0.38	0	0	0	0	1.5
-1	0	0	0	0	0	1	0	0	0	0
-0.75	0	0	-0.13	0	0.38	0	1	0	0	1.5
3	0	0	0.5	0	-0.5	0	0	1	0	2
0.5	0	0	0.75	0	0.75	0	0	0	1	15

Since, we can see that, no positive unit solution for x variable, in this condition it can be taken as 0, y = 1.5 and z = 2, the maximum value of P whiting the given condition is 15

Solution 2

As given in problem,

We have to minimize total length i.e. f(x,y,z) = 4x+4y+4z, in which x, y and z are length width and height

Which is subjected to the constant g(x,y,z) = xyz = 1000 (5+1)² = 36000 cm³,

By implementing Lagrange multiplier, we get

                        f(x­₀,y₀,z₀) = λ f (x­₀,y₀,z₀)

Using this equation in the above minimization problem

            4x + 4y =  λxy             ….. (i)

            4y + 4z =  λyz             ….. (ii)

            4x + 4z =  λzx             ….. (iii)

Since the constraints x  0, y  0, and z  0, in this condition, we have to solve λ for each equation in pairs we get,

                             ….. (iv)

                              ….. (v)

                  ….. (vi)

From equation (iv) and (v) we get,

              =   or x =z

            Similarly, equation (v) and (vi) we get

                        X =z, i.e. x =y=z

From the above solution it’s clear that the sum will be minimum when all dimension will be equal, i.e. the box will be in the form of cuboid

                        Putting g the value in constrain

                                    Xyz = x³ = 36000

                        Or,   x = , therefore all side will be x = =            Ans

Solution 3

As given in question,

The value of x range as given =  = [0, 2]

The steps to be followed is as given

1         

Now applying the gold section method at  (Suppose)

2  Now putting the value in function,        

           We have to minimise the problem          

            F(0) = 4

Now f(0) = 0, f(0.7639) = -24.361,  f(1.2631) = -18.958

            Value less than f(2) = 4

            X₃ 0.4722 = (0+L₃^*)           

            F(0) = 0 à  f(x1) = -24.361           

                        F(0) = 0    

Function	L1	L­2 (0, 1.2361)	L3 (0.4722, 1.2361)
f(x1)	(0,2)	-24.361
f(x2)	(0,2)	-18.958
f(x3)	(0,2)		-21.1

The constraints can be tabulated as follows

	Profit	Raw Material	Electricity	Labor
Product A	3	5	1	1
Product B	4	2	1	2
Amount available	----	36	10	16

Suppose the number of product A =x

And No of product B = y

            Then, Profit (Z) = 3x +4y, we must maximize Z to solve the problem

            The constraints can be written as

            5x+2y  36       ……… (i)

            x+y  10            ……… (ii)

            x+2y  16           ……... (iii) 

Suppose s₁ , s_2, s_3, s_{4 ,} s₅  are the slack variable for the given above equation.

After performing different operation in row and column

Table	1
x	y	s1	s2	s3	s4	s5	p
5	2	1	0	0	0	0	0	36
1	1	0	1	0	0	0	0	10
1	2	0	0	1	0	0	0	16
1	0	0	0	0	-1	0	0	0
0	1	0	0	0	0	-1	0	0
-3	-4	0	0	0	0	0	1	0

 

Table	2
x	y	s1	s2	s3	s4	s5	p
5	2	1	0	0	0	0	0	36
1	1	0	1	0	0	0	0	10
1	2	0	0	1	0	0	0	16
-1	0	0	0	0	1	0	0	0
0	1	0	0	0	0	-1	0	0
-3	-4	0	0	0	0	0	1	0

 

Table	3
x	y	s1	s2	s3	s4	s5	p
5	2	1	0	0	0	0	0	36
1	1	0	1	0	0	0	0	10
1	2	0	0	1	0	0	0	16
-1	0	0	0	0	1	0	0	0
0	-1	0	0	0	0	1	0	0
-3	-4	0	0	0	0	0	1	0

 

Table	4
x	y	s1	s2	s3	s4	s5	p
4	0	1	0	-1	0	0	0	20
0.5	0	0	1	-0.5	0	0	0	2
0.5	1	0	0	0.5	0	0	0	8
-1	0	0	0	0	1	0	0	0
0.5	0	0	0	0.5	0	1	0	8
-1	0	0	0	2	0	0	1	32

 

Table	5
x	y	s1	s2	s3	s4	s5	p
0	0	1	-8	3	0	0	0	4
1	0	0	2	-1	0	0	0	4
0	1	0	-1	1	0	0	0	6
0	0	0	2	-1	1	0	0	4
0	0	0	-1	1	0	1	0	6
0	0	0	2	1	0	0	1	36

After making positive in all bottom line It was found that the value of x and are 4 and 6 respectively, the maximum profit that can be made is 36. This is tabulated below.           

	Profit	Raw Material	Electricity	Labor
Product A	12	20	4	4
Product B	24	12	6	12
Amount available	----	32 <=36	10	16

Aczel Amir D.  Complete business statistics. NJ :: Morristown, , 2012.

Shuqin Yang. Applications of Excel in teaching Statistics. 2005.

Berenson Mark. 2 Basic Business Statistics. Sydney :: Pearson. 2012.

Broadman Bart.  DBS Group Holdings Ltd | Annual Report 2015. Singapore :: DBS Pub. 2014.

Barron's.  Business Statistics. New York :: 2010.

Krehbiel Heather Haskin & Timothy. Business statistics at the top 50 US business programmes. Dubline:: NSK. 2011.

Chng Pamela.  Bettr Barista Coffee Academy. Singapore : :Singa publisher. 2015.

Douglas Lind. William Marchal. Samuel Wathen. Basic Statistics for Business and Economics. New York : :McGraw-Hill Higher Education. 2012.