PROGRAM LINEAR
Program linear adalah usaha untuk mengalokasikan faktor-faktor produksi yang terbatas
jumlahnya terhadap berbagai kemungkinan produksi sehingga dicapai hasil yang optimal. Solusi
maksimal tak ada lain adalah mencari kombinasi faktor-faktor produksi yang digunakan, sehingga
faktor tersebut terdistribusi secara efisien sehingga manfaat yang ingin dicapai menjadi maksimal.
Linear Programming dengan n variabel dengan k kendala ketidaksamaan dinyatakan
sebagai:
Maksimumkan f (X1, X2, X3, …., Xn )
Z = C1X1 + C2 X2 + C3X3 + ……. + CnXn
Kendala:
a11X1 + a12X2 + a13X3 + …. + a1nXn ¿ P1
a21X1 + a22X2 + a23X3 + …. + A2nXn ¿ P2
a31X1 + a32X2 + a33X3 + …. + A3nXn ¿ P3
.
.
an1X1 + an2X2 + an3X3 + …. annXn ¿ Pk
dan
X1 ¿ 0 ; X2 ¿ 0 ; X3 ¿ 0 , …. Xn ¿ 0
Dalam bentuk matriks Program Linear (LP) dapat dinyatakan sebagai
Maksimumkan:
Z = C X …………………….( *)
Dengan batasan:
BX ¿ P
X ¿ 0
Dimana C pada persamaan (*) adalah vector baris harga (1xn) atau nilai dalam fungsi tujuan. X
adalah vector atau matriks aktivitas (n x1). B adalah matriks (m x n) dengan elemennya b ij yang
menyatakan input yang diperlukan aktivitas i pekerjaan j dan P adalah matriks sumber daya yang
tersedia (n x1).
Adapun dual dari permasalahan maksimisasi primal adalah
Minimumkan:
R = Pt W
Subject to:
Bt W ¿ C
W ¿ 0
Dimana W adalah vektor harga bayangan dari variabel sebelumnya, P t dan Bt adalah masing-
masing transpose dari matriks P dan B. Primal memaksimalkan fungsi tujuan dari memaksimumkan
sumber daya yang terbatas sementara Dual meminimalkan fungsi tujuan dengan minimalisasi biaya.
17.1. Ciri Programasi Linear
Meskipun aplikasi program linear amat beragam, semua masalah Programasi linear selalu
memiliki ciri umum sebagai berikut ( Render & Stair, 2000 dalam Kuncoro).
1. Semua masalah bertujuan untuk memaksimalkan atau meminimalkan sesuatu, biasanya laba
atau biaya
2. Adanya kendala yang membatasi tingkat tujuan yang dapat dicapai
3. Selalu ada alternatif yang akan yang dipilih
4. Tujuan dan kendala dalam masalah PL harus dinyatakan dalam persamaan atau
ketidaksamaan linear.
Secara teknis, terdapat 5 asumsi dasar yang melandasi analisis program linear yang biasanya
digunakan:
1. Berada dalam kondisi kepastian ( certainty), artinya angka pada fungsi tujuan dan kendala
diketahui secara pasti dan tidak berubah selama periode yang diamati
2. Proposionalitas (proportionality) pada fungsi tujuan dan kendala, yang berarti bahwa bila produksi
1 unit menggunakan 3 jam suatu sumber daya yang langka, maka membuat 10 produk akan
menggunakan 30 jam sumber daya
3. Penjumlahan (additivity), artinya total semua aktivitas sama dengan jumlah aktivitas individual
4. Dapat dibagi (divisibility), suatu solusi tidak perlu dalam jumlah keseluruhan (integer) dan dapat
dalam bentuk pecahan
5. Diasumsikan semua jawaban dan variabel tidak negatif (non negative), karena jumlah fisik
dengan nilai negatif adalah tidak mungkin.
Programasi linear merupakan suatu alat yang dipakai untuk memecahkan persoalan-persoalan
optimasi. Terdapat dua cara untuk memecahkan masalah optimalisasi ( secara manual), yaitu :1).
Cara grafik dan 2). Cara simpleks.
Langkah-langkah pemakaian metode grafik:
1) Menentukan fungsi tujuan yang akan dicapai dalam bentuk fungsi linear
2) Mengidentifikasi batasan-batasan yang berlaku dalam bentuk fungsi linear
3) Menggambarkan masing-masing garis pembatas dalam suatu system salib sumbu
4) Mencari titik-titik yang paling menguntungkan dalam hubungannya dengan fungsi tujuan
5) Menentukan solusi optimum
13.2. PENYELESAIAN PROGRAM LINEAR
Memecahkan masalah programasi linear dapat dilakukan dengan dua metode, yaitu metode
grafik dan metode simplex. Metode grafik terbatas pada dua produk sedangkan metode grafik
dapat dipakai untuk dua produk atau lebih.
17.2.1. Metode Grafik
Metode grafik adalah satu cara yang dapat digunakan untuk memecahkan masalah optimalisasi
dalam programasi linier. Mertode ini hnya dapat memecahkan masalah program linear dengan dua
varaibel. Sehingga menjadi keterbatasan yang utama metode ini.
Contoh 17.1:
Sebuah perusahaan meubel mengalami penurunan penjualan. Perusahaan ini memiliki 3
bagian produksi, yaitu A, B dan C yang masing-masing mengerjakan proses pembuatan meja
dan kursi. Untuk departemen A melakukan proses masing-masing 10 dan 1 jam per unit
dimana tersedia waktu untuk pabrik ini sebesar 500 jam per minggu. Sementara pada
departemen B hanya diolah barang kursi saja dengan 5 jam per unit dimana tersedia waktu
pada bagian ini hanya 200 jam seminggu. Sementara pada bagian C harus diolah dari
kedua produksi tersebut dengan tingkat pengolahan masing-masing produk 4 jam per unit
dan 6 jam per unit dengan waktu yang tersedia 360 jam per minggu. Kontribusi laba untuk
meja per unit adalah Rp. 15 ribu dan Rp.10 ribu untuk kursi. Lakukan perhitungan
sehingga diperoleh jumlah kedua produk memberikan keuntungan maksimum.
Produser akan diberikan contoh sebagai berikut:
Langkah 1
Misalkan jumlah barang meja yang diproduksi R dan jumlah barang kursi yang diprodulsi P
Bentuk suatu persoalan dalam persamaan matematis
Kontribusi laba untuk meja per unit adalah Rp. 15 ribu dan Rp.10 ribu untuk kursi.
Maksimumkan Z = 15 R + 10 P
Subjek dengan kendala-kendala berikut;
10R + P ¿ 500
0R+ 5P ¿ 200
4R + 6P¿ 360
R, P¿ 0
Z= 15 R + 10 P 150 = 15 R + 10 P
4R + 6P = 360
10R + P = 500
Langkah 2. Gambar konstrain tersebut dalam suatu grafik
P
Gambar 17.1. Persentase Grafik 1
Langkah 3. Identifikasi daerah yang fisibel
Daerah yang fisibel menunjukkan semua titik yang memenuhi daerah batasan-batasan.
Dalam contoh ini adalah kombinasi dari barang meja dan kursi yang dapat diproduksi dengan
kapasitas yang tersedia setiap bagian. Daerah yang fisibel ditunjukkan pada Gambar 2 Kadang
kala ditemukan titik terdapat daerah yang fisibel yang memenuhi dari seluruh kendala yang ada.
Langkah 4. Plot Fungsi tujuan
Langkah 5.
Solusi optimal secara grafik dapat ditentukan dengan menggeser fungsi tujuan atau garis Z
menjauhi titik nol digeser terus ke kanan maka mendapatkan titik yang paling luas sehingga
diperoleh titik A (47,14 ; 28,58 ) dan keuntungan maksimum diperoleh Rp.992.840,00
Z = 15 (47,14) + 10 (28,58)= 992.840,00
17.2.2. Metode Simpleks
Penyelesaian masalah programa linear dengan metode simplex ditulis dalam bentuk standar,
yakni permasalahan yang berwujud dengan permasalahan maksimalisasi yang bertanda lebih kecil
dari atau sama dengan (¿ ). Jadi jika terdapat permasalahan selain dari pada bentuk standar ini
dianggap sebagai penyimpangan dari bentuk standar, yang juga akan dibicarakan kemudian.
Bentuk standar fungsi pembatas ditulis sebagai
a11X1 + a12X2 + a13X3 + …. + a1nXn + S1 = b1
a21X1 + a22X2 + a23X3 + …. + a2nXn + S2 = b2
a31X1 + a32X2 + a33X3 + …. + a3nXn + S3 = b3
.
.
.
an1X1 + an2X2 + an3X3 + …. annXn + Sm = bm
Selanjutnya fungsi tujuan ditulis sebagai
Z - C1X1 - C2X2 - C3X3 + …. - CnXn = 0
Atau dalam bentuk Tabel, seperti Tabel 17.1.
Tabel 17.1. Model Program Linear dalam Bentuk Tabel
Variabel Z X1 X2 ….Xn Xn+1 Xn+2 … Xn+m Nilai
Dasar Kanan
Z 1 -C1 –C2 …-Cn 0 0 …. 0 0
Xn+1 0 a11 a12 …. a1n 1 0 ….. 0 b1
Xn+1 0 a21 a22 …. a21 0 1 …. 0 b2
. . .
am1 am2 …. amn 0 0 …… 1
. . .
. . .
Xn+m 0 bn
Selanjutnya dalam menggunakan metode simpleks, pada dasarnya ditempuh langkah-langkah
sebagai berikut:
1. Tentukan fungsi tujuan yang akan dicapai dalam masalah yang dihadapi
2. Tentukan batasan-batasan yang, ada, lalu susun semuanya dalam bentuk fungsi-fungsi
pembatas. Selanjutnya fungsi-fungsi pembatas tersebut diubah dengan memasukkan unsure
peubah slack
Contoh 17. 2:
Masalah program linear pada contoh 1 yang telah dikemukakan sebelumnya telah dipecahkan
dengan metode grafik. Sekarang akan diselesaikan dengan metode simpleks.
Maksimumkan Z = 15 R + 10 P
Subjek dengan kendala-kendala berikut;
10R + P ¿ 500
0R+ 5P ¿ 200
4R + 6P¿ 360
R, P¿ 0
Kolom kunci ditentukan dengan mengambil nilai koefisien fungsi tujuan Z terbesar yang
bertanda negative. Sedang baris kunci ditentukan dengan mengambil hasil bagi terkecil nilai kanan
(NK) dibagi elemen-elemen kolom baris.
Dengan menggunakan Metode Gauss Jordan di peroleh
Tabel 1732. Proses Iterasi Angka dalam Tabel Simplex
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1 0 -85/10 15/10 0 0 750
X1 0 1 1/10 1/10 0 0 50
X4 0 0 5 0 1 0 200
X2 0 0 64/10
56/10 -4/10 0 1 160
( 60/10) +( -4/10)= 56/10
Sebagai penjelasan untuk nilai atau baris Z diperoleh dari
-15 -10 0 0 0 0
10 1 1 0 0 500
------------------------------------------------------------------ X 1/10
1 1/10 1/10 0 0 50
--------------------------------------------------------------------- X 15
15 15/10 15/10 0 0 750
-15 -10 0 0 0 0
----------------------------------------------------------------------- +
0 -85/10 15/10 0 0 750
Demikian juga dengan baris-baris lainnya.
Kombinasi optimalnya:
X1 = 47,14
X2 = 28,58
Dengan nilai optimal 992,84 (dengan satuan Rp. 992.840)
Latihan:
Contoh 2 . Jika contoh 1 diubah sedikit sebagai:
Bentuk suatu persoalan dalam persamaan matematis
Maksimumkan Z = 15 R + 10 P
Subjek dengan kendala-kendala berikut:
10R + 2P¿ 500
0R+ 5P¿ 200
4R + 6P¿ 360
R, P¿ 0
Langkah 2. Gambar 3 konstrain tersebut dalam suatu grafik
Sumber: Diolag dengan PM Calculator.
Gambar 17.2. Persentase Garfik 2
Langkah 3. Identifikasi daerah yang fisibel
Daerah yang fisibel menunjukkan semua titik yang memenuhi daerah batasan-batasan.
Dalam contoh ini adalah kombinasi dari barang Rebecca dan Polly dolls yang dapat diproduksi
dengan kapasitas yang tersedia setiap bagian. Daerah yang fisibel ditunjukkan pada Gambar …
Kadang kala ditemukan titik terdapat daerah yang fisibel yang memenuhi dari seluruh kendala yang
ada.
Langkah 4. Plot Fungsi tujuan
Langkah 5.
Solusi optimal secara grafik dapat ditentukan dengan menggeser fungsi tujuan atau garis Z
menjauhi titik nol digeser terus ke kanan maka mendapatkan titik yang paling luas sehingga
diperoleh titi A (43,85 ; 30,77) dan keuntungan maksimum diperoleh sama dengan Rp.965,38
Membandingkan contoh 1 dan contoh 2 terlihat bahwa perubahan fungsi pembatas 10R + P¿
500 ke 10R + 2P¿ 500 atau merubah koefsien P dari 1 menjadi 2, yang beretrti terjadi peningkatan
input atau biaya sebesar satu unit untuk satu unit P akan mneyebabkan penurunan keuntungan (Rp
992, 84 – Rp 965,38)= Rp 27,46.
Kondisi optimal
Variabel yang dimasukkan (entering variable) dalam masalah minimisasi atau maksimisasi,
merupakan non basis variable yang memiliki koefisien positif atau negative terbesar dalam persamaan
fungsi tujuan. Jika semua koefisien variable non basis adalah non negative (atau non positif), maka
kondisi optimum telah terpenuhi.
Daerah Fisibel
Daerah fisibel suatu program atau permasalahan linear adalah himpunan semua titik yang
memenuhi semua pembatas linear.
Kasus Khusus dalam aplikasi Metode Simpleks
Masalah yang bias timbul dalam pemakaian metode simpleks adalah degeneracy, alternative optima,
unbounded solution dan solusi yang tidak fisibel (infeasible solution).
Soal:
1. Selaesaikan dengan metode grafik dan metode simplex
Fungsi tujuan
Z= 20 X1+ 5 X2
Fungsi pembatas
X1 + 2 X2 ¿ 10
2 X1 + X 2 ¿ 8
X1≥0, X2≥0
2. Sebuah perusahaan memproduksi 2 produk, yaitu A dan B. Kedua produk ini menggunakan bahan
baku R1 dan R2 dengan maksim 20 dan 30 ton. Untuk satu unit produk A menggunakan bahan
baku R1 = 10 kg dan R = 2 kg, dan untuk barang B menggunakan bahan baku R 1 = 30 kg dan
R2= 20 kg.
a. Tentukan jumlah produk A dan B yang akan dihasilkan jika setiap produk mendapatkan
keuntungan maksimum , jika masing-masing produk memiliki Rp.15.000 dan produk B Rp.
10.000.
b. Hitung dan Jelaskan juga dualnya.
c. Cari dan lakukan analisis dengan menggunakan Shadow Price (harga bayangan)
[Link] adalah sorang pembuat kue dadar memiliki 5 kg tepung dan 3 kg gula pasir. Ibu ini membuat
2 jenis kue dadar tersebut, bungkus kecil dan bungkus besar. Untuk membuat 1biji kue besar
diperlukan 10 gram gula pasir dan 20 g tepung, Sedang untuk 1 biji ukuran kecil diperlukan 7 gram
gula pasir dan 11 gram tepung. Tentukan keuntungan maksimum jika kedua kue tersebut dijual dengan
harga Rp 2500 dan Rp 1500