Program linear

Program linear atau pemrograman linear adalah metode untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika (juga dikenal dengan optimisasi matematika).

Secara lebih formal, program linear adalah sebuah teknik optimisasi untuk fungsi objektif linear, dengan kendala (beberapa) persamaan linear dan pertidaksamaan linear. Daerah feasibel dari kendala berupa sebuah politop konveks, yakni sebuah himpunan yang didefinisikan dari perpotongan banyak (namun terhingga) half spaces. Sedangkan fungsi objektif berupa fungsi (linear) bernilai real yang terdefinisi pada politop tersebut. Sebuah algoritme program linear akan mencari sebuah titik pada politop, yang menyebabkan fungsi objektif akan menghasilkan nilai terkecil (atau terbesar); jika titik tersebut ada.

Program linear adalah masalah yang dapat dinyatakan dalam bentuk kanonik (baku) sebagai

Disini, komponen-komponen dari  adalah variabel yang ingin ditentukan nilainya. Vektor   adalah vektor koefisien fungsi objektif, sedangkan  adalah vektor nilai kunci. Fungsi objektif adalah fungsi yang nilainya ingin dimaksimumkan atau diminimumkan, dalam kasus ini berupa fungsi . Matriks  berisi koefisien-koefisien dari persamaan (dan pertidaksamaan) kendala-kendala. Pertidaksamaan  dan  menyatakan daerah pencarian titik untuk mengoptimisasi fungsi objektif. Dalam konteks ini, dua vektor dapat dibandingkan jika keduanya memiliki dimensi yang sama. Vektor  dikatakan lebih kecil atau sama dengan vektor , jika semua nilai komponen vektor  lebih kecil atau sama dengan nilai komponen  yang bersesuaian.

Program linear dapat diterapkan dalam berbagai bidang studi. metode ini digunakan secara luas di bidang matematika dan secara khusus di bidang bisnis, ekonomi, dan teknologi. Banyak bidang industri juga menerapkan program linear, seperti transportasi, pengelolaan energi, telekomunikasi, dan manufaktur. Program ini terbukti berguna dalam memecahkan masalah perencanaan, penjadwalan, dan desain.

Sejarah 

Masalah menyelesaikan sebuah sistem pertidaksamaan linear dapat dilacak ke Fourier, yang pada tahun 1827 menerbitkan sebuah metode untuk menemukan solusinya. Metode ini selanjutnya diberi nama eliminasi Fourier-Motzkin.

Pada tahun 1939, seorang matematikawan dan ekonom Uni Soviet, Leonid Kantorovich, membuat formulasi program linear dari masalah yang serupa dengan formulasi masalah program saat ini. Ia juga mengusulkan sebuah metode untuk menyelesaikannya. Formulasi ini ia kembangkan pada masa Perang Dunia II, untuk merencanakan pengeluaran dan pendapatan agar mengurangi rugi bagi tentara dan meningkatkan kerugian bagi musuh. Karya Kantorovich awalnya dihiraukan oleh USSR. Pada saat yang sama dengan Kantorovich, ekonom Amerika-Belanda T. C. Koopmans memformulasikan masa ekonomi klasik dalam bentuk program linear. Kantorovich dan Koopmans nantinya mendapatkan penghargaan Nobel bidang ekonomi tahun 1975. Pada tahun 1941, Frank Lauren Hitchcock juga memformulasikan masalah transportasi dalam bentuk program linear, dan memberikan solusi yang sangat mirip dengan metode simpleks. Hitchcock meninggal pada tahun 1957 dan penghargaan Nobel tidak diberikan secara anumerta.

Sepanjang tahun 1946–1947, George B. Dantzig secara independen mengembangkan formulasi program linear yang umum agar dapat digunakan dalam masalah perencanaan di Angkata Udara Amerika Serikat. Di tahun 1947, juga menemukan metode simpleks yang untuk pertama kalinya menyelesaikan banyak masalah program linear secara efisien. Ketika Dantzig melakukan pertemuan dengan John von Neumann untuk mendiskusikan metode simpleksnya, Neumann langsung memberikan konjektur tentang teori tentang dualitas; dari realisasinya bahwa ini ekuivalen dengan masalah yang ia kerjakan di bidang teori permainan. Dantzig memberikan bukti formal pada sebuah laporan yang tidak dipublikasikan, "A Theorem on Linear Inequalities" pada 5 Januari 1948. Karya Dantzig dipublikasikan ke publik pada tahun 1951. Dalam masa setelah perang, banyak industri yang menerapkan metodenya dalam masalah perencanaan harian mereka.

Contoh masalah yang diberikan Dantzig adalah menemukan penugasan 70 orang ke 70 pekerjaan. Daya komputasi untuk mengecek semua permutasi kemungkinan penugasan sangat besar, melebihi banyaknya partikel yang ada di alam semesta yang teramati. Namun, butuh waktu yang singkat untuk menemukan solusi ketika masalah disusun sebagai program linear dan menerapkan algoritme simpleks. Teori yang mendasari program linear secara drastis mengurangi banyaknya kemungkinan solusi yang perlu dicek.

Masalah program linear dibuktikan dapat diselesaikan dalam waktu polinomial oleh Leonid Khachiyan pada tahun 1979. Namun baru pada tahun 1984 terobosan besar di bidang teori dan praktek terjadi, ketika Narendra Karmarkar memperkenalkan metode interior-point untuk menyelesaikan masalah program linear.

Bentuk baku 
Bentuk baku atau bentuk standar dari program linear adalah bentuk yang umum dan paling yang mudah dipahami untuk menjelaskan permasalahan program linear. Bentuk ini terdiri dari tiga bagian:
 Sebuah fungsi tujuan yang ingin dimaksimumkan, sebagai contoh 
Batasan atau kendala dari permasalahan, dinyatakan dalam bentuk

 dan variabel-variabel bernilai nonnegatif 

Bentuk ini juga bisa ditulis dalam bentuk matriks, atau secara lebih ringkas sebagaiFormulasi lainnya, seperti masalah minimisasi, masalah dengan pertidaksamaan melibatkan operator , juga masalah melibatkan variabel yang dapat bernilai negatif, selalu dapat disusun menjadi bentuk baku.

Contoh 
Misalkan seorang petani memiliki sepetak lahan, anggap  km2, dan ingin mendapatkan untung dengan menanam singkong dan jagung. Petani memiliki jumlah pupuk dan pestisida yang terbatas, masing-masing sebanyak  dan  kilogram. Satu km2 tanaman singkong memerlukan  kg pupuk dan  kg pestisida, sedangkan satu km2 tanaman jagung  kg pupuk dan  kg pestisida. Dengan sedikit perhitungan, petani tersebut  menemukan harga jual singkong per km2 sebesar  rupiah, sedangkan rupiah adalah harga jual jagung per km2. Anggap  dan  secara berurutan adalah luas lahan yang ditanami singkong dan jagung. Keuntungan yang maksimum dapat diperoleh petani dengan memilih nilai yang optimal bagi  dan . Menyatakan permasalahan tersebut dalam bentuk baku, kita mendapatkan program linear:

Masalah tersebut dapat disusun dalam bentuk matriks sebagai:
 maksimumkan 
 dengan kendala

Bentuk imbuhan 
Program linear juga dapat dinyatakan dalam bentuk imbuhan (augmented form, slacks form) agar dapat diselesaikan dengan metode simpleks. Bentuk ini menggunakan variabel-variabel nonnegatif yang disebut lempai (slack) untuk mengubah bentuk-bentuk pertidaksamaan dalam kendala menjadi bentuk persamaan. Selanjutnya permasalahan dapat ditulis ulang dalam bentuk matriks sebagai:
 Maksimumkan 
Dengan kendala

Disini,  adalah vektor berisi variabel-variabel lempai (),  dan  adalah vektor keputusan. Variabel  'menyimpan' nilai dari fungsi objektif yang ingin dioptimalkan.

Contoh 
Menggunakan contoh permasalahan petani di atas, bentuk imbuhan ditulis sebagai

 {|
|-
| colspan="2" | Maksimumkan: 
| (Fungsi objektif)
|-
| Dengan kendala:
| 
| (Batasan dengan imbuhan)
|-
|
| 
| (Batasan dengan imbuhan)
|-
|
| 
| (Batasan dengan imbuhan)
|-
|
| 
|}
Dalam bentuk ini,  merupakan variabel-variabel lempai, yang secara berurutan menyatakan luas lahan yang tidak digunakan, banyak pupuk yang tersisa, dan banyak pestisida yang tersisa (atau tidak digunakan). Dalam bentuk matriks formulasi tersebut dinyatakan sebagai:
 maksimumkan :

Contoh kasus sederhana 
Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan metode simpleks. Karena batasan visualisasi, metode grafik hanya dapat digunakan untuk menyelesaikan program linear dengan dua atau tiga variabel. Metode simpleks dapat digunakan tanpa memiliki batasan jumlah variabel, tetapi lebih rumit daripada metode grafik. Dalam bagian ini, akan dibahas cara penyelesaian masalah program linear dua variabel dengan menggunakan metode grafik. Berikut sebuah masalah memaksimumkan keuntungan:

Seorang pemilik tanah mengubah lahan seluas 150 m2 yang dia miliki menjadi tempat parkir. Melihat keadaan ekonomi di daerahnya, ia menetapkan harga parkir untuk mobil sebesar Rp. 3000 dan harga parkir untuk motor sebesar Rp. 2000. Dari pengukuran didapatkan bahwa satu motor memerlukan 1 m2 petak tanah, sedangkan satu mobil memerlukan 3 m2. Malangnya, desain dari tempat parkir hanya memungkinkan untuk menampung maksimum 100 kendaraan. Setelah beberapa bulan, pemilik tanah memerlukan data keuntungan maksimum yang mungkin ia diperoleh, sebagai salah satu pertimbangannya untuk memperbaiki desain tempat parkir tersebut. 

Secara umum, terdapat beberapa tahapan dalam menyelesaikan sebuah program linear, yakni: menentukan variabel-variabel keputusan dari masalah, dan dilanjutkan dengan membuat fungsi objektif. Setelah itu setiap kendala/batasan perlu diformulasikan dalam bentuk persamaan atau pertidaksamaan. Tahap berikutnya adalah menentukan/mengecek daerah penyelesaian, karena sedikit banyak hal ini akan berpengaruh pada algoritma pencarian solusi yang perlu digunakan. Masalah program linear dianggap terselesaikan, ketika titik optimal sudah ditemukan (dan sudah dapat diartikan/dimaknai). Untuk permasalahan di atas, kita dapat menyusun program linear berikut:
 Mencari maksimum dari  (keuntungan parkir dalam rupiah)
 dengan kendala:
  (batas jumlah kendaraan)
  (batas luas kendaraan dalam m2)
  (jumlah tidak boleh negatif)
  (jumlah tidak boleh negatif)
dengan  dan  masing-masing menyatakan banyak mobil dan motor yang terparkir.

Pada metode grafik, kita membentuk persamaan garis dari setiap kendala program linear. Hal ini dilakukan dengan mengubah setiap pertidaksamaan menjadi bentuk persamaan. Sebagai contoh, persamaan garis dari kendala  adalah . Selanjutnya, kita mencatat setiap titik yang terbentuk dari semua perpotongan dua persamaan garis yang mungkin. Tabel berikut berisi titik perpotongan dari persamaan garis pada kolom dengan persamaan garis pada baris.
Titik-titik perpotongan yang memenuhi semua kendala (berwarna hijau pada tabel) adalah solusi feasibel (yang mungkin) dari permasalahan program linear. Langkah berikutnya yang perlu dilakukan adalah menghitung fungsi objektif  pada keempat titik tersebut.
Dari tabel di atas, terlihat bahwa keuntungan maksimum yang dapat diperoleh adalah Rp 225.000. Hal ini tercapai ketika tempat parkir terisi dengan 25 mobil dan 75 motor.

Dualitas 
Setiap masalah program linear, yang juga dikenal dengan masalah primal, dapat diubah menjadi sebuah masalah dual. Masalah dual juga merupakan sebuah program linear, dan solusi masalah ini memberikan sebuah batas atas untuk nilai optimal dari masalah primal. Untuk mendapatkan dual dari masalah primal, ada cara sistematis yang perlu dilakukan:

 Setiap variabel pada program linear primal akan menjadi kendala di program linear dual.
 Setiap konstrain pada program linear primal akan menjadi konstrain di program linear dual.
 Arah fungsi objektif akan berbalik—masalah memaksimumkan di primal akan menjadi masalah meminimumkan di dual, dan sebaliknya.

Dalam bentuk matriks, hubungan masalah primal dengan masalah dual dapat ditunjukkan dengan:

 Maksimumkan  dengan kendala  dan ; akan memiliki masalah dual simetrik  Minimimumkan  dengan kendala  dan .
 Maksimumkan  dengan kendala ; akan memiliki masalah dual asimetrik  Minimumkan   dengan kendala  dan .

Ada dua ide mendasar pada teori dualitas. Ide pertama adalah fakta bahwa (untuk kasus dual simetrik) dual dari masalah dual suatu program linear, adalah masalah primal asal dari program linear tersebut. Selain itu, setiap solusi feasibel dari program linear akan memberikan batas untuk nilai optimal dari fungsi objektif masalah dualnya. Teorema dualitas lemah menyatakan bahwa nilai fungsi objektif dari masalah dual pada setiap solusi feasibel, akan memberikan batas pada nilai fungsi objektif masalah primal pada setiap solusi feasibelnya. Jenis batas (batas atas atau batas bawah) yang terjadi bergantung pada jenis optimisasi yang dikerjakan (memaksimumkan atau meminimumkan). Teorema dualitas kuat menyatakan jika masalah primal memiliki sebuah solusi optimal , maka masalah dual juga memiliki sebuah solusi optimal , dan keduanya terikat oleh hubungan .

Bentuk kendala dari program linear juga dapat tidak terbatas (unbounded) atau tidak feasibel (infeasible). Teorema dualitas lemah menunjukkan bahwa jika masalah primal tidak terbatas maka masalah dual yang terbentuk akan tidak feasibel. Dan sebaliknya, jika masalah dual tidak terbatas maka masalah primalnya akan tidak feasibel. Namun, ada kasus kedua jenis masalah (primal dan dual) adalah masalah yang tidak feasibel.

Dualitas masalah pengepakan dan penutupan 
Masalah pengepakan (packing) adalah kelas masalah optimisasi yang mencari cara menyusun (mengepak) objek-objek ke dalam sebuah kontainer. Sedangkan, masalah penutupan (covering) membahas apakah suatu kombinasi struktur "menutupi" sebuah objek, atau seberapa besar ukuran struktur yang diperlukan agar dapat melakukan hal tersebut. Masalah program linear terkait pengepakan dan penutupan sering muncul sebagai "relaksasi" dari sebuah masalah kombinatorial.

Masalah program linear penutupan memiliki bentuk:
 Minimumkan: ,
 dengan kendala: , 
Dual dari masalah ini masalah program linear pengepakan, yang memiliki bentuk:
 Maksimumkan: ,
 dengan kendala: , .
Dalam kedua jenis permasalahan ini, matriks , vektor , dan vektor , bernilai nonnegatif.

Complementary slackness 
Solusi optimal dari dual dapat didapatkan hanya dengan mengetahui solusi optimal dari masalah primal, dengan menggunakan teorema complementary slackness. Teorema ini menyatakan:

Misalkan  adalah solusi feasibel di masalah primal, dan  adalah solusi feasibel di masalah dual. Misalkan pula  adalah variabel lempai (slack) di masalah primal, dan  adalah variabel lempai di masalah dual. Vektor  dan  optimal di jenis masalah mereka masing masing, jika dan hanya jika:

  untuk , dan
  untuk .

Jadi, jika variabel lempai ke-i dari masalah primal tidak bernilai nol, maka variabel keputusan ke-i dari masalah dual akan bernilai nol; dan sebaliknya.

Referensi

Bacaan lebih lanjut

Pranala luar 

  Guidance On Formulating LP Problems
  Mathematical Programming Glossary
  The Linear Programming FAQ
  Benchmarks For Optimisation Software

 
Matematika
Matematika terapan