linear programming ( pemrograman linier)

DR. Rahma Fitriani, S.Si., M.Sc

Linear Programming(Pemrograman Linier)Program Studi StatistikaSemester Ganjil 2011/2012

Algoritma Simpleks dalam Notasi Matriks

),...,2,1(0

...

.

.

.

.

.

.

.

.

.

.

.

.

...

... ..

...max

2211

22222121

11212111

2211

nix

bxaxaxa

bxaxaxa

bxaxaxats

xcxcxcz

i

mnmnmm

nn

nn

nn

LP Secara umum:

LP yang bersesuaian untuk Dakota

0,,,,,

8 5.05.12

20 5.124

48 68 ..

000203060max

321321

3321

2321

1321

321321

sssxxx

sxxx

sxxx

sxxxts

sssxxxz

Tableau Optimal dari LP Dakota

25.10.5 25.1

8 42 2

24 82 2

2801010 5

3221

3232

3212

322

ssxx

ssxx

sssx

ssxz

Tableau 2 z x1 x2 x3 s1 s2 s3 rhs BV

Baris 0 1 0 5 0 0 10 10 280 z=280Baris 1 0 0 -2 0 1 2 -8 24 s1=24Baris 2 0 0 -2 1 0 2 -4 8 x3=8Baris 3 0 1 1.25 0 0 -0.5 1.5 2 x1=2

Atau dalam bentuk lain:

131 ,, xxsBV 322 ,, ssxNBV

Beberapa Notasi

131 ,, xxsBV 322 ,, ssxNBV

1

3

1

x

x

s

BVx

3

2

2

s

s

x

NBVx

Koefisien untuk BV pada struktur biaya di fungsi obyektif:

60200BVc

321321 000203060 sssxxxz

Koefisien untuk NBV pada struktur biaya di fungsi obyektif:

0003NBVc

Beberapa Notasi

Koefisien untuk BV pada kendala dapat dinyatakan dalam bentuk matriks:

8 5.05.12

20 5.124

48 68

3321

2321

1321

sxxx

sxxx

sxxx 131 ,, xxsBV

1s3x1x

25.00

45.10

811

B

0

0

1

1sa

5.0

5.1

1

3a

2

4

8

1a

Beberapa Notasi

Koefisien untuk NBV pada kendala dapat dinyatakan dalam bentuk matriks:

8 5.05.12

20 5.124

48 68

3321

2321

1321

sxxx

sxxx

sxxx 322 ,, ssxNBV

2x 2s 3s

105.1

012

006

N

5.1

2

6

2a

0

1

0

2sa

1

0

0

3sa

Beberapa Notasi

Koefisien untuk rhs pada kendala dapat dinyatakan dalam bentuk vektor:

8 5.05.12

20 5.124

48 68

3321

2321

1321

sxxx

sxxx

sxxx

8

20

48

b

LP Dakota dalam notasi matriks

3

2

2

1

3

1

003060200max

s

s

x

x

x

s

z

8

20

48

105.1

012

006

25.00

45.10

811

..

3

2

2

1

3

1

s

s

x

x

x

s

ts

0,,,,,

8 5.05.12

20 5.124

48 68 ..

000203060max

321321

3321

2321

1321

321321

sssxxx

sxxx

sxxx

sxxxts

sssxxxz

,0

1

3

1

x

x

s

0

3

2

2

s

s

x

1

3

1

x

x

s

BVx

3

2

2

s

s

x

NBVx

105.1

012

006

N

8

20

48

b

60200BVc 0003NBVc

25.00

45.10

811

B

0,

B ..

max

NBVBV

NBVBV

NBVNBVBVBV

ts

z

xx

bNxx

xcxc

Dengan Notasi Matriks dan vektor:

Penentuan solusi dalam notasi matriks

Solusi suatu sistem persamaan dalam notasi matriks adalah dengan perkalian invers matriks

bNxx NBVBVB

Kendala LP dalam notasi matriks:

Solusi diperoleh jika BV mempunyai bentuk kanonik.Matriks bagi BV dalam bentuk matriks identitas hasil perkalian dengan invers-nya.IBB-1

bNxx -1-1-1 BBBB NBVBV

Mengalikan setiap suku dengan invers dari B

bNxx -1-1 BB NBVBV

Penentuan solusi dalam notasi matriksUntuk LP Dakota:

25.00

45.10

811

B

5.15.00

420

8211B

Dengan mengalikan invers dari B pada kendala: bNxx -1-1 BB NBVBV

8

20

48

5.15.00

420

821

105.1

012

006

5.15.00

420

821

3

2

2

1

3

1

s

s

x

x

x

s

2

8

24

5.15.025.1

422

822

3

2

2

1

3

1

s

s

x

x

x

s

Penentuan Solusi dalam notasi Matriks: untuk Kendala



2

8

24

5.15.025.1

422

822

3

2

2

1

3

1

s

s

x

x

x

s

Kolom untuk peubah xj dalam kendala di tableau optimal:

ja-1B

Kolom untuk rhs dalam kendala di tableau optimal:b-1B

Perbandingan dengan Tableu Optimal



Misal: Kolom untuk peubah x2 dan dalam kendala di tableau optimal:

2-1B a

Kolom untuk peubah s2 dalam kendala di tableau optimal:

5.15.00

420

8211B

5.1

2

6

2a

25.1

2

2

B 21- a

2

-1B sa

5.15.00

420

8211B

0

1

0

2sa

5.0

2

2

B2

1-sa

Dengan cara sama untuk peubah yang lain

-2-2

1.25

22

-0.5

Perbandingan dengan Tableu Optimal




5.15.00

420

8211B

8

20

48

b

2

8

24

B 1- b

Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif

0 NBVNBVBVBVNBVNBVBVBV zz xcxcxcxc

bNxx NBVBVB

Tableau 2 z x1 x2 x3 s1 s2 s3 rhs

Baris 0 1 0 5 0 0 10 10 280

131 ,, xxsBV

Di dalam tableau optimal, koefisien BV harus sama dengan nol, koefisien NBV ≠ 0

=0

Dengan memanfaatkan persamaan pada kendala: lakukan ERO

Tambahkan kendala yang sudah dikalikan dengan matriks yang bersesuaian pada baris nol, untuk membuat jadi nol BV


0 NBVNBVBVBVz xcxc

bNxBx NBVBV

(*) + (**)

Kalikan dengan:-1BBVc

bBcNxBcBxBc -1-1-1BVNBVBVBVBV bBcNxBcxc -1-1

BVNBVBVBVBV

(*)

(**)

_____________________________

0 1-1- bBcNxBcxc

xcxc

BVNBVBVBVBV

NBVNBVBVBVz

bBcxcNBc 11 BVNBVNBVBVz

Kendala:


bBcxcNBc 11 BVNBVNBVBVz

Pada tableau optimal, koefisien NBV ≠ 0:

NBVBV cNBc 1

105.1

012

006

N

5.1

2

6

2a

0

1

0

2sa

1

0

0

3sa

Komponen dari matriks N (dan B) adalah vektor (kolom) koefisien setiap peubah NBV (dan BV) pada kendala: aj

Komponen dari vektor CNBV (dan CBV ) adalah koefisien fungsi obyektif setiap peubah NBV (dan BV): cj 0003NBVc

322 ss ccc

Contoh LP Dakota:


Secara umum koefisien baris nol pada tableau optimal per komponen:

jjBVj cBc ac 1

RHS baris nol pada tableau optimal: bBc 1-BV

Contoh LP Dakota:

5.15.00

420

8211B

5.1

2

6

2a

0

1

0

2sa

1

0

0

3sa

10100BVc

221

2 cc BV aBc

101001 BcBV

30

5.1

2

6

10100

0030NBVc

53035

Koefisien untuk x2


5.15.00

420

8211B

5.1

2

6

2a

0

1

0

2sa

1

0

0

3sa

10100BVc

222

1ssBVs cc aBc

101001 BcBV

0

0

1

0

10100

0030NBVc

10010

Koefisien untuk s2

333

1ssBVs cc aBc 0

1

0

0

10100

10010

Koefisien untuk s3

Koefisien rhs baris nol (z maks):

8

20

48

101001- bBcBV 280802000

Ringkasan solusi optimal dalam notasi matriks

Kolom untuk peubah xj dalam kendala di tableau optimal:

ja-1B


Koefisien baris nol pada tableau optimal per komponen:

jjBVj cBc ac 1

RHS baris nol pada tableau optimal: bBc 1-BV

Contoh LP dan solusinya dengan notasi Matriks

0,

82

62 ..

4max

21

21

21

21

xx

xx

xxts

xxz

Diketahui solusi optimal mempunyai: 22 , sxBV

Tentukan tableau optimal dengan menggunakan metode matriks!Bentuk standar LP:

0,,,

8 2

6 2 ..

4max

2121

221

121

21

ssxx

sxx

sxxts

xxz

22 , sxBV

0,,,

8 2

6 2 ..

4max

2121

221

121

21

ssxx

sxx

sxxts

xxz

Tentukan matriks/vektor yang diperlukan:

B

11

02b

8

6 04BVc

Kolom untuk peubah x1 dalam kendala di tableau optimal:

1-1B a

1

0

21

21

1B

2

1

1

0

21

21

23

21

Di dalam tableau optimal, peubah BV pasti mempunyai bentuk kanonik, tinggal menentukan kolom untuk peubah NBV

11, sxNBV

01NBVc

Kolom untuk peubah s1 dalam kendala di tableau optimal:

1

-1B sa

0

1

1

0

21

21

21

21

Tableau Optimal z x1 x2 s1 s2 rhs

Baris 0

Baris 1

Baris 2

1/2

3/2

1/2

-1/2

Kolom untuk peubah BV dalam kendala di tableau optimal: Bentuk kanonik

22 , sxBV

Kolom untuk peubah x2 :

0

1

Cross cek dengan rumus:2

-1B a

1

2

1

0

21

21

0

1

Kolom untuk peubah s2 :

1

0

2

-1B sa

1

0

1

0

21

21

1

0


Baris 0

Baris 1

Baris 2

1/2

3/2

1/2

-1/2

1

0

0

1

Kolom untuk rhs pada tableau optimal:

b-1B

8

6

1

0

21

21

5

3

-1BBVc

1

004

21

21

02


Baris 0

Baris 1

Baris 2

1/2

3/2

1/2

-1/2

1

0

0

1

3

5

Komponen baris nol untuk BV pada tableau optimal selalu sama dengan nol. 22 , sxBV

0 0

Komponen baris nol untuk NBV pada tableau optimal memerlukan hasil perkalian:

11-1

1 B cc BV ac


Baris 0

Baris 1

Baris 2

1/2

3/2

1/2

-1/2

1

0

0

1

3

5

0 0

Komponen baris nol untuk NBV pada tableau optimal:

02B-1 BVc

11, sxNBV 01NBVc

12

102

112

111

-1B ssBVs cc ac 00

102

202

1 2

bc -1BBV


Baris 0

Baris 1

Baris 2

1/2

3/2

1/2

-1/2

1

0

0

1

3

5

0 0

Komponen baris nol untuk rhs pada tableau optimal:

8

602 12

1 2

8

6b

12

Lengkapi kolom z

1

0

0

Solusi optimal: (max)12,5,0,3,0 2121 zssxx

BV

z=12

x2=3

s2=5

linear programming ( pemrograman linier)

Documents