LINIEAR
PROGRAMMING
TE O R I P E NG A M B I L A N KE P U TU S
A N AN D R I H E L M I M , S . E . , M . M .
NA NA S U P R I ATNA , M. P D .
INTRODUCTION
Masalah keputusan yang biasa dihadapi para analis adalah alokasi optimum sumber daya yang
langka. Sumber daya dapat berupa modal, tenaga kerja, bahan mentah, kapasitas mesin, waktu,
ruangan atau teknologi. Tugas analis adalah mencapai hasil terbaik yang mungkin dengan
keterbatasan sumber daya ini. Hasil yang diinginkan mungkin ditunjukkan sebagai maksimisasi dari
beberapa ukuran seperti profit, penjualan dan kesejahteraan atau minimisasi seperti biaya, waktu
dan jarak.
Identifikasi masalah penerapan tujuan formulasi model matematik(3 tahap);
1. Menentukan variabel yang tidak diketahui (variabel keputusan) dinyatakan dalam simbol
matematik
2. Membentuk fungsi tujuan uang ditunjukkan sebagai suatu hubungan linier (bukan perkalian)
dari variabel keputusan
3. Menentukan semua kendala masalah tersebut dan mengekspresikan dlaam persamaan dan
pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang
mencerminkan keterbatasan sumberdaya masalah itu.
PENGERTIAN
• Linear programming adalah suatu teknis matematika yang
dirancang untuk membantu manajer dalam merencanakan dan
membuat keputusan dalam mengalokasikan sumber daya yang
terbatas untuk mencapai tujuan perusahaan
• LP merupakan suatu model umum yang dapat digunakan dalam
pemecahan masalah pengalokasian sumber-sumber yang
terbatas secara optimal
• Model yang digunakan dalam memecahkan masalah
alokasi sumberdaya perusahaan adalah model matematis
• Semua fungsi matematis yang disajikan dalam model haruslah dalam
bentuk fungsi linear
CIRI LINEAR PROGRAMMING
• Penyelesaian masalah mengarah pada pencapaian
tujuan maksimisasi atau minimisasi
• Kendala yang ada membatasi tingkat pencapaian
tujuan
• Ada beberapa alternatif penyelesaian
• Hubungan matematis bersifat linear
ASUMSI DASAR LINEAR
PROGRAMMING
1. Proporsionality Naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang
tersedia akan berubah secara sebanding (proporsional) dengan perubahan tingkat kegiatan
2. Additivity Nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau kenaikan dari nilai
tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa
mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.
3. Divisibility Keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa
bilangan pecahan, demikian pula nilai Z yang dihasilkan.
4. Deterministic (Certainty) Semua parameter yang terdapat dalam model LP
(aij,bi,Cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat
MODEL LINEAR PROGRAMMING
• Model LP merupakan bentuk dan susunan dalam menyajikan masalah-
masalah yang akan dipecahkan dengan teknik LP
• Dalam model LP dikenal 2 (dua) macam “fungsi”, yaitu fungsi tujuan
(Objective Function) dan fungsi batasan (constraint function)
• Fungsi Tujuan fungsi yang menggambarkan tujuan/sasaran di dalam
permasalahan LP yang berkaitan dengan pengaturan secara optimal
sumberdaya-sumberdaya, untuk memperoleh keuntungan maksimal atau
biaya minimal. Nilai yang akan dioptimalkan dinyatakan sebagai Z
• Fungsi Batasan merupakan bentuk penyajian secara matematis
batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara
optimal ke berbagai kegiatan
SIMBOL DALAM LINEAR
PROGRAMMING
• m = macam batasan sumber atau fasilitas yang tersedia
• n = macam kegiatan yang menggunakan sumber atau fasilitas tersebut
• i = nomor setiap macam sumber atau fasilitas yang tersedia (i=1,2,...,m)
• j = nomor setiap macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia (j = 1,2,...,n)
• xj = tingkat kegiatan ke, j. (j = 1,2,...,n)
• aij = banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran (output) kegiatan j (I
= 1,2,...,m, dan j = 1,2,...,n)
• bi = banyaknya sumber (fasilitas) yang tersedia untuk dialokasikan ke setiap unit kegiatan (I = 1,2,...,n)
• Z = nilai yang dioptimalkan (maksimum atau minimum)
• Cj = kenaikan nilai Z apabila ada pertambahan tingkat kegiatan (xj) dengan satu satuan (unit); atau
merupakan sumbangan setiap satuan keluaran kegiatan j terhadap nilai Z
DATA UNTUK LINIER PROGRAMMING
MODEL MATEMATIS PERMASALAHAN LP
• Fungsi Tujuan:
Maksimumkan Z = C1X1 + C2X2 + C3X3 + ... + CnXn
• Batasan-batasan:
1) a11X1 + a12X2 +a13X3 + ...+a1nXn b1
2) a21X1 + a22X2 +a23X3 + ...+a2nXn b2
m) am1X1 + am2X2 +am3X3 + ...+amnXn bm
dan
X10, X2 0, ..., Xn 0
PENDEKATAN LP
Dalam menyelesaikan permasalahan dengan menggunakan Linear
Programming, ada dua pendekatan yang bisa digunakan, yaitu metode
grafik dan metode simpleks.
1) Metode grafik hanya bisa digunakan untuk menyelesaikan
permasalahan dimana variabel keputusan sama dengan dua.
2) Metode simpleks bisa digunakan untuk menyelesaikan
permasalahan dimana variabel keputusan dua atau lebih.
CONTOH 1:
Sebuah perusahaan ingin menentukan berapa banyak masing-masing dari tiga
produk yang berbeda (A, B dan C) yang akan dihasilkan dengan tersedianya
sumber daya yang terbatas agar diperoleh keuntungan maksimum. Kebutuhan
buruh dan bahan mentah dan sumbangan keuntungan masing-masing produk.
Produk A memerlukan kebutuhan buruh 5 jam/unit dan bahan 4 kg/ unit dengan
keuntungan yang diharapkan Rp 3/ unit. Produk B memerlukan buruh 2 jam/ unit
dan bahan 6 kg/ unit, keuntungan yang diharapkan Rp 5/ unit dan produk C
memerlukan buruh 4 jam/ unit dengan 3 kg/ unit bahan, keuntungan yang
diharapkan Rp 2/ unit. Tersedia 240 jam kerja dan bahan mentah sebanyak 400 kg.
masalahnya adalah menentukan jumlah masing-masing produk agar keuntungan
maksimum. Bagaimana rumusan/ formula LP-nya?
CONTOH 2
Untuk menjaga kesehatan, seseorang harus memenuhi kebutuhan minimum perhari akan
beberapa zat makanan. Misalkan hanya ada tiga jenis zat makanan yang dibutuhkan yaitu
kalsium, protein dan vitamin A. sementara makanan yang tersedia ada tiga jenis juga yitu:
makanan A, B dan C yang harganya, zat-zat yang terkandung di dalamnya dan kebutuhan
minimum perhari akan zat-zat makanan tersebut dapat dilihat pada table berikut:
Makanan Kebutuhan
Kandungan
I II III Minimum
Kalsium 5 1 0 8
Protein 2 2 1 10
Vitamin A 1 5 4 22
Harga/ unit 0,5 0,8 0,6
Bagaimana kombinasi ketiga jenis makanan akan memenuhi kebutuhan minimum perhari dan
memberikan biaya terendah?
PENYELESAIAN GRAFIK MODEL LP
Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan dimana
hanya terdapat dua variabel keputusan. Untuk menyelesaikan permasalahan
tersebut, langkah pertama yang harus dilakukan adalah memformulasikan
permasalahan yang ada ke dalam bentuk Linear Programming (LP). Langkah-langkah
dalam formulasi permasalahan adalah :
1. Pahamilah secara menyeluruh permasalahan manajerial yang dihadapi
2. Identifikasikan tujuan dan kendalanya
3. Definisikan variabel keputusannya
4. Gunakan variabel keputusan untuk merumuskan fungsi tujuan dan fungsi
kendala secara matematis.
CONTOH
Perusahaan Krisna Furniture yang akan membuat meja dan kursi. Keuntungan yang diperoleh dari
satu unit meja adalah $7,- sedang keuntungan yang diperoleh dari satu unit kursi adalah $5,-.
Namun untuk meraih keuntungan tersebut Krisna Furniture menghadapi kendala keterbatasan
jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4 jam kerja. Untuk pembuatan 1 unit
kursi dia membutuhkan 3 jam kerja. Untuk pengecatan 1 unit meja dibutuhkan 2 jam kerja, dan
untuk pengecatan 1 unit kursi dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk
pembuatan meja dan kursi adalah 240 jam per minggu sedang jumlah jam kerja untuk pengecatan
adalah 100 jam per minggu. Berapa jumlah meja dan kursi yang sebaiknya diproduksi agar
keuntungan perusahaan maksimum?
Dari kasus di atas dapat diketahui bahwa tujuan perusahaan adalah memaksimumkan profit.
Sedangkan kendala perusahaan tersebut adalah terbatasnya waktu yang tersedia untuk pembuatan
dan pengecatan.
Jam kerja untuk membuat 1 unit produk Total waktu tersedia per
Meja Kursi minggu
Pembuatan 4 3 240
Pengecatan 2 1 100
Profit per unit 7 5
Mengingat produk yang akan dihasilkan adalah meja dan kursi, maka dalam rangka memaksimumkan
profit, perusahaan harus memutuskan berapa jumlah meja dan kursi yang sebaiknya diproduksi. Dengan
demikian dalam kasus ini, yang merupakan variabel keputusan adalah meja (X1) dan kursi (X2).
1) Fungsi Tujuan: Maksimisasi Z = $7X1 + $5X2
2) Fungsi Kendala
4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan) 2X1 +
1 X2 ≤ 100 (kendala departemen pengecatan) X1, X2 ≥ 0
(kendala non negatif pertama)
PENYELESAIAN LINEAR PROGRAMMING SECARA GRAFIK
• Langkah pertama dalam penyelesaian dengan metode grafik adalah menggambarkan fungsi kendalanya. Untuk
menggambarkan kendala pertama secara grafik, kita harus merubah tanda pertidaksamaan menjadi tanda persamaan seperti
berikut.
4X1+3X2 = 240 Kendala ini akan memotong salah satu atau kedua sumbu
• Kendala I: 4X1 + 3X2 = 240 memotong
sumbu X1 pada saat X2 = 0 4 X1 + 0 =
240
X1 = 240/4
X1 = 60.
memotong sumbu X2 pada saat X1 = 0
0 + 3 X2 = 240
X2 = 240/3
X2 = 80
Kendala I memotong sumbu X1 pada titik (60, 0) dan memotong sumbu X2 pada titik (0, 80).
• Kendala II: 2X1+ X2 =100
memotong sumbu X1 pada saat X2 = 0 2
X1 + 0 = 100
X1 = 100/2
X1 = 50
memotong sumbu X2 pada saat X1 =0
0 + X2 = 100
X2 = 100
Kendala II memotong sumbu X1 pada titik (50, 0) dan memotong sumbu X2 pada titik (0, 100)
Grafik Area Layak Titik potong kedua kendala bisa dicari dengan cara substitusi atau
eliminasi 2X1+ X2 =100
X2 = 100 - 2 X1
4 X1 + 3 X2 = 240
4 X1 + 3 (100 - 2X1) = 240
4X1+300-6X1 =240
-2X1 =240-300
-2X1 = - 60
X1 = -60/-2 = 30.
X2 = 100 - 2 X1
X2 = 100 - 2 * 30
X2 = 100 - 60
X2 = 40
Sehingga kedua kendala akan saling berpotongan pada titik
(30, 40).
Tanda ≤ pada kedua kendala ditunjukkan pada area sebelah kiri dari
garis kendala. Sebagaimana nampak pada feasible region (area
layak) meliputi daerah sebelah kiri dari titik A (0; 80), B (30; 40), dan
C (60; 0).
Untuk menentukan solusi yang optimal, ada dua cara yang bisa digunakan yaitu
1) dengan menggunakan garis profit (iso profit line)
2) dengan titik sudut (corner point)
Penyelesaian dengan menggunakan garis profit adalah penyelesaian dengan menggambarkan fungsi tujuan.
Kemudian fungsi tujuan tersebut digeser ke kanan sampai menyinggung titik terjauh dari dari titik nol, tetapi
masih berada pada area layak (feasible region). Untuk menggambarkan garis profit, kita mengganti nilai Z
dengan sembarang nilai yang mudah dibagi oleh koefisien pada fungsi profit. Pada kasus ini angka yang mudah
dibagi angka 7 (koefisien X1) dan 5 (koefisien X2) adalah 35. Sehingga fungsi tujuan menjadi 35 = 7X1 + 5X2. Garis ini
akan memotong sumbu X1 pada titik (5, 0) dan memotong sumbu X2 pada titik (0, 7).
Iso profit line menyinggung titik B yang merupakan titik terjauh dari titik nol. Titik B ini merupakan titik optimal.
Untuk mengetahui berapa nilai X1 dan X2, serta nilai Z pada titik B tersebut, kita mencari titik potong antara
kendala I dan kendala II (karena titik B merupakan perpotongan antara kendala I dan kendala II). Dengan
menggunakan eliminiasi atau subustitusi diperoleh nilai X1 = 30, X2 = 40. dan Z =
410. Dari hasil perhitungan tersebut maka dapat disimpulkan bahwa keputusan perusahaan yang akan
memberikan profit maksimal adalah memproduksi X1 sebanyak 30 unit, X2 sebanyak 40 unit dan
perusahaan akan memperoleh profit sebesar 410.
Iso Profit Line • Penyelesaian dengan menggunakan titik sudut (corner point) artinya
kita harus mencari nilai tertinggi dari titik-titik yang berada pada
area layak (feasible region). Dari peraga 1, dapat dilihat bahwa ada 4
titik yang membatasi area layak, yaitu titik 0 (0, 0), A (0, 80), B
(30,
40), dan C (50, 0).
• Keuntungan pada titik O (0, 0) adalah (7 x 0) + (5 x 0) = 0.
Keuntungan pada titik A (0; 80) adalah (7 x 0) + (5 x 80) = 400.
Keuntungan pada titik B (30; 40) adalah (7 x 30) + (5 x 40) =
410. Keuntungan pada titik C (50; 0) adalah (7 x 50) + (5 x 0) =
350.
Karena keuntungan tertinggi jatuh pada titik B, maka sebaiknya
perusahaan memproduksi meja sebanyak 30 unit dan kursi sebanyak
40 unit, dan perusahaan memperoleh keuntungan optimal sebesar
410.
Contoh 2;
1. Sebuah pabrik memproduksi meja dan kursi. Setiap meja memerlukan 2,5 jam untuk
perakitan (A), 3 jam pemolesan (B) dan 1 jam pengepakan (C). Sedangkan setiap kursi
memerlukan 1 jam perakitan, 3 jam pemolesan, dan 2 jam pengepakan. Perusahaan tidak
dapat menggunakan lebih dari 20 jam perakitan, 30 jam pemolesan, dan 16 jam pengepakan
setiap minggunya. Margin laba Rp 3 per meja dan Rp 4 per kursi. Berapakah meja dan kursi
yang harus diproduksi agar laba maksimum?
2. Seorang pengusaha rokok kretek ingin membuat rokok merek X1 dan X2 denan komponen
utama kertas, tembakau dan cengkeh. Pengusaha tersebut mencoba meramu dan membuat
sendiri rokok yang akan diproduksinya, dengan menyediakan bahak baku secara terbatas yaitu
500 gram kertas, 900 gram tembakau dan 400 gram cengkeh untuk 2 merek rokok tersebut.
Merek X1 perbantang memerlukan 1 gram kertas, 4 gram tembakau, 2 gram cengkeh dengan
biaya Rp 200. merek X2 perbatang memerlukan 1,5 gram kertas, 5 gram tembakau dan 3
gram cengkeh dengan biaya Rp 300. bagaimana kombinasi yang paling murah dari kedua
merek roko tersebut ? (Minimisasi)
SOAL
1. Sebuah usaha dagang memproduksi springbed dua model yaitu model lux (X) dan model
eksekutif (Y) masing-masing terbuat dari kayu. Model Lux memerlukan 4 jam perakitan, 6 jam
pengamplasan dan 3 jam pemelituran. Model Eksekutif memerlukan 3 jam perakitan, 4 jam
pengamplasan dan 3 jam pemelituran. Margin laba model Lux sebesar 200 dan model
eksekutif 100. berapakah produksi dialokasikan untuk memaksimumkan laba jika tersedia 90
jam perakitan, 70 jam pengamplasan dan 60 jam pemeliharaan?
2. Soal: maksimumkan dan minimumkan:
Tabel Bahan yang diperlukan untuk membuat Penyediaan bahan
produk/ unit
A B
Bahan 1 2 3 8
Bahan II 1 2 5
Harga Pasar 15.000 10.000
3)PT LAQUNATEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu
kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang
sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60
kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit
produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut:.
Jenis bahan baku dan Kg Bahan Baku dan Jam Tenaga Kerja Maksimum
tenaga kerja Kain Sutra Kain Wol Penyediaan
Benang sutra 2 3 60 kg
Benang wol - 2 30 kg
Tenaga kerja 2 1 40 kg