SEKOLAH TINGGI ILMU EKONOMI

DWI SAKTI BATURAJA

WRITTEN BY
HEMA MALINI, S.E., M.M.
 KATA PENGANTAR

Penulis panjatkan puji syukur Alhamdulillah kepada Allah SWT, atas segala
limpahan rahmat, karunia, dan kekuatan yang dianugerahkan kepada penulis sehingga
disela-sela kesibukan mengajar dan menjalankan tugas sebagai dosen, penulis dapat
menyelesaikan modul Riset Operasi.
Modul ini isinya sangat singkat dan padat dengan teori-teori yang dihimpun dari
kumpulan materi kuliah yang penulis berikan selama beberapa tahun mengajar di STIE
Dwi Sakti Baturaja. Dimulai dengan membahas teknik linear programming yang
meliputi metode grafik dan simpleks, teori dualitas, metode transportasi dan masalah
penugasan, kemudian analisis network dan teori permainan. Meskipun uraiannya
sangat singkat tetapi dirasa cukup untuk membantu mahasiswa dalam memahami
tentang riset operasi.
Akhirnya kepada pembaca penulis serahkan untuk memberikan penilaian dan
kritik yang membangun, sehingga mendorong penulis untuk memperbaiki modul ini di
masa yang akan datang.

Baturaja, Maret 2023

Penulis,

i
 DAFTAR ISI

Kata Pengantar .... .................................................................................................... ....... ii

Daftar Isi ...........................................................................................................................iii
Halaman
BAB I. PENDAHULUAN
A. Perkembangan Riset Operasi 1
B. Pengertian Riset Operasi 2
C. Pemodelan Matematis 2

BAB II. PROGRAM LINEAR

A. Pengertian Program Linear 4
B. Model Linear Programming 4
C. Asumsi-asumsi Linear Programming 6
D. Metode Grafik 6

BAB III. METODE SIMPLEKS

A. Pengertian Metode Simpleks 13
B. Langkah-Langkah Metode Simpleks 13
C. Penyimpangan Bentuk Standar 18

BAB IV. DUALITAS

A. Teori Dualitas 22
B. Analisis Sensitivitas 23

BAB V. METODE TRANSPORTASI

A. Pengertian Metode Transportasi 25
B. Stepping Stone 25
C. Modified Distribution 29
D. Vogel’s Approximation 30

BAB VI. MASALAH PENUGASAN

A. Pengertian Masalah Penugasan 35
B. Masalah Minimisasi 35
C. Jumlah Pekerjaan yang Tidak Sama dengan
Jumlah Karyawan 38
D. Masalah Maksimisasi 39

BAB VII. ANALISIS NETWORK

A. Pengertian Network 42
B. Analisis Jalur Kritis 42
C. Kegiatan Semu (Dummy) 43

DAFTAR PUSTAKA

ii
 BAB I
PENDAHULUAN

A. Perkembangan Riset Operasi

Teori Evolusi Manajemen, riset operasi mulai berkembang sejak tahun 1945,
pada saat Perang Dunia Kedua. Pendekatan kuantitatif dalam menyelesaikan
persoalan, di mana matematika dan statistika memegang peranan yang sangat
dominan telah menempatkan riset operasi secara teoritis sebagai ilmu
pengetahuan yang berakar Scientific Management yang dipelopori oleh Taylor pada
Abad XVIII. Di Inggris, dikenal sebagai Operational Research.
Sejak revolusi industri, dunia usaha diwarnai pertumbuhan dalam hal
besarnya dan kompleksitas organisasi-organisasi perusahaan. Bagian yang tampak
mencolok mengalami perubahan adalah perkembangan dalam pembagian kerja dan
tanggung jawab manajemen dalam organisasi tersebut.
Kompleksitas dan spesialisasi dalam suatu organisasi menumbuhkan
kesulitan yang semakin besar untuk mengalokasikan sumber daya-sumber daya
yang tersedia untuk kegiatan organisasi yang beranekaragam dengan cara yang
paling efektif dan efisien.
Perkembangan teknologi dalam era globalisasi yang begitu cepat dan
kompleks, salah satunya riset operasi sebagai salah satu ilmu terapan praktis yang
diperlukan dalam penyelesaian suatu permasalahan yang semakin kompleks
melalui pendekatan kuantitatif.
Tim-tim riset operasi dalam lingkungan dunia bisnis ini menandai kemajuan
teknik-teknik riset operasi, seperti metode simpleks untuk pemecahan masalah
linear programming. Kemajuan teknologi komputer juga telah menandai kemajuan
teori riset operasi dalam acuan pengambilan keputusan pemecahan masalah yang
optimum.

B. Pengertian Riset Operasi

Riset operasi terdiri dari dua kata yaitu Riset dan Operasi,
1. Riset adalah suatu proses yang terorganisasi dalam mencari kebenaran akan
masalah atau hipotesa.
2. Operasi dapat didefinisikan sebagai tindakan-tindakan yang diterapkan pada
beberapa masalah atau hipotesa.

2
Beberapa pengertian riset operasi;
1. Riset operasi adalah sebuah pendekatan kuantitatif yang menggunakan
metode-metode optimisasi untuk menyelesaikan suatu persoalan matematis.
2. Menurut Churchman, Arkoff dan Arnoff, Riset operasi adalah aplikasi metode-
metode, teknik-teknik dan peralatan-peralatan ilmiah dalam menghadapi
masalah-masalah yang timbul di dalam operasi perusahaan dengan tujuan
ditemukannya pemecahan yang optimum.
3. Menurut Morse dan Kimball, Riset operasi adalah metode ilmiah yang
memungkinkan para manajer mangambil keputusan mengenai kegiatan yang
mereka tangani dengan dasar kuantitatif.
4. Menurut Miller dan M.K. Starr, Riset operasi adalah peralatan manajemen yang
menyatukan ilmu pengetahuan, matematika dan logika dalam kerangka
pemecahan masalah yang dihadapi sehari-hari sehingga permasalahan dapat
diselesaikan secara optimal.

C. Pemodelan Matematis

Bagian terpenting dari Riset Operasi adalah bagaimana menerjemahkan

permasalahan sehari-hari ke dalam model matematis. Faktor-faktor yang
mempengaruhi pemodelan harus disederhanakan dan apabila ada data yang
kurang, kekurangan tersebut dapat diasumsikan atau diisi dengan pendekatan yang
bersifat rasional. Dalam Riset Operasi diperlukan ketajaman berpikir dan logika.
Yang perlu diperhatikan dalam proses pemodelan yaitu:
1. faktor-faktor dalam permasalahan,
2. kendala masing-masing faktor
3. asumsi-asumsi yang dibangun.

3
 Model dan Penyelesaian Optimal
Dunia Nyata Dunia Simbol

Abstraksi
Masalah Masalah ke Model
Model

Pembuatan
Analisis
Pertimbangan- Keputusan
Pertimbangan
Manajemen
Interpretasi
Intuisi dan Penyelesaian
Hasil Olahan
Pengalaman Optimal
Optimal

Tahapan dalam riset operasi yaitu :

1. Merumuskan masalah
a Variabel keputusan
b Tujuan
c Kendala
2. Pembentukan model
3. Mencari penyelesaian masalah
4. Validasi model
5. Penetapan hasil akhir

Teknik-teknik Riset Operasi

Banyak model RO yang sudah dikembangkan dan digunakan terhadap permasalahan-
permasalahan bidang bisnis. Mereka itu dapat dikelompokkan ke dalam beberapa jenis,
seperti dapat dilihat pada tabel berikut:
Program Linier Matematika Model Program Linier
Analisis Grafik
Metode Simplex
Model Minimasi
Post Optimasi
Transportasi dan Penugasan
Program Linier Integer
Program Linier Sasaran

4
Teknik Probabilistik Probabilitas Teori
Permainan
Analisis Keputusan
Analisis Markov
Antrian
Simulasi
Peramalan
Program Linier Matematika Model Program
Linier Analisis
Grafik Metode
Simplex Model
Minimasi
Post Optimasi
Transportasi dan
Penugasan
Program Linier
Integer Program
Linier Sasaran
Teknik Probabilistik Probabilitas Teori
Permainan
Analisis
Keputusan
Analisis Markov
Antrian
Simulasi
Peramalan
Teknik Persediaan Permintaan pasti
Permintaan tak
pasti

Teknik Jaringan Arus Jaringan

CPM/PERT

Teknik Non-Linier lainnya Program Dinamis

Analisis Titik
Impas
Teknik Solusi
berdasarkan
Kalkulus

METODE-METODE UMUM MENCARI SOLUSI

5
 Pada umumnya, terdapat tiga metode untuk mencari solusi terhadap model RO,
yaitu: 1) metode analitis, 2) metode numerik, dan 3) metode Monte Carlo.

Pendekatan analitik. Metode analitik memerlukan perwujudan model

dengan solusi grafik atau perhitungan matematik. Jenis matematik yang digunakan
tergantung dari sifat-sifat model. Misalkan fungsi matematik diselesaikan melalui
penggunaan integral kalkulus.

Pendekatan Numerik. Metode numerik berhubungan dengan perulangan

atau coba-coba dari prosedur-prosedur kesalahan, melalui perhitungan numerik
pada setiap tahap. Metode numerik digunakan jika metode analitik gagal untuk
mencari solusi. Urutannya dimulai dengan solusi awal dan diteruskan dengan
seperangkat aturan-aturan untuk perbaikan menuju optimum. Solusi awal
kemudian diganti dengan solusi yang diperbaiki dan proses itu diulang sampai
tidak mungkin adanya perbaikan lagi atau biaya perhitungan lebih lanjut tidak
dapat diterima.
Metode Monte Carlo. Metode ini memerlukan konsep probabilistik dan
sampling. Metode Monte-Carlo pada dasarnya adalah suatu teknik simulasi
dimana fungsi distribusi statistik dibuat melalui seperangkat bilangan random

RANGKUMAN

1. Secara umum riset operasi berkenaan dengan pengambilan keputusan yang

optimal dari sistem-sistem baik yang diterministik maupun probabilistik yang
berasal dari kehidupan nyata. Atau dunia pengelolaan atau dunia usaha yang
memakai pendekatan ilmiah atau pendekatan sistematis disebut riset operasi
(Operations Research).
2. Tujuan dari Riset Operasi adalah menerapkan pendekatan ilmiah guna
memecahkan permasalahan atau persoalan, dengan mengambil langkah-
langkah dan strategi yang tepat serta target yang sesuai secara sistematis
dalam rangka mencapai tujuan yang telah ditentukan secara optimal.
3. Sejalan dengan pekembangan dunia industri dan didukung dengan kemajuan
dibidang komputer, Riset Operasi semakin diterapkan di berbagai bidang
untuk menangani masalah yang cukup kompleks. Beberapa contoh-contoh
penggunaan Riset Operasi dibeberapa bidang yaitu Akuntansi dan Keuangan,
Pemasaran, Operasi Produksi, dan lain-lain.
6
4. Model dalam riset operasi terbagi atas 3 bagian utama, yaitu: Teknik
pemrograman matematika, Teknik pemrosesan stokastik dan metodestatistik.
5. Dalam riset operasi, pembuatan model melibatkan 3 komponen dasar yang
penting, yaitu variabel keputusan, tujuan dan kendala.
6. Tahapan-tahapan dalam penerapan Riset Operasi untuk memecahkan
persoalan adalah sebagai berikut: Merumuskan/menganalisis persoalan
sehingga jelas tujuan apa yang akan dicapai, Pembentukan model matematika
untuk mencerminkan persoalan yang akan dipecahkan, Mencari pemecahan
dari model yang telah dibuat dalam tahap sebelumnya, Menguji model dan
hasil pemecahan dari penggunaan model. Sering juga disebut melakukan
validasi, Implementasi hasil pemecahan.

7
 BAB II
PROGRAM LINEAR

A. Pengertian Program Linear

Program linear adalah salah satu model matematika yang digunakan untuk
menyelesaikan masalah optimisasi, yaitu memaksimumkan atau meminimumkan
fungsi tujuan yang bergantung pada sejumlah variabel input. Linear Programming
adalah salah satu model riset operasi yang menggunakan teknik Optimisasi
matematika linear di mana seluruh fungsi harus berupa fungsi matematika linear.
Suatu model umum yang dapat digunakan dalam pemecahan masalah
pengalokasian sumber-sumber yang terbatas secara optimal. Masalah akan timbul
apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan
yang membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Hal terpenting
yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa
penyebab masalah tersebut.
Dalam memecahkan masalah linear programming menggunakan model
matematis. Sebutan linear berarti bahwa semua fungsi-fungsi matematis yang
disajikan dalam model ini haruslah fungsi-fungsi linear.

B. Model Linear Programming

Model linear programming merupakan bentuk dan susunan dalam
menyajikan masalah-masalah yang akan dipecahkan dengan teknik linear
programming. Dalam linear programming dikenal dua fungsi, yaitu fungsi tujuan
dan fungsi kendala.
1. Fungsi Tujuan : Di mana tujuan yang hendak dicapai harus diwujudkan ke dalam
sebuah fungsi matematika linear, yang kemudian fungsi itu dimaksimumkan atau
diminimumkan terhadap kendala-kendala yang ada.
2. Fungsi Kendala : Kendala dalam hal ini dapat diumpamakan sebagai suatu
pembatas terhadap kumpulan keputusan yang mungkin dibuat dan harus
dituangkan ke dalam fungsi matematika linear yang dihadapi oleh manajemen.

8
 Tabel Standar Linear Programming
Kegiatan Pemakaian sumber per unit kegiatan Kapasistas
Sumber
Sumber

1 a11 a12 a13 . . . a1n b1

2 a21 a22 a23 . . . a2n B2

3 a31 a32 a33 . . . a3n b3

.
.
.

m am1 am2 am3 . . . anm bm

Z C1 C2 C3 . . . Cn
Tk. Kgt. X1 X2 X3 . . . Xn

C. Asumsi Dasar Linear Programming

Asumsi dasar linear programming adalah sebagai berikut :
1. Proportional
Asumsi ini bahwa naik turunnya Z dan penggunaan sumber yang tersdia akan
berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan.
2. Additivity
Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi,
atau dalam linear programming dianggap bahwa kenaikan dari nilai tujuan Z yang
diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi
Z yang diperoleh dari kegiatan lain.
9
3. Divisibility
Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap
kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang
dihasilkan.
4. Deterministik
Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model linear
programming dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.

D. Metode Grafik
Metode grafik hanya dapat digunakan dalam pemecahan masalah linear
programming yang berdimensi 2 x n, karena keterbatasan kemampuan suatu grafik.
Langkag-langkah dalam metode grafik adalah sebagai berikut :
1. Menentukan fungsi tujuan dan memformulasikan dalam bentuk matematis
2. Mengidentifikasi batasan-batasan yang berlaku dan memformulasikan dalam
bentuk matematis
3. Menggambarkan masing-masing garis fungsi batasan dalam satu sistem sumbu
koordinat
4. Mencari titik yang paling menguntungkan (optimal)
Perhitungan dengan metode grafik :
1. Masalah Maksimisasi
Maksimisasi dapat berupa memaksimalkan keuntungan atau hasil.
Contoh:
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 Kg bahan baku & Jam tenaga kerja Maksimum
dan tenaga kerja Kain sutera Kain wol penyediaan
Benang sutera 2 3 60 kg
Benang wol - 2 30 kg
Tenaga kerja 2 1 40 jam
Kedua jenis produk memberikan keuntungan sebesar Rp 40 juta untuk kain
sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan

10
jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan
yang diperoleh bisa maksimal.

Langkah-langkah:

a. Tentukan variabel X1=kain sutera X 2=kain wol

b. Fungsi tujuan Zmax = 40X1 + 30X2
c. Fungsi kendala / batasan

1) 2X1 + 3X2 60 (benang sutera)

2) 2X2 30 (benang wol)

3) 2X1 + X2 40 (tenaga kerja)

d. Membuat grafik

1) 2X1 + 3 X 2=60 X1=0, X2 =60/3 = 20 X2=0, X1= 60/2 = 30

2) 2X2 30 X2=15
3) 2X1 + X2 40 X1=0, X2 = 40 X2=0, X1= 40/2 = 20

X2

40
3

20

D
15 E 2
C

0 20 30 X1
A B

daerah penyelesaian

Cara mendapatkan solusi optimal ;

Dengan mencari nilai Z setiap titik ekstrim.
Titik A, X1=0, X2=0

masukkan nilai X1 dan X2 ke Z Z = 40 (0) + 30 (0) = 0

Titik B, X1=20, X2=0

masukkan nilai X1 dan X2 ke Z Z = 40 (20) + 30 (0) = 800

11
Titik C, Mencari titik potong (1) dan (3) 2X1 + 3X2 = 60

2X1 + X2 = 40
2X2 = 20 X2=10

Masukkan X2 ke kendala (1) 2X1 + 3X2 = 60

2X1 + 3 (10) = 60

2X1 + 30 = 60

2X1 = 30 X1 = 15

masukkan nilai X1 dan X2 ke Z

40X1 + 30X2 = 40 (15) + 30 (10) = 600 + 300 = 900 (optimal)

Titik D

2X2 = 30

X2 = 15

masukkan X2 ke kendala (1) 2X1 + 3 (15) = 60

2X1 + 45 = 60

2X1 = 15 X1 = 7,5

masukkan nilai X1 dan X2 ke Z

Z = 40 (7,5) + 30 (15) = 300 + 450 = 750

Titik E

X2 = 15

X1 = 0

masukkan nilai X1 dan X2 ke Z Z = 40 .

0 + 30 (15) = 450
Kesimpulan :

untuk memperoleh keuntungan optimal, maka X1 = 15 dan X2 = 10 dengan keuntungan

sebesar Rp 900 juta.

12
Dengan cara menggeser garis fungsi tujuan.
Solusi optimal akan tercapai pada saat garis fungsi tujuan menyinggung
daerah feasible (daerah yang diliputi oleh semua kendala) yang terjauh dari titik
origin. Pada gambar, solusi optimal tercapai pada titik C yaitu persilangan garis
kendala 1 dan 3.
Titik C
Mencari titik potong (1) dan (3)

2X1 + 3X2 60

2X1 + X2 = 40
2X2 = 20
X2 = 10
Masukkan X2 ke kendala (1)
2X1 + 3X2 = 60
2X1 + 3 . 10 = 60

2X1 + 30 = 60

2X1 = 30 X1 = 15

masukkan nilai X1 dan X2 ke Z

40X1 + 30X2 = 40 (15) + 30 (10) = 600 + 300 = 900

2. Masalah Minimisasi
Minimisasi dapat berupa meminimumkan biaya produksi. Solusi optimal
tercapai pada saat garis fungsi tujuan menyinggung daerah fasible yang terdekat
dengan titik origin.
Contoh :

Perusahaan makanan ROYAL merencanakan untuk membuat dua jenis

makanan yaitu Royal Bee dan Royal Jelly. Kedua jenis makanan tersebut
mengandung vitamin dan protein. Royal Bee paling sedikit diproduksi 2 unit dan
Royal Jelly paling sedikit diproduksi 1 unit. Tabel berikut menunjukkan jumlah
vitamin dan protein dalam setiap jenis makanan:

13
 Jenis makanan Vitamin Protein Biaya per unit
(unit) (unit) (ribu rupiah)

Royal Bee 2 2 100

Royal Jelly 1 3 80
minimum kebutuhan 8 12
Bagaimana menentukan kombinasi kedua jenis makanan agar meminimumkan
biaya produksi.
Langkah-langkah:

a. Tentukan variabel X1 = Royal Bee X2 = Royal Jelly

b. Fungsi tujuan

Zmin = 100X1 + 80X2

c. Fungsi kendala

1) 2X1 + X2 8 (vitamin)

2) 2X1 + 3X2 12 (protein)

3) X1 2
4) X2 1

d. Membuat grafik

1) 2X1 + X2 = 8

X1 = 0, X2 = 8

X2 = 0, X1 = 4

2) 2X1 + 3X2 = 12

X1 = 0, X2 = 4

X2 = 0, X1 = 6

3) X1 = 2

4) X2 = 1

14
 X2
(1) (3)

(2)
daerah
C penyelesaian
4

B (4)
1 A

2 4 6 X1

Solusi optimal tercapai pada titik B (terdekat dengan titik origin), yaitu persilangan
garis kendala (1) dan (2).
2X1 + X2 = 8

2X1 + 3X2 = 12

-2X2 = -4 X2 = 2

masukkan X2 ke kendala (1)

2X1 + X2 = 8
2X1 + 2 = 8

2 X1 = 6 X1 = 3

masukkan nilai X1 dan X2 ke Z

Z min = 100X1 + 80X2 = 100 . 3 + 80 . 2 = 300 + 160 = 460

Kesimpulan :

Untuk meminimumkan biaya produksi, maka X 1 = 3 dan X2 = 2 dengan biaya produksi

460 ribu rupiah.

RANGKUMAN

1. Masalah pemrograman linier adalah masalah optimisasi bersyarat yakni pencarian

nilai maksimum atau pencarian nilai minimum suatu fungsi tujuan berkenaan dengan
kendala yang harus dipenuhi. Program linear juga membutuhkan kemampuan untuk
mengubah bahasa cerita menjadi bahasa matematika atau model matematika.

15
2. Model matematika adalah bentuk penalaranmanusia dalam menerjemahkan
permasalahan menjadi bentuk matematika (dimisalkan dalamvariabel dan ) sehingga
dapat diselesaikan.

3. Program linier adalah cabang dari matematika terapan yang model matematikanya
berupa persamaan-persamaan atau pertidaksamaan-pertidaksamaan linier.
Sedangkan yang dimaksud dengan persoalan program linier adalah suatu persoalan
untuk menentukan besarnya masing-masing nilai variabel yang memaksimumkan
atau meminimumkan suatu nilai fungsi tujuan, dengan memperhatikan pembatasan-
pembatasan yang ada yang dinyatakan dalam bentuk persamaan atau pertidaksamaan
linier.
4. Model persoalan dikatakan merupakan persoalan program linier jika memenehui
ketentuan-ketentuan berikut ini.

a. Memuat fungsi tujuan yang harus dapat dinyatakan dalam bentuk fungsi linier
dari variabel-variabelnya. Sebagai contoh, Fungsi tujuan
ini harus mencerminkan tujuan persoalan yang akan dicapai.

b. Sumber-sumber yang tersedia dalam jumlah yang terbatas (biaya terbatas,

bahan mentah terbatas, waktu terbatas, tenaga terbatas, dan lain-lain).
Pembatasan tersebut harus dapat dinyatakan dalam bentuk persamaan
linier atau pertidaksamaan linier.
c. Harus terdapat alternative penyelesaian atau himpunan penyelesaian yang
mungkin, yaitu penyelesaian yang membuat fungsi tujuan menjadi
maksimum atau minimum.
5. Model dasar program linier yaitu: Maksimumkan
atau minimumkan:
+…+ Dengan
kendala-kendala:
+…+

+…+
+…+
Dan untuk
6. Solusi Program linier dapat diselesaikan dengan metode grafikdan juga
menggunakan metode simpleks.

16
 BAB III
METODE SIMPLEX

A. Pengertian Metode Simpleks

Metode grafik tidak dapat menyelesaikan persoalan linear program yang
memilki variabel keputusan yang cukup besar atau lebih dari dua, maka untuk
menyelesaikannya digunakan Metode Simplex. Salah satu teknik penentuan solusi
optimal yang digunakan dalam pemrograman linear adalah metode simpleks.
Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik
eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa
titik ekstrim satu persatu dengan cara perhitungan iterasi.
Beberapa ketentuan yang perlu diperhatikan, antara lain:
1. Nilai kanan (NK / RHS) fungsi tujuan harus nol (0).
2. Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut
harus dikalikan –1.
3. Fungsi kendala dengan tanda “ ” harus diubah ke bentuk “=” dengan
menambahkan variabel slack/surplus. Variabel slack/surplus disebut juga
variabel dasar.
4. Fungsi kendala dengan tanda “ ” diubah ke bentuk “ ” dengan cara mengalikan
dengan –1, lalu diubah ke bentuk persamaan dengan ditambahkan variabel slack.
Kemudian karena RHS-nya negatif, dikalikan lagi dengan –1 dan ditambah
artificial variabel (M).
5. Fungsi kendala dengan tanda “=” harus ditambah artificial variabel (M).

B. Langkah-Langkah Metode Simpleks

1. Langkah-langkah metode simpleks;
Rubah fungsi tujuan dan batasan
2. Menyusun fungsi tujuan dan batasan ke dalam tabel simpleks
3. Tentukan kolam kunci, di baris Z, angka negatif terbesar
4. Tentukan baris kunci indeks = NK / NK Kunci
5. Merubah baris kunci
6. Merubah nilai selain nilai pada baris kunci
BB = NL – (Koefisien x NB)
7. Lihat pada baris Z, masih adakah nilai negatif?
17
a. Jika masih ada, ulangi mulai langkah ke-3
b. Jika tidak ada, maka tabel optimal

Tabel Simpleks
Variabel Z X1 X2 X3 ... Xn Xn+1 Xn+2 ... Xn+m NK
Dasar

Z 1 -C1 -C2 -C3 -Cn 0 0 0 0

Xn+1 0 a11 a12 a13 a1n 1 0 0 b1

Xn+2 0 a21 a22 a23 a2n 0 1 0 b2

. .
. .
. .

Xn+m 0 am1 am2 am3 amn 0 0 1 bm

Contoh soal:

Z = 3X1 + 5X2
Kendala:

1) 2X1 8

2) 3X2 15

3) 6X1 + 5X2 30

Langkah-langkah:
1. Mengubah fungsi tujuan dan fungsi kendala (lihat beberapa ketentuan yang
harus diperhatikan di atas!)
Fungsi tujuan

Z = 3X1 + 5X2 => Z - 3X1 - 5X2 = 0

Fungsi kendala

1) 2X1 8 => + X3 = 8
2X1

2)3X2 15 => 3X2 + X4 = 15

3) 6X1 + 5X2 30 => + 5X2 + X5 = 30

18
 6X1

(X3, X4 dan X5 adalah variabel slack)

2. Menyusun persamaan-persamaan ke dalam tabel

[Link] Z X1 X2 X3 X4 X5 NK index
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30

3. Memilih kolom kunci

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang
bernilai negatif dengan angka terbesar.
[Link] Z X1 X2 X3 X4 X5 NK index
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30

4. Memilih baris kunci

Nilai Kanan (NK)
Indeks =
Nilai Kolom Kunci

Baris kunci adalah baris yang mempunyai index terkecil

[Link] Z X1 X2 X3 X4 X5 NK inde
r x
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8 ~
X4 0 0 3 0 1 0 15 5
X5 0 6 5 0 0 1 30 6

5. Mengubah nilai-nilai baris kunci

=> dengan cara membaginya dengan angka kunci Baris baru kunci = baris
19
 kunci : angka kunci sehingga tabel menjadi seperti berikut:
[Link] Z X1 X2 X3 X4 X5 NK index
Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8 ~
X2 0 0 1 0 1/3 0 5 5
X5 0 6 5 0 0 1 30 6
6. Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci (selain
baris kunci) = 0
Baris baru = baris lama – (koefisien angka kolom kunci x nilai baris baru
kunci)
Baris Z
Baris lama [ -3 -5 0 0 0 0]

NBBK -5 [ 0 1 0 1/3 0 5]
Baris baru -3 0 0 5/3 0 25

Baris X3

Baris lama [2 0 1 0 0 8]

NBBK 0 [0 1 0 1/3 0 5]

Baris baru 2 0 1 0 0 8

Baris X5
Baris lama [6 5 0 0 1 30 ]

NBBK 5 [0 1 0 1/3 0 5]

Baris baru 6 0 0 -5/3 1 5

Masukkan nilai di atas ke dalam tabel, sehingga tabel menjadi seperti berikut:
[Link] Z X1 X2 X3 X4 X5 NK index
Z 1 -3 0 0 5/3 0 25
X3 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
X5 0 6 0 0 -5/3 1 5

7. Melanjutkan perbaikan-perbaikan (langkah 3-6) sampai baris Z tidak ada nilai

20
 negatif

[Link] Z X1 X2 X3 X4 X5 NK inde
r x
Z 1 -3 0 0 5/3 0 25
X3 0 2 0 1 0 0 8 4
X2 0 0 1 0 1/3 0 5 ~
X5 0 6 0 0 -5/3 1 5 5/6

Z 1 0 0 0 5/6 1/2 27½ Zmax

X3 0 0 0 1 5/9 -1/3 6 1/3
X2 0 0 1 0 1/3 0 5
X1 0 1 0 0 - 1/6 5/6
5/1
8

Diperoleh hasil: X1 = 5/6 , X2 = 5, Zmax = 27 ½

C. Penyimpangan-Penyimpangan Bentuk Standar

1. Fungsi batasan dengan tanda sama dengan (=)
=> ditambah dengan variabel buatan Contoh :
Fungsi kendala:
1) 2X1 8 => 2X1+ X3 =8
2) 3X2 15 => 3X2 +X4 = 15
3) 6X1 + 5X2 = 30 => 6X1 + 5X2 + X5 = 30
Fungsi tujuan:
Z = 3X1 + 5X2 => Z – 3X1 – 5X2+ MX5 = 0

Nilai setiap variabel dasar (X5) harus sebesar 0, sehingga fungsi tujuan harus
dikurangi dengan M dikalikan dengan baris batasan yang bersangkutan (3). Nilai
baris Z sebagai berikut:

21
 [ -3 -5 0 0 M , 0]

M [6 5 0 0 1 , 30]

(-6M-3) (-5M-5) 0 0 0 -30M

Tabel:

[Link] Z X1 X2 X3 X4 X5 NK index
Z 1 -6M-3 -5M-5 0 0 0 -30M
X3 0 2 0 1 0 0 8 4
X4 0 0 3 0 1 0 15 ~
X5 0 6 5 0 0 1 30 5

VD Z X1 X2 X3 X4 X5 NK index
Z 1 0 -5M-5 3M+3/ 0 0 -6M+12
2
X1 0 1 0 1/2 0 0 4 ~
X4 0 0 3 0 1 0 15 5
X5 0 0 5 -3 0 1 6 6/5

Z 1 0 0 -3/2 0 M+1 18
X1 0 1 0 ½ 0 0 4 8
X4 0 0 0 9/5 1 -3/5 19/3 5/27
X2 0 0 1 -3/5 0 1/5 6/5 -2

Z 1 0 0 0 5/6 M+1/ 27 ½ max

2
X1 0 1 0 0 - 1/6 5/6
5/18
X3 0 0 0 1 5/9 -1/3 6
1/3
X2 0 0 1 0 1/3 0 5

Diperoleh hasil : X1 = 5/6, X2 = 5 dan Zmax = 27 ½

22
2. Fungsi tujuan : Minimisasi
Soal minimisasi harus diubah menjadi maksimisasi dengan cara mengganti
tanda positif dan negatif pada fungsi tujuan.
Contoh:
Minimumkan Z = 3X1 + 5X2
Fungsi batasan: 1) 2X1 = 8
2) 3X2 15
3) 6X1 + 5X2 30
Penyelesaian:
Fungsi batasan: 1) 2X1+ X3 = 8
2) 3X2 + X4= 15
3) 6X1 + 5X2-X5 + X6 = 30
Fungsi tujuan menjadi:
maksimumkan (-Z) = -3X1 – 5X2 –MX3 – MX6
diubah menjadi fungsi implisit => -Z + 3X1 + 5X2 + MX3 + MX6 =
0 Nilai – nilai variabel dasar (X3 dan X6 ) harus = 0, maka:
[ 3 5 M 0 0 M , 0 ]

-M [ 2 0 1 0 0 0 , 8 ]

-M [ 6 5 0 0 -1 1 , 30 ]
+
(-8M+3) (-5M+5) 0 0 M 0 , -38M

Tabel:

VD Z X1 X2 X3 X4 X5 X6 NK index
Z -1 -8M+3 -5M+5 0 0 0 0 -38M
X3 0 2 0 1 0 0 0 8 4
X4 0 0 3 0 1 0 0 15
X6 0 6 -5 0 0 -1 1 30 5

Z -1 3 -5M+5 4M- 0 M 0 -6M-12

23
 3/2
X1 0 1 0 ½ 0 0 0 4
X4 0 0 3 0 1 0 0 15 5
X6 0 0 5 -3 0 -1 1 6 6/
5

Z -1 0 0 M+3/ 0 1 M+1 -18 min

2
X1 0 1 0 ½ 0 0 0 4
X4 0 0 1 9/5 1 3/5 -3/5 5
2/5
X2 0 0 1 -3/5 0 - 1/5 6/5
1/5

(karena –Z= -18, maka Z=18)

Penyelesaian optimal: X1 = 4, X2 = 6/5 dan Zmin = 18

24
 BAB IV

A. Teori Dualitas
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang
saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua
[Link] Dual adalah kebalikan dari bentuk Primal. Hubungan Primal dan Dual
sebagai berikut:
Masalah Primal (atau Dual) Masalah Dual (atau Primal)
Koefisien fungsi tujuan ………………............ Nilai kanan fungsi
batasan Maksimumkan Z (atau Y) …………... Minimumkan Y (atau Z)
Batasan i …………………………….............. Variabel yi (atau xi)
Bentuk …………………………... yi 0
Bentuk = …………………………….............. yi dihilangkan
Variabel Xj ……………………... Batasan j
Xj 0 ……………………………….............. Bentuk
Xj 0 dihilangkan ………………….............. Bentuk =

Contoh 1: Primal Minimumkan Z = 5X1 + 2X2 + X3

Fungsi batasan: 1) 2X1 + X3 + X3 = 20

2) 6X1 + 8X + 5 X2 = 30
3) 7X1 + X2 + 3X3 = 40
X1 , X2 , X3 0
Dual
Maksimumkan Y= 20 y1 + 30 y2 + 40 y3

Fungsi batasan: 1) 2Y1 + 6Y2 + 7Y3 = 5

2) 3Y1 + 6Y2 + Y3 = 2
3) X1 + Y2 + 3X3 =1

25
Contoh 2 : Primal
Minimumkan Z = 2X1 + X2
Fungsi batasan: 1) X1 + 5X2 10
2) X1 + 3X2 6
3) 2X1 + 2X2 8
X1, X2 0
Dual
Maksimumkan Y = 10 y1 + 6y2 + 8y3
Fungsi batasan : 1) y1 + y2 + 2y3 2
2) 5y1 + 3y2 + 2y3 1
y1, y2 0

Contoh 3:
Primal
Maksimumkan Z = X1 + 3X2 – 2X3
Fungsi batasan: 1) 4X1 + 8X2 + 6X3 = 25
2) 7X1 + 5X2 + 9X3 = 30
X1, X2, X3 0
Dual
Minimumkan Y= 25y1 + 30y2
Fungsi batasan: 1) 4y1 + 7y2 1
2) 8y1 + 5y2 3
3) 6y1 + 9y2 -2

B. Analisis Sensitivitas
Analisis sensitivitas, bertujuan untuk mengurangi dan menghindari
perhitungan-perhitungan ulang, bila terjadi perubahan-perubahan satu atau
beberapa koesifien model linear programming pada saat penyelesaian optimal
telah tercapai.
Pada dasarnya perubahan-perubahan yang mungkin terjadi setelah
dicapainya penyelesaian optimal terdiri dari beberapa macam, yakni :
1. Keterbatasan kapasitas sumber
2. Koefisien-koefisien fungsi tujuan
3. Koefisien-koefisien teknis fungsi-fungsi batasan

26
4. Penambahan variabel-variabel baru
5. Penambahan batasan baru
Secara umum, perubahan-perubahan tersebut akan mengakibatkan salah satu
diantara :
1. Penyelesaian optimal tidak berubah, artinya baik variabel dasar maupun nilai-
nilainya tidak mengalami perubahan
2. Variabel-variabel dasar mengalami perubahan, tetapi nilai-nilainya tidak berubah
3. Penyelesaian optimal sama sekali berubah

27
 BAB V
METODE TRANSPORTASI

A. Pengertian Metode TRansportasi

Metode transportasi merupakan suatu metode yang digunakan untuk
mengatur distribusi dari sumber-sumber yang menyediakan produk yang sama, ke
tempat-tempat yang membutuhkan secara optimal. Metode transportasi
memecahkan masalah pendistribusian produk dari sumber ke tujuan dengan biaya
total distribusi minimum. Alokasi produk ini harus diatur sedemikian rupa karena
terdapat perbedaan biaya-biaya alokasi dari satu sumber atau beberapa sumber ke
tempat tujuan yang berbeda.
Tabel awal dapat dibuat dengan dua metode, yaitu:
1. Metode North West Corner (NWC) => dari pojok kiri atas ke pojok kanan bawah
Kelemahan : tidak memperhitungkan besarnya biaya sehingga kurang efisien.
2. Metode biaya terkecil => mencari dan memenuhi yang biayanya terkecil dulu.
Lebih efisien dibanding metode NWC.

Tabel Transportasi

B. Stepping Stone (batu loncatan)

Langkah-langkah metode Stepping Stone yaitu :
a. Isilah data kapasitas, kebutuhan dan biaya kedalam tabel transportasi.
b. Alokasikan produk dari sumber ke tujuan.
c. pedoman sudut barat laut (northwest corner rule)
d. Mengubah alokasi secara trial and error
Untuk mempermuah penjelasan metode Stepping Stone, berikut ini akan

28
dipergunakan sebuah contoh.
Contoh :

ke Gudang A Gudang B Gudang C Kapasitas

dari pabrik

Pabrik W Rp 20 Rp 5 Rp 8 90

Pabrik H Rp 15 Rp 20 Rp 10 60

Pabrik P Rp 25 Rp 10 Rp 19 50

Kebutuhan gudang 50 110 40 200

Jawaban :
1. Metode NWC

ke Gudang A Gudang B Gudang C Kapasita

dari s pabrik
Pabrik 20 5 8 90
40
W 50

Pabrik 15 20 10 60
60
H
Pabrik 25 10 19 50
10 40
P
Kebutuhan
gudang 50 110 40 200

Biaya yang dikeluarkan :

50 (20) + 40 (5) + 60 (20) + 10 (10) + 40 (19) = 3260

2. Metode biaya terkecil

ke Gudang A Gudang B Gudang C Kapasita
dari s pabrik
Pabrik 20 5 8 90
90
W
Pabrik 15 20 10 60
20 40
H
Pabrik 25 10 19 50
30 20
P
29
Kebutuhan
gudang 50 40
110 200
Biaya yang dikeluarkan :
90 (5) + 20 (15) + 40 (10) + 30 (25) + 20 (10) = 2400

Mengoptimalkan tabel:

1. Metode Stepping Stone , misal tabel awal menggunakan yang NWC

ke Gudang A Gudang B Gudang C Kapasita

dari s
Pabrik W 20 5 8 pabri
40
50 - + k
Pabrik H 20
15 10 60
60 90
+ -
Pabrik P
25 10 19 50
Kebutuhan 10 40

gudang
50 110 40 200

Perbaikan 1 dengan cara trial and error

ke Gudang A Gudang B Gudang C Kapasita s
dari pabrik
20 5 8
Pabrik 40 90
50 - + 90
W
Pabrik 15 20 10 60
60
H 50 + -
10
Pabrik 25 10 19 50
P 10 40

Kebutuha
n
50 110 40 200
gudang

Setelah dihitung dengan trial and error, biaya yang dikeluarkan:

50 (15) + 90 (5) + 10 (20) + 10 (10) + 40 (19) = 2260

30
 Perbaikan 2
ke Gudang A Gudang B Gudang C Kapasita
dari s pabrik
Pabrik 20 50 5 40 8 90
90 +
W -
Pabrik 15 20 10 60
H 50 10

Pabrik 25 10 19 50
10
P 50 + 40
-
Kebutuhan
gudang 50 40
110 200

Biaya yang dikeluarkan :

(50 . 5) + (40 . 8) + (50 . 15) + (10 . 20) + (50 . 10) = 2020

Perbaikan 3
ke Gudang A Gudang B Gudang C Kapasita
dari s pabrik
Pabrik 20 60 5 30 8 90
50 40
W + -
Pabrik 15 20 10 60
H 50 10 - + 10
Pabrik 25 10 19 50
50
P
Kebutuhan 110 200
gudang 50 40

Biaya yang dikeluarkan :

60 (5) + 30 (8) + 50 (15) + 10 (10) + 50 (10) = 1890 (paling optimal)
Jika hasil belum optimal, lakukan perbaikan terus sampai mendapatkan hasil yang
optimal.

C. Modified Distribution Method (MODI)

Langkah-langkah Metode MODI :
a. Isilah data kapasitas, kebutuhan dan biaya kedalam tabel transportasi.

31
b. Isilah tabel pertama dari sudut kiri atas ke kanan bawah.
c. Menentukan nilai baris dan kolom, Cij = Ri + Kj
d. Menghitung indeks perbaikan, IPij = Cij - Ri – Kj
e. Memilih titik tolak perubahan
f. Memperbaiki alokasi
Contoh :

baris Kolo biaya

1. W-A = R1 + K1 = 20

2. W-B = R1 + K2 =5

3. H-B = R2 + K2 = 20

4. P-B = R3 + K2 = 10

5. P-C = R3 + K3 =19

dari persamaan di atas, hitung K1 dan R1 dengan cara meng-nol-kan variabel R1

atau K1, misal R1 = 0

1. R1 + K1 = 20 => 0 + K1 = 20 , K1 =20
2. R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5
3. R2 + K2 = 20 => R2 + 5 = 20 , R2 = 15
4. R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5
5. R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14

letakkan nilai tersebut pada baris / kolom yang bersangkutan

k Gudang A K1 Gudang B Gudang C Kapasita
e dari = 20 K2 = 5 K3 = 14 s pabrik
Pabrik 5
20 40 8 90
W
50 20 10 60
R1 = 0 60
15
PabrikH 25 10 19 50
R2 = 15 10 40

PabrikP
50 110 40 200
R3 = 5 32

Kebutuhan
a. Hitung nilai/ index perbaikan setiap sel yang kosong dengan rumus:

Cij - Ri - Kj

1. H-A = 15 – 15 – 20 = - 20
2. P-A = 25 – 5 – 20 = 0
3. W-C = 8 – 0 – 14 = - 14
4. H-C = 10 – 15 – 14 = - 19
(optimal jika pada sel yang kosong, indek perbaikannya 0, jika belum maka
pilih yang negatifnya besar)
b. Memilih titik tolak perubahan
Pilih nilai yang negatifnya besar yaitu H-A
c. Buat jalur tertutup
Berilah tanda positif pada H-A. Pilih 1 sel terdekat yang isi dan sebaris (H-B), 1
sel yang isi terdekat dan sekolom (W-A), berilah tanda negatif pada dua sel
terebut. Kemudian pilih satu sel yang sebaris atau sekolom dengan dua sel
bertanda negatif tadi (W-B) dan beri tanda positif. Selanjutnya pindahkan isi
dari sel bertanda negatif ke yang bertanda positif sebanyak isi terkecil dari sel
yang bertanda positif (50). Jadi, H-A kemudian berisi 50, H-B berisi 60-50=10,
W-B berisi 40+50=90 dan W-A tidak berisi.

k Gudang A Gudang B Gudang C Kap.

e dari K1 = 20 K2 = 5 K3 = 14 pabrik
Pabrik 5
20 40 8 90
50 - + 90
W
PabrikH 15 20 10 60
R1 = 0 60
R2 = 15 50 + - 10
PabrikP 25 10 19 50
R3 = 5 10 40

[Link] 50 110 40 200

d. Ulangi langkah-langkah c – f sampai indeks perbaikan bernilai 0 hitung sel

yang berisi:

33
 W-B = R1 + K2 = 5 => 0 + K2 =5, K2 = 5

H-A = R2 + K1 = 15 => R2 + 0 = 15, R2 = 15

H-B = R2 + K2 = 20 => 15 + 5 = 20 ,

P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5

P-C = R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14

Perbaikan indeks:
W-A = 20 – 0 – 0 = 20
W-C = 8 – 0 – 14 = - 6
H-C = 10 – 15 – 14 = - 19
P-A = 25 – 5 – 0 = 20

ke Gudang A K1 Gudang B K2 Gudang C K3 Kapasita

dari =0 =5 = 14 s pabrik
PabrikW 20 5 8 90
90
R1 = 0
PabrikH 15 20 10 60
50 10
R2 = 15 - + 10
PabrikP 25 10 19 50
20 + - 40 30
R3 = 5
Keb. Gdg 50 110 40 200

Biaya transportasi : 90 (5) + 50 (15) + 10 (10) + 20 (10) + 30 (19) = 2070

Hitung sel yang berisi:

W-B = R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5

P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5

P-C = R3 + K3 = 19 => 5 + K3 = 19 , K3 = 14

H-C = R2 + K3 = 10 => R2 + 14 = 10 , R2 = - 4

H-A = R2 + K1 = 15 => - 4 + K1 = 15 , K1 = 19

Perbaikan indeks (sel kosong) :

W-A = 20 – 0 – 0 = 20
W-C = 8 – 0 – 14 = - 6

34
 H-B = 20 – 15 – 5 = 0
P-A = 25 – 5 – 0 = 20

ke Gudang A K1 Gudang B K2 Gudang C K3 Kapasita

dari = 19 =5 = 14 s pabrik

PabrikW 20 80 5 8 90
R1 = 0 90 + 10

PabrikH 15 - 20 10 60
50 10
R2 = - 4

PabrikP 25 10 19 50
R3 = 5 20 + 30 - 30 20
Keb. Gdg 50 110 40 200

Biaya transportasi :
80 (5) + 10 (8) + 50 (15) + 10 (10) + 30 (10) + 20 (19) = 2010

Sel berisi:
W-B = R1 + K2 = 5 => 0 + K2 = 5 , K2 = 5
W-C = R1 + K3 = 8 => 0 + K3 = 8 , K3 = 8
H-C = R2 + K3 = 10 => R2 + 8 = 10 , R2 = 2
H-A = R2 + K1 = 15 => 2 + K1 = 15 , K1 = 13
P-B = R3 + K2 = 10 => R3 + 5 = 10 , R3 = 5
Indeks perbaikan:
W-A = 20 – 0 – 19 = 1
H-B = 20 – (-4) – 5 = 19
P-A = 25 – 5 – 19 = 1
Indeks perbaikan sudah positif semua, berarti sudah optimal.

k Gudang A Gudang B Gudang C Kapasita

e dari K1 = 13 K2 = 5 K3 = 8 s pabrik
Pabrik 5 8 90
20 80 10
W
15 20 10 60
R1 = 0 10
50
PabrikH 25 10 19 50
30
R2 = 2 20

50 110 40 200
PabrikP
R3 = 5

Keb. Gdg
35
D. Vogel’s Approximation Method (VAM).
Langkah-langkah Metode Vogel’s yaitu :
a. Susunlah kebutuhan, kapasitas dan biaya pengangkutan ke dalam tabel
transportasi.
b. Carilah perbedaan dari dua biaya terkecil.
c. Pilihlah satu nilai perbedaan yang terbesar diantara semua nilai perbedaan pada
kolom dan baris.
d. Isilah pada salah satu segi empat yang termasuk dalam kolom atau baris terpilih
(biaya terendah).
e. Hapus baris atau kolom yang telah terisi.
f. Ulangi lagi mulai langkah ke-b

A B C Kapasita Perbedaan baris

s
W 20 5 8 90 8–5=3
H 15 20 10 60 15 – 10 = 5
P 25 10 19 50 19 – 10 = 9
kebutuhan 50 110 40
Perbedaan 20 – 10-5 10-8 XPB = 50
15
kolom =5 =2 Hilangkan baris P
=5

A C Kapasitas Perbedaan baris

W 20 8 90-60 =30 20 – 8 = 12
H 15 10 60 15 – 10 = 5
Kebutuhan 50 40
Perbedaan 20-15= 10-8=2 XWC=30
5
kolom Hilangkan baris W

36
 A C kapasitas
H 15 10 60
Kebutuhan 50 (40- XHA=50
30)=10
XHC= 10

Biaya transportasi :
10 (50) + 5 (60) + 8 (30) + 15 (50) + 10 (10) = 1890 (optimal)

37
 BAB VI
MASALAH PENUGASAN

A. Pengertian Masalah Penugasan

Masalah penugasan merupakan suatu kasus khusus dari masalah linear
programming pada umumnya. Metode Hungarian adalah salah satu dari teknik
pemecahan untuk masalah penugasan. Pada Metode Hungarian, jumlah sumber-
sumber yang ditugaskan harus sama persis dengan jumlah tugas yang akan
diselesaikan. Setiap sumber harus ditugaskan hanya untuk satu tugas. Jadi, masalah
penugasan akan mencakup sejumlah n sumber yang mempunyai n tugas, sehingga
ada n! (n faktorial) kemungkinan. Masalah ini dapat dijelaskan dengan mudah
dalam bentuk matriks segi empat, dimana baris-barisnya menunjukkan sumber-
sumber dan kolom- kolomnya menunjukkan tugas-tugas.

B. Masalah Minimisasi

Contoh:

Sebuah perusahaan kecil mempunyai 4 pekerjaan yang berbeda untuk

diselesaikan oleh 4 karyawan. Biaya penugasan seorang karyawan untuk pekerjaan
yang berbeda adalah berbeda karena sifat pekerjaan berbeda-beda. Setiap
karyawan mempunyai tingkat ketrampilan, pengalaman kerja dan latar belakang
pendidikan serta latihan yang berbeda pula. Sehingga biaya penyelesaian pekerjaan
yang sama oleh para karyawan yang berlainan juga berbeda. Tabel biaya sebagai
berikut:
pekerjaan I II III IV

karyawan

Raihan Rp 150 Rp 200 Rp 180 Rp 220

Hamdan Rp 140 Rp 160 Rp 210 Rp 170

Hasan Rp 250 Rp 200 Rp 230 Rp 200

Dzakwan Rp 170 Rp 180 Rp 180 Rp 160

Masalahnya adalah bagaimana menugaskan keempat karyawan untuk

38
menyelesaikan keempat pekerjaan agar total biaya pekerjaan minimum.
Langkah-langkah:
1. Menyusun tabel biaya seperti tabel di atas.
2. Melakukan pengurangan baris, dengan cara:
a. memilih biaya terkecil setiap baris
b. kurangkan semua biaya dengan biaya terkecil setiap baris
Sehingga menghasilkan reduced cost matrix /matrik biaya yang telah dikurangi.

pekerjaan I II III IV

karyawan

Raihan (150-150) =0 (200-150) =50 (180-150) = 30 (220-150) = 70

Hamdan (140-140) = 0 (160-140) = 20 (210-140) =70 (170-140) = 30

Hasan (250-200) = 50 (200-200) = 0 (230-200) = 30 (200-200) = 0

Dzakwan (170-160) = 10 (180-160) = 20 (180-160) = 20 (160-160) = 0

3. Melakukan pengurangan kolom

Berdasarkan hasil tabel langkah 2, pilih biaya terkecil setiap kolom untuk
mengurangi seluruh biaya dalam kolom-kolom tersebut. Pada contoh di atas hanya
dilakukan pada kolom III karena semua kolom lainnya telah mempunyai elemen
yang bernilai nol (0). Jika langkah kedua telah menghasilkan paling sedikit satu
nilai nol pada setiap kolom, maka langkah ketiga dapat dihilangkan. Berikut matrix
total opportunity cost, dimana setiap baris dan kolom terdapat paling sedikit satu
nilai nol.
Tabel total opportunity cost matrix

pekerjaan I II III IV

karyawan

Raihan 0 50 (30-20)=10 70

Hamdan 0 20 (70-20)=50 30

Hasan 50 0 (30-20)=10 0

Dzakwan 10 20 (20-20)=0 0

39
4. Membentuk penugasan optimum
Prosedur praktis untuk melakukan test optimalisasi adalah dengan menarik
sejumlah minimum garis horisontal dan/ atau vertikal untuk meliputi seluruh
elemen bernilai nol dalam total opportunity cost matrix. Jika jumlah garis sama
dengan jumlah baris/ kolom maka penugasan telah optimal. Jika tidak maka harus
direvisi.

pekerjaan I II III IV

karyawan

Raihan 0 50 10 70

Hamdan 0 20 50 30

Hasan 50 0 10 0

Dzakwan 10 20 0 0

5. Melakukan revisi tabel

a. Untuk merevisi total opportunity cost, pilih angka terkecil yang tidak terliput
(dilewati) garis. (pada contoh di atas = 10)
b. Kurangkan angka yang tidak dilewati garis dengan angka terkecil (10)
c. Tambahkan angka yang terdapat pada persilangan garis dengan angka
terkecil (10) yaitu (50) pada Hasan dan (10) pada Dzakwan.
d. Kembali ke langkah 4 Revised matrix:

Berikut tabel penugasannya

Penugasan Biaya

Raihan - III Rp 180

Hamdan - I Rp 140

Hasan - II Rp 200

Dzakwan - IV Rp 160

Rp 680

40
C. Jumlah Pekerjaan Tidak Sama Dengan Jumlah Karyawan
Bila jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus
ditambahkan karyawan semu (dummy worker). Biaya semu sama dengan nol
karena tidak akan terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu.
Bila jumlah karyawan lebih banyak daripada pekerjaan, maka ditambahkan
pekerjaan semu (dummy job). Sebagai contoh, bila jumlah pekerjaan lebih
besar dari jumlah karyawan dapat dilihat pada tabel berikut:
pekerjaan I II III IV

karyawan

Raihan Rp 150 Rp 200 Rp 180 Rp 220

Hamdan Rp 140 Rp 160 Rp 210 Rp 170

Hasan Rp 250 Rp 200 Rp 230 Rp 200

Dzakwan Rp 170 Rp 180 Rp 180 Rp 160

Dummy X Rp 0 Rp 0 Rp 0 Rp 0

Prosedur penyelesaian sama dengan langkah-langkah sebelumnya.

C. Masalah Maksimisasi
Dalam masalah maksimisasi, elemen-elemen matriks menunjukkan tingkat
keuntungan. Efektivitas pelaksanaan tugas oleh karyawan diukur dengan jumlah
kontribusi keuntungan.
Contoh: Tabel keuntungan

Pekerjaan I II III IV V

Karyawan

Afif Rp 1000 Rp 1200 Rp 1000 Rp 800 Rp 1500

Bady Rp 1400 Rp 1000 Rp 900 Rp 1500 Rp 1300

Dzaky Rp 900 Rp 800 Rp 700 Rp 800 Rp 1200

Farras Rp 1300 Rp 1500 Rp 800 Rp 1600 Rp 1100

Ghazy Rp 1000 Rp 1300 Rp 1400 Rp 1100 Rp 1700

41
Langkah-langkah:

1. Seluruh elemen dalam setiap baris dikurangi dengan nilai maksimum dalam
baris yang sama. Prosedur ini menghasilkan Matriks Opportunity Loss. Matriks
ini sebenarnya bernilai negatif.

Pekerjaan I II III IV V

karyawan

Afif 500 300 500 700 0

Bady 100 500 600 0 200

Dzaky 300 400 500 400 0

Farras 300 100 800 0 500

Ghazy 700 400 300 600 0

2. Meminimumkan opportunity-loss dengan cara mengurangi seluruh elemen

dalam setiap kolom (yang belum ada nol-nya) dengan elemen terkecil dari
kolom tersebut.

Pekerjaan I II III IV V
karyawan

AfAlif 400 200 200 700 0

BaBady 0 400 300 0 200

Dzaky 200 300 200 400 0

Farras 200 0 500 0 500

Ghazy 600 300 0 600 0

Matriks total opportunity loss

Dari matriks di atas dapat dilihat bahwa seluruh elemen yang bernilai nol baru
dapat diliput oleh 4 garis. Jadi matriks harus direvisi.

42
 a. Merevisi matriks

Pekerjaan I II III IV V
karyawan
Afif 200 0 0 500 0
Bady 0 400 300 0 400

Dzaky
0 100 0 200 0
Farras 200 0 500 0 700

600 300 0 600 20

Ghazy 0

Schedul penugasan optimal dan keuntungan total untuk dua alternatif

penyelesaian adalah:
Penugasan alternatif 1 keuntungan Penugasan alternatif 2 keuntungan
Afif - II Rp 1200 Afif -V Rp 1500
Bady -I Rp 1400 Bady - IV Rp 1500
Dzaky -V Rp 1200 Dzaky -I Rp 900
Farras - IV Rp 1600 Farras - II Rp 1500
Ghazy - III Rp 1400 Ghazy - III Rp 1400

Rp 6800 Rp 6800

D. Masalah-Masalah Penugasan Tambahan

Dalam masalah-masalah penugasan di muka, seluruh elemen matriks
diketahui konstan. Bagaimana pun juga, kadang-kadang beberapa elemen matriks
tidak diketahui. Dalam masalah penugasan personalia, contoh, seorang karyawan
tertentu tidak dapat ditugaskan untuk melaksanakan pekerjaan tertentu karena
tidak memenuhi persyataran keterampilan yang diperlukan. Penugasan untuk
keadaan tersebut tidak mungkin dilakukan.

Untuk pemecahan masalah tidak mungkin dilakukan, kita hanya menandai

setiap elemen penugasan yang tidak mungkin dengan suatu nilai sangat besar yang
tidak diketahui. Langkah pemecahan selanjutnya, sama persis dengan prosedur
Hungarian.

43
 BAB VII
ANALISIS NETWORK

A. Pengertian Network

Jaringan (Network) merupakan sebuah istilah untuk menandai model-model

yang secara visual bisa diidentifikasi sebagai sebuah sistem jaringan yang terdiri
dari rangkaian-rangkaian noda (node) dan kegiatan (activity).

B. Analisis Jalur Kritis

Analisis yang berguna untuk pengendalian kegiatan produksi, karena dengan
melakukan kegiatan ini maka perusahaan dapat :
1. Mengetahui logika ketergantungan dalam proses produksi
2. Mengetahui kegiatan mana yang penting (kegiatan kritis) yang tidak boleh
terlambat pengerjaannya.
3. Mengetahui waktu kritis, waktu terpanjang penyelesaian proses produksi.

Ciri-ciri Jalur Kritis

1. Memakan waktu terpanjang dalam proses produksi

2. Tidak ada tenggang waktu antara selesainya tahap sebelumnya dengan waktu
dimulainya kegiatan.
Cara melakukan analisis jalur kritis
1. Mengidentifikasi kegiatan” dalam proses produksi
2. Mengidentifikasi logika ketergantungan dan waktunya
3. Buat diagram network, dengan menggunakan simbol”

44
 Keterangan simbol
, arah kegiatan
, kegiatan semu

Keterangan :
EN = nomor kejadian
EFT = waktu penyelesaian
EN
tercepat
LST = waktu paling lambat
dimulai

C. Kegiatan Semu (Dummy)

Kegiatan yang waktunya relatif sangat singkat, tetapi sangat menentukan
apakah kegiatan selanjutnya bisa dilaksanakan atau tidak.
Sifat kegiatan semu (Dummy)
1. Waktu yang dibutuhkan sangat singkat , dianggap nol
2. Menentukan boleh tidaknya kegiatan selanjutnya dilakukan
3. Dapat mengubah jalur kritis dan waktu kritis

Contoh :
Nomor Kegiatan Kegiatan Waktu
sebelum
1 A - -
2 B A 1
3 C B 2
4 D C 1
5 E D 1
6 F B 4
7 G F 3
8 H G 2
9 I E 1
H 1
10 J I 1

45
 DAFTAR PUSTAKA

Affandi Pardi, 2019. Buku Ajar Riset Operasi. CV IRDH, Malang.

Aminudin, 2005. Prinsip-Prinsip Riset Operasi, Erlangga
Hamdy Taha, Operation Research An Introduction, Edisi 4, Macmillan, New York
Richard Bronson, Theory and Problem of Operation Research , McGraw-Hill,
Singapore.
Subagyo Pangestu, Marwan Asri, dan T. Hani Handoko. 2000. Dasar-Dasar
Operation Research, Yogyakarta: PT. BPFE-Yogyakarta
Yulian Zamit, Manajemen Kuantitatif, BPFE, Yogyakarta

46