1.

3 Teori Singkat Linear Programming

Program linier merupakan model analisis yang diterapkan untuk mengalokasikan sumber daya yang
terbatas pada penggunaan sumber daya yang bersaing dengan cara sedemikian rupa guna mendapatkan
pemecahan yang optimal (Natalia dkk, 2013). Sederhananya, program linier merupakan suatu model
umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber daya yang terbatas
secara optimal. Program linier memuat suatu rencana kegiatan untuk menghasilkan hasil yang optimal
yang didesain untuk membantu para manajer operasi dalam merencanakan dan membuat keputusan
yang diperlukan untuk mengalokasikan sumber daya (mesin, tenaga kerja, uang, waktu, kapasitas
gudang, dan bahan baku) yang dimiliki oleh sebuah organisasi atau perusahaan.

Linear programming merupakan model matematika yang diterapkan untuk menyelesaikan

permasalahan mengenai beberapa penentuan sebagai berikut (Fauzy, 2008).

1. Jumlah data input yang dipakai dalam suatu masalah.

2. Kombinasi data input yang tersedia atau kombinasi data output yang

akan dihasilkan.

3. Jumlah data output yang dihasilkan untuk mencapai sasaran (objective) pengoptimalan suatu kasus,
misalnya untuk mencapai keuntungan maksimum atau biaya modal minimum.

Terdapat empat unsur utama yang membangun suatu program linear yaitu:

1. Variabel keputusan

Variabel keputusan adalah variabel yang mempengaruhi nilai tujuan yang hendak dicapai. Variabel
keputusan merupakan nilai keputusan- keputusan yang akan dibuat. Dalam hal ini variabel keputusan
dinyatakan dalam bentuk X1, X2, X3, X4,.., Xn. Pada proses pembentukan suatu model, menentukan
variabel keputusan merupakan langkah pertama sebelum menentukan fungsi tujuan dan fungsi kendala.

2. Fungsi tujuan

Fungsi tujuan merupakan fungsi dari variabel keputusan yang akan dimaksimumkan atau diminimumkan
terhadap fungsi-fungsi kendala yang ada. Fungsi tujuan pada model pemrograman linear harus
berbentuk linear. Fungsi tujuan digambarkan dalam bentuk maksimum atau minimum yang biasanya
dinyatakan dalam variabel Z.

3. Fungsi kendala

Fungsi kendala adalah suatu kendala yang dapat dikatakan sebagai suatu pembatas terhadap variabel-
variabel keputusan yang dibuat. Fungsi kendala untuk model pemrograman linear juga harus berupa
fungsi linear. Fungsi kendala dalam kasus linear programming kendala yang dihadapi berjumlah lebih
dari satu kendala.

4. Fungsi non-negative

Fungsi yang menyatakan bahwa setiap variabel yang terdapat di dalam model pemrograman linear
berharga positif atau tidak boleh negatif. Secara matematis ditulis sebagai X1, X2, X3,..., Xn ≥ 0. Teknik
linear programming dapat digunakan dalam 2 cara, yaitu :

1. Meminimumkan biaya dalam rangka tetap mendapatkan total penerimaan atau total keuntungan
sebesar mungkin. Cara ini dikenal dengan istilah program “minimasi atau meminimumkan (minimize)”.

2. Memaksimalkan total penerimaan atau total keuntungan pada kendala sumber daya yang terbatas.
Cara ini disebut dengan istilah program “memaksimumkan atau maksimisasi (maximize)”.

Fungsi tujuan memaksimumkan dinotasikan dengan Z dan relasi dalam kendala berbentuk (≤) sehingga
bentuknya dapat dilihat pada persamaan.

Maksimumkan fungsi tujuan:

Z = c1x1 + c2x2 + ... + cjxj

Terhadap kendala-kendala :

Kendala non negatif :

xj ≥ 0 (j = 1, 2, ..., n)

Fungsi tujuan meminimumkan dinotasikan dengan W dan relasi dalam kendala berbentuk (≥) sehingga
menjadi :

Meminimumkan fungsi tujuan :

Terhadap kendala-kendala :

Kendala non negatif :

xj ≥ 0 (j = 1, 2, ..., n)

Keterangan :

xj : variabel keputusan –j/banyaknya produk ke-j (j = 1, 2,..., n)

bi : suku tetap/bahan mentah jenis ke-i yang tersedia (i = 1, 2,..., n)

aij : koefisien kendala/bahan mentah ke-i yang digunakan untuk memproduksi satu unit produk j.

cj : koefisien ongkos/harga jual satu unit j.

Linear Programming memiliki empat ciri khusus yang melekat, yaitu:

1. Penyelesaian masalah mengarah pada pencapaian tujuan maksimasi atauminimasi.

2. Kendala yang ada membatasi tingkat pencapaian tujuan.

3. Ada beberapa alternatif penyelesaian.

Secara teknis, ada lima syarat tambahan dari permasalahan linear programming yang harus diperhatikan
yang merupakan asumsi dasar, yaitu

1. Certainty (kepastian)

Certainty (kepastian) adalah fungsi tujuan dan fungsi kendala sudah diketahui dengan pasti dan tidak
berubah selama periode analisa.

2. Proportionality (proporsionalitas)

Proportionality (proporsionalitas) memiliki arti adanya proporsionalitas dalam fungsi tujuan dan fungsi
kendala. Naik turunnya nilai Z dan penggunaan sumber daya yang tersedia akan berubah berbanding
lurus dengan perubahan tingkat kegiatan.

3. Additivity (penambahan)

Additivity (penambahan) memiliki arti aktivitas total sama dengan penjumlahan aktivitas individu.
Additivity berarti bahwa nilai tujuan setiap kegiatan tidak saling mempengaruhi, atau dalam Linear
Programming dianggap bahwa kenaikan dari nilai tujuan (Z) yang disebabkan oleh kenaikan suatu
kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.

4. Divisibility (bisa dibagi-bagi)

Divisibility (bisa dibagi-bagi) memiliki arti solusi tidak harus merupakan bilangan integer (bilangan bulat),
tetapi bisa juga berupa pecahan.

5. Non-negative variable (variabel tidak negatif)

Non-negative variable (variabel tidak negatif) memiliki arti bahwa semua nilai jawaban atau variabel
tidak negatif.
Dalam menyelesaikan permasalahan linear programming, ada dua pendekatan yang dapat digunakan,
yaitu metode grafik dan metode simplex. Metode grafik hanya dapat digunakan untuk menyelesaikan
permasalahan jika terdapat dua variabel keputusan. Sedangkan metode simplex dapat digunakan untuk
menyelesaikan permasalahan jika terdapat dua atau lebih variable keputusan.

A. Metode Grafik

Metode grafik hanya dapat digunakan untuk menyelesaikan permasalahan dimana hanya terdapat dua
variabel keputusan. Untuk menyelesaikan masalah tersebut dengan metode grafik, langkah pertama
adalah memformulasikan permasalahan yang ada kedalam bentuk linear programming (LP). Langkah-
langkah dalam formulasi permasalahan adalah:

1. Menentukan fungsi tujuan dan memformulasikannya dalam bentuk matematis.

2. Mengidentifikasi batasan-batasan yang berlaku dan memformulasikannya dalam bentuk matematis.

3. Menggambarkan masing-masing garis fungsi batasan dalam suatu system salib sumbu.

4. Mencari titik yang paling menguntungkan (optimal) dihubungan dengan dengan fungsi tujuan.

B. Metode Simpleks

Metode simpleks digunakan untuk mencari nilai optimal dari program linier yang melibatkan banyak
constraint (pembatas) dan banyak variabel (lebih dari dua variabel). Langkah yang harus dilakukan untuk
menggunakan metode simpleks adalah dengan menyesuaikan formulasi permasalahan dengan standard
simpleks. Dengan kata lain harus mengubah pertidaksamaan menjadi persamaan. Ada beberapa hal
yang harus diperhatikan dalam membuat bentuk baku,

yaitu:

1. Nilai kanan fungsi tujuan harus sama dengan nol.

2. Nilai kanan fungsi kendala harus positif, apabila negatif nilai tersebut dikalikan dengan (-1).

3. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, diubah menjadi persamaan (=)
dengan menambahkan satu variable slack.

4. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, diubah menjadi persamaan (=)
dengan mengurangkan satu variabel surplus.

5. Fungsi kendala dengan persamaan dalam bentuk umum, ditambahkan satu variabel artifisial (variabel
buatan).

C. Tipe-tipe Khusus Persoalan Linear Programming

Linear programming mempunyai beberapa karakteristik-karakteristik khusus, diantaranya ialah bahwa

persoalan-persoalan tersebut cenderung membutuhkan sejumlah pembatas dan variabel yang sangat
banyak sehingga dibutuhkan
penggunaan komputer dalam penyelesaian metodenya, atau mungkin proses perhitungannya akan
menghadapi berbagai hambatan. Tipe khusus persoalan linear programming yang paling penting ialah
apa yang dikenal sebagai persoalan transportasi. Selain itu juga ada yang dikenal dengan persoalan
transhipment dan persoalan penugasan (assignment) yang erat kaitannya dengan persoalan
transportasi. Terdapat beberapa contoh dari penerapan program linear. Pertama, agen periklanan harus
mencapai kemungkinan terbaik bagi nasabah produknya dengan biaya advertising terendah. Ada
berlusinan kemungkinan yang dapat dijadikan tempat, masing-masing dengan tarif dan pembaca yang
berbeda. Kedua, perusahaan mebel juga harus memaksimumkan labanya. Kedua departemennya
menghadapi batas waktu produksi yang tidak bisa ditawar untuk memenuhi permintaan para
pelanggannya. Ketiga, membuat suatu jadwal produksi yang akan mencukupi permintaan pada masa
mendatang akan suatu produk perusahaan dan pada saat yang bersamaan meminimalkan biaya
persediaan dan biaya produksi total.