simplex - soalan kuiz 17feb 2014.xls

8/12/2019 Simplex - soalan kuiz 17Feb 2014.xls

1/6

Example 2

Example of using the Simplex method to solve linear programming problem.

Original Q: A factory produces two types of drink, an "energy" drink and a "refresher" drink.

The day's output is to be planned. Each drink requires syrup, vitamin and flavouring

as shown in the table The last row in the table shows how much of each ingredient

is available for the day's production.

Syrup Vitamin Flavouring Syrup Vitamin Flavouring

5L Energy Drink 1.25L 2 units 30cc 1L Energy Drink 0.25L 0.4 units 6 cc

5L Refresher Drink 1.25L 1 unit 20cc 1L Refresher Drink 0.25L 0.2 unit 4 cc

Available 250L 300 units 4.8L Available 250L 300 units 4800 cc

Let x = number of litres of Energy drink produced slack

y = number of litres of Refresher drink produced variable

Then, 0.25x + 0.25y 250 x+y 1000 x 4 s1

0.4x + 0.2y 300 2x+y 1500 x 5 s2

6x + 4y 4800 3x+2y 2400 2 s3

To maximise I = x + 0.8y

x,y 0 Trivial so no need to consider

x+y 1000 Introduce slack variable s1: x + y + s1 = 1000

2x+y 1500 Introduce slack variable s2: 2x+ y + s2 = 1500

3x+2y 2400 Introduce slack variable s3: 3x+ 2y + s3 = 2400

Choose x as the pivot column(although not necessary. Can also choose y as the pivot column)Divide RHS by entries of pivot column. The row with the smallestresult is the pivot row (R2)

I x y s1 s2 s3 RHS

1 -1 -0.8 0 0 0 0 R0

0 1 1 1 0 0 1000 R1 10001=1000

0 2 1 0 1 0 1500 R2 1500 2=750 PR

0 3 2 0 0 1 2400 R3 24003=800

I x y s1 s2 s3 RHS

1 -1 -0.8 0 0 0 0 R0

0 1 1 1 0 0 1000 R1

R2 2 0 1 0.5 0 0.5 0 750 R2

0 3 2 0 0 1 2400 R3

I x y s1 s2 s3 RHS

R0 + (R2) 1 0 -0.3 0 0.5 0 750 R0

R1 + (-R2) 0 0 0.5 1 -0.5 0 250 R1 2500.5= 500

R2 0 1 0.5 0 0.5 0 750 R2 7500.5=1500 PR

R3 + (-3R2) 0 0 0.5 0 -1.5 1 150 R3 1500.5= 300 next PR

I x y s1 s2 s3 RHS s2 is now the pivot column

R0+ (0.6R3) 1 0 0 0 -0.4 0.6 840 R0

R1+ (-R3) 0 0 0 1 1 -1 100 R1 1001= 100 next PR

R2+ (-R3) 0 1 0 0 2 -1 600 R2 6002= 300

R3 0 0 0.5 0 -1.5 1 150 R3

I x y s1 s2 s3 RHS

R0+(0.4R1) 1 0 0 0.4 0 0.2 880 R0

R1 0 0 0 1 1 -1 100 R1 PR

R2+(-2R1) 0 1 0 -2 0 1 400 R2

R3+(1.5R1) 0 0 0.5 1.5 0 -0.5 300 R3

The R0 row contains only positive elements and so the maximum value

for P has been reached. The top row gives: I+ 0.4s1+ 0.3s3 = 880

I + 0.4s1 + 0.2s3 = 880 I = 880 - 0.4s1 - 0.2s3 I max when s1= s3 = 0

s1 + s2 - s3 = 100

x - 2s1 + s3 = 400 s2 = 100

y +3s1 - s3 = 600

Hence the maximum value is I max= 880and occurs when x = 400, y = 600,

S2 = 100. Then vitamin not used = (100/5) = 20 units

Convert to equation by introducing slack variable si I - x - 0.8y = 0

ipgm/koo


2/6

Kuiz 1 : Simpleks (5 markah)

Menggunakan kaedah simpleks untuk menyelesaikan masalah pengaturcaraan linear.

Bagi memaksimakan P = -x + 8y + z berdasarkan kepada kekangan-kekangan berikut:

Tukar kekangan kepada persamaan dengan memperkenalkan pembolehubah slack; s i

(i) x + 2y + 9z 10 masukkan pembolehubah slack and x+2y+9z+s1=10

(ii) y + 4z 12 tulis dalam bentuk persamaan y+4z+s2=12

(iii) x, y, z 0 diabaikan

Lajur pangsiLP

P x y z s1 s2 RHS

R 1 1 -8 -1 0 0 0 R

R 0 1 2 9 1 0 10 R PR

R 0 0 1 4 0 1 12 R

P x y z s1 s2 RHS

R 1 1 -8 -1 0 0 0 R

R1 2 0 0.5 1 4.5 0.5 0 5 RR 0 0 1 4 0 1 12 R

P x y z s1 s2 RHS

R0+8(R1) 1 5 0 35 4 0 40 R

R 0 0.5 1 4.5 0.5 0 5 R

R2-R1 0 -0.5 0 -0.5 -0.5 1 7 R

Rmengandungi elemen positif. Dengan ini boleh dikatakan nilai maksima bagi P telah tercapai.

R P+5x+35z+4s1=40

R 0.5x+y+4.5z+0.5s1=5

R 0.5z -0.5 s1+s2=7

Oleh itu, nilai maksima bagi P ialah = ? dan akan berlaku apabila P=40

x = 5, z=35, y=0, s=4 s= 0

5

Tukar P +x-8y-z=0

BP= baris pangsi

ipgm/koo


3/6

ipgm/koo


4/6

Kuiz 2

P=16x+24y x,y 0

2x+3y 24 2x+3y +s1= 24

2x+y 16 2x+y +s2= 16

y 6 y +s3= 6

Mula dengan x sebagai LP

P x y s1 s2 s3 RHS P x y s1 s2

1 -16 -24 0 0 0 0

0 2 3 1 0 0 24

0 2 1 0 1 0 16

0 0 1 0 0 1 6


1 -16 0 0 0 24 1440 2 0 1 0 -3 6

0 2 0 0 1 -1 10

0 0 1 0 0 1 6


1 -16 0 0 0 24 144

0 2 0 1 0 -3 6

0 2 0 0 1 -1 10

0 0 1 0 0 1 6


1 -16 0 0 0 24 144

0 1 0 0.5 0 -1.5 3

0 2 0 0 1 -1 10

0 0 1 0 0 1 6


1 0 0 8 0 0 192

0 1 0 0.5 0 -1.5 3

0 0 0 -1 1 2 4

0 0 1 0 0 1 6

P x y s1 s2

Jawapan: P=192

x=3

y=6

Jawapan

Mula dengan y sebagai LP (lajur pangsi)


5/6

RHS

RHS

RHS

RHS

RHS

RHS


6/6

Exercise 1A. No. 3 P=9x+10y+6z x,y,z 0

2x+3y+4z 3

6x+6y+2z 8

P x y z s1 s2 RHS

R0 1 -9 -10 -6 0 0 0 R0

R1 0 2 3 4 1 0 3 R1 PR

R2 0 6 6 2 0 1 8 R2 ?

P x y z s1 s2 RHSR0 1 -9 -10 -6 0 0 0 R0

R13 0 1 1.33 0.33 0 1 R1

R2 0 6 6 2 0 1 8 R2

P x y z s1 s2 RHS

R0 +10(R1) 1 -2.3 0 7.3 3.3 0 10 R0

R1 0 0.67 1 1.33 0.33 0 1 R1

R2-6(R1) 0 2 0 -6 -2 1 2 R2

P x y z s1 s2 RHS

R0 1 -2.3 0 7.3 3.3 0 10 R0

R1 0 0.67 1 1.33 0.33 0 1 R1 ?R2 0 2 0 -6 -2 1 2 R2 PR

P x y z s1 s2 RHS

R0 1 -2.3 0 7.3 3.3 0 10 R0

R1 0 0.67 1 1.33 0.33 0 1 R1

R22 0 1 0 -3 -1 0.5 1 R2

P x y z s1 s2 RHS

R0 + 21/3(R2) 1 0 0 0.33 1 12 1/3 R0

R1-2/3 (R2) 0 0 1 3 1/3 1 -0.33 R1

R2 0 1 0 -3 -1 1 R2

Berdasarkan jadual simpleks yang terakhir: tulis persamaan untuk

P = 12 1/3

x =1

y= 1/3

z=0

Oleh itu, nilai maksima bagai P = 37/3 apabila

x = 1 y=1/3, z=0

2

3

7

6

1

3

1

2

simplex - soalan kuiz 17feb 2014.xls

Documents