Linear programming merupakan suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal, mencakup perencanaan kegiatan untuk mencapai suatu hasil yang "optimal", yaitu suatu hasil yang mencerminkan tercapainya sasaran tertentu yang paling baik (menurut model matematis) di antara beberapa alternatif yang memungkinkan, dengan menggunakan fungsi linear.
Mengenal Linear Programming
Model Linear Programming
Model matematis perumusan masalah umum pengalokasian sumber daya untuk berbagai kegiatan, dalam model LP dikenal dua macam fungsi:
1. Fungsi Tujuan (Objective Function)
Adalah fungsi yang menggambarkan tujuan/sasaran di dalam permasalahan LP yang berkaitan dengan pengaturan secara optimal beberapa sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Nilai yang dioptimalkan dinyatakan sebagai Z.
2. Fungsi Batasan (Contraint Function)
Merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.
Agar memudahkan pembahasan model LP ini, digunakan simbol-simbol sebagai berikut:
- m = macam-macam batasan sumber atau fasilitas yang tersedia.
- n = macam-macam kegiatan yang menggunakan sumber atau fasilitas tersebut.
- i = nomor setiap macam sumber atau fasilitas yang tersedia (i = 1, 2, 3, ...,m).
- j = nomor setiap macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia (j = 1, 2, 3, ..., n).
- xj = tingkat kegiatan ke j (j =1, 2, 3, ..., n)
- aij = banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran (output) kegiatan j (i = 1, 2, 3, ..., m; j = 1, 2, 3, ..., n)
- bi = banyaknya sumber (fasilitas) i yang tersedia untuk dialokasikan ke setiap unit kegiatan (i = 1, 2, 3, ..., m).
- Z = nilai yang dioptimalkan (maksimum atau minimum)
- Cj = kenaikan nilai Z apabila ada pertambahan tingkat kegiatan (xj) dengan satu satuan (unit); atau merupakan sumbangan setiap satuan keluaran kegiatan j terhadap nilai Z.
Keseluruhan simbol-simbol diatas selanjutnya disusun ke dalam bentuk tabel standar LP sebagai berikut:
Tabel 1.1. Data untuk model Linear Programming
| Kegiatan | Pemakaian sumber per unit kegiatan (keluaran) | | | | | Kapasitas Sumber |
|------------------|-----------------------------------------------|-----|-----|---|-----|------------------|
| Sumber | 1 | 2 | 3 | … | n | |
| 1 | a11 | a12 | a13 | … | a1n | b1 |
| 2 | a21 | a23 | a23 | … | a2n | b2 |
| 3 | a31 | a33 | a33 | … | a3n | b3 |
| … | … | … | … | … | … | … |
| 4 | am1 | am2 | am3 | | amn | bm |
| Increment Z (∆Z) | C1 | C2 | C3 | … | Cn | |
| Tingkat kegiatan | X1 | X2 | X3 | … | Xn | |Alasan dasar tabel diatas dapat disusun suatu model matematis yang digunakan untuk mengemukakan suatu permasalahan LP sebagai berikut:
Fungsi tujuan:
Maksimumkan Z = C1X1 + C2X2 + C3X3 + ... + CnXn
Batasan-batasan:
1. a11X1 + a12X2 + a13X3 + ... + a1nXn ⪯ b1
2. a21X1 + a22X2 + a23X3 + ... + a2nXn ⪯ b2
.. ..... + ..... + ..... + ... + ..... . ..
.. ..... + ..... + ..... + ... + ..... . ..
m. am1X1 + am2X2 + am3X3 + ... + amnXn ⪯ bm
dan
X1 ⪰ 0, X2 ⪰ 0, ... Xn ⪰ 0Bentuk model LP diatas merupakan bentuk standar bagi masalah-masalah LP yang akan dipakai selanjutnya. Dengan kata lain bila setiap masalah dapat diformulasikan secara matematis mengikuti model diatas, maka maslah tersebut dapat dipecahkan dengan teknik LP.
Fungsi batasan dapat dikelompokan menjadi dua macam:
- Fungsi batasan fungsional, yaitu fungsi-fungsi batasan sebanyak m.
- Fungsi batasan non negatif, yaitu fungsi-fungsi batasan yang dinyatakan dengan Xi ⪰ 0.
Dalam prakteknya tidak semua masalah dapat persis mengikuti model diatas, terdapat beberapa varian masalah seperti berikut:
1. Masalah minimisasi
Dimana seorang dituntut untuk menentukan kombinasi (output) yang dapat diminimumkan. Dalam hal ini, fungsi tujuan dinytakan sebagai berikut:
Minimumkan Z = C1X1 + C2X2 + C3X3 + ... + CnXn
2. Fungsi batasan memiliki tanda matematis ⪰
Apabila dirumuskan terlihat seperti berikut:
ai1X1 + ai2X2 + ai3X3 + ... + ainXn ⪰ bi
3. Fungsi batasan memiliki tanda matematis =
Apabila dirumuskan terlihat seperti berikut:
ai1X1 + ai2X2 + ai3X3 + ... + ainXn = bi
4. Fungsi batasan non negatif tidak ada atau tidak terbatas.
Beberapa Asumsi Dasar Linear Programming
1. Proportionality
Berarti bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan. Misal;
a. Z = C1X1 + C2X2 + C3X3 + ... + CnXn
- Setiap pertambahan 1 unit X1 akan menaikan penggunaan sumber/fasilitas 1 dengan a11
- Setiap pertambahan 1 unit X2 akan menaikan penggunaan sumber/fasilitas 1 dengan a12
- dan seterusnya.
b. a11X1 + a12X2 + a13X3 + ... + ainXn ⪯ bi
- Setiap perubahan 1 unit X1 akan menaikan penggunaan sumber/fasilitas 1 dengan a11
- Setiap perubahan 1 unit X2 akan menaikan penggunaan sumber/fasilitas 1 dengan a12
- dan seterusnya.
2. Additivity
Berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi , atau dalam LP dianggapbahwa kenaikan dari tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain. Misal:
Dimana, Z = 3X1 + 5X2 dan X1 = 10; X2 =2;
Sehingga, Z = 30 + 10= 40
Andaikata X1 bertambah 1 unit, maka sesuai dengan asumsi pertama, nilai Z menjadi 40 + 3 = 43.
Jadi, nilai 3 karena kenaikan X1 dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2(X2). Dengan kata lain, tidak ada korelasi antara X1 dan X2.
3. Divisibility
Menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan, demikian nilai Z yang dihasilkan.
Misal: X1 = 6.5; Z = 10.75
4. Deterministic (Certainty)
Menyatakan bahwa semua parameter yang terdapat dalam model LP (aji, bi, Cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.
Beberapa Pengertian Dalam Linear Programming
Solution (Penyelesaian)
Adalah jawaban akhir dari suatu masalah
Feasible Solution
Adalah penyelesaian yang tidak melanggar batasan-batasan yang ada.
No Feasible Solution
Berarti tidak ada daerah feasible, artinya apabila sifat atau letak batasan-batasan sedemikian rupa sehingga tidak memungkinkan terdapatnya daerah atau alternatif-alternatif yang feasible.
Optimal Solution
Adalah feasible solution yang mempunyai nilai tujuan (nilai Z dalam fungsi tujuan) yang optimal atau terbaik (maksimum atau minimum)
Multiple Optimal Solutions
Berarti terdapatnya beberapa alternaif optimal dalam suatu masalah.
Boundary Equation
Terjadi apabila suatu batasan dengan tanda "sama dengan (=)"
Corner Point Feasible Solutions
Adalah feasible solution yang terletak pada sudut (perpotongan) antara dua garis.
Corner Point Infeasible Solutions
Adalah titik yang terletak pada perpotongan 2 garis tetapi diluar daerah feasible.
No Optional Solution
Terjadi apabila suatu masalah tidak mempunyai jawaban atau penyelesaian optimal, hal ini dapat disebabkan karena faktor-faktor:
- Tidak ada feasible Solution
- Ada batasan yang tidak membatasi besar nilai Z.
Ketentuan atau Sifat Linear Programming
Ketentuan 1
- Jika hanya ada satu optimal solution, pasti berupa corner point feasible solution.
- Jika multiple solutions maka terdapat lebih dari 2 titik optimal yang terletak pada garis yang menghubungkan 2 corner solutions.
Ketentuan 2
Corner point feasible solutions jumlahnya terbatas
Ketentuan 3
Jika suatu corner point feasible solution lebih baik dari 2 corner point feasible solutions yang terdekat, maka titik itu merupakan titik optimal atau teraik diantara semua corner point feasible solutions.
Beberapa Metode Linear Programming
- Metode Grafik
- Metode Simpleks
- Metode Transportasi (Stepping Stone)
- Metode MODI (Modified Distribution)
Referensi:
Modul Riset Operasi, Bab 2 Linear Programming, disusun oleh Minawarti, ST.