Or#04 Solusi Simpleks

Operations Research

Linier Programming: Solusi Simpleks

Contents 1

Pendahuluan

2

Langkah Metode Simpleks

3

Tabel Simpleks Pertama

4

Tabel Simpleks Kedua

5

Tabel Simpleks Ketiga

gesit thabrani

FE UNP

Pendahuluan
Permasalahan di dunia nyata terlalu kompleks untuk bisa diselesaikan dengan menggunakan metode grafik
Metode Simpleks merupakan sebuah algoritma dalam menyelesaikan permasalahan yang lebih kompleks


Dikembangkan oleh George Dantzig di akhir tahun1940--an tahun1940
Kebanyakan paket LP yang berbasis komputer menggunakan metode Simpleks gesit thabrani

FE UNP

Pendahuluan
Metode simpleks dapat digunakan untuk permasalahan dengan jumlah variabel sebanyak dua atau lebih


Tanda pertidaksamaan pada fungsi kendala adalah kurang dari atau sama dengan
Metode ini menyelesaikan masalah LP melalui perhitunganperhitungan-ulang (iteration (iteration)) di mana langkahlangkah-langkah perhitungan yang sama diulang berkaliberkali-kali sebelum solusi optimum dicapai gesit thabrani

FE UNP

Contoh: Kasus 1 Sebuah perusahaan pabrikasi hendak membuat 2 buah produk, yaitu meja dan kursi yang masingmasing-masing menghasilkan laba bersih sebesar 7 dan 5 dolar. Kedua produk tersebut diproduksi di dua departemen yaitu pengecatan dan perkayuan, dimana waktu yang tersedia di departemen pengecatan paling banyak 100 jam, sedangkan di departemen perkayuan maksimal 240 jam. Untuk memproses meja di departemen pengecatan dibutuhkan waktu 2 jam, untuk kursi dibutuhkan waktu 1 jam. Sedangkan untuk memproses meja di departemen perkayuan dibutuhkan waktu 4 jam, sedangkan untuk kursi 3 jam. Bagaimana solusi permasalahannya! gesit thabrani

FE UNP

Contoh: Kasus 1 Matriks Permasalahan Waktu/jam yang diperlukan untuk meproduksi 1 unit

Pengecatan Perkayuan

Profit/ unit

gesit thabrani

Meja

kursi

2 4

1 3

$7

$5

Waktu/jam yang tersedia

100 240

FE UNP

Contoh: Kasus 1 Formulasi permasalahannya adalah: X1 = jumlah meja yang dibuat (unit) X2 = jumlah kursi yang dibuat (unit) Maks Z = 7X1 + 5X2 subject to:

2X1 + 1X2 ≤ 100 (pengecatan) 4X1 + 3X2 ≤ 240 (perkayuan) X1 , X2 ≥ 0 (nonnegatif)

gesit thabrani

FE UNP

Langkah-langkah Metode Simpleks 1. Langkah pertama adalah merubah bentuk pertidaksamaan pada fungsi kendala ke dalam bentuk persamaan


Caranya adalah dengan menambahkan variabel S

(slack) sehingga diperoleh persamaan yang baru
Jika solusi optimal menggunakan lebih sedikit dari sumber daya yang tersedia, maka sumber daya yang tidak terpakai disebut slack
Karena variabel S tidak menimbulkan laba maka parameternya dalam fungsi tujuan berharga nol

gesit thabrani

FE UNP

Sehingga diperoleh persamaan baru sebagai berikut: Maks Z = 7X 7X1 + 5X 5X2 + 0S 0S1 + 0S 0S2 subject to:

2X1 + 1X 1X2 + S1 = 100 (pengecatan) 4X1 + 3X 3X2 + S2 = 240 (perkayuan) X1 , X2 , S1, S2 ≥ 0

gesit thabrani

(nonnegatif)

FE UNP


Perhatikan sekarang jumlah variabel

menjadi empat, sedangkan jumlah persamaan hanya dua buah
Dengan menggunakan prinsip aljabar, hal

ini dapat dipecahkan dengan memisalkan dua variabel berharga nol
Metode simpleks dimulai dengan initial

feasible solution atau basic feasible solution
Semua variabel real (variabel X) dipilih

berharga nol, sehingga pasti menghasilkan fungsi tujuan berharga nol gesit thabrani

FE UNP

Langkah-langkah Metode Simpleks 2. Langkah Kedua, membuat tabel inisial Tabel inisial (Tabel iterasi keke-nol)

Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$0

S1

2

1

1

0

100

$0

S2

4

3

0

1

240

Zj

0

0

0

0

0

Cj - Z j

$7

$5

$0

$0

gesit thabrani

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya:
Pertama, mengisi judul dan variabel pada baris solution mix
Baris adalah arah yang mendatar/ke samping, sedangkan kolom adalah arah yang menurun/ke bawah


Isi baris ini adalah semua variabel yang ada dalam permasalahan ini yaitu: variabel X1 , X2 , S1, S2 Solution Mix

gesit thabrani

X1

X2

S1

S2

Quantity

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya: Solution Mix S1


Kedua, menentukan isi dari kolom solution



S2 Zj Cj - Z j





mix Kolom ini disebut juga kolom variabel dasar (basic variable) variable) Dalam kasus maksimasi ini, yang menjadi variabel dasar adalah variabel baru yaitu variabel S1, S2 Bagian kedua dari bawah adalah Zj yang merupakan fungsi tujuan Bagian paling bawah adalah Cj – Zj yang menjadi indikator apakah tabel telah mencapai titik optimal

gesit thabrani

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya:


Ketiga, mengisi kolom pada variabel X1 , X2 , S1 , S2

dengan melihat pada persamaan kendala dari bentuk standar


Perhatikan, intersection baris kolom S1 akan

bernilai 1, begitu juga dengan untuk intersection baris kolom S2 akan bernilai 1


Isi dari kolom Quantity adalah nilai dari Right Hand

Side (RHS) yaitu bagian kanan persamaan

Solution Mix

X1

X2

S1

S2

Quantity

S1

2

1

1

0

100

S2

4

3

0

1

240

gesit thabrani

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya: Cj

$0 $0

$7

$5

$0

$0


Keempat, simbol Cj yang berarti

Contribution, yaitu suatu parameter dari Contribution, masing--masing variabel masing


Nilai ini merupakan harga jual jika kasus

memaksimasi penjualan, atau merupakan biaya yang timbul jika kasusnya minimasi biaya


Jika proses iterasi telah dimulai maka nilai ini

akan berubah sesuai dengan perpindahan variabel

gesit thabrani

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya: Kelima, nilai dari baris Zj
diperoleh dengan perkalian kolom Cj dengan kolom pada baris yang sesuai
Sebagai contoh, untuk di bagian kolom X1 diperoleh dari (0 x 2) + (0 x 4) = 0, dan seterusnya untuk kolom variabel yang lain pada baris Zj


Cj

Solution Mix

X1

X2

S1

S2

Quantity

$0

S1

2

1

1

0

100

$0

S2

4

3

0

1

240

Zj

0

0

0

0

0

gesit thabrani

FE UNP

Tabel Initial (Tabel Iterasi ke – 0) Penjelasan gambar tabel dan cara membuatnya:
Keenam, nilai dari baris Cj – Zj adalah pengurangan dari baris paling atas (baris Cj) dengan baris Zj yang dibuat pada poin kelima
Untuk menilai apakah suatu tabel telah mendapatkan solusi optimum, adalah dengan cara melihat angka pada baris ini
Untuk kasus maksimasi maksimasi,, solusi optimum tercapai apabila angka pada baris ini tidak ada yang positif artinya nilainya negatif atau nol
Untuk kasus minimasi, solusi optimum tercapai bila angka pada baris ini tidak ada yang negatif artinya nilainya positif atau nol Cj - Z j gesit thabrani

$7

$5

$0

$0 FE UNP

Langkah-langkah Metode Simpleks 3. Langkah Ketiga, melakukan iterasi dan membuat iterasi ke - 1
Pertama Pertama,, menentukan entering variable (variabel

masuk)
Untuk kasus maksimasi, variabel masuk didapat dari tabel iterasi sebelumnya (tabel iterasi keke-0) pada pada baris Zj – Cj , kolom yang memiliki nilai yang paling besar
Pilihannya adalah kolom X1 dengan nilai 7 atau kolom X2 dengan nilai 5, maka dipilih variabel X1 sebagai variabel masuk
Kolom yang dipilih ini disebut dengan kolom pivot/kunci gesit thabrani

FE UNP

Penentuan entering variable Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$0

S1

2

1

1

0

100

$0

S2

4

3

0

1

240

Zj

0

0

0

0

0

Cj - Zj

$7

$5

$0

$0

gesit thabrani

FE UNP


Kedua Kedua,, menentukan leaving variable (variabel

keluar)


Baik untuk kasus maksimasi atau minimasi, cara

penentuannya sama, yaitu dengan membagi nilai quantity dengan nilai pada kolom pivot


Alternatif /kandidat untuk variabel keluar adalah,

untuk S1 sbb: 100/2 = 50 atau untuk S2 sbb: 240/4 = 60


Dipilih hasil rasio yang memiliki nilai paling kecil


Karena nilai dari S1 lebih kecil, maka yang dipilih

menjadi variabel keluar adalah S1

gesit thabrani

FE UNP

Penentuan leaving variable Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

Rasio

$0

S1

2

1

1

0

100

100/2 = 50

$0

S2

4

3

0

1

240

240/4 = 60

Zj

0

0

0

0

0

Cj - Zj

$7

$5

$0

$0

gesit thabrani

FE UNP






Ketiga, menentukan angka pivot dan koefisien untuk Ketiga, baris yang lain Angka pivot diperoleh dari intersection kolom dan baris pivot, yaitu bernilai 2

Sedangkan koefisien untuk baris S2 yang baru adalah 4

Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

Rasio

$0

S1

2

1

1

0

100

100/2 = 50

$0

S2

4

3

0

1

240

240/4 = 60

Zj

0

0

0

0

0

Cj - Zj

$7

$5

$0

$0

gesit thabrani

FE UNP


Keempat Keempat,, membuat tabel baru dengan

memperhitungkan entering dan leaving variable, variable, sbb

Cj Solution Mix $7

X1

$0

S2

$7

$5

$0

$0

X1

X2

S1

S2

Quantity

Zj Cj - Zj gesit thabrani

FE UNP


Kelima Kelima,, mengisi baris pivot yang baru, yaitu baris X1


Isi baris pivot ini sama dengan nilai baris pivot lama

dibagi angka pivot 2 = 1 2

1* = 0 .5 2

1 = 0 .5 2

Cj

0 = 0 2

100 2

= 50

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$7

X1

1

1/2

1/2

0

50

$0

S2 Zj Cj - Zj

gesit thabrani

FE UNP


Keenam Keenam,, mengisi baris S2 yang baru


Isi baris ini = baris lama - (koef. Kolom masuk x

nilai baris pivot baru)

Nilai dalam Nlai dalam Nilai di bawah baris S2 = baris – nilai pivot baru S2 lama 0

1

–2 1

40

=

=

=

=

=

gesit thabrani

4 3

0

1

240

– –

–

–

–

(4) (4)

(4)

(4)

(4)

×

Nilai pada baris pivot baru X1

×

(1)

× × × ×

(0.5)

(0.5) (0)

(50)

FE UNP

Sehingga menjadi: Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$7

X1

1

1/2

1/2

0

50

$0

S2

0

1

-2

1

40

Zj Cj - Zj

gesit thabrani

FE UNP


Ketujuh Ketujuh,, mengisi nilai baris Zj seperti penjelasan

pada langkah kedua poin lima


dan mengisi nilai baris Cj – Zj seperti pada langkah

kedua poin enam


Diperoleh tabel iterasi keke-1 yang lengkap, sbb: Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$7

X1

1

1/2

1/2

0

50

$0

S2

0

1

-2

1

40

Zj

7

7/2

7/2

0

350

Cj - Zj

0

3/2

-7/2

0

gesit thabrani

FE UNP


Apakah sudah diperoleh nilai optimum?


Berdasarkan langkah kedua poin enam, maka

belum diperoleh nilai optimum karena belum semua nilai pada baris Cj – Zj bernilai negatif atau 0


Jika dibandingkan dengan metode grafik, proses

dari iterasi keke-0 ke iterasi ke ke--1 merupakan proses perpindahan dari titik 1 menuju titik 4 [(dari titik (0,0) pindah ke titik (50,0)]

gesit thabrani

FE UNP

Corner--Point Method Corner X2 100 –

2 – Jumlah Kursi

80 – – 60 – –

3

40 – – 20 – –

1

|– 0

|

| 20

|

| 40

|

4

| 60

|

| 80

|

| 100

X1

Jumlah meja gesit thabrani

FE UNP

Tabel Iterasi ke - 2
Karena hasil belum optimum, langkah keempat

adalah melakukan iterasi dan membuat tabel iterasi keke-2 dengan cara yang sama dengan membuat tabel iterasi keke-1


Didapat hasil sebagai berikut: Cj

$7

$5

$0

$0

Solution Mix

X1

X2

S1

S2

Quantity

$7

X1

1

0

3/2

-1/2

30

$5

X2

0

1

-2

1

40

Zj

7

5

1/2

3/2

410

Cj - Zj

0

0

-1/2

-3/2

gesit thabrani

FE UNP


Hasil yang diperoleh adalah kondisi optimum,

karena semua nilai baris Cj – Zj telah bernilai negatif atau nol
Pada intersection kolom quantity dan baris Zj

terdapat angka 410
Angka ini merupakan hasil nilai Z yang optimum

dengan jumlah produksi X1 (yaitu jumlah meja) sebanyak 30 dan X2 (jumlah kursi) sebanyak 40


Bandingkan dengan hasil pada metode grafis

gesit thabrani

FE UNP