PROGRAM LINIER

MULYANA MACHMUD, SE.,MA.K

 PENGANTAR

Program linier (linear programming yang disingkat LP) mungkin merupakan salah
satu teknik OR yang digunakan paling luas dan diketahui dengan baik. Ia merupakan
metode matematika dalam mengalokasikan sumber daya yang langka untuk mencapai
tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya. LP
banyak diterapkan dalam membantu menyelesaikan masalah ekonomi, industri, militer,
sosial dan lain-lain. LP berkaitan dengan penjelasan suatu dunia nyata sebagai suatu
model matematika yang terdiri atas sebuah fungsi tujuan linier dan sistem kendala linier.
 FORMULASI MODEL LP

Masalah keputusan yang sering dihadapi analist adalah alokasi optimum sumber daya
yang langka. Sumber daya dapat berupa uang, mesin, waktu, ruangan atau teknologi. Tugas
analis adalah mencapai hasil terbaik yang mungkin dengan keterbatasan sumber daya itu. Hasil
yang diinginkan mungkin ditunjukkan sebagai maksimisasi dari beberapa ukuran seperti profit,
penjualan dan kesejahteraan, atau minimalisasi seperti pada biaya, waktu dan jarak.
Setelah masalah diidentifikasikan, tujan ditetapkan, langkah selanjutnya adalah formulasi
model matematika yang meliputi tiga tahap seperti berikut:
a. Tentukan variabel yang tak diketahui (variabel keputusan) dan nyatakan dalam simbol
matematika.
b. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu huhungan linier (hukan
perkalian) dari varfabel keputusan.
c. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam per samaan atau
pertidaksamaan yang juga merupakan huhungan linier dari variabel keputusan yang
mencerminkan, keterbatasan sumber daya masalah itu.
Ingat bahwa pembentukan model bukan bersifat ilmiah murni tetapi lebih bersifat seni dan akan
menjadi dimengerti terutama karena praktik. Karena itu pada uraian berikut ini akan disajikan
beberapa contoh yang menunjukkan langkah-langkah formulasi model LP.

Contoh 1: Masalah Kombinasi Produk

Sebuah perusahaan menghasilkan tiga jenis produk, yaitu sepatu, tas dan dompet. Jumlah
waktu kerja buruh yang tersedia adalah 240 jam kerja dan bahan mentah 400 hg dan harga
masing-masing produk adalah seperti yang tersaji pada Tabel 1.1 Apa, yang harus dilakukan
perusahaan ini?

Tabel 1.1
Kebutuhan sumber daya
Jenis Produk Harga (Rp/unit)
Buruh (jam/unit) Bahan (Kg/unit)
Produk 1 (sepatu) 5 4 3
Produk 2 (tas) 2 6 5
Produk 3 (dompet) 4 3 2
Pada kasus ini masalah yang dihadapi perusahaan adalah menentukan jumlah masing-masing
produk yang harus dihasilkan agar keuntungan maksimum sekarang kita akan merumuskan
masalah dalam suatu model LP

a) Variabei keputusan
Tiga variabel dalam masalah ini adalah jumlah sepatu, taa, dan dompet yang harus
dihasilkan, jumlah ini dapat dilambangkan sebagai :
X1 = jumlah produk 1
X2 = jumlah produk 2
X3= jumlah produk 3
b) Fungsi tujuan
Tujuan dari masalah kombinasi produk adalah untuk memaksimumkan penerimaan total
adalah jumlah penerimaan yang diperoleh dari produk 1 adalah perkalian antara jumlah
produk 1 dengan harga per unit (Rp 3). Penerimaan produk 2 dan 3 ditentukan dengan cara
serupa. Sehingga penerimaan total, Z, dituliskan sebagai :
Z = 3X1+5X2 +2X3.
C ) Sistem kendala
Dalam masalah ini kendalanya adalah iumlah buruh dan bahan mentah yang terbatas.
Masing-masing produk membutuhkan baik buruh maupun bahan mentah. Bagi produk 1,
buruh yang dibutuhkan untuk menghasilkan tiap unit adalah 5 jam, sehingga buruh yang
dibutuhkan untuk produk 1 adalah 5X1 jam, dengan cara serupa, produk 2 membutuhkan 2X 2
jam buruh, dan produk 3 membutuhkan 4X3, jam. jumlah jam buruh yang tersedia adalah
240. Sehingga kendala buruh dituliskan
5X1 + 2X2 + 4X3 ≤ 240.

Kendala bahan mentah dirumuskan dengan cara yang sama. Produk 1 membutuhkan 4
Kg per unit. produk 2 membutuhkan 6 kg pet unit, dan produk 3 membutuhkan 6kg per unit.
Karena terdapat 400 Kg bahan mentah maka kendala iui dituliskan sebagai:
4X1 + 6X2 + 3X3 ≤ 400.
Kita juga membatasi masing-masing variabel hanya pada nilat positif karena akan tidak
masuk akal untuk menghasikan jumlah produk negatif. Kendala-ketulala ini dinamakan
non-negativity constraints dan secara matematika dituliskan sebagai:
X1 >0, X2 > 0, X3 ≥ 0.
Sekarang masalah LP yang lengkap dapat siringkas sebagai
suatu model matematika.

Maksimumkan Z = 3x1 + 5x2 + 2x3.

dengan syarat : SX1 + 2X2 + 4X3 ≤ 240
4X1 + 6X2 +3X3 ≤ 400
X 1 , X 2 , X3 ≥ 0

Dengan mencari solusi model ini untuk variabel X1 , X2 ,dan X3

Yang optimum peneriman total Z akan dimaksimumkan.
 BENTUK UMUM MODEL LP

Bentuk umum model LP adalah :

Maksimumkan(minimumkan) Z = ∑ C1 X2
Dengan syarat : aµ Xj (≤, =, ≥)bi, untuk semua i (i= 1,2,...m) semua X1 ≥ 0 Keterangan :
Xj : banyaknya kegiatan j, di mana j = 1,2,...n. Berarti disini terdapat n variabel keputusan
Z : nilai fungsi tujuan
Cj : sumbangan per unit kegiatan, untuk masalah maksimasi c, menunjukkan keuntungan atau
penerimaan per unit, sementara dalam kasus minimasi ia menunjukkan biaya per unit.
bi : jumlah sumber daya i (i = 1,2,....m), berarti terdapat m jenis sumber daya.
aµ : banyaknya sumber daya i yang di konsumsi sumber daya j.

Ingat bahwa dalam pelaksanaan tidak perlu sama untuk setiap kendala.
 ASUMSI MODEL LP

Model LP mengandung asumsI-asumsi implisit tertentu dal defi yang harus dipenuhi agar
definisinya sebagai suatu masalah LP menjadi absah. Asumsi itu menuntut bahwa hubungan
fungsional dalam masalah itu adalah linier dan aditif, dapat dibagi dan deterministik. Berikut
ini akan diterangkan lebih rinci.
a. linierity dan Additivity
Syarat utama dari LP adalah bahwa fungsi tujuan dan semua kendala harus linier dengan
kata lain, jika suatu kendala melibatkan dua variabel keputusan, dalam diagram dimensi
dua ia akan berupa suatu garis lurus.
 PENYELESAIAN GRAFIK MODEL LP
Pikirkan masalah kombinasi produksi yang sederhana seperti berikut.
Suatu perusahaan menghasilkan 2 barang, meja dan kursi. Harga masing-masing
barang dan kebutuhan sumber daya terlihat pada tabel berikut. Disamping itu
menurut bagian penjualan, permintaan meja tidak akan melebihi 4 unit.
Tabel 1.4
Sumber daya Meja Kursi Sumber daya yang tersisa
Bahan mentah 1 2 10
Buruh 6 6 36
Harga per unit 4 5

Masalah untuk memaksimumkan penerimaan dirumuskan menjadi :

Maksimumkan Z = 4X1 = 5X2
Dengan syarat : X1 =2X2 ≤ 10
6X1 + 6X2 ≤ 36
X1 ≤4
X11 X2 ≥ 0
 suatu cara sederhana untuk meggambarkan masing-masing persamaan gais adalah
dengan menentapkan salah satu variabel dalam suatu persamaan sama dengan nol dan
kemudian mencari nilai variabel yang lain. Misalnya, pada kendala pertama jika X 1 = 0,
maka 2X2 = 10 atau X2 = 5. secara serupa, X2 = 0, maka X1 = 10. kedua titik ini {(0,5) dari
(10,0)} kemudian dihubungkan dengan suatu garis lurus.
suatu daerah yang secara bersamaan memenuhi ketiga kendala ditujukan oleh area
yang di arsir, yaitu area ABCDE pada gambar 1.2. wilayah ini dinamakan solusi layak atau
ruang solusi (feasible solution or solution space). Sementara itu pasangan nilai-nilai (X 1,
X2) diluar daerah ini bukan merupakan solusi layak, karena menyimpang dari satu atau
lebih kendala. Contohnya, titik R dan S adalah solusi layak, semtara P dan Q bukan solusi
layak.
X2

8 X1 = 4
6X1 = 6X2 = 36
6
Gambar 1.1.
4
X2 = 2X2 = 10
2

0 2 4 6 8 10 X1
X2

6
A
. Q

4 ..
B Gambar 2.2.

2 .
.R R
S . C
E .P
0 2 4 6 8 10 X1
TERIMAKASIH