Linear Programming : Metode Grafik
Linear programming adalah suatu teknis matematika yang dirancang untuk
membantu manajer dalam merencanakan dan membuat keputusan dalain
mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan.
Tujuan perusahaan pada umumnya adalah memaksimalisasi keuntungan, namun
karenaterbatasnya sumber daya, maka dapat juga perusahaan meminimalkan biaya.
Linear Programming memiliki empat ciri khusus yang melekat, yaitu :
1. penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau
minimisasi
2. kendala yang ada membatasi tingkat pencapaian tujuan
3. ada beberapa alternatif penyelesaian
4. hubungan matematis bersifat linear
Secara teknis, ada lima syarat tambahan dari permasalahan linear
programming yang harus diperhatikan yang merupakan asumsi dasar, yaitu:
1. certainty (kepastian). Maksudnya adalah fungsi tujuan dan fungsi kendala
sudah diketahui dengan pasti dan tidak berubah selama periode analisa.
2. proportionality (proporsionalitas). Yaitu adanya proporsionalitas
dalam fungsi tujuan dan fimgsi kendala.
3. additivity (penambahan). Artinya aktivitas total sama dengan penjumlahan
aktivitas individu.
4. divisibility Coisa dibagi-bagi). Maksudnya solusi tidak harus
merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan.
5. non-negative variable (variabel tidak negatif). Artinya bahwa semua
nilai jawaban atau variabel tidak negatif.
Dalam menyelesaikan permasalahan dengan menggunakan Linear Programming,
ada dua pendekatan yang bisa digunakan, yaitu metode grafik dan metode
simpleks. Metode grafik hanya bisa digunakan lantuk menyelesaikan permasalahan
dimana variabel keputusan sama dengan dua. Sedangkan metode simpleks bisa
digu-nakan untuk menyelesaikan permasalahan dimana variabel keputusan dua atau
lebih.
Dalam Bab I ini, akan dibahas Linear Programming dengan metode grafik
untuk fungsi tujuan baik maksimum maupun minimum. Fungsi tujuan maksimum akan
diuraikan pada topik I sedang fungsi tujuan minimum akan diuraikan pada
topik II.
Dengan mempelajari modul ini dengan baik dan benar, diharapkan Anda dapat
memahami pennasalahan Linear Programming dengan metode grafik.
Setelah mempelajari medul ini diharapkan anda dapat:
1. Mengenal linear programming sebagai alat pengambilan keputusan
2. Merumuskan permasalahan operasi ke dalam bentuk linear programming
3. Menyelesaikar. permasalahan linear programming dengan grafik/
matematik
4. Memahami permasalahan infeasibility, unboundedness, alternative
optima, dan redundancy.
Linier Programming dengan Metode Grafik :
Fungsi Tujuan Maksimisasi
A. FORMULASI PERMASALAHAN
Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan
dimana hanya terdapat dua variahel keputusan. Untuk menyelesaikan permasalahan
tersebut, langkah pertama yang harus dilakukan adalah memformulasikan
permasalahan yang ada ke dalam bentuk Linear Programming (LP). Langkah-langkah
dalam formulasi pennasalahan adalah :
1. pahamilah secara menyelwuh pennasalahan manajerial yang dihadapi 2.
identifikasikan tujuan dan kendalanya
3. definisikan variabel keputusannya
4. gunakan variabel keputusan untuk merumuskan fungsi tujuan dan fungsi kendala
secaramatematis.
Sebagai contoh dalam memfonnulasikan pennasalahan, berikut ini akan
dibahas perusahaan Krisna Furniture yang akan membuat meja dan kursi.
Keuntungan yang diperoleh dari satu unit n:eja adalah $7,- sedang keuntungan
yang diperoleh dari satu unit kursi adalah $5,-.
Namun untuk meraih keuntungan tersebut Kr;_sna. Furniture menghadapi
kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4
jam kerja. Untuk peinbuatan 1 unit kursi dia membutuhkan 3 jam kerja. Untuk pengecatan
1 unit meja dibutuhkan 2 jam kerja, dan ~-mtuk pengecatan 1 unit kursi
dibiatuhkan 1 jam kerja. Jumlah jam kerja yang tersedia ur.tuk pembuatan meja
dan kursi adalah 240 jam per minggu sedang jumlah jam kerja un-,uk pengecatan
adalah 100 jam per minggu. Berapa jumlah meja dan kursi yang sebaiknya
diproduksi agar keuntungan perusahaan maksimum?
Dari kasus di atas dapat diketahui bahwa tujuan perusahaan adalah
memaksimumkan profit. Sedangkan kendala perusahaan tersebut adalah terbatasnya
waktu yang tersedia untukpembuatan darn pengecatan. Apabila permasalahan
tersebut diringkas dalam satu tabel akan tarnpak sebagai berikut:
TABEL 1.1 Informasi Permasalahan Krisna Furniture
|
Jam kerja untuk membuat 1
unit produk
|
Total waktu tersedia perminggu
|
|
Meja
|
Kursi
|
|
Pembuatan
|
4
|
8
|
240
|
Pengecatan
|
2
|
1
|
100
|
Profit per unit
|
7
|
5
|
|
Mengingat produk yang akan dihasilkan adalah meja dan k-ursi, maka dalam
rangka memaksimumkan profit, perusahaan harus memutuskan berapa jumlah meja dan
kursi yang sebaiknya diproduksi. Dengan demikian dalam kasus ini, yang
merupakan variabel keputusan adalah meja (X1) dan kursi (X2).
Setelah kita mendefinisikan variabel keputusan, maka langkah selanjutnya
adalah menuliskan secara matematis fungsi tujuan dan fungsi kendala.
1. Fungsi Tujuan
Tujuan perusshaan adalah maksimisasi keuntungan, sehingga kita dapat
menuliskan fungsi tujuan sebagai berikut :
P = ($7 x jamlah meja +($5 x jumlah kursi
Yang
diproduksi) yang
diproduksi)
Atau secara matematis dapat dituliskan : Maksimisasi Z = $7X1 + $5X2
2. Fungsi kendala
Berkaitan dengan sumber daya vang digunakan, perusahaan tidak bisa
memperkirakan secara tepat kebutuhan sumber daya yang digunakan untuk mencapai
keuntungan tertentu. Biasanya perusahaan menyediakan sumber daya tertentu yang
merupakan kebutuhan minimum atau maksimum. Kondisi seperti ini secara matematis
diungkapkan dengan pertidaksamaan.
Kendala yang pertama adalah waktu yang tersedia di departemen pembuatan.
Total waktu yang diperlukan untuk pembuatan Xl (meja) dimana untuk membuat satu
unit meja diperlukan waktu 4 jam kerja dan untuk pembuatan X2 (kursi) dimana
untuk membuat satu unit kursi diperlukan waktu 3 jam kerja adalah 240 jam.
Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis menjadi :
4 X1 + 3 X2 <_>
Seperti halnya pada kendala yang pertama, maka pada kendala kedua dapat
diketahui bahwa total waktu yang diperlukan untuk pengecatan X1 (me)'a) dimana
untuk mengecat satu unit meja diperlukan waktu 2 jam kerja dan untuk pembuatan
X2 (kursi) dimana untuk mengecat satu unit kursi dibutuhkan waktu 1 jam kerja
adalah 100 jam. Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis
menjadi :
2X1 + 1 X2 <>
Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah
asumsi nilai X1 dan X2 tidak negatif. Artinya bahwa
X1 > 0 (jumlah meja yang diproduksi adalah lebih besar atau sama
dengan nol)
X2 > 0 (jumlah kursi yang diproduksi adalah lebih besar atau sama
dengan nol)
Dari uraian di atas dapat dirumuskan formulasi permasalahan secara
lengkap sebagai
berikut :
Fungsi tujuan :
Maksimisasi Z = $7X1 + $SX2. Fungsi kendala :
4 X1 + 3 X2 <>
2X1 + 1 X2 <>_ 0 (kendala non negatif pertama)
X2 >, 0 (Kendala Non Negatif kedua )
B. PENYELESAIAN LINEAR PROGRAMMING SECARA GRAFIK
Kasus Krisna Furniture tersebut akan kita selesaikan dengan metode
grafik. Keterbatasan metode grafik adalah bahwa hanya tersedia dua sumbu
ordinat, sehingga tidak bisa digunakan untuk menyelesaikan kasus yang lebih
dari dua variabel keputusan.
Langkah pertama dalam penyelesaian dengan metode grafik adalah
menggambarkan fungsi kendalanya. Untuk menggambarkan kendala pertama secara
grafik, kita harus merubah tanda pertidaksamaan menjadi tanda persamaan seperti
berikut.
4X1+3X2 = 240
Kend,qla ini akan memotong salah satu atau kedua sumbu.
Sebagaimana halnya yang sudah kita pelajari dalam aljabar, bahwa untuk
mengaambarkan fungsi linear yang tidak lain merupakan garis lurus, maka kita
akan mencari titik potong garis tersebut dengan kedua sumbu. Suatu garis akan
memotong salah satu sumbu apabila nilai variabel yang lain sama dengan nol.
Dengan demikian kendala pertama akan memotong X1, pada saat X2 = 0, demikian
juga kendala ini akan memotong X2, pada saat Xl = 0.
Kendala I: 4 XI + 3 X2 = 240
memotong sumbu X1 pada saat X2 = 0 4X1+0=240
Xl = 240/4 Xl = 60.
memotong sumbu X2 pada saat X1 = 0 0 + 3 X2 = 240
X2 = 240/3 X2 = 80
Kendala I memotong sumbu Xl pada titik (60, 0) dan memotong sumbu X2 pada
titik (0,80)
Kendala II: 2 X1 + 1 X2 = 100
memotong sumbu X1 pada saat X2 = 0
2X1+0=100
Xl = 100/2
XI = 50
memotong sumbu X2 pada saat X1 =0
O+X2=100
X2 = 100
Kendala I memotong sumbu X1 pada titik (50, 0) dan memotong sumbu X2 pada
titik (0,100).
Peraga 1.1. Grafik Area Layak
(not available)
X2=100-2X1
4 X1 + 3 X2 = 240 4X1+3(100-2X1)=240
4X1+300-6X1 =240
-2X1 =240-300
-2X1=-60
X1 = -60/-2 =
30.
X2=100-2X1
X2 = 100 - 2 *
30
X2=100-60
X2 = 40
Sehingga kedua kendala akan saling berpotongan pada titik (30, 40).
Tanda <>
Untuk menentakan solusi yang optimal, ada dua cara yang bisa digunakan
yaitu 1. dengan menggunakan garis profit (iso profit linc) 2. dengan titik
sudut (corner point)
Penyelesaian dengan menggunakan garis profit adalaha penyelesaian dengan
menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kanan
sampai menyinggung titik terjauh dari dari titik nol, tetapi masih berada pada
area layak (feasible region). Untuk menggambarkan garis profit, kita mengganti
nilai Z dengan sembarang nilai yang mudah dibagi oleh koefisien pada fungsi
profit. Pada kasus ini angka yang mudah dibagi angka 7 (koefisien Xl) dan 5
(koefisien X2) adalah 35. Sehingga fungsi tujuan menjadi 35 = 7 X1 + 5 X2.
Garis ini akan memotong sumbu Xl pada titik (5, 0) dan memotong sumbu X2 pada
titik (0, 7).
Dari Peraga 1. 2 dapat dilihat bahwa iso profit line menyinggung titik B
yang merupakan titik terjauh dari titik nol. Titik B ini merupakan titik
optimal. Untuk mengetahui berapa nilai X1 dan X2, serta nilai Z pada titik B
tersebut, kita mencari titik potong antara kendala I dan kendala II(karena
titik B merupakan perpotongan antara kendala I dan kendala 11). Dengan
menggunakan eliminiasi atau subustitusi diperoleh nilai Xl = 30, X2 = 40. dan Z
= 410. Dari
hasil perhitungan tersebut maka dapat disimpulkan bahwa keputusan
perusahaan yang akan memberikan profit maksimal adalah memproduksi Xl sebanyak
30 unit, X2 sebanyak 40 unit dan perusahaan akan memperoleh profit sebesar 410.
Peraga 1. 2. Iso profit line
(not available)
Penyelesaian dengan menggunakan titik sudut (corner point) artinya kita
harus mencari nilai tertinggi dar: titik-titik yang berada pada area layak
(feasible region). Dari peraga 1, dapat dilihat bahwa ada 4 titik yang
membatasi area layak, yaitu titik 0 (0, 0), A (0, 80), B (30, 40), dan C (50,
0).
Keuntungan pada titik O(0, 0) adalah (7 x 0) + (5 x 0) = 0.
Keuntungan pada titik A (0; 80) adalah (7 x 0) + (5 x 80) = 400.
Keuntungan pada titik B (30; 40) adalah (7 x 30) + (5 x 40) = 410.
Keuntungan pada titik C (50; 0) adalah (7 x 50) + (5 x 0) = 350.
Karena keuntungan tertinggi jatuh pada titik B, maka sebaiknya perusahaan
memproduksi meja sebanyak 30 unit dan kursi sebanyak 40 unit, dan perusahaan
memperoleh ketuitungan optimal sebesar 410.