LINEAR PROGRAMMING

A. DEFINISI LINEAR PROGRAMMING

Linear Programming merupakan salah satu pendekatan
matematik yang paling sering diterapkan manajerial dalam
pengambilan keputusan. Tujuan dari penggunaan linear
programming adalah untuk menyusun suatu model yang dapat
dipergunakan untuk membantu pengambilan keputusan dalam
menentukan alokasi yang optimal dari sumber daya perusahaan ke
berbagai alternatif.
Penggunaan linear programming dalam hal ini adalah
mengalokasikan sumber daya tersebut, sehingga laba akan
maksimum atau alternatif biaya minimum. Alokasi yang dibuat
tergantung dari sumber daya yang tersedia dan permintaan atas
sumber daya tersebut. Sedangkan tujuan dari alokasi adalah
memaksimumkan laba atau meminimalkan biaya.
Jadi linear programming adalah sebuah metode matematis
yang berkarakteristik linear untuk menemukan suatu penyelesaian
optimal dengan cara memaksimumkan atau meminimumkan fungsi
tujuan terhadap satu susunan kendala.
B. MODEL LINEAR PROGRAMMING
Model linear programming merupakan bentuk dan susunan
dalam menyajikan masalah-masalah yang akan dipecahkan dengan
teknik Linear Programming (LP).
Model LP mempunyai tiga unsur utama, yaitu:
1. Variabel keputusan yaitu variabel persoalan yang akan
mempengaruhi nilai tujuan yang hendak dicapai. Didalam
proses pemodelan, penemuan variabel keputusan harus
dilakukan terlebih dahulu sebelum merumuskan fungsi tujuan
dan fungsi batasan (kendala-kendalanya). Misalnya dengan
mengajukan pertanyaan: keputusan apa yang harus dibuat agar
nilai fungsi tujuan menjadi maksimum atau minimum.

2. Fungsi tujuan yaitu fungsi yang menggambarkan tujuan dalam

permasalahan LP yang berkaitan dengan pengaturan secara
optimal sumber daya - sumber daya, untuk memperoleh
keuntungan maksimal atau biaya minimum. Dengan simbol Z.
Oleh karena itu hanya ada dua kemungkinan fungsi tujuan, yaitu
a. Maksimimkan Z = f (X1, X2, ...Xn)
b. Minimumkan Z = f (X1, X2, ...Xn)

3. Fungsi batasan (kendala) yaitu bentuk penyajian secara

matematis batasan-batasan kapasitas yang tersedia yang akan
dialokasikan secara optimal ke berbagai kegiatan.

Untuk memudahkan pembahasan model Linear

Programming ini, digunakan simbol-simbol sebagai berikut:
Xj = banyaknya kegiatan j ( j = 1, 2, ..., n). Variabel X j ini disebut
juga dengan variabel keputusan (decision variables)
Z = nilai fungsi tujuan yang diopotimalkan (maksimum atau
minimum)
Cj = kenaikan nilai Z apabila ada pertambanhan tingkat kegiatan
(Xj) dengan satu satuan (unit) atau merupakan keuntungan
per unit (masalah maksimasi), biaya per unit (masalah
minimasi) kegiatan j terhadap nilai Z.
aij = banyaknya sumber i yang di perlukan guna menghasilkan
setiap unit output kegiatan j (i = 1, 2, ..., m, dan j = 1,2, ..., n)
bi = banyaknya sumber (fasilitas) i yang tersedia untuk
dialokasikan ke setiap unit kegiatan (i = 1,2, ..., m)
Keseluruhan simbol-simbol diatas selanjutnya disusun ke
dalam bentuk tabel standar Linear Programming, seperti pada
Tabel 2.1 di bawah ini:
Tabel 2.1. Data Model Linear Programming
Kegiatan Pemakaian sumber per unit Kapasitas
Sumber 1 2 3.............n Sumber
1 a11 a 12 a13................a1n b1
2 a21 a22 a23................a2n b2
. . . . ......... . .
. . . . ......... . .
m am1 am2 am3..............anm bm
C1 C2 C3................Cn
Banyak kegiatan X1 X2 X3................Xn

Atas dasar Tabel 2.1 di atas, dapat disusun model standard

Linear Programming sebagai berikut:
Fungsi tujuan :
Maksimumkan/minimumkan:
Z  Cj .X j = C1X1 + C2X2 + ... + CnXn

Dengan kendala atau batasan:

Atau:
1. a11X1 + a12X2 + ... + a1nXn b1
2. a21X1 + a22X2 + ... + a2nXn b2
.
.
m. am1X1 + am2X2 + ... + amnXn bm
dan
Xj 0 atau X1 0, X2 0, ...... Xn 0

 Batasan pertama artinya: jumlah hasil (barang/jasa) 1 yang

dihasilkan oleh kegiatan 1 dikalikan dengan kebutuhan akan
sumber 1 per satuan (berarti total alokasi 1 untuk kegiatan 1)
ditambah dengan hasil kegiatan 2 dikalikan dengan kebutuhan
tiap satuan keluaran 2 terhadap sumber 1 (dan seterusnya sampai
dengan kegiatan ke-n) tidak akan melebihi atau sama dengan
atau tidak boleh kurang dari jumlah (kapasitas) tersedianya
sumber 1 (yang dinyatakan dengan b1). Hal ini berlaku untuk
batasan-batasan lainnya sampai ke m.
 Fungsi-fungsi batasan dapat di kelompokkan menjadi 2 macam,
yaitu:
 1. Fungsi batasan fungsional, adalah fungsi-fungsi batasan
sebanyak m yaitu a11X1 + a12X2 + ... + a1nXn
2. Fungsi batasan non negatif (non negative constraints) yaitu
fungsi-fungsi batasan yang dinyatakan dengan
Xi 0
 Variabel Xj disebut sebagai variabel keputusan (decision
variables)
 aij, bi, Cj, yaitu masukan-masukan input konstan, disebut sebagai
parameter model.

C. METODE PEMECAHAN MODEL

LINEAR PROGRAMMING

Ada 2 (dua) metode/pendekatan yang dapat digunakan

untuk menyelesaikan persoalan-persoalan Linear Programming
(LP), yaitu dengan metode grafis dan dengan metode simpleks.
Bila persoalan LP hanya mempunyai 2 (dua) variabel keputusan,
maka dua metode tersebut dapat dipergunakan. Bila variabel yang
terlibat dalam penyelesaian LP lebih dari dua, maka metode grafis
tidak dapat dipergunakan lagi.
Metode yang lazim diterapkan untuk memecahkan
persoalan LP yang mempunyai variabel keputusan lebih dari dua
adalah metode simpleks. Melalui metode simpleks, kombinasi
variabel keputusan optimal diselesaikan dengan menggunakan
pendekatan matematis.
1. Metode Grafis
a. Persoalan Maksimasi
o Untuk memaksimumkan laba
o Fungsi batasan bertanda ≤
o Daerah feasible akan berada disebelah kiri bawah garis batas
tersebut
Contoh :

Perusahaan sepatu IDEAL membuat 2 model sepatu. Model

pertama merek A dengan sol dari karet, dan model ke-dua merek B
dengan sol dari kulit. Untuk membuat sepatu-sepatu itu, perusahaan
memiliki tiga macam mesin. Mesin 1 khusus membuat sol dari
karet, mesin 2 khusus membuat sol dari kulit, dan mesin 3
membuat bagian atas sepatu dan melakukan assembling bagian atas
dengan sol. Setiap lusin sepatu merek A mula-mula dikerjakan
mesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus
dikerjakan di mesin 3 selama 6 jam. Sedangkan untuk sepatu merek
B tidak diproses di mesin 1, tetapi pertama kali dikerjakan di mesin
2 selama 3 jam, kemudian di mesin 3 selama 5 jam. Jam kerja
maksimum setiap hari untuk untuk mesin 1 = 8 jqm, mesin 2 = 15
jam, dan mesin 3 = 30 jam. Sumbangan terhadap laba untuk setiap
lusin sepatu merek A = Rp 30.000, sedangkan untuk setiap lusin
sepatu merek B = Rp 50.000. Berapa lusin sebaiknya sepatu merek
A dan merek B yang di buat agar bias memaksimumkan laba.
Data diatas dapat disusun ke dalam Tabel 2.2 berikut ini:
 Tabel 2.2. Data Model Linear Programming
Merek Jenis Produksi Kapasitas
Mesin A B Sumber
1 2 0 8
2 0 3 15
3 6 5 30
Sumbangan terhadap
Laba (Rp. 10.000) 3 5

Langkah-langkah penyelesaian:
1) Memformulasikan fungsi tujuan dan fungsi kendala (batasan)
dalam bentuk matematis.

 Fungsi tujuan
Maksimumkan Z  3X1  5X 2
 Dengan batasan (1) 2X1  8
(kendala) (2) 3X 2  15
(3) 6X1  5X 2  30
Batasan non negatif: X1 , X 2  0

Tiga (3) pertidaksamaan diatas disebut batasan tekhnis

(technical constraints) yang ditentukan oleh keadaan
tekhnologi dan tersedianya input. Dan batasan non negatif
(non negative constraint) ditetapkan untuk menghindarkan
nilai negatif (yang tidak dapat diterima) dalam penyelesaian
persoalan.
2) Robah ketiga fungsi batasan ketidaksamaan menjadi kesamaan
( = ). Selesaikan masing-masing variabel
X 1 dan X 2 dengan
menetapkan salah satu variabel = 0.

(1) 2X1 = 8 X1 = 4
(2) 3X2 = 15 X2 = 5
(3) 6X1 + 5X2 = 30
X1 = 0 5X2 = 30 X2 = 6
X2 = 0 6X1 = 30 X1 = 5

3) Gambarkan masing-masing fungsi batasan dalam suatu sistem

sumbu. Grafik dari ketidaksamaan ≤ mencakup semua titik –
titik yang memenuhi fungsi batasan, yaitu semua titik pada
garis dan disebelah kiri bawah garis batas tersebut.

2X1 = 8
X2

6
D C 3X2 = 15
5

Daerah
Fisibel B

A
0 4 5 X1
6X1 + 5X2 = 30
 4) Tentukan daerah feasible untuk X 1 dan X 2 (diarsir), yaitu
daerah yang memuat semua titik-titik yang memenuhi ketiga
batasan ditambah batasan non negatif.
Daerah feasible dari soal di atas adalah OABCD (daerah yang
di arsir)

5) Tentukan solusi optimal, yaitu suatu titik singgung nilai fungsi

tujuan dengan daerah feasible yang terjauh dari titik nol.
Solusi optimal untuk soal diatas adalah pada titik C yaitu
perpotongan antara garis DC dengan garis BC.

6) Eliminasikan dan substitusikan, sehingga diperoleh nilai X 1

dan
X 2 . Dan nilai tersebut disubstitusikan ke fungsi tujuan
(Z).

3X2 = 15 5 15X2 = 75
6X1 + 5 X2 = 30 3 18X1 + 5X2 = 90
-18X1 = -15
X1 = 18/18 = 5/6

6X1 + 5X2 = 30
6(5/6) + 5X2 = 30
5 + 5X2 = 30 5X2 = 25 X2 = 5
Sehingga diperoleh harga X1 = 5/6 dan X2 = 5, kemudian
substitusikan kedalam fungsi tujuan:
Z  3 X1  = 3 (5/6) + 5 (5) = 2,5 + 25 = 27,5
5X 2
 Dengan demikian, solusi optimum dari soal diatas adalah
perusahaan harus membuat sepatu merek A sebanyak 5/6 lusin
dan merek B sebanyak 5 lusin setiap hari dengan keuntungan
sebesar Rp 275.000 ( 27,5 x Rp 10.000)

Cara lain untuk menentukan solusi optimal adalah dengan

membandingkan nilai Z yang diperoleh pada berbagai titik X1 dan
X2 di daerah fisibel. Nilai Z makin besar bila makin jauh dari titik
origin ( 0 ). Untuk itu yang dibandingkan sebaiknya adalah titik-
titik yang ada di sudut-sudut daerah feasible, yaitu titik 0, A, B, C,
dan D.

Titik O Pada titik ini X1 = 0, X2 = 0, sehingga Z = 0

Titik A Pada titik ini X1 = 4 dan X2 = 0, sehingga Z = 12
Titik B Pada titik ini X1 = 4.
6(4) + 5X2 = 30; X2 = (30 – 24)/5 = 6/5.
Sehingga Z = 18
Titik C Pada titik ini X2 = 5
6X1+ 5(5) = 30; X1 = (30 – 25)/6 = 5/6
Sehingga Z = 27,5
Titik D Pada titik ini X1 = 5 dan X2 = 0, sehingga Z = 30
Diantara ke-lima alternatif diatas, nilai Z terbesar adalah pada titik
C, yaitu sebesar 27,5. Titik ini merupakan titik optimal, dengan X1
= 5/6 lusin dan X2 = 5 lusin, dengan keuntungan sebesar Rp
275.000.
b. Persoalan Minimasi
o Untuk meminimalkan biaya
o Fungsi batasan bertanda ≥
o Daerah feasible akan berada disebelah kanan atas garis batas
tersebut
Contoh:
PT. Asia Automotif memproduksi 2 jenis mobil, yaitu mobil sedan
dan truk. Untuk dapat meraih konsumen berpenghasilan tinggi,
perusahaan ini memutuskan untuk melakukan promosi dalam 2
macam acara TV, yaitu pada acara hiburan dan acara olahraga.
Promosi pada acara hiburan akan disaksikan oleh 7 juta pemirsa
wanita dan 2 juta pemirsa laki-laki. Promosi pada acara olahraga
akan disaksikan oleh 2 juta pemirsa wanita dan 12 juta pemirsa
laki-laki. Biaya promosi pada acara hiburan adalah Rp 5 juta per
menit, sedangkan pada acara olahraga biayanya 10 juta per menit.
Jika perusahaan menginginkan promosinya disaksikan sedikitnya
oleh 28 juta pemirsa wanita dan sedikitnya 24 juta pemirsa laki-
laki, bagaimanakah promosi itu sebaiknya?
Data diatas disusun kedalam tabel seperti terlihat pada
Tabel 2.3 dibawah ini

Tabel 2.3. Data dari Perusahaan Asia Automotif

Promosi Jenis Promosi Jumlah

Pemirsa H (X1) O (X2) Pemirsa
Wanita 7 2 28
Laki-laki 2 12 24
Biaya Promosi (Rp. Juta) 5 10
Langkah-langkah penyelesaian:
1) Memformulasikan fungsi tujuan dan fungsi kendala (batasan)
dalam bentuk matematis:
 Fungsi tujuan
Maksimumkan
Z  5X 1 10X 2

 Dengan batasan (1)

7 X1  2X 2  28
(kendala) (2) 2X 12 X  24
1 2

Batasan non negatif: X1 , X 2  0

2). Robah ketiga fungsi batasan ketidaksamaan menjadi kesamaan (

= ). Selesaikan masing-masing variabel
X 1 dan X 2 dengan
menetapkan salah satu variabel = 0.
(1) 7X1 + 2X2 = 28
X1 = 0 2X2 = 28 X2 = 14
X2 = 0 7X1 = 28 X1 = 4

3) Gambarkan masing-masing fungsi batasan dalam suatu sistem

sumbu. Grafik dari ketidaksamaan ≥ mencakup semua titik –
titik yang memenuhi fungsi batasan, yaitu semua titik pada
garis dan disebelah kanan garis batas tersebut.

4) Tentukan daerah feasible untuk X 1 dan X 2 (diarsir), yaitu

daerah yang memuat semua titik-titik yang memenuhi ketiga
batasan ditambah batasan non negatif.
 X2

D
14

Daerah feasible

2 C

A B
0 4 12 X1

5) Tentukan daerah feasible untuk X 1 dan X 2 (diarsir), yaitu

daerah yang memuat semua titik-titik yang memenuhi ketiga
batasan ditambah batasan non negatif.
6) Tentukan solusi optimal, yaitu suatu titik singgung nilai fungsi
tujuan dengan daerah feasible yang terdekat dengan titik nol.
Solusi optimal untuk soal diatas adalah pada titik C yaitu
perpotongan antara garis DC dengan garis BC.
7) Eliminasikan dan substitusikan, sehingga diperoleh nilai X1
dan X2. Dan nilai tersebut disubstitusikan ke fungsi tujuan (Z).

7X1 + 2X2 = 28 6 42X1 + 12X2 = 168

2X1 + 1 2X2 = 24 1 2X1 + 12X2 = 42
40X1 = 144
X1 = 3,6
7X1 + 2X2 = 28
7(3,6) + 2X2 = 28
25,2 + 2X2 = 28 2X2 = 2,8 X2 = 1,4
Sehingga diperoleh harga X1 = 3,6 dan X2 = 1,4, kemudian
substitusikan kedalam fungsi tujuan:

Z  5 X1 = 5 (3,6) + 10 (1,4) = 18 + 14 = 32
10X 2
 Keputusannya adalah lama promosi dalam acara hiburan 3,6 menit sedangkan
dalam acara olahraga 1,4 menit dengan total biaya Rp 32 juta. Cara lain untuk
menentukan solusi optimal adalah dengan membandingkan nilai Z yang diperoleh
pada tiap-tiap alternatif.