Linier Programming Simplex MethodRiski Aditya

Operation Research

Pre-Test (Dalam 10 Menit)

Sebuah lembaga penelitian di DI.Yogyakarta hendak

menyebarkan 10000 kuesioner (harus habis) ke dua

pulau, yaitu P. Sumatra dan P. Bali.Ongkos kirim P.

Sumatra Rp 1.200,- per kuesioner dan Bali Rp 1.000,-

per kuesioner. Jumlah kuesioner yang dikirim ke Bali

paling sedikit 3000 kuesioner dan untuk Sumatra paling

sedikit 1500 kuesioner. Berapa komposisi kuesioner yang

harus dikirim ke masing-masing pulau? Berapa total

biaya pengirimannya?

Pengantar Simplex

Mahasiswa akan membeli laptop untuk

keperluan kuliah dan kerjanya. Ia diberikan

kesempatan memilih 4 jenis laptop

(hp/lenovo/vaio/samsung). Masing-masing

laptop memili spesifikasi dan harga yang

berbeda. Bagaimana mahasiswa itu akan

memilih laptop yang sesuai dengan

kebutuhan dan kantongnya ?

Syarat Awal Metode Simplek

Semua kendala harus berbentuk persamaan matematikabiasa (dengan tanda =). Apabila kendala berbentuk

persamaan linier, maka harus diubah kebentuk

persamaan matematika dengan penambahan variabel

slack secukupnya.

Fungsi kendala dengan tanda diubah ke bentuk dengan cara mengalikan dengan 1, lalu diubah ke bentukpersamaan matematika biasa dengan ditambahkan

variabel slack. Kemudian karena RHS-nya negatif,

dikalikan lagi dengan 1 dan ditambah artificial variabel(M).

Semua ruas kanan variabel keputusan (Z) harus bernilai= 0

Rubah menjadi bentuk simplek

Minimum/maksimum

kendala

Contoh Kasus

Perusahaan sepatu membuat 2 macam sepatu. Yang pertama

merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan

3 macam mesin. Mesin 1 membuat sol karet, mesin 2

membuat sol kulit, dan mesin 3 membuat bagian atas sepatu

dan melakukan assembling bagian atas dengan sol. Setiap

lusin sepatu merek I1 mula-mula dikerjakan di mesin 1 selama

2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di

mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak

diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2

selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja

maksimum setiap hari mesin 1 adalah 8 jam, mesin 2 adalah

15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap

laba setiap lusin sepatu merek I1 = Rp 30.000,00 sedang

merek I2 = Rp 50.000,00. Masalahnya adalah menentukan

berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang

dibuat agar bisa memaksimumkan laba.

Penyelesaian (Bentuk Matematika)

Maksimumkan Z = 3X1 + 5X2 Batasan (constrain)

(1) 2X1 8

(2) 3X2 15

(3) 6X1 + 5X2 30

Langkah-langkah metode simpleks

Langkah 1:

Mengubah fungsi tujuan dan batasan-batasan

Fungsi tujuan

Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.

Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)

(1) 2X1 8 menjadi 2X1+ X3 = 8

(2) 3X2 15 menjadi 3X2+ X4= 15

(3) 6X1 + 5X2 30 menjadi 6X1 +5X2+X5= 30

Beberapa Istilah dlm Metode Simplek

NK adalah nilai kanan persamaan, yaitu nilai di belakang

tanda sama dengan ( = ). Untuk batasan 1 sebesar 8,

batasan 2 sebesar 15, dan batasan 3 sebesar 30.

Variabel dasar adalah variabel yang nilainya sama

dengan sisi kanan dari persamaan. Pada persamaan

2X1 + X3 = 8, kalau belum ada kegiatan apa-apa, berarti

nilai X1 = 0, dan semua kapasitas masih menganggur,

maka pengangguran ada 8 satuan, atau nilai X3 = 8. Pada

tabel tersebut nilai variabel dasar (X3, X4, X5) pada fungsi

tujuan pada tabel permulaan ini harus 0, dan nilainya pada

batasan-batasan bertanda positif

Hasil Pengubahan

Z = 3X1 + 5X2 menjadi Z - 3X1 - 5X2 = 0.

(1) 2 X1 8 menjadi 2X1+ X3= 8

(2) 3 X2 15 menjadi 3X2+ X4 = 15

(3) 6 X1 + 5 X2 30 menjadi 6X1 +5X2+ X5= 30

Tabel Simplek Awal

Variabel

DasarZ X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

Langkah 2 : Pemilihan Kolom Kunci

Kolom kunci adalah kolom yang merupakan dasar untuk

mengubah tabel simplek. Pilihlah kolom yang mempunyai

nilai pada garis fungsi tujuan yang bernilai negatif

dengan angka terbesar.

Pemilihan Kolom Kunci

Jika suatu tabel sudah tidak memiliki nilai negatif pada barisfungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi(sudah optimal).

Variabel

DasarZ X1 X2 X3 X4 X5 NK

Keterang

an

(Indeks)

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

Langkah 3 : Pemilihan Baris Kunci

Baris kunci adalah baris yang merupakan dasar untuk mengubah

tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan

membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada

kolom kunci.

Indeks = (Nilai Kolom NK) / (Nilai kolom kunci)

Untuk baris batasan 1 besarnya indeks = 8/0 = , baris batasan 2 =

15/3 = 5, dan baris batasan 3 = 30/5 = 6. Pilih baris yang mempunyai

indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2

yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris

kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam

baris kunci disebut angka kunci

Mengubah Nilai Baris Kunci

Nilai baris kunci diubah dengan cara membaginya dengan angka

kunci, seperti tabel 3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3

= 1/3; 0/3 = 0; 15/3 = 5). Gantilah variabel dasar pada baris itu

dengan variabel yang terdapat di bagian atas kolom kunci (X2).

Tabel Perubahan Baris Kunci

Langkah 4 : Penentuan Baris Baru

[ 6 5 0 0 1, 30 ]

(5) [ 0 1 0 1/3 0, 5 ] ( - )

Nilai baru = [ 6 0 0 -5/3 1, 5 ]

Variabel

DasarZ X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0

X3 0 2 0 1 0 0 8

X4 0 0 3 0 1 0 15

X5 0 6 5 0 0 1 30

Z 1 -3 0 0 5/3 0 25

X3 0 2 0 1 0 0 8

X2 0 0 1 0 1/3 0 5

X5 0 6 0 0 -5/3 1 5

Tabel pertama nilai lama dan tabel kedua nilai baru

Ulangilah langkah-langkah perbaikan

mulai langkah 2 sampai langkah ke-4

untuk memperbaiki tabel-tabel yang telah

diubah/diperbaiki nilainya. Perubahan

baru berhenti setelah pada baris pertama

(fungsi tujuan) tidak ada yang bernilai

negatif

Langkah 5 : Lanjut Perbaikan

[-3 0 0 5/3 0, 25 ]

(-3) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = [ 0 0 0 5/6 , 271/2]

[ 2 0 1 0 0, 8 ]

(2) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = 0 0 1 5/9 -1/3, 61/3]

[ 0 1 0 1/3 0, 5 ]

(0) [ 1 0 0 -5/18 1/6, 5/6] ( - )

Nilai baru = 0 1 0 1/3 0, 5]

Baris ke-1

Baris ke-2 (batasan 1)

Baris ke-3 tidak berubah karena nilai pada kolom kunci = 0

Baris pertama (Z) tidak ada lagi yang bernilainegatif. Sehingga tabel tidak dapat dioptimalkanlagi dan tabel tersebut merupakan hasil optimal

X1 = 5/6

X2 = 5

Zmaksimum = 271/2

Tabel Hasil Akhir

Variabel

DasarZ X1 X2 X3 X4 X5 NK

Z 1 0 0 0 5/6 271/2

X3 0 0 0 1 5/9 -1/3 61/3

X2 0 0 1 0 1/3 0 5

X1 0 1 0 0 -5/18 1/6 5/6

Perusahaan Riski corp memproduksi 3 buah model almari (A, B,dan C). Waktu pembuatan (jam kerja) dan harga pembelianbahan baku (ratusan ribu rupiah) tiap almari dapat dilihat padatabel.

Kerena keterbatasan modal, biaya pembelian bahan bakuterbatas sebesar 20.000.000 dan waktu pembuatan jugaterbatas selama 150 jam. Hasil penjualan lemari A, B, Cmasing-masing memberikan keuntungan 400.000, 200.000,300.000. berapakan banyaknya lemari yang harus dibuat agarbisa mendapatkan keuntungan maksimal ?

Latihan 1

A B C

Waktu pembuatan (jam) 7 3 6

Harga bahan baku 400000 400000 500000

Perusahaan mempunyai anggaran produksi

sebesar $2000 dan jam kerja maksimum

665 jam per hari. Maksimum permintaan

tiap hari 200 unit untuk jam dinding, 300 unit

radio, 150 unit toaster. Keuntungan

maksimum tiap produk adalah $15 untuk

jam dinding, $20 untuk radio, dan $12 untuk

toaster. Tentukan produksi optimal agar

keuntungan maksimum !

Latihan 2

Tugas 1

Silahkan buat tim (1 tim terdiri 2-3 Orang).

Lakukan observasi lapangan langsung

(tempat penelitian bebas). Analisa kebutuhan

untuk linier programming dan buatkan

kesimpulan dari hasil analisanya.

Cat.

Object yang diteliti harus menghasilkan

minimal 3 variabel

TERIMA KASIH

Operation Research