PROGRAM LINEAR

1. PENDAHULUAN

Data seringkali kurang dimanfaatkan dalam proses pengambilan keputusan,

sehingga banyak keputusan yang dibuat tidak mencapai sasaran atau tujuan organisasi.
Suatu organisasi pada umumnya menginginkan aliran arus pemasukan yang maksimum
dengan keterbatasan-keterbatasan yang dimiliki oleh organisasi tersebut, di lain pihak
ada organisasi yang menginginkan aliran arus pengeluaran yang minimum dengan
keterbatasan –keterbatasan yang dimiliki organisasi tersebut.

Dalam suatu organisasi bisnis, biasanya seorang manajer berperan dalam

proses pengambilan keputusan. Saat manajer berusaha mengambil keputusan dengan
memanfaatkan data yang tersedia untuk menyelesaikan masalah dengan tujuan yang
dibatasi oleh keterbatasan tertentu, manajer tersebut dapat memanfaatkan program
linear.

Program linear merupakan teknik aplikasi dari matematika yang disusun oleh
George B. Dantzig di tahun 1947 pada saat memimpin Air Force Statistical Control’s
Combat Analysis Branch di Pentagon. Pada saat Dantzig menganalisis masalah
perencanaan Air Force, dia menyadari dapat merumuskan sistem ketidaksamaan linear,
hal di atas merupakan awal pemberian nama untuk teknik “program dalam struktur
linear”, yang belakangan disederhanakan menjadi program linear.

Definisi sederhana program linear adalah suatu teknik aplikasi matematika

dalam menentukan pemecahan masalah yang bertujuan untuk memaksimumkan atau
meminimimkan sesuatu yang dibatasi oleh batasan-batasan tertentu, dimana hal ini
dikenal juga sebagai teknik optimalisasi.

2. FORMULASI MODEL PROGRAM LINEAR

Manajer Diva adalah seorang manajer di perusahaan penghasil kerajinan

tangan. Perusahaannya mempekerjakan pengrajin untuk memproduksi piring dan gelas
dengan desain Bali. Sumber daya utama yang digunakan perusahaan adalah tanah liat
dan tenaga kerja. Menyadari keterbatasan sumber daya, manajer Diva ingin
mengetahui berapa banyak pring dan gelas yang akan diproduksi tiap hari dalam rangka
memaksimalkan laba. Tabel 1.1 berikut menyajikan data yang dimanfaatkan oleh
manajer Diva.
Tabel 1. kebutuhan Sumber Daya , Persediaan Sumber Daya dan Laba

Jam Tenaga Kerja Pon Tanah Liat Per Laba Per Unit
Produk
Per unit Unit Produk

Piring 1 4 80

Gelas 2 3 100

Persediaan per hari 40 120

Tabel 1.1 menunjukkan bahwa setiap unit piring dapat dihasilkan dengan 1 jam tenaga
kerja dan 4 pon tanah liat dan laba per unit 80 satuan mata uang. Gelas setiap unitnya
dapat dihasilkan dengan 2 jam tenaga kerja dan 3 pon tanah liat dan laba per unitnya
100 satuan mata uang.

Hal-hal yang terkait dengan tujuan (dalam hal ini memaksimumkan laba) dan
batasan yang membatasi tujuan tersebut (dalam hal ini persediaan per hari dari sumber
daya) adalah unit pring dan unit gelas yang dapat diproduksi tiap hari. Berdasarkan hal
tersebut, keputusan yang dihadapi oleh Diva dalam masalah ini adalah berapa banyak
piring dan gelas yang harus diproduksi tiap hari. Jika jumlah yang diproduksi untuk tiap
jenis produk dapat diwakili oleh simbol berikut :

x1 = jumlah piring yang diproduksi tiap hari

x2 = jumlah gelas yang diproduksi tiap hari

Karena x1 dan x2 merupakan variabel yang harus nilai harus diputuskan oleh Diva
dengan memperhatikan tujuan dan batasan yang membatasi tujuan tersebut sebagai
variabel keputusan. Setelah diidentifikasikan hal-hal yang terkait dengan tujuan dan
batasan-batasannya, maka Diva dapat melanjutkan tahapan berikutnya yaitu membuat
fungsi yang menggambarkan besarnya laba bila x2 dan x2 nilai ditetapkan, dalam hal ini
disebut sebagai fungsi tujuan.

Tujuan perusahaan adalah memaksimalkan total laba, dimana merupakan hasil

dari penjumlahan dari total laba piring dan total laba gelas. Total laba dari
memproduksi piring sebanyak x1 dengan laba per unitnya 80 adalah 80 x1, sedangkan
total laba dari memproduksi gelas sebanyak x2 dengan laba per unitnya 100 adalah 100
x2. Jika total laba dinotasikan dengan Z, maka

Fungsi tujuan : memaksimumkan Z=80 x1 + 100 x2

Dalam memutuskan nilai x1 dan x2 agar Z maksimum, Diva harus mengacu pada
batasan-batasan yang mencakup nilai-nilai yang membatasi tujuan memaksimumkan Z.
Dengan demikian harus ada fungsi yang menggambarkan hubungan antara nilai batasan
da x1 maupun x2, dalam hal ini disebut sebagai fungsi kendala. Nilai batasan yang
 pertama adalah persediaan jam tenaga kerja per hari sebesar 40 jam. Setiap unit piring
menggunkana 1 jam tenaga kerja dan per unit gelas menggunakan 2 jam tenaga kerja,
sehingga hubungannya adalah

1 x1 + 2 x2 ≤ 40

Nilai batasan yang kedua adalah persediaan tanah liat per hari sebesar 120 pon. Setiap
unit piring menggunakan 4 pon tanah liat dan per unit gelas menggunakan 3 pon tanah
liat, sehingga hubungannya adalah :

4 x1 + 3 x2 ≤ 120

Berdasarkan uraian diatas, maka model program linear untuk masalah yang dihadapi
oleh Diva adalah sebagai berikut :

Fungsi Tujuan : memaksimumkan Z = 80 x1 + 100 x2

Fungsi Kendala 1 x1 + 2 x2 ≤ 40

4 x1 + 3 x2 ≤ 120

x1, x2 ≥ 0

3. Metode Grafik

Penyelesaian dengan menggunakan metode grafik dapat digunakan dengan

mudah bila pemahaman mengenai fungsi linear, kemiringan garis dan titik potong pada
masing-masing sumbu sudah dipahami dengan baik.

Langkah-langkah dalam metode grafik adalah :

a. Buat grafik stiap kendala yang ada di fungsi kendala

b. Tentukan titik-titik sudut di daerah layak

c. Evaluasi nilai Z pada titik-titik sudut di daerah layak

d. Tentukan titik sudut yang memberikan nilai Z maksimum sebagai solusi optimal dari
model program linear atau sebaliknya titik sudut yang memberikan nilai Z minimum
sebagai solusi optimal dari model program linear. Hal tersebut tergantung dari
tujuan (memaksimumkan atau meminimumkan).

Berikut ini adalah hasil dari langkah-langkah tersebut di atas :

Langkah (a)
Gambar 1. Daerah Layak Model Program Linear

Langkah (b)

Titik-titik sudut di daerah layak :

x1 x2

O 0 0

A 0 20

B 24 8

C 30 0

Langkah (c)

Evaluasi nilai Z pada titik-titik sudut di daerah layak

 x1 x2 Z = 80 x1 + 100 x2

O 0 0 80 (0) + 100 (0) = 0

A 0 20 80 (0) + 100 (20) = 2000

B 24 8 80 (24) + 100 (8) = 2720

C 30 0 80 (30) + 100 (0) = 2400

Langkah (d)

Karena tujuannya adalah memaksimumkan, maka titik sudut yang memberikan Z

maksimum (Z = 2720) adalah titik B. hasil ini menunjukkan bahwa solusi optimal untuk
model program linear adalah

Zopt = 2720

x1 = 24, x2 = 8

4. Metode Simpleks

Sebelum kita membahas metode simpleks, perlu diingat bahwa kendala yang
terdapat dalam fungsi kendala model program linear dapat dibedakan dengan tanda
hubungan matematis berupa :

≤ (pertidaksamaan kurang dari)

= (persamaan)

≥ (pertidaksamaan lebih dari)

Berdasarkan hal tersebut maka dalam metode simpleks perlu ditambahakan

pada ruas kiri setiap kendala dalam fungsi kendala model program linear variabel yang
dikenal sebagai variabel penolong, yang terdiri dari slack, variabel surplus dan variabel
artificial.

Aturan penambahan variabel penolong disajikan pada table 2 berikut.

Tabel 2. Aturan Penambahan variabel penolong

Nama Variabel Notasi Penambahan untuk Kendala

Slack S ?

Surplus -S ?
Artifical A ?

Mari kita perhatikan model program linear berikut :

Fungsi Tujuan : memaksimumkan Z = 80 x1 + 100 x2

Fungsi Kendala 1 x1 + 2 x2 ≤ 40

4 x1 + 3 x2 ≤ 120

x1, x2 ≥ 0

Setelah dilakukan penambahan variabel penolong maka model program linear

menjadi model persamaan linear sebagai berikut :

Maksimumkan Z = 80 x1 + 100 x2 + 0 s1 + 0 s2

Dengan batasan 1 x1 + 2 x2 + 1 s1 + 0 s2 = 40

4 x1 + 3 x2 + 0 s1 + 1 s2 = 120

Proses untuk memperoleh solusi optimal dengan metode simpleks dilakukan

dengan menggunakantabel yang dinamakan tabel simpleks sebagai berikut :

Cj
Basis bi bi/akk

Zj
Cj-Zj

Langkah-langkah dalam metode simpleks adalah

a. Merubah model program linear menjadi model persamaan linear.

b. Menyusun tabel simpleks awal.

c. Menyusun nilai Zj pada setiap kolom bi.

d. Menghitung nilai (Cj – Zj) pada setiap kolom variabel.

e. Periksa nilai-nilai (Cj – Zj), jika (Cj – Zj) ≤ 0 (untuk tujuan memaksimumkan) maka ke
langkah (l) atau jika (Cj – Zj) ≥ 0 (untuk tujuan meminimumkan) maka ke langkah (l).

f. Tentukan kolom kunci berdasarkan nilai (Cj – Zj). Kolom kunci terletak pada kolom
variabel yang nilai (Cj – Zj) positip terbesar jika tujuannya memaksimumkan,
sebaliknya kolom kunci terletak pada kolom variabel yang nilai (Cj – Zj) negatip
terbesar jika tujuannya meminimumkan.

g. Tentukan baris kunci berdasarkan nilai (bi/akk) positip terkecil.

h. Tentukan angka kunci (akk), yaitu angka yang terletak pada kolom kunci dan baris
kunci.

i. Ganti variabel yang teletak pada baris kunci dengan variabel yang terletak pada
kolom kunci.

j. Lakukan transformasi setiap baris yang dimulai dengan baris kunci dengan rumus
transformasi sebagai berikut :

Bk baru = (Bk lama) / ak

Bi baru = Bi – ai,kk * Bk baru

k. Kembali ke langkah (c)

l. Solusi optimal diperoleh, dimana nilai variabel basis untuk masing-masing baris
terletak pada kolom bi.

Varibel basis pada tabel awal adalah variabel-variabel yang bukan variabel
keputusan, dimana variabel tersebut pada setiap kendalanya mempunyai koefisien (aij)
sebesar satu. Nilai varibel basis pada tabel simpleks terletak pada kolom b i. penentuan
variabel basis untuk tabel selanjutnya ditentukan oleh kolom kunci dan penempatannya
berdasarkan baris kunci.

Variabel non basis pada tabel simpleks adalah variabel-variabel yang nilainya
sama dengan nol.

Notasi i menunjukkan baris, dimana banyaknya baris sama dengan banyaknya

kendala, sedangkan notasi j menunjukkan kolom variabel dimana banyaknya kolom
sama dengan banyaknya variabel dalam model persamaan linear (gabungan variabel
keputusan dan variabel penolong yang terdapat dalam model persamaan linear).
Sedangkan kolom bi disebut sebagai kolom nol.

Berikut ini adalah hasil dari langkah-langkah dalam metode simpleks :

Langkah (a) :
 Fungsi Tujuan : memaksimumkan Z = 80 x1 + 100 x2

Fungsi Kendala 1 x1 + 2 x2 ≤ 40

4 x1 + 3 x2 ≤ 120

x1, x2 ≥ 0

Maksimumkan Z = 80 x1 + 100 x2 + 0 s1 + 0 s2

Dengan batasan 1 x1 + 2 x2 1 + s1 + 0 s2 = 40

4 x1 + 3 x2 + 0 s1 + 1 s2 = 120

Langkah (b) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
S1 0 1 2 1 0 40
S2 0 4 3 0 1 120

Zj
Cj-Zj

Langkah (c) :

Nilai Zj pada kolom variabel sama dengan jumlah dari perkalian unsur-unsur pada kolom
Cj dengan unsur –unsur yang terletak pada kolom variabel tersebut, sedangkan nilai Zj
pada kolom bi sama dengan jumlah dari perkalian unsur-unsur pada kolom Cj dengan
unsur-unsur yang terletak pada kolom bi. Perkalian dilakukan bila unsur-unsur tersebut
terletak pada baris yang sama.

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
S1 0 1 2 1 0 40
 S2 0 4 3 0 1 120

Zj 0 0 0 0 0
Cj-Zj

Langkah (d) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
S1 0 1 2 1 0 40
S2 0 4 3 0 1 120

Zj 0 0 0 0 0
Cj-Zj 80 100 0 0

Langkah (e) :

C1 – Z1 = 80

C2 – Z2 = 100

C3 – Z3 = 0

C4 – Z4 = 0

Bila diperhatikan, nilai-nilai (Cj – Zj) e ≥ 0, maka hal ini menunjukkan bahwa nilai Z masih
dapat ditingkatkan (ingat tujuannya adalah memaksimumkan) atau dengan kata lain,
tabel simpleksnya harus direvisi (belum menyediakan solusi optimal).

Langkah (f) :

Berdasarkan nilai (Cj – Zj) dan tujuannya memaksimumkan, maka kolom kuncinya adalah
kolom variabel x2, hal ini menunjukkan bahwa variabel x2 akan ditempatkan pada
kolom basis untuk menggantikan variabel basis yang teletak di kolom basis, namun
variabel mana yang akan digantikan? Yaitu variabel yang terletak di baris kunci.

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
 S1 0 1 2 1 0 40
S2 0 4 3 0 1 120

Zj 0 0 0 0 0
Cj-Zj 80 100 0 0

KK

Langkah (g) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk

S1 0 1 2 1 0 40 20 BK

S2 0 4 3 0 1 120 40

Zj 0 0 0 0 0
Cj-Zj 80 100 0 0

KK

Baris kunci (BK) terletak pada baris pertama, maka variabel x2 akan menggantikan
variabel S1.

Langkah (h) :

Angka kunci sebesar 2.

Langkah (i) dan (j) :

Pada tabel simpleks berikutnya, variabel S1 digantikan oleh x2 dengan nilai C j untuk
variabel x2 sebesar 100. Kemudian unsur-unsur pada setiap baris ditransformasi,
misalnya unsur-unsur baris pertama yang merupakan baris kunci ditransformasi dengan
rumus

B1 baru = (B1 lama) / 2

B2 baru = B2 lama – (3) B1 baru

 Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 ½ 1 ½ 0 20
S2 0 5/2 0 -3/2 1 60

Zj
Cj-Zj

Setelah ini kembali ke langkah (c) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 ½ 1 ½ 0 20
S2 0 5/2 0 -3/2 1 60

Zj 50 100 50 0 2000
Cj-Zj

Langkah (d) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 ½ 1 ½ 0 20
S2 0 5/2 0 -3/2 1 60

Zj 50 100 50 0 2000
Cj-Zj 30 0 -50 0

Langkah (e) :

C1 – Z1 = 30
C2 – Z2 = 0

C3 – Z3 = -50

C4 – Z4 = 0

Nilai-nilai (Cj - Zj) tersebut diatas menunjukkan bahwa tabel simpleks harus direvisi
(Tujuan dari model program linear adalah memaksimumkan). Jadi masih
memungkinkan untuk menaikkan nilai Z dari Z = 2000. Nilai (Cj - Zj) dapat diartikan
sebagai penambahan nilai Z untuk setiap kenaikan perunit dari nilai variabelnya.
Sebagai contoh, x1 jika menjadi 24, maka nilai Z yang baru akan sama dengan 2000 +
720 = 2720.

Langkah (f) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 ½ 1 ½ 0 20
S2 0 5/2 0 -3/2 1 60

Zj 50 100 50 0 2000
Cj-Zj 30 0 -50 0

Langkah (g) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 ½ 1 ½ 0 20 40
S2 0 5/2 0 -3/2 1 60 24

Zj 50 100 50 0 2000
Cj-Zj 30 0 -50 0

Langkah (h) :

Angkah kunci nilai 5/2, yaitu nilai yang terletak pada kolom kunci dan baris kunci.
Langkah (i) dan (j) :

Pada tabel simpleks berikutnya, variabel S2 digantikan oleh x1 dengan nilai C j untuk
variabel x1 sebesar 80. Kemudian unsur-unsur untuk setiap baris ditransformasi,
misalnya unsur-unsur baris kedua yang merupakan baris kunci ditransformasi dengan
rumus

B2 baru = (B2 lama) / (5 / 2)

B1 baru = B1 lama – (1 / 2) B2 baru

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 0 1 4/5 -1/5 8
X1 80 1 0 -3/5 2/5 24

Zj
Cj-Zj
Tabel simpleks diatas menyajikan solusi, x1 = 24, x2 = 8, S1 = 0 dan S2 = 0. Apakah solusi
ini merupakan solusi optima? Hal ini tentu dapat diperiksa dengan mengulangi kembali
langkah (c) dan seterusnya. Tabel menyajikan solusi optimal dinamakan sebagai Tabel
Simpleks Optimal dan tabel simpleks optimal menyajikan berbagai informasi yang tidak
langsung diperoleh dari metode grafik.

Langkah (c) :

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 0 1 4/5 -1/5 8
X1 80 1 0 -3/5 2/5 24

Zj 80 100 32 12 2720
Cj-Zj

Langkah (d) :
 Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 0 1 4/5 -1/5 8
X1 80 1 0 -3/5 2/5 24

Zj 80 100 32 12 2720
Cj-Zj 0 0 -32 -12

Apakah solusi dimana x1 = 24, x2 = 8, S1 = 0 dan Z maksimum sebesar 2720 merupakan

solusi optimal? Mari kita perhatikan langkah € berikut.

Langkah (e) :

C1 – Z1 = 0

C2 – Z2 = 0

C3 – Z3 = -32

C4 – Z4 = -12

Karena (Cj – Zj) ≤ 0, maka solusi tersebut di atas optimal

Cj 80 100 0 0
Basis X1 X2 S1 S2 bi bi/akk
X2 100 0 1 4/5 -1/5 8
X1 80 1 0 -3/5 2/5 24

Zj 80 100 32 12 2720
Cj-Zj 0 0 -32 -12

Pada tabel simpleks optimal, menunjukkan bahwa solusi optimalnya adalah x1 = 24, x2
= 8, S1 = 0, S2 = 0 dan Z (laba maksimum) = 2720.