KATA PENGANTAR

Assalamualaikum Warahmatullahi Wabarakatuh

Segala puji dan syukur kami panjatkan kepada Allah SWT. atas rahmat dan karunia-
Nya, kami dapat menyelesaikan tugas dalam bentuk penulisan modul ini dengan tepat
waktu. Tidak lupa shalawat serta salam tercurah kepada junjungan kita Nabi Muhammad
SAW yang syafa’at nya kita nantikan di akhirat kelak.
Penyusun mengucapkan terimakasih kepada Ibu Wardhani Utami Dewi, [Link]. selaku
dosen pengampu mata kuliah Progrram Linear yang telah membimbing kami. Modul ini
berjudul “Sejarah Singkat Program Linear dan Pemodelan Formulasi Matematika”,
penyusun harap dapat membuka dan menambah wawasan pembaca sehingga dapat
bermanfaat untuk kehidupan sehari-hari serta sebagai media belajar.
Modul ini masih memerlukan penyempurnaan, terutama pada bagian isi. Penyusun
menerima segala bentuk kritik dan saran pemmbaca demi penyempurnaan modul.
Apabila terdapat banyak kesalaham pada modul ini, kami memohon maaf. Demikian yang
dapat penyusun sampaikan.
Wassalamualaikum Warahmatullahi Wabarakatuh

Metro, 18 Maret 2025

Penyusun

ii
 DAFTAR ISI

KATA PENGANTAR...........................................................................ii
DAFTAR ISI.....................................................................................iii
DAFTAR TABEL................................................................................iv
BAB I SEJARAH PROGRAM LINEAR.....................................................1
1.1 Pengertian Program Linear....................................................................1
1.2 Latihan Soal 1........................................................................................ 3
BAB II BENTUK UMUM PROGRAM LINEAR...........................................4
2.1 Bentuk Umum Program Linear...............................................................4
2.2 Formulasi Pemodelan Matematika.........................................................6
2.3 Latihan Soal 2........................................................................................ 9
BAB III METODE GRAFIK.................................................................10
3.1 Prinsip Dasar Metode Grafik.................................................................10
3.2 Solusi Model Program Linear Metode Grafik........................................10
3.3 Latihan Soal 3...................................................................................... 13

iii
DAFTAR TABEL

iv
 BAB I

SEJARAH PROGRAM LINEAR

Tujuan Pembelajaran:

Pada Bab ini diharapkan mahasiswa dapat:

1. Memahami Pengertian program linear

2. Menjelaskan Sejarah Perkembangan Program Linear

3. Menyebutkan Tokoh-Tokoh Penting dalam Sejarah Program Linear

1.1 Pengertian Program Linear

Beberapa matematikawan menemukan dan mengembangkan Program Iinear sebelum
Perang Dunia Kedua. Rata-rata penemuan dan pengembangan mereka didasarkan pada
masalah atau persoalan yang sedang berkembang, seperti industri dan peperangan.
Matematikawan terkenal seperti Naranda Karmarkar, Leonid V Kartovich, George B.
Dantzig, John von Neumann, dan Leonid Khachiyan. Ini adalah sejarah penemuan
program lincar oleh beberapa matematikawan di atas

A. Leonid Vitalevich Kartovich

Di Leningrad, Rusia, Leonid V. Kartovich lahir pada Januari 1912. Leonid tumbuh
dengan rasa ingin tahu yang besar; dia tertarik dengan politik dan sejarah kontemporer. Ia
masuk ke Departemen Matematika Universitas Leningrad pada usia 14 tahun dan mulai
menyadari bahwa ia tertarik pada matematika dan ilmu pengetahuan. Pada tahun
keduanya di universitas, Leonid sudah unggul dari teman-temannya dalam matematika,
bahkan menguasai matematika kompleks dan abstrak. Ia sudah menjadi penulis
matematika di usia 18 tahun.
Setelah lulus, Leonid terus belajar matematika teoritis. Namun, seiring waktu, dia mulai
berkonsentrasi pada matematika terapan dan akhirnya memberi kontribusi terbesarnya
pada matematika ekonomi. Di bawah pemerintahan Joseph Stalin, Uni Soviet mengalami
masa industrialisasi, mengubah ekonominya dari pertanian ke industri. Keadaan ini
membuat Leonid menemukan masalah dengan pekerjaannya sebagai konsultan
laboratorium pemerintah. Permasalahan ini terkait dengan proses produksi; ia harus
menyelesaikan masalah menghemat uang dan menghemat bahan baku sambil
menghasilkan output yang maksimal. Pada awalnya, masalah ini dianggap sederhana
sebagai kasus kalkulus diferensial. Namun, ternyata lebih kompleks daripada yang
terlihat. Ini memulai keinginan Leonid untuk menggunakan matematika dalam ekonomi.
Akhirnya, pada tahun 1939, Leonid menyampaikan kesimpulan pemikirannya tentang

1
masalah yang ada dan cara menyelesaikannya. Ternyata ide-idenya menghasilkan apa
yang sekarang dikenal sebagai Program Linear. Pemikirannya tersebut pada awalnya
diragukan oleh banyak orang. tetapi dengan cepat terbukti ketika ia menghitung jumlah
maksimum suatu pabrik harus memakai baja agar biaya produksi tetap efisien, dan
ternyata pemikirannya tersebut terbukti biaya produksi dapat diefisienkan secara
signifikan. Penemuan Leonid membuka era baru dalam perekonomian Uni Soviet. Ini
membuat Uni Soviet sangat tertarik pada matematika terapan, dan sejak itu Leonid
menjadi revolusioner dalam ekonomi matematika.

B. George Bernard Dantzig

George Bernard Dantzig lahir pada tanggal November 1914 di Portland, Oregon,
Amerika Serikat. Ayah Dantzig adalah seorang profesor matematika dan ibunya adalah
seorang ahli bahasa Slavia. Pada tahun 1936, dia mendapatkan gelar sarjana dari
University of Maryland, tetapi dia tidak menyukai semua mata kuliah matematik yang dia
ambil karena dia tidak menemukan manfaat dari apa yang dia pelajari.
Tahun berikutnya, ia memasuki program pascasarjana di Sekolah Matematik
Universitas Michigan. Selain mata kuliah statistika, ia merasa semua mata kuliah
matematika terlalu abstrak, jadi ia meninggalkan sekolah dan mencari pekerjaan. Dia
kemudian bekerja di Biro Statistik Tenaga Kerja dan dua tahun kemudian pergi ke Berkley
untuk mendapatkan gelar doktor dalam statistika. Dia bergabung dengan Angkatan Udara
Amerika sebagai penasehat matematik untuk pusat kontrol Angkatan Udara setelah
mendapatkan gelar doktor pada tahun 1947.
Angkatan Udara membutuhkan metode cepat untuk menghitung waktu latihan,
distibusi logistik, dan durasi program. Dantzig mengatakan bahwa "I began noticing that
the feasible regionis a convex body, that is, a polyhedral set. Therefore, movement along
the borders from one extreme point to the next would improve the process”. Namun,
tampak bahwa prosedur ini tidak efisien. “The area could be represented in three
dimensions as a diamond with faces, edges, and vertex. In the cases of many borders,
the process would take a journey along them before the optimal point corner of the
diamond would be reached”. Dari penjelasan di atas diperoleh kesimpulan bahwa ketika
sebuah masalah dibuat dalam bentuk tiga dimensi, seperti berlian, dengan tampak depan,
garis pinggir, dan puncak, mereka akan saling bertemu di tempat yang ideal. Ini adalah
awal pembuatan program linear menggunakan metode simpleks oleh Dantzig.
C. John Von Neumann
Pada tahun-tahun berikutnya, Leonid Khachiyan dan Naranda Karmarkar membuat
program linear untuk menyelesaikan masalah yang lebih kompleks, tetapi metode grafik
belum ditemukan

2
1.2 Latihan Soal 1

3
 BAB II

BENTUK UMUM PROGRAM LINEAR

Tujuan Pembelajaran:
Pada Bab ini diharapkan mahasiswa dapat:
1. Memahami Bentuk Umum Program Linear
2. Menjelaskan Bentuk Umum program Linear
3. Mengidentifikasi Fungsi Objektif dalam Program Linear

2.1 Bentuk Umum Program Linear

Secara umum, bentuk matematis dari program linear dapat dituliskan sebagai berikut :
Fungsi tujuan (objective function):
Maksimum/minimum: Z=c 1 x 1 +c 2 x 2 +…+ cn x n
Fungsi kendala (constraint function): a 11 x 1 +a 12 x 2+ …+a1 n x n ≤ atau ≥ b 1
a 21 x 1+ a22 x 2 +…+a 2 n x n ≤atau ≥ b2
⁞⁞⁞⁞⁞⁞
a m x 1 +a m 2 x 2+ …+a mn x n ≤ atau ≥ bm
x 1 ≥ 0 , x 2 ≥ 0 , … xn ≥ 0
Keterangan :
Z = fungsi tujuan
xn = variabel keputusan pada variabel ke-n
a mn = koefisien sisi kiri pada kendala ke-m dan variabel ke-n
bm = koefisien sisi kanan pada kendala ke-m
cn = koefisien fungsi tujuan pada variabel ke-n
m,n = batasan variabel

a. Metode Simpleks dalam Program Linear

Metode simpleks merupakan teknik untuk menyelesaikan program linear sebagai
teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan
pengalokasikan sumber daya secara optimal.
Beberapa ketentuan dalam penyelesaian metode simpleks yaitu:
1. Nilai ruas kanan fungsi tujuan harus nol
2. Nilai ruas kanan fungsi kendala harus positif
3. Fungsi kendala harus berupa persamaan, jika dalam bentuk pertidaksamaan harus
diubah dengan menambahkan variabel slack/surplus disebut juga variabel dasar.

4
Ketentuan penggunaan tabel simpleks yaitu :
1. Fungsi kendala harus berupa persamaan
2. Proses pengulangan dihentikan apabila koefisien – koefisien dari fungsi tujuan sudah
tidak ada yang berniali negatif.
Variabel Z X1 ... Xn Slack Variabel NK
Dasar X n+1 ... X n+n
Z 1 −C 1 ... −C n 0 ... 0 0

X n+1 0 a 11 ... a 1n 1 ... 0 B1

⁞ ⁞ ⁞ ⁞ ⁞
X n+n 0 am1 ... a mn 0 ... 1 Bm
Tabel 1.1 Tabel Simpleks

Dimana :
m = banyaknya fungsi kendala
n = banyaknya variabel output
B1 = batasan sumber 1
Bm = batasan sumber ke-m
NK = nilai ruas kanan
Tahapan penyelesaian dengan metode simpleks adalah:
1. Menentukan fungsi tujuan dan fungsi kendala
2. Mengubah fungsi tujuan dan fungsi kendala kebentuk standar tabel awa simpleks

Dalam program linear, langkah yang paling penting adalah memformulasikan model
program linear dengan mengidentifikasi apa yang berkaitan dengan tujuan dan batasan
yang membatasi tujuan tersebut. Model program linear ditampilkan dalam bentuk fungsi
tujuan dan fungsi kendala, dan komponen penyusun program linear adalah variabel
keputusan, fungsi tujuan, fungsi kendala/pembatas, dan batasan variabel.
Variabel keputusan adalah variabel yang memiliki kemampuan untuk menentukan
pilihan apa yang harus dilakukan untuk mencapai solusi optimal. Kesalahan dalam
menentukan variabel keputusan akan menyebabkan hasil solusi yang tidak optimal, jadi
Anda harus tahu karakteristik masalah ril yang akan disusun program linearnya.
Fungsi tujuan adalah fungsi linear yang menggambarkan tujuan atau sasaran dengan
variabel tujuan, seperti pendapatan, keuntungan, atau biaya. Fungsi tujuan juga
menentukan tujuan dari masalah, apakah akan memaksimalkan atau meminimalkan
fungsi variabel. Batasan variabel menunjukkan wilayah variabel dengan syarat tidak
bernilai negatif. Di sisi lain, fungsi kendala atau batasan merupakan rumusan terhadap

5
hambatan yang dihadapi dalam mencapai suatu tujuan, biasanya terkait dengan
keterbatasan sumber daya yang dimiliki untuk mencapai tujuan tersebut.

2.2 Formulasi Pemodelan Matematika

Dalam program linear, langkah yang paling penting adalah memformulasikan model
program linear dengan mengidentifikasi apa yang berkaitan dengan tujuan dan batasan
yang membatasi tujuan tersebut. Model program linear ditampilkan dalam bentuk fungsi
tujuan dan fungsi kendala, dan komponen penyusun program linear adalah variabel
keputusan, fungsi tujuan, fungsi kendala/pembatas, dan batasan variabel.
Variabel keputusan adalah variabel yang memiliki kemampuan untuk menentukan
pilihan apa yang harus dilakukan untuk mencapai solusi optimal. Kesalahan dalam
menentukan variabel keputusan akan menyebabkan hasil solusi yang tidak optimal, jadi
Anda harus tahu karakteristik masalah ril yang akan disusun program linearnya.
Fungsi tujuan adalah fungsi linear yang menggambarkan tujuan atau sasaran dengan
variabel tujuan, seperti pendapatan, keuntungan, atau biaya. Fungsi tujuan juga
menentukan tujuan dari masalah, apakah akan memaksimalkan atau meminimalkan
fungsi variabel. Batasan variabel menunjukkan wilayah variabel dengan syarat tidak
bernilai negatif. Di sisi lain, fungsi kendala atau batasan merupakan rumusan terhadap
hambatan yang dihadapi dalam mencapai suatu tujuan, biasanya terkait dengan
keterbatasan sumber daya yang dimiliki untuk mencapai tujuan tersebut.

Contoh Soal:
2.1 Sebuah toko roti memproduksi dua jenis kue, yaitu brownies dan cheesecake. Untuk
membuat kedua jenis kue ini, toko membutuhkan bahan utama tepung terigu dan
gula. Jenis kue brownies membutuhkan tepung terigu 200 gram dan gula 100 gram
dengan keuntungan per kue yaitu Rp 25.000 dan untuk jenis kue cheesecake
membutuhkan tepung terigu sebanyak 150 gram dan gula 200 gram dengan
keuntungan per kue adalah Rp 30.000. Toko hanya memiliki 10.000 gram tepung
terigu dan 8.000 gram gula setiap harinya. Tentukan jumlah brownies dan
cheesecake yang harus diproduksi agar keuntungan maksimal.
Penyelesaian:
Variabel keputusan:
x 1 :jumlah brownies yang diproduksi
x ❑2 : jumlah cheesecake yang diproduksi
Fungsi objektif:
Max Z = 25000 x 1+30000 x 2

6
Kendala:
Kebutuhan Tepung terigu Gula Keuntungan per kue
Jenis kue (gram) (gram) (Rp)
Brownies 200 100 25.000
Cheesecake 150 200 30.000
Jumlah yang 10.000 8.000
tersedia
Tabel 1.2 kendala soal 1

a. Kendala tepung terigu: 2 x1 +150 x 2 ≤ 10.000

b. Kendala gula: 100 x 1+200 x 2 ≤8.000
c. Peubah non-negatif:
Menyusun sIstem persamaan:
200 x 1+150 x 2=10.000
100 x 1+200 x 2=8.000 x 2
200 x 1+150 x 2=10.000
200 x 1+ 400 x 2=16.000
Eliminasi:
( 200 x 1+ 400 x 2 )−( 200 x 1 +150 x2 ) =16.000−10.000
250 x 2=6.000
x 2=24 (cheesecake)
Subtitusi:
200 x 1+150 (24)=10.000
200 x 1+3.600=10.000
200 x 1=6.400
x 1=32 (brownies)
Keuntungan maksimum:
Max Z ¿ 25000 x 1+30000 x 2
Keuntungan dari brownies:
25.000 x 32 = 8.00.000
Keuntungan cheesecake:

7
 30.000 x 24 = 720.000
Jumlah hasil tersebut: 800.000 + 720.000 = 1.520.000
Jadi, keuntungan maksimum yang diperoleh adalah 1.520.000 dengan memproduksi
32 brownies dan 24 cheesecake.

2.2 Seorang penjahit mempunyai persediaan 4 m kain wol dan 5 m kain satin. Dari kain
tersebut akan dibuat 2 model baju. Baju pesta memerlukan 2 m kain wol dan 1 kain
satin, sedangkan dress memerlukan 1 m kain wol dan 2 m kain satin. Baju pesta I
dijual dengan harga Rp. 600.000,00 dan dress dijual dengan harga Rp 500.000,00.
Jika baju pesta tersebut terjual, hasil penjualan maksimum penjahit tersebut adalah…
Penyelesaian :
Variabel keputusan :
x 1=¿banyaknya baju pesta yang di produksi
x 2=¿banyaknya dress yang diproduksi
Fungsi objekstif :
Maks z=Rp. 600.0000 x 1+ Rp .500 .000 x 2
Kendala:
Kain wol Kain satin Harga
Jenis produk
(m) (m) (Rp)
Baju pesta 2 1 Rp. 600.000
Dress 1 2 Rp. 500.000
Jumlah yang tersedia 4 5
Tabel 1.3 kendala soal 2

Model matematika:
2 x1 + x 2 ≤ 4
x 1+ 2 x 2 ≤5
x1 ≥ 0 , x2 ≥ 0
Hasil penjualan maksimum:
Maks z=Rp. 600.0000 x 1+ Rp .500 .000 x 2

Hasil penjualan baju pesta : Rp .600.000 × 2+ Rp .500 .000 ×0=Rp .1.200 .000
Hasil penjualan dress : Rp .600.000 × 0+ Rp .500.000 × 2, 5=Rp . 1.250 .000
Jumlah hasil dari penjualan baju pesta dan dress adalah Rp .2.450 .000
Jadi, hasil penjualan maksimum sebesar Rp .2.450 .000

8
9
2.3 Latihan Soal 2

10
 BAB III

METODE GRAFIK

Tujuan Pembelajaran:
Pada Bab ini diharapkan mahasiswa dapat:
3.1 Menjelaskan prinsip dasar metode grafiik
3.2 Jenis-jenis solusi dari suatu program linear
a. Solusi optimal unik
b. Solusi optimal banyak
c. Solusi optimal unbounded
d. Solusi tidak layak

3.1 Prinsip Dasar Metode Grafik

Jika semua bentuk kendala dituliskan dalam:
gi ( x ) ≤ 0 , i=1 ,2 , … , m
Maka,
a. Titik solusi fisibel adalah tiitik yang memenuhi gi (x )≤ 0 , ∀ i
b. Daerah solusi fisibel (s) adalah himpunan atau kumpulan titik solusi fisibel yang
merupakan daerah yang dibatasi oleh pertidaksamaan kendala
c. Calon titik solusi optimal adalah titik-titik perpotongan persamaan kendalanya dalam
S.
Jika fungsi tujuan/fungsi objektif model program linear:
f ( x )=c 1 x 1+ c 2 x 2+ …+c n x n
¿
Maka f (x ) disebut titik solusi optimal jika
f ( x ¿ ) ≤ f ( x ) , ∀ x ∈ S → minimisasi
f ( x ¿ ) ≥ f ( x ) , ∀ x ∈ S → maksimisasi

3.2 Solusi Model Program Linear Metode Grafik

Berikut merupakan langkah-langkah solusi Metode Grafik:
a. Menyelesaikan masalah program linear
Pogram linear adalah suatu metode yang digunakan utntuk memecahkan masalah yang
berkaitan dengan optimal (nilai maksimum dan nili minimum). Program linear tidak lepas
dengan sistem pertidaksmaan linear. Khususnya padat tingkat sekolah menengah, sistem
pertidaksamaan linear yang dimaksud adalah sistem prtidaksamaan linear dua variabel.

11
b. Daerah himpunan penyelesaian
Penyelesaian program linear sangat teerkait dengan kemampuan melakukan sketsa
daerah himpunan penyelesaian sistem.
Berikut ini adalah teknik menemukan daerah himpunan penyelesaian:
1. Buat sumbu koordinat kartesius
2. Tentukan titik potong pada sumbu x dan y dari semua persamaan-persamaan
linernya.
3. Sketsa grafiknya dengan menghubungkan antara titik-titik potonganya.
4. Pilih salah satu titik uji yang berada di luar garis.
5. Substitusikan pada persamaan
6. Tentukan daerah yang dimaksud.

12
Contoh Soal:

13
3.3 Latihan Soal 3

14
15
 BAB V
TEORI DUALITAS
Tujuan Pembelajaran :

Pada bab ini diharapkan mahasiswa dapat :

5.1 Menjelaskan teori dualitas

5.2 Mengubah bentuk primal ke bentuk dual ataupun sebaliknya

5.1 Teori Dualitas

Teori dualitas adalah salah satu konsep program linier yang paling penting dan menarik,
secara teori dan praktis.
Ide utama di balik teori ini adalah bahwa setiap persoalan program linier memiliki suatu
program linier yang saling berkaitan yang disebut "dual", dan solusi untuk persoalan
semula atau asal juga memberi solusi untuk dualnya. Variabel-variabel dari masalah dual
dapat di interpretasikan sebagai harga-harga yang berhubungan dengan kendala-kendala
pada masalah primal.

Berikut bentuk umum masalah primal dual :

Primal : Dual :

Maksimum : z = c x + c x + .... +c x Minimum : w = b y + b y + .... +

1 1 2 2 n n b y 1 1 2 2
Kendala: m m
Kendala:
a x + a x + ... a x ≤ b
11 1 12 2 1n n 1
a y + a y + ... + a y ≥ c
a x + a x + ... a x ≤ b 11 1 21 2 m1 m 1
21 1 22 2 2n n 2
..... a y + a y + ... + a y ≥ c
12 1 22 2 m2 m 2
.....
a x + a x + ... a x ≤ b
m1 1 m2 2 mn n m
a y + a y + ... + a y ≥ c
x ,x ,....,x ≥ 0 1n 1 2n 2 mn m n
1 2 n
y ,y ,...y ≥ c
1 2 m n

5.2 Mengubah Bentuk Primal ke Bentuk Dual

Contoh soal 1 :
Tentukanlah bentuk dual dari program linear berikut!

Primal : Dual :
Max z=60 x 1+30 x 2 +20 x3 Min w=48 y 1 +20 y 2+ 8 y 3
Kendala : Kendala :

16
8 x 1+ 6 x2 + x 3 ≤ 48 8 y 1 +4 y 2+2 y 3 ≥60
4 x1 +2 x 2+ 1, 5 x 3 ≤ 20 6 y 1 +2 y 2+1 , 5 y 3 ≥ 30
2 x1 +1 , 5 x 2 +0 , 5 x 3 ≤ 8 y 1 +1 ,5 y 2 +0 , 5 y 3 ≥ 20
x1 , x2 , x3 ≥ 0 y1 , y2 , y3 ≥ 0

Contoh soal 2 :
Tentukan dual dari bentuk program linear berikut :

Primal : Dual :
Max z=22 x1 +3 x 2+ 6 x3 ≤ 7 Min s=7 y 1 +11 y 2 +21 y3
Kendala : Kendala :
x 1+ 5 x 2 +6 x 3 ≤ 7 y 1− y 2 +2 y 3 ≥ 22
−x 1+ x2 + 4 x 3=11 5 y 1+ y 2+ 3 y3 ≤ 3
2 x1 +3 x 2 + x3 ≥ 21 6 y 1 +4 y 2+ y 3=6
x 1 ≥ 0 , x 2 ≤ 0 , x 3 bebas y 1 ≥0 , y 2 bebas , y 3 ≤ 0

17
Latihan Soal :

18
 BAB VII
PENUGASAN

Tujuan Pembelajaran :

Pada bab ini diharapkan mahasiswa dapat :

7.1 Menjelaskan penugasan (Metode Hungarian)

7.2 Menggunakan rumus teori hungarian dengan tepat

7.3 Penugasan.

Masalah penugasan (Assignment Problem ) sering muncul dalam

banyak kasus pembuatan keputusan, seperti kasus menentukan siapa
mengerjakan apa, menetapkan fungsi sebuah mesin, menentukan
selesman untuk suatu wilayah pemasaran dan sebagainya.
Dengan kata lain, masalah penugasan berkaitan dengan masalah
penetapan tugas atau pekerjaan sebuah mesin, seorang pekerja, atau
suatu proyek dengan tujuan tertentu dan merupakan suatu kasus khusus
dari masalah linier. Tujuan yang dimaksud, antara lain :
memaksimumkan keuntungan, memaksimumkan hasil produksi,
meminimumkan waktu pengerjaan, dan meminimumkan jumlah personel.
Oleh karenanya, metode yang diterapkan untuk kasus penugasan
telah didesain khusus untuk menyelesaikan masalah penugasan, yang
disebut dengan Metode Penugasan Hungarian (Hungarian Metode/Flood’s
Technique). Metode ini menggunakan apa yang disebut pengurangan
matriks (Matrix Reduction). Dengan mengurangi dan menambah suatu nilai
dalam matriks. Sehingga akan menghasilkan penyelesaian optimal masalah
penugasan. Contoh kegiatan yang termasuk masalah penugasan antara
lain yaitu: penempatan karyawan pada suatu posisi jabatan di perusahaan,
pembagian wilayah tugas salesman, pembagian tugas dalam suatu tim
renang estafet.

19
 penugasan adalah menetapkan jumlah sumber-sumber yang
tugaskan kepada sejumlah tujuan (satu sumber untuk satu tujuan),
sedemikian hingga didapat ongkos total yang minimum atau
keuntungan total yang maksimum. Biasanya yang dimaksud dengan
sumber ialah pekerja. Sedangkan yang dimaksud dengan tujuan
adalah obyek dari pekerjaan tersebut. Jadi, masalah penugasan akan
mencakup sejumlah m sumber yang mempunyai n tugas. Ada n! (n
faktorial) penugasan yang mungkin dalam suatu masalah karena
berpasangan satu-satu. Apabila pekerjaan i (i= 1,2,3,....n) ditugaskan
kepada obyek j (j=1,2,3,...m) akan muncul biaya penugasan Cn maka
sudah jelas bahwa tujuan dari penugasan adalah mencari ongkos dari
tiap-tiap pekerjaan kepada obyek dengan total ongkos yang minimum
atau memberikan keuntungan yang maksimum.

1. LANGKAH 1
Mencari biiaya terkecil untuk setiap baris, dan kemudian
menggunakan biaya terkecil tersebut untuk mengurangi semua biaya
yang ada pada baris yang sama. Dengan langkah ini hasil yang
diperoleh adalah :
Pekerjaan

karyawan

I II III IV

A 0 5 1 7

B 0 2 5 3

C 5 0 1 0

D 1 2 0 0

20
 Sekarang setiap baris dan kolom sudah memiliki nilai nol, maka
langkah selanjutnya adalah:

2. LANGKAH 3

Langkah selanjutnya adalah memastikan atau mengecek apakah

dalam tabel penugasan tersebut, telah berhasil ditemukan nilai nol,
sebanyak sumber daya (bisa karyawan, mesin, alat transportasi,
atau sumber daya lainnya) yang juga tercermin dengan jumlah
barisnya. Misalnya bila yang akan ditugaskan adalah 4 karyawan,
maka harus ditemukan nilai nol sebanyak 4 buah yang terletak di
baris dan kolom yang berbeda. Sebaiknya dimulai dari baris
yang hanya memiliki 1 nilai nol. Langkah ini menganduk arti bahwa
setiap karyawan hanya dapan ditugaskan pada satu pekerjaan saja.

Perhatikan!

Dari matrik di atas ternyata nilai nol yang ditemukan dalam

baris 1 dan 2, meskipun berbeda baris namun masih berada dalam
kolom yang sama, sehingga dapat dipastikan masalah belum optimal
dan perlu dilanjutkan ke langkah berikutnya.

3. LANGKAH 4
Pekerjaan

karyawan

I II III IV

A 0 5 1 7

21
 B 0 2 5 3

C 5 0 1 0

D 1 2 0 0

Dari langkah di atas terlihat bahwa garis yang berhasil dibuat adalah
tiga, dengan menyisakan beberapa nilai yang tidak terkena garis.

4. LANGKAH 5

Selanjutnya, perhatikan nilai-nilai yang belum terkena garis. Pilih nilai

yang paling kecil (dari tabel di atas adalah nilai 1), kemudian nilai 1
tersebut dipergunakan untuk mengurangi nilai-nilai lain yang belum
terkena garis, dan gunakan untuk menambah nilai-nilai yang terkena
garis dua kali. Dengan langkah

Pekerjaan

karyawan

I II III IV

A 0 4 0 6

22
 B 0 1 4 2

C 6 0 1 0

D 2 2 0 0

Perhatikan ! Semua nilai yang tidak terkena garis nilainya akan berkurang
sebesar nilai teerkecil dari nilai yang belum terkena garis sebelumnya.
Sementara itu nilai 5 dan 1 pada kolom 1 akan bertamba 1, karen kedua nilai
tersebut terkena garis dua kali.

5. LANGKAH 6
Pekerjaan

karyawan

I II III IV

A 0 4 0 6

B 0 1 4 2

C 6 0 1 0

D 2 2 0 0

Dari hasil di atas dapat dikatakan bahwa kasus penugasan tersebut

telah optimal, dengan alokasi penugasan sebagai berikut :

Karyawan A ditugaskan mengerjakan pekerjaan III dengan biaya

23
Rp 18.000

Karyawan B ditugaskan mengerjakan pekerjaan I dengan biaya

Rp 14,000

Karyawan C ditugaskan mengerjakan pekerjaan II dengan biaya

Rp 20,000

Karyawan D ditugaskan mengerjakan pekerjaan IV dengan biaya

Rp 16.000

Dengan demikian dapat disimpulkan bahwa dengan metode

Hungarian, kasus penugasan dalam perusahaan di atas dapat
diselesaikan dengan biaya optimal sebesar Rp 68.000

24
LATIHAN SOAL

25
 Masalah Transportasi (Optimisasi)

Salah satu bentuk khusus dari program linier (PL) adalah masalah transportasi.
Tujuan dari materi transportasi ini yaitu untuk mencari optimasi biaya/ongkos yang berhubungan
dengan transportasi.
Masalah transportasi membicarakan cara pendistribusian suatu komoditi dari sejumlah sumber
(origin) ke sejumlah tujuan (destination).
Sasarannya adalah mencari pola pendistribusian dan banyaknya komoditas yang diangkut dari
masing-masing sumber ke masing-masing tujuan yang meminimalkan ongkos angkut secara
keseluruhan, dengan kendala-kendala yang ada.

Karakteristik Transportasi
Ada Sumber (asal), ada Tujuan.
Ada komoditas yang diangkut .
Ada ongkos per unit komoditas.
Sumber memiliki kapasitas (supply).
Tujuan memiliki kebutuhan (demand)

Metode Penyelesaian Transportasi

Ada beberapa metode yang dapat digunakan untuk mencari solusi optimal dari masalah
transportasi, diantara yang sering digunakan adalah:
1. Metode Barat Laut (MBL) / North West Corner Method (NWC)
2. Least Cost Method (LCM).
3. Vogel’s Approximation Method (VAM) / Metode Pendekatan Vogel (MPV)

Contoh :
1. Sebuah Perusahaan memiliki tiga pabrik di tiga kota yang berlainan, dan ketiga – tiganya
menghasilkan barang yang sama. Hasil produksi dari 3 pabrik diserap oleh empat took
penjualan. Tiga pabrik kita tndai dengan O 1 ,O 2 , dan O 3 dan took sebgai pelanggan
ditandai dengan D 1 , D 2 , D3 , dan D 4.

Model Transportasi adalah suatu model khusus dari model Linear Programming dalam bentuk
minimisasi biaya. Model Transportasi yang akan dibahas adalah tentang distribusi suatu produk

26
tunggal dari beberapa sumber dengan penawaran terbatas ke beberapa tujuan dengan permintaan
tertentu dan dengan biaya transportasi minimum.

Asumsi Dasar : Biaya transportasi pada suatu rute tertentu proporsional dengan
banyaknya unit produk yang dikirim.
Gambaran Masalah :
Jika terdapat : 3 Pabrik (sumber) 3 Pasar (tujuan)
Diketahui : Biaya transportasi per unit dari masing-masing pabrik ke masing-masing pasar.
Masalah : Menentukan kombinasi jumlah produk yang harus dikirim dari masing-masing
pabrik ke masing-masing pasar dengan tujuan meminimumkan biaya transportasi.
Kendala : Permintaan tiap pasar harus tepat dipenuhi penawaran
Misalnya :
cij = Biaya transportasi per unit produk dari sumber i ke tujuan j.
xij = Jumlah produk yang dikirim dari sumber i ke tujuan j.
Si = Kapasitas produksi sumber i.
Dj = Jumlah pemintaan tujuan j.

Masalahnya menjadi :

Jika diperhatikan dari masalah di atas, untuk masalah transportasi dengan 3 sumber dan 3 tujuan
akan memberikan 9 variabel keputusan dan 6 bentuk kendala yang akan memberikan 6 tambahan
artificial variable. Artinya dengan 15 varibel yang diperhatikan, akan terasa rumit untuk
diselesaikan dengan metode simpleks. Oleh karena masalah transportasi dibahas dengan metode
khusus dengan menggunakan Tabel Transportasi seperti tabel simpleks awal pada metode
simpleks. Kemudian dicari solusi awal fisibel dengan metode yang ada dan selanjutnya

27
berdasarkan solusi awal fisibel tersebut dianalisa solusi optimalnya dengan metode tertentu pula.
Tabel transportasinya berbentuk sebagai berikut :

Metode North West Corner

Langkah-langkah
1. Mulai dari pojok barat laut tabel, alokasikan sebanyak mungkin pada X11, tapi tidak
melanggar kendala pemintaan & penawaran, X11 = min {S1, D1}.
Keterangan: Menyebabkan permintaan tujuan 1 terpenuhi atau menghabiskan penawaran sumber 1.
Atau tidak ada lagi produk yang dapat dialokasikan ke kolom atau baris yang telah dipenuhi.
(Hilangkan baris atau kolom tersebut).
2. Alokasikan sebanyak mungkin ke kotak di dekatnya pada baris/kolom yang tidak
dihilangkan. Jika baris dan kolom telah dihilangkan, pindah secara diagonal pada kotak
berikut.
3. Lanjutkan dengan cara yang sama, sampai semua permintaan dan penawaran terpenuhi.
Contoh :
Suatu perusahaan akan mendistribusikan pupuk dari 3 pabrik ke 3 pasar. Tentukan biaya
transportasi dan kombinasi alokasi distribusinya, jika kapasitas supply pabrik dan jumlah
demand pasar, serta biaya transport per unit adalah sebagai berikut:

28
Penyelesaian :
1. Alokasikan sebanyak mungkin dari pabrik 1 ke pasar 1, X11 = min{S1, D1} =
min{120,150} = 120. Artinya pupuk di pabrik 1 sudah habis didistribusikan, S1 = 0, tidak
bisa lagi mengirim dari pabrik 1 (hilangkan baris 1). Sisa permintaan di pasar 1, D1 = 150
– 120 = 30.

2. Alokasikan sebanyak mungkin dari pabrik 2 ke pasar 1, X21 = min{S2, D1} = min{80,30}
= 30. Artinya permintaan dari pasar 1 sudah terpenuhi, D1 = 0, tidak bisa lagi mengirim ke
pasar 1 (hilangkan kolom 1). Sisa pupuk di pabrik 2, S1 = 80 – 30 = 50.

3. Alokasikan sebanyak mungkin dari pabrik 2 ke pasar 2, X22 = min{S2, D2} = min{50,70}
= 50. Artinya pupuk di pabrik 2 sudah habis didistribusikan, S2 = 0, tidak bisa lagi
mengirim dari pabrik 2 (hilangkan baris 2). Sisa permintaan di pasar 2, D2 = 70 – 50 = 20.

29
 4. Alokasikan sebanyak mungkin dari pabrik 3 ke pasar 2, X32 = min{S3, D2} = min{80,20}
= 20. Artinya permintaan dari pasar 2 sudah terpenuhi, D2 = 0, tidak bisa lagi mengirim ke
pasar 2 (hilangkan kolom 1). Sisa pupuk di pabrik 3, S3 = 80 – 20 = 60.

5. Alokasi terakhir dari pabrik 3 ke pasar 3 dengan jumlah penawaran dan permintaan sama
(setimbang), X33 = min{S3, D3} = min{60,60} = 60. Artinya pupuk di pabrik 3 sudah
habis didistribusikan dan permintaan dari pasar 3 sudah terpenuhi. Solusi awal sudah
diperoleh.

Supply dari pabrik 1 ke pasar 1 = X11 = 120

Supply dari pabrik 2 ke pasar 1 = X21 = 30
Supply dari pabrik 2 ke pasar 2 = X22 = 50
Supply dari pabrik 3 ke pasar 2 = X32 = 20
Supply dari pabrik 3 ke pasar 3 = X33 = 6
Dengan biaya transportasi

30
X11 = 120 120 (8) = 960
X21 = 30 30 (15) = 450
X22 = 50 50 (10) = 500
X32 = 20 20 (9) = 180
x33 = 60 60 (10) = 600
Maka total biaya transportasi = 2690 Catatan : Xij > 0 Variabel Basis (Kotak terisi) Xij = 0
Variabel Non Basis (Kotak kosong)

2. Jika Pertamina memiliki 3 daerah penambangan minyak di pulau Jawa yaitu di Cepu,
Cilacap, dan Cirebon dengan kapasitas produksi masingmasing sebesar 600.000 galon,
500.000 galon, 800.000 galon setiap harinya. Dari tempat-tempat tersebut, minyak
kemudian diangkut ke daerah-daerah pemasaran yang terpusat di Semarang, Jakarta, dan
Bandung, dengan daya tampung masing-masing sebanyak 400.000 galon, 800.000 galon,
dan 700.000 galon per hari. Ongkos pengangkutan per hari per 100.000 galon adalah :
- Dari Cepu ke Semarang, Jakarta, dan Bandung masing-masing sebesar Rp 120.000, Rp
250.000, dan Rp 50.000.
- Dari Cilacap ke Semarang, Jakarta, dan Bandung masing-masing sebesar Rp 300.000,
Rp 100.000, dan Rp 80.000.
- Dari Cirebon ke Semarang, Jakarta, dan Bandung masing-masing sebesar Rp 200.000,
Rp 250.000, dan Rp 120.000.
Tentukan solusi awal fisibel dengan metode north west corner untuk menentukan biaya
transportasi dan kombinasi alokasi distribusnya.

Penyelesaian
Rasio perbandingan angka-angkanya adalah sebagai berikut :
Untuk jumlah galon 1 : 100.000 , karena biaya terhitung per 100.000 galon.
Untuk biaya transportasi 1 : 10.000 , untuk mempermudah penulisan dan perhitungan.
Selanjutnya kita cari solusi fisibel awal dengan menggunakan metode North West Corner.
Tabel transportasinya :

Dengan menggunakan metode north west corner, diperoleh:

31
 Jadi alokasi dan biaya transportasi :
X11 = 4 , 4 (12) = 48
X12 = 2 , 2 (25) = 50
X22 = 5 , 5 (10) = 50
X32 = 1 , 1 (25) = 25
X33 = 7 , 7 (12) = 84
257
Total = 257  10.000 (rasio perbandingan)
= Rp 2.570.000

Metode Least-Cost
Langkah-langkah :
1. Pilih Xij (kotak) dengan cij terkecil dan alokasikan sebanyak mungkin, Xij = min { Si ,
Dj }. Hilangkan baris-i/kolom-j yang telah dipenuhi.
2. Dari Xij (kotak) sisa yang layak, pilih nilai cij terkecil dan alokasikan sebanyak mungkin.
3. Lakukan proses ini sampai semua permintaan/ penawaran dipenuhi.

Contoh :
1. Tentukan biaya transportasi dan kombinasi alokasi distribusinya pada masalah
Penyelesaian :
1) Biaya paling murah adalah pabrik 3 ke pasar 1, C31 = 3. Alokasikan sebanyak
mungkin dari pabrik 3 ke pasar 1, X31 = min{S3, D1} = min{80,150} = 80. Artinya
pupuk di pabrik 3 sudah habis didistribusikan, S3 = 0, tidak bisa lagi mengirim dari
pabrik 1 (hilangkan baris 3). Sisa permintaan di pasar 1, D1 = 150 – 80 = 70.

32
2) Biaya paling murah selanjutnya yang mungkin adalah pabrik 1 ke pasar 2, C12 = 5.
Alokasikan sebanyak mungkin dari pabrik 1 ke pasar 2, X12 = min{S1, D2} =
min{120,70} = 70. Artinya permintaan pasar 2 sudah terpenuhi, D2 = 0, tidak bisa lagi
mengirim ke pasar 2 (hilangkan kolom 2). Sisa pupuk di pabrik 1, S1 = 120 – 70 = 50.

3) Biaya paling murah selanjutnya yang mungkin adalah pabrik 1 ke pasar 3, C13 = 6.
Alokasikan sebanyak mungkin dari pabrik 1 ke pasar 3, X13 = min{S1, D3} =
min{50,60} = 50. Artinya pupuk di pabrik 1 sudah habis terdistribusi, S1 = 0, tidak
bisa lagi mengirim dari pabrik 1 (hilangkan baris 1). Sisa permintaan di pasar 3, S3 =
60 – 50 = 10.

4) Biaya paling murah selanjutnya yang mungkin adalah pabrik 2 ke pasar 3, C23 = 12.
Tidak dipilih pabrik 1 ke pasar 1, C11 = 8, pabrik 3 ke pasar 2, C32 = 9, atau pabrik 3
ke pasar 3, C33 = 10 (walaupun biayanya lebih kecil dari C23) karena ketiganya sudah
tidak mungkin lagi (sudah dihilangkan/hapus), Alokasikan sebanyak mungkin dari
pabrik 2 ke pasar 3, X23 = min{S2, D3} = min{80,10} = 10. Artinya permintaan pasar

33
 3 sudah terpenuhi, D3 = 0, tidak bisa lagi mengirim ke pasar 2 (hilangkan kolom 3).
Sisa pupuk di pabrik 2, S2 = 120 – 70 = 70.

5) Alokasi terakhir yang mungkin dari pabrik 2 ke pasar 1 dengan jumlah penawaran dan
permintaan sama (setimbang), X21 = min{S2, D1} = min{70,70} = 70. Artinya pupuk
di pabrik 2 sudah habis didistribusikan dan permintaan dari pasar 1 sudah terpenuhi.
Solusi awal sudah diperoleh

Supply dari pabrik 1 ke pasar 2 = X12 = 70

Supply dari pabrik 1 ke pasar 3 = X13 = 50
Supply dari pabrik 2 ke pasar 1 = X21 = 70
Supply dari pabrik 2 ke pasar 3 = X23 = 10
Supply dari pabrik 3 ke pasar 1 = X31 = 80
Dengan biaya transportasi
X12 = 70 70 (5) = 350
X13 = 50 50 (6) = 300
X21 = 70 70 (15) = 1050
X23 = 10 10 (12 )= 120
X31 = 80 80 (3) = 240
Maka total biaya = 2060.
Catatan : Jika ada cij kembar, pilih pengalokasian secara sembarang.

Metode Pendekatan Vogel (MPV)

34
35
36
Biaya = (5x5)+(5x4)+(60x9)+(20x4,5)+ (20x0,4)+(35x3)+(50x3)= 938
Latihan 1
Sebuah perusahaan listrik berencana memenuhi kebutuhan listrik untuk 4 kota. Saat ini tenaga
listrik tsb dibangkitkan dari 3 pembangkit listrik. Table berikut memberikan informasi tentang
kebutuhan masing-masing kota serta biaya yang dibutuhkan untuk mengalirkan 1juta kwh dari
masing2 pembangkit listrik. Gunakanlah ketiga metode diatas untuk menyelesaikan masalah ini.
Total Biaya

Jawaban :
Metode Barat Laut = 940
Least Cost Method = 740
Metode Pendekatan Vogel = 710

Transportasi Tidak Seimbang

Pengertian
1. Transportasi tidak seimbang yaitu jumlah kapasitas/supply tidak sama dengan jumlah
permintaan/kebutuhan.

37
2. Jika kapasitas > permintaan, maka ditambahkan “DUMMY” pada sel permintaan
dengan biaya nol.
3. Jika permintaan > kapasitas, maka ditambahkan “DUMMY” pada sel kapasitas
dengan biaya nol.
4. “DUMMY” adalah sel bohongan.

Contoh: Kapasitas > Permintaan

Pasar 1 Pasar 2 Pasar 3 Kapasitas/supply
Pabrik 1 7 4 2 400
Pabrik 2 6 5 1 600
Permintaan/Kebutuhan 400 300 200

Pasar Pasar Pasar Pasar 4

Kapasitas/supply
1 2 3 (Dummy)
Pabrik 1 7 4 2 0 400
Pabrik 2 6 5 1 0 600
Permintaan/Kebutuhan 400 300 200 100

Pasar 1 Pasar 2 Pasar 3 Kapasitas/supply

Pabrik 1 7 4 2 400
Pabrik 2 6 5 1 500
Permintaan/
400 350 300
Kebutuhan

Pasar 1 Pasar 2 Pasar 3 Kapasitas/supply

Pabrik 1 7 4 2 400
Pabrik 2 6 5 1 500
Pabrik 3
0 0 0 150
(Dummy)
Permintaan/
400 350 300
Kebutuhan

K1 K2 K3 K4 K5 KAPASITAS
B1 4 3 1 2 6 40
B2 5 2 3 4 5 30
B3 3 5 6 3 2 20
B4 2 4 4 5 3 10
PERMINTAA
30 30 15 20 15
N

38
 K1 K2 K3 K4 K5 KAPASITAS
B1 4 3 1 2 6 40
B2 5 2 3 4 5 30
B3 3 5 6 3 2 20
B4 2 4 4 5 3 10
Dummy 0 0 0 0 0 10
PERMINTAAN 30 30 15 20 15

Hasil
1. Metode Barat Laut = 335
2. LCM = 200
3. MPV= 200

Metode Steppingstone
K1 K2 Kapasitas

B1 900 100 1000

B2 600 600
Permintaan 900 700

Metode Steppingstone
K1 K2 Kapasitas

B1 -1 +1 1000
B2 +1 -1 600
Permintaan 900 700

Hasil Perubahan
K1 K2 Kapasitas

B1 300 700 1000

B2 600 0 600
Permintaan 900 700

Contoh :
Sebuah perusahaan distribusi memiliki 3 gudang dan 4 toko. Jumlah barang
(dalam satuan) yang tersedia di tiap gudang dan permintaan dari tiap toko
adalah sebagai berikut :

39
40
41
42
43
44