Program linear

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Loncat ke navigasi Loncat ke pencarian

Program linear adalah cara untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika.

Secara formal, suatu program linear digambarkan sebagai

usaha untuk memaksimalkan dengan kendala dan

dengan adalah vektor koefisien fungsi tujuan/objektif, adalah matriks koefisien persamaan kendala, adalah vektor nilai kunci, dan adalah vektor peubah/variabel.

Program linear dapat diterapkan dalam berbagai bidang. Ia digunakan secara luas di bidang matematika dan secara khusus di bidang bisnis, ekonomi, dan teknologi. Industri pun menerapkan program linear, seperti transportasi, pengelolaan energi, telekomunikasi, dan manufaktur. Program ini terbukti mampu memecahkan masalah perencanaan, penjadwalan, dan desain.

Bentuk baku[sunting | sunting sumber]

Bentuk baku program linear adalah bentuk yang mudah dipahami untuk menjelaskan permasalahan program linear. Bentuk ini terdiri dari tiga bagian:

  • Suatu fungsi tujuan/objektif
  • Batasan/kendala permasalahan
  • Variabel nonnegatif

Bentuk ini juga bisa ditulis dalam bentuk matriks seperti berikut.

Bentuk imbuhan (bentuk lempai/slack)[sunting | sunting sumber]

Program linear juga dapat digambarkan dalam bentuk imbuhan (augmented form) agar dapat diselesaikan dengan metode simpleks. Bentuk ini menggunakan variabel lempai (slack) yang nonnegatif untuk menggantikan pertidaksamaan dalam batasan/kendala. Permasalahan ini dapat ditulis ulang dalam bentuk matriks sebagai berikut.

Maksimalkan pada
dengan adalah vektor variabel lempai () dan adalah vektor penentu.

Penyelesaian[sunting | sunting sumber]

Tahapan umum untuk menyelesaikan program linear adalah

  1. menentukan variabel keputusan;
  2. membuat fungsi objektif;
  3. merumuskan kendala/batasan;
  4. menentukan daerah penyelesaian;
  5. menentukan titik optimal;
  6. mengartikan titik yang diperoleh.

Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan metode simpleks. Metode grafik hanya bisa menyelesaikan program linear dengan hingga dua (grafik dua dimensi) atau tiga variabel (grafik tiga dimensi). Metode simpleks tidak memiliki batasan jumlah variabel, tetapi lebih rumit daripada metode grafik.

Contoh kasus sederhana[sunting | sunting sumber]

Program linear yang memiliki dua variabel dapat digambarkan dalam grafik untuk mempermudah penyelesaian (walau tidak perlu). Berikut contoh soal dan penyelesaiannya.

Harga parkir mobil adalah Rp3 ribu dan harga parkir motor adalah Rp2 ribu. Suatu lahan parkir seluas 150 m2 dapat menampung 100 kendaraan. Satu motor menghabiskan 1 m2 dan satu mobil menghabiskan 3 m2. Bila lahan parkir tersebut disewakan, berapa keuntungan maksimum yang bisa didapat?

Dari soal di atas, dapat disusun program linear berikut:

  • memaksimalkan (keuntungan parkir dalam rupiah)
  • dengan kendala:
    1. (batas jumlah kendaraan)
    2. (batas luas kendaraan dalam m2)
    3. (jumlah tidak boleh negatif)
    4. (jumlah tidak boleh negatif)

dengan adalah mobil dan adalah motor.

Dari empat persamaan itu, dapat diambil empat titik perpotongan yang memenuhi empat persamaan di atas.

  (1) (2) (3) (4)
(1) -
(2) (25, 75) -
(3) (0, 100) (0, 150) -
(4) (100, 0) (50, 0) (0, 0) -
Sel yang berwarna hijau memenuhi empat persamaan di atas.

Hitung fungsi objektif untuk empat titik tersebut.

Titik Nilai (Rp)
(0, 0) 0
(50, 0) 150.000
(0, 100) 200.000
(25, 75) 225.000

Dari tabel di atas, dapat dilihat bahwa keuntungan maksimum yang bisa didapat adalah Rp225 ribu dengan 25 mobil dan 75 motor.

Daftar pustaka[sunting | sunting sumber]

  • Manullang, Sudianto; S., Andri Kristianto; Hutapea, Tri Andri; Sinaga, Lasker Pangarapan; Sinaga, Bornok; S., Mangaratua Marianus; Sinambela, Pardomuan N. J. M. (2017). Matematika untuk SMA/MA/SMK/MAK Kelas XI. Jakarta: Kementerian Pendidikan dan Kebudayaan. 
  • Arifien, Febianto. "Pemrograman Linier". Teknik Riset Operasional. 

Pranala luar[sunting | sunting sumber]