riset operasionaluipnusra.id/siamad/public/uploads/files_stamp/transmisi/...riset operasional...

Riset OperasionalPertemuan 3:

“Program Linier: Metode Simpleks”Dosen : MOH. ALI ALBAR, ST., M.Eng

Program Studi Teknik Informatika

Fakultas Teknik UNRAM

2016

Merupakan perluasan metode grafik

Prinsip kerja metode simpleks dan grafik sebenarnya sama, yaitu mencari

nilai fungsi di titik ujung daerah fisibel.

Hanya saja dalam metode simpleks, pencarian iteratif dilakukan secara

numerik sehingga terhindar dari keterbatasan jumlah variabel seperti yang

dialami oleh metode grafik.

3.1 Bentuk Standar Simpleks

Sebelum melakukan proses iterasi metode simpleks, masalah harus terlebih dahulu

dibawa ke bentuk standar metode simpleks

Bentuk standar metode simpleks adalah sebagai berikut:

Maksimumkan/Minimumkan

dengan kendala:

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

1 2 1 2

...

...

...

...

, , ..., 0 , , ..., 0

n n

n n

m m mn n m

n m

a x a x a x b

a x a x a x b

a x a x a x b

X x x x dan b b b b

1 1 2 2 ... n nf X c x c x c x

Dalam notasi vektor/matriks, bentuk standar simpleks dapat dinyatakan

sebagai

Maksimumkan/Minimumkan

dengan kendala:

11 12 1 1 1

21 12 2 2 2

1 2

1 2

0, 0

...

...; ; ; , , ...,

... ... ... ... ... ...

...

n

n

n

m m mn n n

Ax b

x b dengan

a a a x b

a a a x bA x b c c c c

a a a x b

z c x

Dalam bentuk standar metode simpleks, ada 2 hal yang harus diperhatikan:

1. Semua kendala harus berbentuk persamaan. Apabila kendala berbentuk

pertidaksamaan, maka harus diubah ke bentuk persamaan dengan

penambahan variabel slack secukupnya. Koefisien variabel slack dalam fungsi

sasaran = 0

2. Semua ruas kanan kendala tidak boleh negatif. Apabila ada kendala yang ruas

kanannya negatif maka harus diubah dulu menjadi tak negatif dengan

mengalikan kendala tersebut dengan (-1).

Contoh 3.1 Jadikan betuk berikut ini menjadi bentuk standar simpleks:

a. Maksimumkan

Kendala:

b. Minimumkan

Kendala:

1 2z x x

1 2

1 2

1 2

5 5

2 4

, 0

x x

x x

x x

1 2 32 4z x x x

1 2 3

1 2 3

1 2 3

5 2 3 7

2 2 8

, , 0

x x x

x x x

x x x

Penyelesaian

Jadikan bentuk berikut ini menjadi bentuk standar simpleks :

a. Maksimumkan Z = x1 + x2

Kendala x1 + 5 x2 5

2 x1 + x2 4 x1, x2 0Penyelesaian :

Tiap kendala yg berbentuk pertidaksamaan harus ditambah

variabel slack agar menjadi persamaan

Kendala x1 + 5 x2 = 5

2 x1 + x2 = 4

Maksimumkan Z = x1 + x2

x1, x2 0

x 3

x4

+

+

+ x3 + x400

, x3 , x4

x3 dan x4 adalah

variabel slack. Koefisien

variabel slack di fungsi

tujuan = 0

b. Minimumkan Z = 2 x1 - x2 + 4 x3

Kendala 5 x1 + 2 x2 - 3 x3 -7

2 x1 - 2 x2 + x3 8

x1, x2, x3 0

Penyelesaian :

Ada 2 syarat bentuk standar simpleks :

• Ruas kanan (konstanta) kendala tidak negatif (tidak dipenuhi oleh kendala-1)

kalikan kedua ruas dengan -1

• Semua kendala berbentuk persamaan (tidak dipenuhi oleh kedua kendala)

tambahkan 2 buah variabel slack

Untuk kendala

, variabel

slack bertanda

negatif

Karena kedua kendala berbentuk pertidaksamaan, maka

tambahkan variabel slack untuk tiap kendala

Minimumkan Z = 2 x1 - x2 + 4 x3

Kendala -5 x1 - 2 x2 + 3 x3 7

2 x1 - 2 x2 + x3 8

x1, x2, x3 0

Kalikan kedua ruas kendala 1 dengan -1. Model menjadi :

Kendala -5 x1 - 2 x2 + 3 x3 = 7

2 x1 - 2 x2 + x3 = 8

Minimumkan Z = 2 x1 - x2 + 4 x3

x1, x2 , x3 0

x4

x5

-

+

+ x4 + x500

, x4, x5

Perhatikan bahwa tanda

berubah menjadi akibat

perkalian kedua ruas

dengan (-1)

3.2 Metode Simpleks

Setelah menjadi bentuk standar simpleks, soal siap dimasukkan dalam tabel

simpleks untuk diselesaikan.

Bentuk awal tabel simpleks adalah:

Beberapa bagian penting dalam tabel simpleks adalah:

1. Koefisien-koefisien model program linier

Koefisien fungsi sasaran diletakkan pada baris paling atas.

Matriks kendala diletakkan pada bagian tengah.

Disebelah kanannya adalah nilai ruas kanan kendala

Semua koefisien harus dalam bentuk standar simpleks.

Pada setiap iterasi, nilai matriks A dan vektor b akan selalu direvisi.

2. Variabel basis

Diantara variabel-variabel yang ada, beberapa diantaranya merupakan variabel basis

Variabel basis akan menentukan penyelesaian program linier.

Revisi tabel pada tiap iterasi dilakukan dengan mengubah variabel basisnya.

Variabel basis diletakkan pada kolom ke 2. Koefisiennya diletakkan pada kolom paling kiri.

1 2, , ..., nc c c

ijA a

1 2, , ..., 0mb b b

3. Perhitungan nilai fungsi dan pengecekan optimalitas

Baris paling bawah dipakai untuk menentukan apakah tabel yang dibuat

sudah optimal.

Jika sudah optimal maka iterasi dihentikan.

Jika belum optimal, maka tabel perlu direvisi dengan mengubah variabel

basisnya.

Nilai fungsi pada setiap iterasi tampak pada sel di ujung kanan bawah.

Bagan alir

keseluruhan

proses

penyelesaian

program linier

dengan metode

simpleks

Bagan alir revisi

tabel apabila

tabel belum

optimal

Contoh 3.2

Program Linier – Simpleks Kendala

Contoh 3.2 : Selesaikan dengan metode simpleks !

Maksimumkan Z = 3x1 + 2 x2

Kendala x1 + 2 x2 20

3x1 + x2 20 ; x1, x2 0

Penyelesaian :

Ubah ke bentuk standar simpleks

Kendala x1 + 2 x2 = 20

3 x1 + x2 = 20

Maksimumkan Z = 3x1 + 2 x2

x1, x2 0

+ x3

+ x4

+ 0 x3 + 0 x4

, x3 , x4

var basis :

x3 dan x4

x1 bi

cj

x4x3x2xj

Iterasi Awal

20/3

201 0

3 11x40

2 1

0

x30

20

20/1 = 20

zj 00 00

3 02

0

0cj - zj

3 0

q

02

(cB)i (xB)i

Nilai fungsi

Koefisien fungsi tujuanCalon basis

Elemen

Kunci

keluar

dari basis

Variabel & koefisien

basis

Maksimumkan Z = 3x1 + 2 x2 + 0 x3 + 0 x4

Kendala x1 + 2 x2 + x3 = 20

3x1 + x2 + x4 = 20

0*1 + 0*3 0*2 + 0*1

0*20 + 0*20

Masih ada yg > 0 (soal maks) tabel perlu direvisi

Revisi Tabel (1)

Elemen di baris dimana basis keluar : masing-masing dibagi

dengan elemen kunci

a d

e hf

b c

g

var calon basis

var keluar dari basis

elemen kunci

'e

ef

' 1f

ff

'g

gf

'h

hf

'b e

a af

' 0b f

b bf

'b g

c cf

'b h

d df

(1) (1)2

3

3 002

zj

cj - z

j

201 0

3 11

2 1

0 20

Revisi Tabel (2)

zj

cj - z

j

x1

bi

cj

qx4

x3

x2

(cB)i (x

B)i

xj

20/3

20/1 = 20

x4

0

x3

0

00 00

3 02

0

0

x3

x13

0 0

1

-1/3

0

1

1/3

5/3

1/3 20/3

40/3

3 1 1020

0 01 -1

8

20

(0) (1)1

3

(1) (1)0

3

(1) (3)1

3

(20) (1)20

3

zj

cj - z

j

x1

zj

cj - z

j

x1

bi

cj

qx4

x3

x2

(cB)i (x

B)i

xj

3 002

Revisi Tabel (3)

x3

x13

0 0

1

-1/3

0

1

1/3

5/3

1/3 20/3

40/3

3 1 1020

0 01 -1

8

20

x2

3

2 0

1

-1/5

-1/5

3/5

0

1

2/5 4

8

3

0

2 4/5

-3/5

3/5

028

-4/5

Tabel Opt

x1 = 4

x2 = 8

f(X) = 28

(1/ 3) (0)1

5/ 3

(1/ 3) (1)0

5/ 3

1 (1/ 3) ( 1/ 3)

3 5/ 3

20 (1/ 3) (40/ 3)

3 5/ 3

zj 0

0 00

3 02

0

0cj - z

j

3 0

x1

bi

cj

qx4

x3

x2

02

(cB)i (x

B)i

xj

0

1x1

3

1

0

x3

0 53

13

13

13

403

203

/ = 8403

53

/ = 20203

13

20/3

201 0

3 11x4

0

2 1

0

x3

0

20

20/1 = 20

zj 28

3 2

0 0cj - z

j

35

35

45

45

0

1x1

3

1

0

x2

2 35

25

15

15

8

4

zj 20

3 11

0 -11

0

0cj - z

j

Interpretasi Geometris

A (0,10)

B (20,0)

C (0, 20)

D (20/3, 0)

x1 + 2x2 = 20

3x1 + x2 = 20

x1 = 0

x2 = 0

x1 = 20/3

x2 = 0

x1 = 4

x2 = 8

Contoh 3.3

Selesaikan soal berikut dengan metode simpleks

Maksimumkan

Kendala:

1 2 3 1 2 3, , 5 15 30f x x x x x x

1 2 3

1 1 2 3

3 1 2 3

1 2 3

20 50 80 4000

0.5

0.2

, , 0

x x x

x x x x

x x x x

x x x

Penyelesaian

Lakukan sedikit penyederhanaan

Maksimumkan

Kendala:

1 2 3 1 2 3, , 5 15 30f x x x x x x

1 2 3

1 2 3

1 2 3

1 2 3

2 5 8 400

0

4 0

, , 0

x x x

x x x

x x x

x x x

Penyelesaian

Bentuk standar simpleks:

Maksimumkan

Kendala:

1 2 3 4 5 6 1 2 3 4 5 6, , , , , 5 15 30 0 0 0f x x x x x x x x x x x x

1 2 3 4

1 2 3 5

1 2 3 6

1 2 3 4 5 6

2 5 8 400

0

4 0

, , , , , 0

x x x x

x x x x

x x x x

x x x x x x

LANJUTAN TABEL

Maka titik optimalnya adalah

1 1 1

2000 1200 800 52000, ,

41 41 41 41x x dan x dengan nilai maksimum

x1, x2 0, x3 , x4

Contoh 3.4

Program Linier – Simpleks dgn Kendala (1)

Contoh 3.4 : Selesaikan dengan metode simpleks !

Minimumkan Z = 12x1 + 5 x2

Kendala 4 x1 + 2 x2 80

2 x1 + 3 x2 90 ; x1, x2 0

Penyelesaian :

Ubah ke bentuk standar simpleks

Kendala 4 x1 + 12 x2 = 80

2 x1 + 3 x2 = 90

Minimumkan Z = 12x1 + 5 x2

- x3

- x4

+ 0 x3 + 0 x4

x3 dan x4 var

slack, tapi bukan

var basis krn

koefisien ≠ 1

Contoh 3.4


Tambahkan variabel semu x5, x6 agar muncul var basis

Soal me-min koef x5, x6 di fungsi sasaran = M (bil positif besar)

Minimumkan Z = 12x1 + 5 x2 + 0 x3 + 0 x4 + M x5 + M x6

Kendala 4 x1 + 2 x2 - x3 + x5 = 80

2 x1 + 3 x2 - x4 + x6 = 90

x1, ... , x6 0

Variabel basis : x5, x6

Contoh 3.4


zj

cj - z

j

bi

q(cB)i

cj

(xB)i

xj x

1x

2x

4x

3x

5x

6

12 005 MM

4

2 3

2

0

0

-1

-1 0

1

1

0 90

80 20

45

x5

M

x6

M

6M -M-M M M5M

12-6M MM5-5M 00170 M

zj

cj - z

j

40

25

50 M +

240

1/2

0

-1

-1/4 0

1

1/4

-1/2 50

20x1

12

x6

M

1

0 2

1/2

12 -M(M-6)/2 M2M + 6 (-M+6)/2

0 M-2M-1 0(-M+6)/2 (3M-6)/2Ada yg negatif

(kendala >=)

Tabel perlu

direvisi 4/4 = 1 2/4 = 1/2 3 – (2*2/4) = 2 0 – (-1*2/4) = 1/2

Contoh 3.4


zj

cj - z

j

bi

q(cB)i

cj

(xB)i

xj x

1x

2x

4x

3x

5x

6

12 005 MM

30

-

x1

12

x2

5

12 1/2-13/4 13/4 -1/25

0 -1/213/40 M+1/2M-13/4215

zj

cj - z

j

200

x4

0

x2

5 -1/2

1

0

-3/2 -1

0

3/2

1/2 40

304

2 -1

0

10 0-5/2 0-5 5/2

2 010 M5/2 M - 5/2

1/4

1/4

-1/2

-3/8 -1/4

1/2

3/8

-1/4 25

15/21

0 1

0

Tabel Optimal dengan :

x1 = 0 (krn bukan variabel basis)

x2 = 40

x3 = 0 (krn bukan variabel basis)

x4 = 30

Penyelesaian soal asli :

x1 = 0

x2 = 40

Semua cj – zj

Tdk ada yg negatif

Tabel optimal

Contoh 3.5


Minimumkan

Kendala:

4 6x y z

2 10

4 20

3 40

, , 0

x y

y z

x z

x y z

Penyelesaian

Model terlebih dahulu dijadikan bentuk standar

Minimumkan

Kendala:

4 5 64 6 0 0 0x y z x x x

4

5

6

4 5 6

2 10

4 20

3 40

, , , , , 0

x y x

y z x

x z x

x y z x x x

Penyelesaian

Karena matriks kendala belum membentuk submatriks identitas maka pada

baris/kendala kedua dan ketiga harus ditambah variabel semu

Karena soalnya meminimumkan maka koefisien pada fungsi

sasaran = M (suatu bilangan positif besar)


Minimumkan

Kendala:

7 8x dan x

7 8x dan x

4 5 6 7 84 6 0 0 0x y z x x x Mx Mx

4

5 7

6 8

4 5 6 7 8

2 10

4 20

3 40

, , , , , , , 0

x y x

y z x x

x z x x

x y z x x x x x

LANJUTAN TABEL

Maka penyelesaian masalahnya adalah 0, 0, 40x y dan z

Contoh 3.6


Maksimumkan

Kendala:

1 230 20f x x

1 2

1 2

1 2

1 2

8

6 4 12

5 8 20

, 0

x x

x x

x x

x x

Penyelesaian

Jadikan bentuk standar simpleks dalam bentuk persamaan

Maksimumkan

Kendala:

1 2 3 430 20 0 0f x x x x

1 2 3

1 2 4

1 2

1 2 3 4

8

6 4 12

5 8 20

, , , 0

x x x

x x x

x x

x x x x

Penyelesaian

Dalam kendalanya belum terbentuk matrik identitas,sehingga perlu

ditambahkan variabel semu pada kendala ke-2 dan ke-3


Maksimumkan

Kendala:

1 2 3 4 5 630 20 0 0f x x x x Mx Mx

1 2 3

1 2 4 6

1 2 5

1 2 3 4 5 6

8

6 4 12

5 8 20

, , , , , 0

x x x

x x x x

x x x

x x x x x x

LANJUTAN TABEL

Maka penyelesaian masalahnya adalah

1 24, 0 120x x dengan nilai maksimum fungsi

3.3 Kejadian Khusus

3.3.1 Alternatif Penyelesaian

Alternatif penyelesaian berarti ada 2 penyelesaian atau lebih yang

menghasilkan nilai optimal yang sama.

Adanya alternatif penyelesaian dalam metode simpleks dapat dilihat pada

tabel optimalnya.

Alternatif penyelesaian didapat dengan “memaksa” variabel xk menjadi basis

(meskipun sebenarnya tabelnya sudah optimal).

Contoh 3.7


Maksimumkan

Kendala:1 2 1 2, 3f x x x x

1 2

1 2

1 2

2 20

3 20

, 0

x x

x x

x x

Penyelesaian

Bentuk standar masalah tersebut adalah sebagai berikut:

Maksimumkan

Kendala:

1 2 3 4 1 2 3 4, , , 3 0 0f x x x x x x x x

1 2 3

1 2 4

1 2 3 4

2 20

3 20

, , , 0

x x x

x x x

x x x x

Tampak pada iterasi kedua, tabel tersebut sudah otimal dengan penyelesaian

optimal (karena bukan variabel basis pada tabel optimal)

Tampak bahwa pada tabel optimalnya, meskipun bukan variabel basis

1 2

200

3x dan x

2 2 0c z 2x

Jika dipaksa menjadi basis

Tampak bahwa tabel sudah optimal dengan penyelesaian

2x

1 24 8x dan x

3.3.2 Penyelesaian Tak Terbatas

Penyelesaian tak terbatas berarti bisa diperbesar (atau diperkecil)

sampai titik tak berhingga.

Perhatikan bagan alir untuk merevisi tabel yang belum optimal

Setelah mendapatkan calon basis, langkah berikutnya adalah menguji apakah

ada elemen (elemen dalam kotak vertikal) yang

Jika ada maka langkah berikutnya adalah menghitung nilai dan menentukan

variabel yang harus keluar dari basis.

Akan tetapi, apabila semua , maka berarti penyelesaiannya tak

terbatas (bisa dikatakan juga bahwa soal tidak memiliki penyelesaian)

( )f x

qika 0

0ika

Contoh 3.8


Maksimumkan

Kendala:1 2 1 2, 2 3f x x x x

1 2

1 2

1 2

2 4

3

, 0

x x

x x

x x

Penyelesaian


Maksimumkan

Kendala:

1 2 3 4 5 1 2 3 4 5, , , , 2 3 0 0f x x x x x x x x x Mx

1 2 3

1 2 4 5

1 2 3 4 5

2 4

3

, , , , 0

x x x

x x x x

x x x x x

Pada iterasi kedua, . Karena satu-satunya yang masih bernilai positif,

maka menjadi calon basis.

Akan tetapi sehingga nilai tidak bisa dicari. Ini

berarti bahwa soal memiliki penyelesaian tak terbatas

4 4 3 0c z

4x

14 242 0 1 0a dan a q

3.3.3 Soal Tidak Fisibel

Berarti soal tidak memiliki daerah fisibel (tidak memiliki titik yang memenuhi

semua kendala).

Dalam metode simpleks, variabel semu berfungsi sebaga katalisator agar

muncul matriks identitas sehingga proses simpleks dapat dilakukan.

Ada kalanya variabel semu tetap merupakan variabel basis pada tabel

optimalnya. Hal ini menunjukkan bahwa soalnya tidak fisibel.

Contoh 3.9


Maksimumkan


1 2

1 2

1

1 2

3

2 3

4

, 0

x x

x x

x

x x

Penyelesaian


Maksimumkan

Kendala:

1 2 3 4 5 6 1 2 3 4 5 6, , , , , 4 3 0 0 0f x x x x x x x x x x x Mx

1 2 3

1 2 4

1 5 6

1 2 3 4 5 6

3

2 3

4

, , , , , 0

x x x

x x x

x x x

x x x x x x

Pada tabel terakhir, semua . Ini menunjukkan bahwa tabel sudah optimal.

Akan tetapi yang merupakan variabel semu masih tetap merupakan variabel basis.

Berarti soalnya tidak fisibel sehingga tidak memiliki penyelesaian optimal.

0j jc z

6x

3.3.4 Kemerosotan (Degeneracy)

Berarti ada titik sudut daerah fisibel yang terbentuk dari perpotongan 3 garis

atau lebih (umumnya, suatu titik terbentuk dari perpotongan 2 garis).

Jika titik merupakan perpotongan 3 garis atau lebih maka akan muncul

beberapa minimum yang sama.

Dalam hal ini boleh di ambil sembarang

Pemilihan yang berbeda akan menghasilkan jumlah iterasi yang berbeda

pula, meskipun hasil akhirnya sama.

q

q

q

Contoh 3.10


Maksimumkan


1 2

1 2

1 2

1 2

4 2 12

4 10

4

, 0

x x

x x

x x

x x

Penyelesaian


Maksimumkan

Kendala:

1 2 3 4 5 1 2 3 4 5, , , , 5 3 0 0 0f x x x x x x x x x x

1 2 3

1 2 4

1 2 5

1 2 3 4 5

4 2 12

4 10

4

, , , , 0

x x x

x x x

x x x

x x x x x

Pada iterasi ke-2 terdapat 2 buah nilai minimum yang sama-sama bernilai 2.

Untuk itu dipilih salah satunya secara sembarang.

q

3 5x atau x

TABEL 1

TABEL 2

Kedua tabel menghasilkan penyelesaian optimal yang sama, yaitu

1 22 2x dan x

3.3.5 Variabel Penyusun Tak Bersyarat

Dalam bentuk standar program linier disyaratkan bahwa semua variabel

penyusun harus

Apabila ada variabel penyusun yang bernilai bebas (boleh negatif), maka

sebelum masuk ke proses simpleks, masalah harus terlebih dahulu

ditransformasikan sehingga semua variabel penyusunnya

Caranya adalah dengan menyatakan variabel yang bernilai bebas sebagai

selisih 2 variabel baru yang keduanya

0

0

0

Contoh 3.11


Maksimumkan

Kendala:1 2 3 1 2 3, , 3 2f x x x x x x

1 2 3

1 2

2 3

2 5 12

6 8 22

, 0

x x x

x x

x x

Penyelesaian

Perhatikan bahwa yang disyaratkan hanyalah saja, sedangkan

boleh bernilai sembarang.

Untuk menjadikan ke bentuk standar program linier, maka dinyatakan sebagai

selisih dua variabel baru

Dengan mensubstitusi ke model didapatkan:

Maksimumkan

Kendala:

2 3 4 5 4 5 2 3, , , 3( ) 2f x x x x x x x x

4 5 2 3

4 5 2

2 3 4 5

2( ) 5 12

6( ) 8 22

, , , 0

x x x x

x x x

x x x x

4 5x dan x

1 4 5x x x

2 3x dan x1x

1x

Bentuk standarnya:

Maksimumkan

Kendala:

2 3 4 5 6 7 2 3 4 5 6 7, , , , , 2 3 3 0 0f x x x x x x x x x x x x

2 3 4 5 6

2 4 5 7

2 3 4 5 6 7

5 2 2 12

8 6 6 22

, , , , , 0

x x x x x

x x x x

x x x x x x

Perhatikan bahwa variabel basis awal boleh diambil 3 6x ataupun x

Penyelesaian optimal:

Penyelesaian soal aslinya adalah

Perhatikan di sini bahwa yang bernilai sembarang tidak berarti harus bernilai negatif

dan juga tidak boleh diasumsikan sehingga proses simpleks juga tidak dapat

langsung digunakan.

2

3

4

5 6 7

0

28 14

6 3

22 11

6 3

0

x

x

x

x x x

1

2

3

11

3

0

14

3

x

x

x

1x0

TUGAS

Terakhir dikumpulkan Senin, 26-9-2016

No. 1

No. 2

SELESAI

riset operasionaluipnusra.id/siamad/public/uploads/files_stamp/transmisi/...riset operasional...

Documents