OPERASIONAL RISET

MUHAMMAD RYAN PERMANA ST.,MT

ANNI ROHIMAH ST.,MT
PROGRAMA LINEAR
 Programa linier adalah salah satu metode operasional
riset yang digunakan untuk menyelesaikan persoalan
pengalokasian sumber-sumber terbatas.

 Sifat linier mempunyai arti bahwa seluruh fungsi

dalam model ini merupakan fungsi linier.

Karakteristik2 yang biasa digunakan :

 Variabel Keputusan, merupakan variabel yang
menguraikan secara lengkap keputusan2 yang
akan dibuat (dinotasikan sebagai X1 ,X2 ,X3 ,.... Xn )
 Fungsi Tujuan, merupakan fungsi dari variabel
keputusan yang akan dimaksimumkan
(keuntungan) atau diminimumkan (kerugian)  Z
= ƒ(x)
 Pembatas, merupakan kendala yang dihadapi
sehingga kita tidak bisa menentukan harga2
variabel keputusan secara sembarang
 Pembatas Tanda, pembatas yang menjelaskan
apakah variabel keputusannya diasumsikan hanya
berharga non- negatif atau berharga positif
 Rumuskan masalah dengan menggunakan
sejumlah informasi yang tersedia, lalu terjemahkan
dalam bentuk model matematika.

 Secara umum formulasi masalah programa linier

sbb. :
Minimu atau
m
f Maksimum
= C1 X 1 + C2 X 2 + … + Cn
x Xn

Kendala :

a11 X1 +a12 X 2 + ... + a1n X n ≤ = ≥ ) b1

(
X1 + a22 X 2 a2n X n ( ≤ = ≥ ) b2
a21 + ... +
.

.
.
am 1 X1 + am 2 X2 + ... + amn Xn ( ≤ = ≥ ) bm

≥0
Dan X1, X2, ..., Xn
Contoh :
Sebuah perusahaan merencanakan untuk memproduksi dua macam
produk, yaitu A dan B. Setiap unit produk A membutuhkan 3 unit
sumber daya 1, 8 unit sumber daya 2 dan 4 unit sumber daya 3.
Sedangkan setiap unit produk B membutuhkan 6 unit
sumber daya 2 dan 5 unit sumber daya 3.
Banyaknya sumber daya 1, sumber daya 2 dan sumber daya 3 yang
tersedia masing-masing 12, 48 dan 30 unit.
Setiap unit produk A dan produk B masing-masing memberikan
sumbangan keuntungan sebesar Rp. 120,- dan Rp. 100,-.
Tentukan banyaknya masing-masing produk yang harus
diproduksi agar diperoleh keuntungan maksimal.
 Produk Kapasitas
Sumber A B Maksimum
Daya
1 3 0 12
2 8 6 48
3 4 5 30
Sumbangan
Keuntunga 120 100
n per unit

Maksimumkan :
Z = 120 X1 + 100 X2
Kendala :
3 X1 ≤
8 X1 + 6 X2 12
≤ 48
4 X1 + 5 X2 ≤
30
X1, X2 ≥
0
Maksimumkan :
Z = 120 X1 + 100 X2  Daerah fisibel dibatasi oleh
Kendala : titik
3 X1 ≤ (1)  0, A, B, C dan D
8 X1 + 6 X2 12 (2)
4 X1 + 5 X2 ≤ (3)  Di Titik 0, Z = 0
 Di Titik A, Z = 600
X1, X2 48
≤
30 Di Titik B
≥0 (perpotongan
8 X1 + 6 X2 =
X2 8 X1 + 6 2 ≤ persamaan 2 dan 3).
X 48 3 X1 ≤ 4 X1 + 5 48
12 X2
8 X2 = 3 dan =
X1 =
30 3,75
Z = 750
 Dengan cara yang sama,
6 A Titik C dimana X1 = 4 dan
X2 = 2,6 sehingga Z =
4 X1 + 5 2 ≤  746,6
B X 30 Dengan caraX1 yang
D dimana sama
= 4 dan X2 =
Daerah pula,
0 sehingga Z =
Fisibel C 480
Keuntungan maksimum (Rp. 750) diperoleh
Saat A di produksi 3,75 unit dan B diproduksi 3 u
D
0 6 7,5 X1
Transportasi :
 Pemodelan transportasi adalah masalah pendistribusian
sejumlah produk atau komoditas dari beberapa sumber
distribusi (supply) kepada beberapa daerah tujuan (demand)
dengan berpegang pada prinsip biaya transportasi minimal.
 Bisa juga digunakan untuk mencari perolehan/pendapatan
maksimal dari strategi distribusi komoditi yang mempunyai
keuntungan tertentu
 Ciri Khusus :
1. Ada sumber (pusat distribusi) dan sejumlah tujuan tertentu
2. Jumlah barang yg didistribusikan dari setiap sumber dan yang
diminta dari setiap tujuan, besarnya tertentu
3. Produk yg dikirim sesuai permintaan dan atau kapasitas sumber
4. Ongkos angkut tertentu
5. Kapasitas sumber hrs sama dng kapasitas tujuan, kalau beda
gunakan dummy pada kapasitas sumber atau tujuan
 Sumber distribusi)  Tujuan
(pusat
A

D
Metode-Metode Transportasi
:
 Langkah yang dilakukan :
1. Menentukan solusi fisibel basis awal
1. Metode Pojok Kiri Atas (Northwest Corner)
3. Metode Pendekatan (Vogel’s
2. Metode Ongkos Terkecil (Least Cost)
Vogel Approximation
Method)
2. Melakukan optimalisasi
Metode Pojok Kiri Atas (Northwest
Corner)
 Sebuah distributor merencanakan mengirim
pesanan
ke 4 lokasi Pelanggan, yakni Pelanggan A,
 Pelanggan
B, Pelanggan C dan Pelanggan D.
Seperti biasanya Distributor tersebut mengambil
 pesanannya dari 3 sumber, yakni sumber 1,
 sumber 2
dan sumber 3.
Biaya pengiriman diperkirakan Rp.1000,-/ton
 Kebutuhan Pelanggan A, B, C dan D berturut-turut
20,
65, 60 dan 10 unit sementara sumber 1, 2
dan 3 kapasitasnya berturut-turut 40, 40, 75
unit.
Untuk meminimasi ongkos transportasi,
 Tabel Ongkos

Biaya Pengiriman ke Pabrik Rp. 1000,-/Ton

3 2 1 7 40 1

Kapasitas

Sumber
1 5 7 3 40 2
6 3 4 9 75 3
20 65 60 10 155
Kebutuhan (Ton)
A B C D

Metode Pojok Kiri Atas

A B C D
3 2 1 7
1 40
1 5 7 3
2 40
6 3 4 9
3 75
20 65 60 10
 Metode Pojok Kiri Atas
A B C D
3 2 1 7
1 20 20 40
1 5 7 3
2 40 40
6 3 4 9
3 5 60 10 75
20 65 60 10

Total Biaya Transportasi = (20(3) + 20(2) + 40(5) + 5(3) + 60(4) +

10(9))1000
=
Rp.645.000,-
 Metode Ongkos Terkecil (Least Cost)
:
 kapasitas/kebutuhan pada
Prinsip metode LC  pemberian yang mempunyai
prioritas pengalokasian
tempat ongkos
terkecil (Cij terkecil).
 Alokasikan min(kapi, kebj)
Metode Pojok Kiri Atas

A B C D
3 2 1 7
1 40 40
1 5 7 3
2 20 10 10 40
6 3 4 9
3
65 10 75
20 65 60 10

Total Biaya Transportasi = (40(1) + 20(1) + 10(7) + 10(3) + 65(3) +

10(4))1000
= Rp.395.000,-
Metode Vogel’s
 Prinsipnya memberikan penalty, yaitu nilai
pengurangan
dari dua ongkos terkecil pada tiap-tiap baris dan
kolom.
 Lalu mencari penalty terbesar, alokasikan
sebanyak mungkin kapasitas atau kebutuhan pada
variabel ongkos terkecil, kemudian tandai kolom atau
baris yang sudah terpenuhi.
 Selanjutnya dilakukan perhitungan lagi dengan
 Perhitungan selesai semua
tidak mengikuti kolom yang
bila sudah terpenuhi.
kapasitas/kebutuhan
terpenuhi.
 Metode Vogel's

A B C D penalty

3 2 1 7 1
1 40
40
1 5 7 3 2
2 40
20 10 10
6 3 4 9 1
3 75
65 10
20 65 60 10
penalty 2 1 3 4
 Metode Vogel's

A B C D penalty

3 2 1 7 1
1 40

1 5 7 3 4
2 30
20 10
6 3 4 9 1
3 75

20 65 60 10
penalty 2 1 3 4
 Metode Vogel's
A B C D penalty

3 2 1 7 1
1 40
0

1 5 7 3 2
2 10
20 10
6 3 4 9 1
3 75

20 65 60 10
penalty 2 1 3 4
 Metode Vogel's
A B C D penalty

3 2 1 7
1 0
40
1 5 7 3 2
2 10
20 10
6 3 4 9 1
3 55
20
20 65 60 10
penalty 2 2 3 4
 Metode Vogel's

A B C D penalty

3 2 1 7
1 0
40
1 5 7 3
2 10
10
20 10
6 3 4 9
3 55
55 20
20 65 60 10
penalty 2 2 4
 Metode Vogel's
A B C D
3 2 1 7
1 40
40

1 5 7 3
2 20 10 10
40

6 3 4 9
3 55 20
75

20 65 60 10

Total biaya transportasi = Rp.385.000

Optimal?  uji optimalisasi!

LATIHAN
Uji
Optimalisasi :
1. Setelah penyelesaian awal
POKIA),
(misal dengan metode

2. berikutnya ;
Tentukan nilai Ui (kelompok baris ke i) dan Vj
3. (kelompok kolom ke j) dengan mengawali U1 = 0.
Tentukan nilai Ui dan Vj sisanya dengan menggunakan
sel-sel yang
persamaan teralokasikan
Ui + Vj = Cij. Perhitungan hanya dilakukan pada
(terisi).
Cij adalah ongkos transportasi dari i ke
j.
4. Tentukan nilaitij untuk sel-sel yang tidak teralokasi
(terisi)
dengan menggunakan rumus tij Ui + Vj - Cij
=
5. Jika semua nilai tij adalah NOL atau NEGATIF, maka
optimal sudah dicapai,
solusibila tidak maka identifikasi
putaran tertutup yang diawali dari sel yang
suatu tij
mempunyai
terbesar.
6. Dari tij terbesar menuju sel yang terisi (gerakan bisa
ke
atas, ke bawah, ke kiri atau ke kanan).
7. Tandai putaran tertutup dari sel tij dengan tanda
positip
kemudian berturut-turut bergantian tanda pada sel
yang kena rute perpindahan. Pilih sel yang bertanda
negatip dan pilih kapasitas sumber atau kebutuhan
yang terkecil, kemudian kurangkan atau tambahkan
sel yang kena rute perpindahan. Sel yang bertanda
negatip dilakukan pengurangan, sel bertanda positip
dilakukan penambahan terhadap kapasitas sumber
8. atau kebutuhan yang terpilih.
Bila Tij tidak sama dengan NOL atau NEGATIP, ulangi
lagi langkah ke 2.
 Uji
Optimalisasi
Sel yg tdk teralokasi
3 2 Vj 3 8
tode Pojok Kiri A
M tas
A eB C D
3 2 1 7
0 1 40
20 20
Ui 3 1 5 7 3
2 40
40
6 3 4 9
1 3 5 60 10
75
20 65 60 10

 U1 + VA = C1A    VA = 3 – 0  VA = 3  t1C = U1 + VC - C1C   t1C = 0 + 3 – 1 = 2

 U1 + VB = C1B    VB = 2 – 0  VB = 2  t1D = U1 + VD - C1D   t1D = 0 + 8 – 7 = 1
 U2 + VB = C2B    U2 = 5 – 2  U2 = 3  t2A = U2 + VA – C2A   t2A = 3 + 3 – 1 = 5
 U3 + VB = C3B    U3 = 3 – 2  U3 = 1  t2C = U2 + VC – C2C   t2C = 3 + 3 – 7 = -
 U3 + VC = C3C    VC = 4 – 1  VC = 3 
1
 U3 + VD = C3D    VD = 9 – 1  VD = 8 t2D = U2 + VD – C2D   t2D = 3 + 8 – 3 =
 t3A = U3 + VA – C3A   t3A = 1 + 3 – 6 = -2
8
Iterasi berikut :
Metode Pojok Kiri Atas
A B C D
3 2 1 7
1 20 20 2 1
40
1 - 5 7 + 3
2 5 - -1 + 40
40 8
6 3 4 9
3 -2 + + 60 - - 75
5 10

20 65 60 10
tij
Pilih nilai tij positip

terbesar,
yakni t2D .

Dari t2D (sel non basis)
buat
basis, yakni t2D  t3D  t3B  t2B
 perputaran
Beri tanda +tertutup
di sel mulai
melalui sel2
lalu bergantian mengikuti
perpindahan.
 Pilih sel bertanda negatip
dng nilai terkecil, yakni 10.
 3 2 Vj 3 0
tode Pojok Kiri
M Atas
A eB C D
3 2 1 7
0 1 40
20 20

Ui 1 5 7 3
3 2 40
30 10

6 3 4 9
1 3 15 60
75

20 65 60 10

 U1 + VA = C1A    VA = 3 – 0  VA = 3  t1C = U1 + VC - C1C   t1C = 0 + 3 – 1 = 2

 U1 + VB = C1B    VB = 2 – 0  VB = 2  t1D = U1 + VD - C1D   t1D = 0 + 0 – 7 = -1
 U2 + VB = C2B    U2 = 5 – 2  U2 = 3  t2A = U2 + VA – C2A   t2A = 3 + 3 – 1 = 5
 U2 + VD = C2D    VD = 3 – 3 VD = 0  t2C = U2 + VC – C2C   t2C = 3 + 3 – 7 = -1
 U3 + VB = C3B    U3 = 3 – 2  VD = 1  t3A = U3 + VA – C3A   t3A = 1 + 3 – 6 =
 U3 + VC = C3C    VC = 4 – 1  VC = 3  -2
t3D = U3 + VD – C3D   t3D = 1 + 0 – 9 =
-8
Tij masih ada yg positip, solusi optimal blm tercapai,
Lakukan alokasi ulang kapasitas sumber atau kebutuhan
 3 2 Vj 3 0
tode Pojok Kiri A
M tas
A eB C D
3 2 1 7
0 1 -
+
+ 40
20 - 20
Ui 3 1 5 7 3
2 + - - 40
+ 30 10
6 3 4 9
1 3 15 60
75
20 65 60 10

Metode Pojok Kiri Atas

A B C D
3 2 1 7
1 40
0 40
1 5 7 3
2 10
40
20 10
6 3 4 9
3 15 60
75
20 65 60 10
 Vj
-2 2 tode Pojok Kiri At 3 0
M as
A eB C D
3 2 1 7
0 1 40
40
Ui
3 1 5 7 3
2 10
40
20 10
6 3 4 9
1 3 15 60
75
20 65 60 10

 U1 + VB = C1B    VB = 2 – 0  VB = 2  t1A = U1 + VA - C1A   t1A = 0 - 2 – 3 = -5

 U2 + VB = C2B    U2 = 5 – 2  U2 = 3  t1C = U1 + VC - C1C   t1C = 0 + 3 – 1 =
 U2 + VA = C2A    VA = 1 – 3  U2 = -2 2
 t1D = U1 + VD – C1D   t1D = 0 + 0 – 7 = -7
 U2 + VD = C2D    VD = 3 – 3 VD = 0  t2C = U2 + VC – C2C   t2C = 3 + 3 – 7 =
 U3 + VB = C3B    U3 = 3 – 2  VD = 1  -1
 U3 + VC = C3C    VC = 4 – 1  VC = 3  t3A = U3 + VA – C3A   t3A = 1 - 2 – 6 = -
7
t3D = U3 + VD – C3D   t3D = 1 + 0 – 9 =
-8
 Metode Pojok Kiri Atas
A B C D
3 2 1 7
1 40
-5 40 2 -7
1 5 7 3
2 10
40
20 10 -1
6 3 4 9
3 15 60
75
-7 -8
20 65 60 10

Metode Pojok Kiri Atas

A B C D
3 2 1 7
1 40
-5 - + -7
1 5 7 3
2 10
40
20 10 -1
6 3 4 9
3 75
-7 + - -8
20 65 60 10
 -4 0 tode Pojok Kiri 1 -2
M Atas
A eB C D
3 2 1 7
0 1 40
40
5 1 5 7 3
2 10
40
20 10
6 3 4 9
3 3 55 20
75
20 65 60 10

 U1 + VC = C1C    VC = 1 – 0  VC = 1  t1A = U1 + VA - C1A   t1A = 0 - 4 – 3 = -7

 U3 + VC = C3C    U3 = 4 – 1  U3 = 3  t1B = U1 + VB - C1B   t1B = 0 + 0 – 2 -2
 U3 + VB = C3B    VB = 3 – 3  VB = 0 = -9

 U2 + VB = C2B    U2 = 5 – 0  U2 = 5 t1D = U1 + VD – C1D   t1D = 0 - 2 – 7
 t2C = U2 + VC – C2C   t2C = 3 + 3 – 7 = -1
=
 U2 + VA = C2A    VA = 1 – 5  VA = -4  t3A = U3 + VA – C3A   t3A = 3 - 4 – 6 = -
 U2 + VD = C2D    VD = 3 – 5  VC = -2 
7
t3D = U3 + VD – C3D   t3D = 3 - 2 – 9 = -
8
Semua Tij negatip, hasil optimal total biaya transportasi
= 40(1) +dengan :
20(1) + 10(5) + 10(3) + 55(3)
+ 20(4)
= Rp 385ribu
TERIMA KASIH