Custom Search

Contoh Penyelesaian Masalah Linear Programming

Masalah linear programming dapat dengan mudah diperoleh dengan cara membuat persamaan dan pertidaksamaan batasan – batasan dari problem yang dihadapi. Kemampuan membuat persamaan dari sebuah kasus yang dijumpai menjadi kunci keberhasilan penyelesaian dengan linear programming.

Artikel ini memuat enam contoh penyelesaian dengan linear programming. Pembahasan akan dituntaskan hingga hasil akhir yang diperoleh. Jika anda belum memahami benar tentang dasar linear programming, sebaiknya membaca artikel saya yang berjudul : Tutorial dan Penjelasan Linear programming. pada artikel tersebut telah saya jelaskan tentang teknik dasar dan penjelasan tentang linear programming, namun sedikit contoh penyelesaian masalahnya. Artikel ini berfungsi melengkapi artikel sebelumnya.

Masalah Linear programming 1: Produksi dengan biaya tetap

Pada sebuah perusahaan terdapat sebuah permintaan barang sebagai berikut:

masalah linear programming

Permintaan barang pada sebuah perusahaan

Asumsi yang digunakan pada contoh ini adalah:

  1. Biaya tenaga kerja Rp 1000/jam
  2. Biaya peyimpanan Rp 500/bulan/unit
  3. Tidak ada ketentuan minimum stock
  4. Tidak ada stock awal
  5. Satu unit dikerjakan 0.5 jam kerja
  6. Biaya tetap Rp 1.000.000/bulan, jika berproduksi berapapun quantity nya.

Tentukan produksi bulanan yang optimal menurut Linear programming!

Kita menghitung dahulu kapasitas produksi setiap bulan. Bulan satu terdapat 200 jam kerja, sehingga kapasitas produksi 400 unit ( satu unit dikerjakan 0.5 jam kerja). Sehingga kapasitas produksi bulan dua = 400; bulan tiga = 300; bulan empat = 300; dan bulan lima = 300.

Penyelesaian

Min: 1600Q1 + 1700Q2 + 2000Q3 + 1900Q4 +1200Q5 + 500S1 + 500S2 + 500S3 + 500 S4 + 500 S5 + 1000000R1 +  1000000R2 + 1000000R3 + 1000000R4 + 1000000R5;

Ket : Qn = produksi bulan ke-n; Sn = stock bulan ke-n, Rn = biaya tetap bulan ke-n

Biaya hpp dan tenaga kerja setiap jam dijumlahkan dan menjadi biaya variabel di setiap quantity produksi setiap bulannya. Hal ini dikarenakan satu unit dikerjakan 0.5 jam, sehingga konversi jam ke unit = 2. Jika 1 unit dikerjakan 1 jam, maka konversi unit ke jam = 1

Subject to
Q1 – S1 = 100;
S1 + Q2 – S2 = 300;
S2 + Q3 – S3 = 150;
S3 + Q4 – S4 = 400;
S4 + Q5 – S5 = 200;
Q1 – 400R1 < 0;
Q2 – 400R2 < 0;
Q3 - 300R3 < 0;
Q4 – 300R4< 0;
Q5 – 300R5< 0;

Pada tutorial kali ini saya mencoba menggunakan aplikasi Lips. Sebuah aplikasi freeware atau gratis yang bertujuan menemukan solusi permasalahan dengan menggunakan linear programming tanpa ada batasan jumlah variabel. Hal yang lebih menyenangkan adalah aplikasi ini gratis.

Silahkan download aplikasinya disini, download sesuai petunjuk di website tersebut. Kemudian extract hasil downloadnya, dan klik file yang bernama lips.exe (aplikasi).

masalah linear programming

tampilan aplikasi Lips

Klik file – new – text model. Lalu masukkan solusi model LP dan constrainnya. Perhatikan gambar berikut

masalah linear programming

input kode text di dalam Lips

Berbeda dengan lindo, pada lips harus menggunakan tanda * antara konstanta dan variabel. Jadi model linear programmingnya adalah sebagai berikut:

MIN: 1600*Q1 + 1700*Q2 + 2000*Q3 + 1900*Q4 +1200*Q5 + 500*S1 + 500*S2 + 500*S3 + 500*S4 + 500*S5 + 1000000*R1 +  1000000*R2 + 1000000*R3 + 1000000*R4 + 1000000*R5;

Gunakan tanda ; sebagai batas dari model linear programming.

Kemudian langsung kosongkan row 2 sebagai pemisah antara model Linear programming dengan constrainnya. Tulis constrain, masing masing baris akhiri dengan tanda ;

Kemudian gunakan kode “int” sebagai tanda bahwa variabel tersebut merupakan variabel integer, bukan pecahan desimal.

Karena nilai R1 sampai R4 antara 0 sampai 1, maka saya tambahkan contstrain R1<1, R2<1, R3<1, R4<1, selain menggunakan kode “int” seperti gambar diatas.

Kemudian klik Lips – solve model dan hasilnya adalah sebagai berikut:

masalah linear programming

hasil output Lips untuk masalah 1

Masing –masing variabel telah memiliki nilai, dan ternyata Linear Programming memberikan solusi untuk tidak berproduksi di bulan ke-3. Agar tidak bingung, kita pindahkan nilai tersebut ke dalam tabel perencanaan produksi sebagai berikut:

masalah linear programming

solusi permasalahan Linear Programming

 

Masalah Linear Programming 2 : Rencana Pembelian

Pada suatu perusahaan terdapat sejumlah rencana pembelian sebagai berikut:

penyelesaian linear programming

Rencana Pembelian

Biaya gudang Rp. 2/bulan/unit. Pada empat bulan tersebut, supplier memberikan potongan harga yakni pembelian diatas 200 unit akan dikurangi Rp. 2 setiap unitnya. Jadi misalnya pada bulan satu membeli 300 unit, maka 200 unit dikenakan biaya Rp 12, sedangkan 100 unit dikenakan biaya Rp 10 perunit. Tentukan berapakah sebaiknya perusahaan membeli bahan baku tersebut berkaitan dengan adanya diskon yang diberikan oleh perusahaan?

Baca Juga  ARIMA SARIMA : Si Kembar dari Time Series
Penyelesaian:

Kita asumsikan q merupakan variabel kuantiti pembelian dibawah atau sama dengan 200, r merupakan variabel kuantiti diatas 200, s merupakan variabel stok akhir bulan, dan b merupakan konstanta binary yang berisi 1 atau 0, b bernilai 1 jika kuantiti yang dibeli diatas 200 unit.

Maka:

Pembelian = s. awal + q + r – s. akhir

Pendekatan yang kita gunakan untuk membuat model linear programming adalah pendekatan minimisasi biaya.

Min: 12*q1 + 14*q2 + 16*q3 + 18*q4 + 10*r1 + 12*r2 + 14*r3 + 16*r4 + 2*s1 + 2*s2+ 2*s3 + 2*s4;

Komponen biaya perunit seolah menjadi 2 yakni biaya sebelum mencapai 200 unit dan biaya barang yang diatas 200 unit. Berdasarkan rumus pembelian = s. awal + q + r – s. akhir, maka kit abis amembuat beberapa constrain:

q1 + r1 – s1 = 150;
s1 + q2 + r2 – s2 = 200;
s2 + q3 + r3 – s3 = 250;
s3 + q4 + r4 – s4 = 150;

kemudian, karena nilai q dibatasi hanya sampai 200, maka kita gunakan konstanta biner (b) untuk membatasinya:

q1 – 200*b1 > 0;
q2 – 200*b2 > 0;
q3 – 200*b3 > 0;
q4 – 200*b4 > 0;

karena nilai b juga mempengaruhi nilai r, artinya jika b = 1, berarti r >0, tapi jika b = 0, maka nilai r juga =0.

Maka kita perlu memberikan batasan atau hubungan antara b dan r. kita asumsikan batasannya 750 unit untuk kuantiti yang diperbolehkan untuk pembelian diatas 200. Angka ini adalah angka asumsi yang diperoleh dari total rencana pembelian. Sehingga ada tambahan constrain:

r1 – 750*b1 < 0;
r2 – 750*b2 < 0;
r3 – 750*b3 < 0;
r4 – 750*b4 < 0;

karena nilai b adalah binary, maka kita tambahkan:

b1<1;
b2<1;
b3<1;
b4<1;
int b1,b2,b3,b4;

kita masukkan model linear programming dan constrain yang kita peroleh kedalam aplikasi Lips (cara sama seperti diatas):

model tujuan linear programming

model tujuan dan constrain masalah 2

dan hasilnya adalah :

hasil solusi linear programming

hasil solusi linear programming

Hasil dalam bentuk tabel adalah sebagai berikut:

solusi linear programming

solusi dalam bentuk tabel

 

Masalah Linear programming 3 :Biaya Pengiriman

Pada contoh kali ini, kita beralih dari produksi dan mesin produksi. Anggaplah ada suatu distributor dengan mengusahakan suatu barang ke pengecer atau distributor cabangnya. Biasanya pembelian pada distributor pada pabrik dalam bentuk satuan besar, misalnya fuso, kontainer, dan lain-lain. Sehingga biaya mendatangkan barang tertuang dalam biaya logistik atau pengiriman tersebut. Fuso, kontainer, wingbox, dan lain- lain biasanya dibedakan dari ukuran kapasitas kendaraan.

Distributor AZY memiliki daftar permintaan barang dari konsumennya sebagai berikut:

linear programming

Permintaan barang di sebuah distributor

Sebagai stock awal, distributor tersebut memiliki 100 unit. biaya penyimpanan gudang sebesar Rp. 100/bulan/unit (kita asumsikan biaya simpannya mahal).

Biaya pengiriman dengan menggunakan fuso sebesar Rp. 2000 dengan kapasitas 800 unit setiap pengiriman. Sedangkan jika distributor mendatangkan container, biaya Rp 3000 dengan kapasitas 1500 unit.

Berapa kali distributor tersebut harus menyewa fuso dan container untuk memenuhi permintaan konsumennya ditengah kondisi harga sewa gudang yang mahal?

Penyelesaian

Pertama kita tentukan model tujuan linear programming terlebih dahulu, yakni dengan pendekatan minimisasi biaya:

Asumsikan bahwa q adalah kuantiti barang yang didatangkan dengan kendaraan fuso atau container, r adalah saldo akhir distributor tersebut, f adalah jumlah kedatangan fuso, c adalah jumlah kedatangan container

Maka kita peroleh model (dengan memasang biaya ditiap variabelnya)) adalah:

Min: 30*q1 + 20*q2 + 30*q3 + 40*q4 + 100*r1 + 100*r2 + 100*r3 + 100*r4 + 2000*f1 + 2000*f2 + 2000*f3 + 2000*f4 + 3000*c1 + 3000* c2 + 3000*c3 + 3000*c4;

Kemudian kita mulai menetapkan constraintnya dengan cara analisis in out sederhana, yakni saldo akhir = saldo awal + kedatangan barang – permintaan. Maka kita peroleh:

r0 = 100;
r0 + q1 – r1 = 2500;
r1 + q2 – r2 = 2500;
r2 + q3 – r3 = 2000;
r3 + q4 – r4 = 1800;

nilai q tiap bulannya sama dengan nilai kuantiti yang datang dari fuso atau kontainer. Maka:

q1 – 800*f1 – 1500*c1 =0;
q2 – 800*f2 – 1500*c2 =0;
q3 – 800*f3 – 1500*c3 =0;
q4 – 800*f4 – 1500*c4 =0;

karena nilai f dan c adalah nilai integer, maka kita tambahkan constrain
int f1,f2,f3,f4,c1,c2,c3,c4;

kemudian kita buka aplikasi lips dan masukkan model tujuan dan constrain diatas. Model dan constrain saya input seperti gambar dibawah ini:

masalah linear programming

model tujuan dan constrain

Klik Lips – solve model. Hasilnya adalah sebagai berikut:

maslaah linear programming

solusi hasil linear programming

Pada gambar diatas terlihat bahwa optimal minimum value dari model tujuan linear programming adalah Rp. 347.000 dengan mendatangkan 3 fuso di bulan satu, 2 fuso masing masing dibulan dua sampai empat. Kemudian 1 kontainer di bulan dua.

Baca Juga  6 Kunci Sukses Submit Naskah Ke Jurnal Internasional

Kita ubah hasilnya menjadi tabel adalah sebagai berikut:

linear programming

hasil dalam bentuk tabel

Terlihat bahwa linear programming menghindari jumlah stok di gudang, karena biaya gudang yang tinggi.

Masalah Linear Programming 4 : Optimalisasi Penggunaaan Bahan Baku

Misalkan produk A membutuhkan bahan 4x, 1y, dan 1z. sedangkan produk B membutuhkan 3x, dan 1y. perusahaan memiliki stok bahan baku 200x, 500y, dan 100z. jika terjadi kekurangan bahan, perusahaan harus membeli 1 batch bahan baku yang berisi 10y, 20x, dan 2z. biaya 1 batch sebesar Rp. 8.000. biaya pembuatan produk A sebesar 300 dan produk B sebesar 400. Perusahaan memiliki produksi minimum 1000 unit perbulan.

Tentukan jumlah produk A dan Produk B yang akan diproduksi dengan biaya yang paling minimal?

Penyelesaian:

Jika diasumsikan q adalah jumlah batch, A adalah quantity produk A, dan B adalah quantity produk B, maka kita akan memperoleh model tujuan berdasarkan minimisasi biaya sebagai berikut:

MIN: 8000*q + 300*A + 400*B;

Kemudian kita membuat batasan atau constrain, yakni:

Pertama dari sisi bahan baku x
4*A + 3*B - 20*q < 200;
Kedua dari sisi bahan baku y
A + B – 10*q < 500;
Ketiga dari bahan z
B – 2*q < 100;
Kelima dari jumlah minimal order
A + B > 1000;
Keenam, integer dari variabel q, A, dan B,
Int q, A, B;

Kemudian kita masukkan kedalam aplikasi Lips dan temukan haslnya. Berikut adalah gambar input sekaligus hasil di aplikasi Lips.

linear programming result

model tujuan, constrains dan solusi linear programming

Sangat mudah bukan? Mau dilanjut?

Masalah Linear Programming 5: Pemilihan Produk

Masih mengacu pada contoh latihan diatas, perusahaan membuat keputusan untuk membuat satu produk saja antara A dan B. manakah produk yang kan dipilih untuk meminimalisasi biaya?

Penyelesaian:

Model tujuan linear programming dan constrain masih sama dengan contoh latihan sebelumnya. Kita hanya menambahkan constrain tentang pilihan perusahaan membuat produk A atau B.

Kita tambahkan:

A – 1000*b1 <0;
B + 1000*b1 <1000;
B1<1;
Int q, A, B, b1;

Pada constrain tersebut memberikan penjelasan bahwa b1 merupakan keputusan perusahaan. Jika b1 bernilai 0, maka nilai A akan bernilai 0 dan B akan bernilai 1000. Artinya perusahaan memilih produk B. sebaliknya jika b1 bernilai 1 maka nilai A = 1000 dan nilai b = 0, artinya perusahaan akan memilih produk A.

Kita input ke aplikasi Lips dan hasilnya adalah sebagai berikut:

penyelesaian masalah linear programming

hasil output Lips

Terlihat bahwa perusahaan memilih memproduksi produk A. hal ini wajar karena biaya produksi A lebih kecil daripada biaya produksi B

Masalah Linear Programming 6 : Transportasi

Contoh yang ini saya rasa sudah banyak tersedia di bangku kuliahan. Mengenai jumlah pabrik dan kota – kota tujuan.

Suatu perusahaan semen memiliki dua lokasi pabrik dan melayani 3 daerah tujuan. Pabrik 1 dan 2 masing – masing menghasilkan 250 ton dan 300 ton perminggu. Sementara kebutuhan di daerah A, B dan C masing – masing 100 ton, 250 ton, dan 200 ton perminggu. Bagaimana alokasi distribusi dari pabrik ke tujuan dengan transportasi minimum jika diketahui biaya transportasi masing – masing tujuan adalah sebagai berikut:

masalah linear programming

tabel jumlah pabrik dan kota tujuan

Penyelesaian:

Kita tentukan model tujuan Linear Programming :

Min: 14*A1 + 12*B1 + 10*C1 + 12*A2 + 8*B2 + 13*C2;

Constrain atau batasan kita lihat dari jumlah produksi kuantitas semen

A1 + B1 + C1 < 250;
A2 + B2 + C2 < 300;
A1 + A2 = 100;
B1 + B2 = 250;
C1 + C2 = 200;

Kemudian kita buka aplikasi Lips dan memasukkan pertidaksamaan matematika tersebut. Cara sama dengan diatas. dan kita peroleh sebagai berikut:

hasil linear programming

output aplikasi Lips

Solusi optimal biaya transportasi adalah Rp.5.300. pabrik 1 melayani kota sebagian A, C dan sebagian kota B. sedangkan pabrik 2 melayani sebagian A dan sebagian B.

Pada hasil ini muncul istilah reduced cost, slack, RHS, dan dual price. Saya sudah menjelaskan arti dari istilah tersebut di artikel: Membaca hasil Output Lindo Pada Linear Programming.

Bagaimana? Mudah bukan menggunakan linear programming untuk penyelesaian masalah? Anda bisa juga membandingkan penggunaan Lindo, Lips atau software lainnya. Pada tutorial ini cukup dahulu saya memberikan 6 contoh kasus masalah yang bisa diselesaikan dengan Linear Programming. Untuk penjelasan detil tentang contoh kasus menggunakan Lindo, anda bisa membaca artikel : Solusi Rencana Produksi Terhadap Harga Pokok Produksi dengan Linear Programming

Hasil latihan keenam contoh masalah tersebut dapat anda download disini, dalam format Lips. Anda membukanya dengan aplikasi Lips.

Selamat Belajar!

Terima kasih telah berkunjung.