LATAR BELAKANG PROGRAM LINEAR
Pada tahun 1947 Program linear mulai berkembang pesat karena ditemukannya suatu metode solusi masalah program linear dengan menggunakan metode simpleks oleh George Dantzig. Selanjutnya, berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah riset operasi sampai tahun 1950an.
Program linear banyak digunakan pada bidang ekonomi, industri, pendidikan, sosial, dan lain-lain. Bentuk linear yang dimaksud adalah model matematika dalam masalah program linear tersebut keseluruhan merupakan fungsi linear.
PENGERTIAN PROGRAM LINEAR
Program linear adalah suatu model matematika yang digunakan untuk menyelesaikan suatu permasalahan guna memperoleh hasil yang optimal (maksimum maupun minimum).
Dalam suatu program linear dikenal dua fungsi, yakni fungsi tujuan dan fungsi kendala. Kedua fungsi tersebut merupakan hasil representasi dari suatu permasalahan yang telah diterjemahkan dalam model matematika. Model matematika untuk fungsi tujuan berbentuk persamaan ("=") sedangkan fungsi kendala / fungsi batasan dapat berbentuk persamaan atau pertidaksamaan ().
Untuk dapat membuat formulasi model matematika, terlebih dahulu dibutuhkan pengidentifikasian masalah. Tahapan yang perlu diperhatikan dalam formulasi model matematika, yaitu:
1. menentukan variabel yang tidak diketahui (variabel keputusan). Misalkan, ibu membeli tiga buah pensil seharga Rp10.000, 00. Tentukan harga satu buah pensil. Maka dalam hal ini pensil merupakan suatu variabel yang tidak diketahui harganya.
2. Menentukan tujuan masalah tersebut dalam bentuk suatu persamaan ("=").
3. Menentukan semua kendala masalah tersebut dalam bentuk suatu persamaan ("=") ataupu pertidaksamaan ().
Sehingga, program linear memiliki model matematika dengan bentuk umum sebagai berikut,
Fungsi tujuan:
Maksimumkan atau minimumkan z = c1x1 + c2x2 + ... + Cnxn
Fungsi kendala / batasan:
a11x1 + a12x2 + ... + A1nxn = / ≤ / ≥ b1
a21x1 + a22x2 + ... + a2nxn = / ≤ / ≥ b2
...
am1x1 + am2x2 + ... + amnxn = / ≤ / ≥ bm
x1, x2, ..., xn ≥ 0
Dengan:
· X1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel keputusan (xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan.
· C1, c2, ..., cn merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematisnya.
· A11, ..., a1n, ..., amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematisnya.
· B1, b2, ..., bm menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas.
Pada tahun 1947 Program linear mulai berkembang pesat karena ditemukannya suatu metode solusi masalah program linear dengan menggunakan metode simpleks oleh George Dantzig. Selanjutnya, berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah riset operasi sampai tahun 1950an.
Program linear banyak digunakan pada bidang ekonomi, industri, pendidikan, sosial, dan lain-lain. Bentuk linear yang dimaksud adalah model matematika dalam masalah program linear tersebut keseluruhan merupakan fungsi linear.
PENGERTIAN PROGRAM LINEAR
Program linear adalah suatu model matematika yang digunakan untuk menyelesaikan suatu permasalahan guna memperoleh hasil yang optimal (maksimum maupun minimum).
Dalam suatu program linear dikenal dua fungsi, yakni fungsi tujuan dan fungsi kendala. Kedua fungsi tersebut merupakan hasil representasi dari suatu permasalahan yang telah diterjemahkan dalam model matematika. Model matematika untuk fungsi tujuan berbentuk persamaan ("=") sedangkan fungsi kendala / fungsi batasan dapat berbentuk persamaan atau pertidaksamaan ().
Untuk dapat membuat formulasi model matematika, terlebih dahulu dibutuhkan pengidentifikasian masalah. Tahapan yang perlu diperhatikan dalam formulasi model matematika, yaitu:
1. menentukan variabel yang tidak diketahui (variabel keputusan). Misalkan, ibu membeli tiga buah pensil seharga Rp10.000, 00. Tentukan harga satu buah pensil. Maka dalam hal ini pensil merupakan suatu variabel yang tidak diketahui harganya.
2. Menentukan tujuan masalah tersebut dalam bentuk suatu persamaan ("=").
3. Menentukan semua kendala masalah tersebut dalam bentuk suatu persamaan ("=") ataupu pertidaksamaan ().
Sehingga, program linear memiliki model matematika dengan bentuk umum sebagai berikut,
Fungsi tujuan:
Maksimumkan atau minimumkan z = c1x1 + c2x2 + ... + Cnxn
Fungsi kendala / batasan:
a11x1 + a12x2 + ... + A1nxn = / ≤ / ≥ b1
a21x1 + a22x2 + ... + a2nxn = / ≤ / ≥ b2
...
am1x1 + am2x2 + ... + amnxn = / ≤ / ≥ bm
x1, x2, ..., xn ≥ 0
Dengan:
· X1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel keputusan (xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan.
· C1, c2, ..., cn merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematisnya.
· A11, ..., a1n, ..., amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematisnya.
· B1, b2, ..., bm menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas.