Programa Linier
BAB III PROGRAMA LINIER
3.1 Sejarah Singkat Programa Linier Menurut George B. Dantzig yang sering disebut Bapak Linear Programming, di dalam bukunya : Linear Programming and Extension, menyebutkan, bahwa ide dari pada linear programming ini berasal dari ahli matematik Rusia bernama L.V. Kantorivich yang pada tahun 1939 menerbitkan sebuah karangan dengan judul : “MATHEMATICAL METHODS IN THE ORGANIZATION AND PLANNING OF PRODUCTION” (telah diterjemahkan ke dalam bahasa Inggris dan diterbitkan di dalam majalah : Management Science Vol 6, 1960, halaman 366-422). Didalam
karangan
tersebut
telah
dirumuskan
persoalan
linear
programming untuk pertama kalinya. Akan tetapi ide ini rupanya di Rusia tidak bisa berkembang. Ternyata dunia barat yang memanfaatkan ide ini selanjutnya. Kemudian pada tahun 1947 seorang ahli matematik dari Amerika Serikat, yang namanya telah disebutkan diatas yaitu : George B. Dantzig menemukan suatu cara untuk memecahkan persoalan linear programming tersebut dengan suatu metode yang disebut “simplex method”. Setelah saat itu yaitu sejak tahun lima puluhan linear programming tersebut berkembang dengan pesat sekali mula-mula di bidang kemiliteran (untuk penyusunan strategi perang) maupun didalam bidang business (persoalan untuk mencapai maksimum profit, minimum loss, dan lain sebagainya). Sekarang penggunaan linear programming bukan saja terbatas pada bidang kemiliteran, bidang ekonomi perusahaan yang sifatnya mikro, sebagai alat management, akan tetapi sudah meluas terutama sekali didalam perencanaan pembangunan ekonomi nasional yang makro sifatnya, misalnya didalam penentuan “allocation of investments” ke dalam sektor-sektor
Programa Linier
perekonomian, “rotation corp policy”’ peningkatan penerimaan devisa, dan lain sebagainya.
3.2 Karakteristik Persoalan Programa Linier Programa Linier merupakan bagian dari Matematika yang khusus diterapkan untuk menyelesaikan persoalan yang berkaitan dengan penentuan : a. Jumlah vaiabel-variabel input yang dipakai dalam suatu masalah. b. Kombinasi variabel input yang harus disediakan atau kombinasi output yang harus dihasilkan. c. Jumlah output yang harus dihasilkan untuk mencapai tujuan (objective) tertentu yakni untuk mencapai optimalisasi dari suatu masalah, misalnya untuk mencapai profit maksimum atau biaya minimum. Sesuai dengan sifat dari program ini, maka hubungan antara variabel input/output serta fungsi objective yang harus dicapai harus merupakan hubungan linier baik yang berbentuk persamaan linier atau pertidaksamaan linier sedangkan kuantitas input/output merupakan kuantitas yang non negatif ( 0). Dalam membangun model dari persoalan linier programming digunakan karakteristik-karakteristik sebagai berikut : a. Variabel keputusan Variabel keputusan adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat. Yang dimaksud disini adalah X1, X2 , X3 , X4, ………..., Xn b. Fungsi tujuan Fungsi tujuan merupakan fungsi dari variabel keputusan yang akan dimaksimumkan (untuk pendapatan atau keuntungan) atau diminimumkan (untuk ongkos). c. Pembatas-pembatas
Programa Linier
Merupakan kendala-kendala yang dihadapi sehingga kita tidak bisa menentukan harga variabel keputusan secara sembarang. Jadi maksudnya disini nilai dari variabel keputusan tersebut dibatasi oleh pembatas (constraint). d. Pembatas tanda Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya diasumsikan hanya berharga nonnegatif atau variabel keputusan tersebut boleh berharga positif,
boleh juga negatif (tidak
terbatas dalam tanda).
3.3 Model Programa Linier Model programa linier merupakan suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalokasian ini muncul manakala seseorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Beberapa contoh situasi dari uraian diatas antara lain ialah persoalan pengalokasian fasilitas produksi, persoalan pengalokasian sumber daya nasional untuk kebutuhan domestik, penjadwalan produksi, solusi permainan (game), dan pemilihan pola pengiriman (shipping). Satu hal yang menjadi ciri situasi diatas ialah adanya keharusan untuk mengalokasikan sumber terhadap aktivitas. Bentuk umum dari model programa linier dapat disusun sebagai berikut :
1. Fungsi tujuan : untuk mencapai maksimasi
Z = c 1 x1 + c 2 x2 + … + c n x n 2. Himpunan constraint :
Programa Linier
a 11 x 1 + a 12 x 2 + … + a 1 n x n b1 a 21 x 1 + a 22 x 2 + … + a 2 n x n b2 . . . a m1 x 1 + a m2 x 2 + … + a m n x n bm 3. x
1
, x 2 , …. , x n 0
dimana : c1 x1 + c2 x2 + … + cn xn : fungsi tujuan atau fungsi kriteria yang akan dimaksimasi, dinyatakan dengan Z c1 , c2 , … , cn
: koefisien ongkos (yang diketahui)
x 1 , x 2 , …. , x n
: variabel keputusan atau level aktivitas yang harus dicari
aij , i = 1, 2, … , m
: pembatas ke i
j = 1, 2, … , n bi
: koefisien teknologi : koefisien ruas kanan
x 1 , x 2 , …. , x n 0 : pembatas nonnegatip Formulasi diatas dinamakan sebagai bentuk standar dari persoalan programa linier, dan setiap situasi yang formulasi matematisnya memenuhi model ini adalah persoalan programa linier. Istilah yang lebih umum dari model programa linier ini adalah sebagai berikut : a. Fungsi yang memaksimumkan, yaitu c1 x1 + c2 x2 + … + cn xn , disebut sebagai fungsi tujuan. b. Pembatas-pembatas adalah constraint. c. Sebanyak m buah konstrain pertama sering disebut sebagai konstrain fungsional atau pembatas teknologis. d. Pembatas x j 0 disebut sebagai konstrain non negatif. e. Variabel adalah variabel keputusan.
Programa Linier
f. Konstanta-konstanta a
ij , bi dan
cj adalah parameter-parameter model.
Selain model programa linier dengan bentuk seperti yang telah diformulasikan diatas, ada pula model programa linier dengan bentuk yang agak lain, seperti : 1. Fungsi tujuan bukan memaksimumkan, melainkan meminimumkan. Contoh : Meminimumkan : Z = c1 x1 + c2 x2 + … + cn xn 2. Beberapa konstrain fungsionalnya mempunyai ketidaksamaan dalam bentuk lebih besar atau sama dengan. Contoh : a i1 x 1 + a i2 x 2 + … + a i n x n bi Untuk beberapa harga i 3. Beberapa konstrain fungsionalnya mempunyai bentuk persamaan. Contoh : a i1 x 1 + a i2 x 2 + … + a i n x n = bi untuk beberapa harga i 4. Menghilangkan konstrain nonnegatif untuk beberapa variabel keputusan. Contoh : x j tidak terbatas dalam tanda, untuk beberapa harga j
3.4 Asumsi dalam Model Programa Linier Dalam menggunakan model programa linier, diperlukan beberapa asumsi sebagai berikut : a. Asumsi kesebandingan (proportionality) Kontribusi setiap variabel keputusan terhadap fungsi tujuan dan ruas kiri dari setiap pembatas adalah sebanding dengan nilai variabel keputusan itu. Jadi variabel Xj berkonribusi pada ongkos Cj Xj dan pada pembatas aij Xj. Jika Xj ditingkatkan dua kali, maka Cj Xj dan aij Xj akan meningkat dua kali. b. Asumsi penambahan (additivity)
Programa Linier
Ongkos total adalah penjumlahan dari ongkos individual, dan kontribusi total pada batas yang ke- i merupakan penjumlahan dari kontribusi individual dari individu aktivitas. Jadi berapapun nilai X2 , pembuatan sejumlah X1 suatu variabel keputusan akan selalu berkontribusi sebesar C1 terhadap fungsi tujuan. Dan berapapun harga X1 tidak akan mempengaruhi pembuatan sejumlah X2 c. Asumsi pembagian (divisibility) Variabel keputusan dapat dibagi menjadi beberapa level fraksi (pecahan) sehingga nilai variabel keputusan dibolehkan bukan integer. Jadi semua variabel dapat memiliki harga berapapun asalkan real non negatif. d. Asumsi kepastian (certainty) Setiap parameter, seperti koefisien fungsi tujuan, ruas kanan, koefisien teknologis, diasumsikan dapat diketahui secara pasti.
3.5 Bentuk-bentuk Model Programa Linier Untuk menyelesaikan masalah programa linier, maka model pemecahan persoalan perlu dinyatakan dalam bentuk tertentu. Bentuk-bentuk model matematis programa linier dapat dinyatakan dalam dua bentuk, yaitu bentuk kanonik dan bentuk standar (baku).
a. Bentuk Kanonik Karakteristik dari bentuk kanonik adalah sebagai berikut : 1. Semua variabel keputusan adalah tidak negatip. 2. Semua kendala berbentuk ketidaksamaan lebih kecil atau sama dengan (). 3. Fungsi tujuan berbentuk maksimasi Secara umum, bentuk kanonik dapat dinyatakan sebagai berikut :
Programa Linier
n
Maksimasi : Z c j x j j 1
Dengan memperhatikan kendala :
a jj x j b j xj 0
, i 1, 2,..., m , j 1, 2, ...., n
Bentuk umum diatas dapat dijabarkan ke dalam bentuk yang lebih lebgkap dibawah ini : Maksimasi : Z = c1 x1 + c2 x2 + … + cn xn Dengan memperhatikan kendala : a 11 x 1 + a 12 x 2 + … + a 1 n x n b1 a 21 x 1 + a 22 x 2 + … + a 2 n x n b2 . . . a m1 x 1 + a m2 x 2 + … + a m n x n bm x 1 , x 2 , …. , x n 0 b. Bentuk Standar Karakteristik dari bentuk standar persoalan programa linier adalah sebagai berikut : 1. Semua kendala berbentuk persamaan (=), kecuali untuk kendala ketidaknegatipan (non-negativity constraint). 2. Elemen ruas kanan dari setiap kendala yang menyatakan kapasitas maksimum suatu fasilitas atau aktivitas adalah tidak negatif. 3. Semua variabel keputusan adalah tidak negatip. 4. Fungsi tujuan berbentuk maksimasi atai minimasi. Secara umum bentuk standar programa linier untuk persoalan maksimasi dan minimasi adalah sebagai berikut :
Programa Linier
Fungsi tujuan : n
c
Maksimasi
j 1
j
xj
Dengan memperhatikan kendala : n
a j 1
ij
x j bi
i 1, ...., m
xj 0
j 1,...., n
Fungsi tujuan : n
Minimasi
c j 1
j
xj
Dengan memperhatikan kendala : n
a j 1
ij
x j bi
xj 0
i 1, ...., m j 1,...., n
Jika di dalam persoalan yang dihadapi ada kendala yang berbentuk ketidaksamaan ( atau ), maka ketidaksamaan ini harus diubah ke dalam bentuk persamaan, yaitu dengan menambahkan atau mengurangkan variable slack dari ruas kiri ketidaksamaan tersebut. Kalau ketidaksamaan berbentuk lebih kecil atau sama dengan (), maka harus ditambah dengan variable slack agar menjadi suatu persamaan. Sebaliknya, untuk ketidaksamaan berbentuk lebih besar atau sama dengan (), maka harus dikurangi dengan variabel surplus agar menjadi suatu persamaan.
