Linier Programming
LINEAR PROGRAMMING
Model umum yang digunakan dalam
pemecahan masalah pengalokasian sumbersumber yang terbatas secara optimal
Masalah timbul bila seseorang diharuskan
untuk memilih/menentukan tingkat setiap
kegiatan yang akan dilakukannya, dimana
masing-masing kegiatan membutuhkan
sumber sama sedangkan jumlah terbatas
Dalam model LP dikenal
2 (dua) macam fungsi,
1. Fungsi tujuan menggambarkan tujuan
sasaran di dalam permasalahan LP yang
berkaitan dengan pengaturan secara optimal
sumberdaya-sumberdaya, untuk memperoleh
keuntungan maksimal atau biaya minimal.
Dinyatakan sebagai Z.
2. Fungsi batasan (fungsi kendala) bentuk
penyajian secara matematis batasan-batasan
kapasitas yang tersedia yang akan dialokasikan
secara optimal ke berbagai kegiatan.
Formulasi Model
Komponen Model :
1. Variabel Keputusan
2. Fungsi Tujuan
3. Batasan Model
Variabel Keputusan
Merupakan simbol matematika yang
menggambarkan tingkatan aktifitas perusahaan.
Contoh :
perusahaan elektronik menginginkan untuk
memproduksi x1 radio, x2 bakaran roti, dan x3
jam, dimana x1, x2 dan x3 adalah lambang yang
menunjukkan jumlah variabel setiap item yang
tidak diketahui.
Nilai akhir dari x1, x2, x3, merupakan keputusan
(misal x1 = 10 radio adalah keputusan
perusahaan untuk memproduksi radio).
5
Fungsi Tujuan
Merupakan hubungan matematika linier
yang menjelaskan tujuan perusahaan
dalam terminologi variabel keputusan.
Fungsi tujuan selalu mempunyai salah satu
target : memaksimumkan atau
meminimumkan suatu nilai
(memaksimumkan laba atau
meminimumkan biaya produksi)
Batasan Model
Menunjukkan keterbatasan perusahaan karena
lingkungan operasi perusahaan.
Dapat berupa keterbatasan sumber daya atau
pedoman.
Contoh : hanya 40 jam tenaga kerja tersedia,
untuk membuat radio selama proses produksi.
Simbol yang Umum
Digunakan
Z = Nilai dari semua standar performansi
xj = Tingkat aktivitas j (untuk j = 1, 2, , n)
cj = Penambahan terhadap Z yang diakibatkan
oleh peningkatan tiap unit di tingkat aktivitas
j
bi = Jumlah sumber daya i yang tersedia untuk
aktivitas (untuk i = 1, 2, , m)
aij = Jumlah sumber daya i yang dipakai oleh tiap
unit aktivitas j
8
Data yang Diperlukan
Penggunaan Sumber Daya per Unit
Aktivitas
Sumber Daya
1
2
:
m
Kontribusi terhadap Z
per unit aktivitas
Aktivitas
1
a11
a21
am1
c1
2
a12
a22
am2
c2
n
a1n
a2n
amn
cn
Jumlah
Sumber
Daya yang
Tersedia
b1
b2
:
bm
Bentuk Standar
n
max Z c j x j
min Z c j x j
ST :
ST :
j 1
a x
j 1
ij
bi ; i 1,2,..., m
x j 0; j 1,2,..., n
j 1
a x
j 1
ij
bi ; i 1,2,..., m
x j 0; j 1,2,..., n
10
Assumptions of Linear
Programming
Proportionality
naik turunnya nilai Z dan penggunaan
sumber atau fasilitas yang tersedia akan
berubah secara sebanding (proportional)
dengan perubahan tingkat kegiatan.
11
Assumptions of Linear
Programming
Additivity
nilai tujuan tiap kegiatan tidak saling
memperngaruhi, atau kenaikan dari
nilai tujuan (Z) yang diakibatkan oleh
kenaikan suatu kegiatan dapat
ditambahkan tanpa mempengaruhi
bagian nilai Z yang diperoleh dari
kegiatan lain.
12
Assumptions of Linear
Programming
Additivity
Misal : Z = 3X1 + 5X2
Dimana
X1 = 10; X2 = 2;
Sehingga
Z = 30 + 10 = 40
Andaikata X1 bertambah 1 unit, maka nilai
Z menjadi 40 + 3 = 43. Jadi, nilai 3 karena
kenaikan X1 dapat langsung ditambahkan
pada nilai Z mula-mula tanpa mengurangi
bagian Z yang diperoleh dari kegiatan 2
(X2).
Dengan kata lain, tidak ada korelasi antara
X1 dan X2.
13
Assumptions of Linear
Programming
Divisibility
Asumsi ini menyatakan bahwa
keluaran (output) yang dihasilkan
oleh setiap kegiatan dapat berupa
bilangan pecahan. Demikian pula
dengan nilai Z yang dihasilkan.
Misal : X1 = 6,5; Z = 1.000,75
14
Assumptions of Linear
Programming
Certainty/deterministik
Nilai yang diberikan oleh tiap
parameter dari model pemrograman
linier diasumsikan sebagai konstanta
yang diketahui yaitu nilai aij,bi, cj
15
Contoh 1. Perusahaan sepatu
Perusahaan sepatu membuat 2 macam sepatu. Yang pertama
merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan 3
macam mesin. Mesin 1 membuat sol karet, mesin 2 membuat sol
kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan
assembling bagian atas dengan sol. Setiap lusin sepatu merek I1
mula-mula dikerjakan di mesin 1 selama 2 jam, kemudian tanpa
melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedang
untuk sepatu merek I2 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 mesin 1 adalah 8 jam, mesin
2 adalah 15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap
laba setiap lusin sepatu merek I1 = Rp 30.000,00 sedang merek I2
= Rp 50.000,00. Masalahnya adalah menentukan berapa lusin
sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa
memaksimumkan laba.
Bentuk Tabel
Mesin
I1
(X1)
I2
(X2)
1
2
3
2
0
6
0
3
5
Merek
Sumbangan laba
(dlm puluhan
ribu)
Kapasitas
Maksimum
perhari (jam)
8
15
30
Bentuk Matematis
Maksimumkan Z = 3X1 + 5X2
Batasan (constrain)
(1) 2X1
8 (kap max/hari mesin 1)
(2)
3X2 15 (kap max/hari mesin 2)
(3) 6X1 + 5X2 30 (kap max/hari mesin 3)
X1 0, X2 0
Fungsi batasan pertama (2 X1 8)
X2
2X1 = 8
2X1 8 dan
X1 0, X2 0
X1
Gambar di atas merupakan bagian yang
memenuhi batasan-batasan:
X1 0, X2 0 dan 2X1 8
Fungsi batasan (2 X1 8); 3X2 15;
6X1 + 5X2 30; X1 0 dan X2 0
X2
2X1 = 8
6X1 + 5X2 = 30
6
5D
3X2 = 15
Daerah
feasible
B
0
A
4
X1
MENCARI KOMBINASI YANG OPTIMUM
Dengan membandingkan nilai Z pada tiap-tiap alternatif
Z = 3X1 + 5X2
OPTIMUM
Z=27,5; x1=5/6; x2=5
X2
2X1 = 8
6X1 + 5X2 = 30
Titik C:
X2 = 5. Substitusikan batasan (3),
maka 6X1 + 5(5) = 30.
Jadi nilai X1 = (30 25)/6 = 5/6.
Nilai Z = 3(5/6) + 5(5) = 27,5
Titik D:
Pada titik ini nilai
X2 = 5; X1 = 0
Nilai Z = 3(0) + 5(5) = 25
3X2 = 15
Titik A:
Daerah
feasible
Titik B:
X1 = 4. Substitusikan batasan
(3), maka 6(4) + 5X2 = 30.
Jadi nilai X2 = (30 24)/5 = 6/5.
Nilai Z = 3(4) + 5(6/5) =18
Pada titik ini nilai
X1 = 4; X2 = 0
Nilai Z = 3(4) + 0 = 12
B
0
A
4
X1
Formulasi model pada LINGO
Penyelesaian dengan bantuan LINGO
Klik LINGO/Solve
Solusi
Untuk mendapatkan keuntungan yang maksimum,
maka perusahaan membuat sepatu
Merek I1 sebanyak 5/6 lusin
Merek I2 sebanyak 5 lusin
Memperoleh keuntungan sebesar 27,5 (dalam
ribuan)
Abaikan jumlah sepatu yang
bilangan pecahan => soal hanya
untuk contoh
Penyelesaian bisa dengan integer
linear programming => materi yang
akan datang
CONTOH 2. Perusahaan Mangkok dan cangkir
Perusahaan Barang Maju Bersama memproduksi 2
produk setiap hari yaitu mangkok dan cangkir.
Perusahaan mempunyai 2 sumber daya yang
terbatas jumlahnya yang digunakan untuk
memproduksi produk-produk tersebut seperti tanah
liat dan tenaga kerja. Dengan keterbatasan sumber
daya, perusahaan ingin mengetahui berapa
banyak mangkok dan gelas yang akan diproduksi
tiap hari dalam rangka memaksimumkan laba.
Kedua produk mempunyai kebutuhan sumber daya
untuk produksi serta laba per item adalah sebagai
berikut:
25
Kebutuhan Sumber Daya
Produk $ /
Tenaga
Tanah Liat
unit
Kerja (Jam)
(Pon)
Laba
Mangkok
Cangkir
Tersedia 40 jam tenaga dan 120 pon tanah liat setiap hari untuk
produksi. Masalah ini akan dirumuskan sebagai model program
linier dengan mendefinisikan terpisah setiap komponen model dan
menggabungkan komponen-komponen tersebut dalam satu
model.
26
Variabel Keputusan
Keputusan yang dihadapi manajemen dalam
masalah ini adalah berapa banyak mangkok dan
cangkir yang harus diproduksi tiap hari.
Jumlah yang diproduksi untuk tiap jenis produk
adalah sebagai berikut :
X1 : jumlah mangkok yang diproduksi
X2 : jumlah cangkir yang diproduksi
27
Fungsi Tujuan
Tujuan perusahaan adalah untuk
memaksimumkan total laba. Laba perusahaan
adalah jumlah dari laba setiap mangkok dan
cangkir.
memaksimumkan Z = $ 4 x1+ $ 5 x2
dimana
Z = total laba tiap hari
$4x1 = laba dari mangkok
$5x2 = laba dari cangkir
28
Batasan Model-1
Dalam masalah berikut terdapat 2 sumber
daya digunakan : tenaga kerja dan tanah liat
BATASAN TENAGA KERJA :
Untuk setiap mangkok yang diproduksi memerlukan
1 (satu) jam tenaga kerja dan untuk setiap cangkir
diperlukan 2 jam tenaga kerja .. 1x1 + 2x2
Akan tetapi jumlah tenaga kerja sebesar 1x1 + 2x2
dibatasi sampai dengan 40 jam perhari, maka
batasan tenaga kerja menjadi:
1x1 + 2x2 40 jam
29
Batasan Model-2
BATASAN TANAH LIAT :
Setiap mangkok memerlukan 4 pon tanah liat.
Jumlah tanah liat yang digunakan tiap hari untuk
memproduksi mangkok adalah 4 x1 pon
Setiap cangkir memerlukan 3 pon tanah liat.
Jumlah tanah liat yang digunakan tiap hari adalah 3
x2.
Jika diasumsikan bahwa tanah liat yang tersedia
tiap hari adalah 120 pon, batasan bahan baku
dapat dirumuskan sebagai berikut
4 x1 + 3 x2 120 pon
30
Batasan Model-3
Batasan akhir adalah bahwa jumlah
mangkok dan cangkir yang
diproduksi bernilai nihil atau positif
x1 0, x2 0
31
Model Program Linier :
Memaksimumkan Z = $ 4 x1 + $ 5 x2
Terbatas pada
1 x1 + 2 x2 40
4 x1 + 3 x2 120
x 1, x 2 0
32
Formulasi model pada LINGO
Penyelesaian dengan bantuan LINGO
Klik LINGO/Solve
Soal 3.
Suatu pabrik menghasilkan 2 jenis produk (A,B) yang
diolah dengan tiga mesin (I, II, III). Tiap unit produk A
membutuhkan waktu pengolahan 1 menit di mesin I, 3
menit di mesin II, dan 1 menit di mesin III. Sedangkan
tiap unit produk B membutuhkan waktu pengolahan 2
menit di mesin I, 1 menit di mesin II, dan 1 menit di
mesin III. Kapasitas operasi maksimum mesin 1 =
1600 menit, mesin II = 2400 menit, dan mesin III =
1000 menit. Jika diketahui laba per unit produk A =
1000 dan produks B = 1500, maka berapa kombinasi
produk A dan B yang dapat diproduksi agar tercapai
laba maksimum ?
Soal 4.
Sebuah perusahaan manufaktur memproduksi 4 jenis produk
yang dibuat dari 3 jenis bahan baku yang berbeda.
Penggunaan masing-masing jenis bahan baku untuk masingmasing jenis produk adalah:
Bahan Baku (kg)
Produk A
3,5
Produk B
Produk C
2,5
Produk D
3,5
2,5
Selanjutnya untuk memproduksi setiap unit:
Produk A diperlukan 5 jam orang (man-hours)
Produk B diperlukan 4 jam orang (man-hours)
Produk C diperlukan 3 jam orang (man-hours)
Produk D diperlukan 6 jam orang (man-hours)
Bahan baku yang tersedia :
Bahan baku 1 = 200 kg
Bahan baku 2 = 300 kg
Bahan baku 3 = 400 kg
Jam orang yang tersedia selama periode produksi
adalah 300 jam. Jika keuntungan dari setiap unit produk
A, B, C, D adalah Rp7.000; Rp10.000; Rp5.000;
Rp6.000.
Formulasikan permasalahan diatas ke dalam model
Program Linier jika diharapkan keuntungan maksimum
pada periode tersebut