MAKALAH

PRIMAL-DUAL

Disusun Untuk Memenuhi Tugas Mata Kuliah Program Linear

Dosen Pengampu : As Elly, [Link].

Oleh :

Kelompok 2

1. Fredy Wahyudi (4021011)

2. Indah Rahmawati (4021023)
3. Cherin Anggraini (101220066)

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS PGRI SILAMPARI

 KATA PENGANTAR

Puji syukur kami panjatkan kehadirat Allah SWT yang telah memberikan rahmat,
karunia, taufik serta hidayah-Nya sehingga kami dapat menyelesaikan makalah ini yang berjudul
“PRIMAL-DUAL” tepat pada waktunya.

Kami berterima kasih kepada Ibu As Elly, [Link]. selaku dosen mata kuliah Program
Linear yang telah memberikan tugas ini kepada kami. Kami menyadari sepenuhnya bahwa di
dalam makalah ini masih terdapat banyak kekurangan dan jauh dari kata sempurna.

Kami juga berharap makalah ini dapat bermanfaat bagi pembaca dan juga kami sebagai
penulis. Sebelumnya kami mohon maaf apabila terdapat kesalahan kata-kata yang kurang
berkenan dan kami memohon kritik, saran dan usulan yang membangun dari Ibu dan teman-
teman sekalian dari perbaikan makalah ini di waktu yang akan datang, mengingat tidak ada
sesuatu yang sempurna tanpa saran yang membangun.

Lubuklinggau, 21 Mei 2024

Penyusun
 DAFTAR ISI

HALAMAN JUDUL .....................................................................i

KATA PENGANTAR.........................................................................................i

DAFTAR ISI II..................................................................................................ii

BAB I PENDAHULUAN..................................................................................1

1.1 Latar Belakang..............................................................................................1

1.2 Rumusan Masalah.........................................................................................2

1.3 Tujuan...........................................................................................................2

BAB II PEMBAHASAN....................................................................................3

2.1 Definisi Primal-Dual...................................................................................3

2.2 Bentuk Umum Masalah Primal –Dual........................................................3
2.3 Hubungan Primal-Dual...............................................................................4
2.4 Contoh Soal Primal-Dual............................................................................6

BAB III PENUTUP..........................................................................................19

A. Kesimpulan................................................................................................19
B. Saran...........................................................................................................21

DAFTAR PUSTAKA.......................................................................................22
 BAB 1
PENDAHULUAN

1.1 Latar belakang

Pemrograman linear (linear programming) adalah salah satu teknik

Operations Research yang paling banyak digunakan perusahaanperusahaan di
Amerika menurut penelitian Turban, Russel, Ledbetter, Cox, dan lain-lain. Di
samping itu, teknik ini telah menjadi dasar pengembangan teknik Operations
Research yang lain seperti Goal Programming, Binary Integer Programming atau
Zero-One Programming. Juga, teknik ini bisa digunakan untuk menyelesaikan teknik
Operations Research yang lain, seperti Transportation, Assignment, Crash Time and
Crash Cost Program pada Critical Path Method, Equilibrium condition pada Markov
Analysis, Dual Programming pada Game Theory, dan Network Analysis seperti
Transhipment, Shortest Route, Minimum Spanning Tree, dan Maximal Flow
(Siswanto, 2007).

Salah satu metode pemograman linear yang digunakan untuk

mengoptimalkan suatu produksi adalah metode simpleks. Metode simpleks ialah
suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel
ke pemecahan dasar yang fisibel lainnyadan ini dilakukan berulang-ulang sehingga
akhirnya tercapai suatu pemecahan dasar yang optimum dan pada setiap tahap
menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih besar (lebih kecil) atau
sama dari tahap-tahap sebelumnya. Metode simpleks merupakan suatu cara yang
lazim dipakai untuk menentukan kombinasi optimal dari tiga variabel atau lebih.
Secara matematis penyelesaian optimal sebuah kasus pemrograman linier
selalu berhubungan dengan penyelesaian optimal sebuah kasus pemrograman linier
yang lain. Dalam penyelesaian persoalan linier dengan membentuk formulasi terlebih
dahulu sudah dikenal dengan istilah primal, yaitu bentuk asli dari suatu model
program linier sementara 2 bentuk kedua yang berhubungan. dinamakan dengan
istilah dual di dalam pemrograman linier, sehingga solusi optimal disatu metode
menghasilkan informasi yang lengkap untuk solusi optimal yang lainnya. Dual
adalah suatu bentuk alternatif model berisi informasi mengenai nilai-nilai sumber
yang biasanya membentuk batasan model.. Jika suatu program linier diselesaikan
dengan metode simpleks, sesungguhnya diperoleh penyelesaian untuk dua masalah
Linear Programming (Becker et al. 2015).
Dalam mengoptimalkan suatu produksi, fungsi tujuan yang dioptimalkan adalah
memaksimumkan keuntungan yang diperoleh dan meminimumkan biaya
produksi dengan memperhatikan batasan-batasan yang ada yaitu pembatasan
mengenai inputnya seperti faktor-faktor yang mempengaruhi produksi tersebut.
Dengan memperhatikan keterbatasan-keterbatasan yang ada merupakan
salah satu cara untuk menghadapi kendala-kendala tersebut dengan tujuan untuk
mencari kombinasi produksi yang optimal, sehingga dapat menghasilkan laba yang
maksimum dalam mengoptimalkan produksi, yaitu dengan penggunaan model
optimasi program linier Primal-Dual.

1.2 Rumusan Masalah

1. Apa yang dimaksud dengan primal-dual?

2. Bagaimana bentuk umum dari primal-dual?
3. Bagaimana hubungan primal dan dual?
4. Bagaimana meyelesaikan contoh soal primal-dual?
1.3 Tujuan

1. Dapat memahami pengertian dari primal-dual.

2. Dapat memahami bentuk umum dari primal-dual.
3. Dapat memahami hubungan primal dan dual.
4. Dapat meyelesaikan contoh soal primal-dual.
 BAB II
PEMBAHASAN

2.1 Definisi Primal-Dual

Teori dualitas merupakan salah sa5tu konsep program linier yang

penting dan menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang
melatarbelakangi teori ini adalah bahwa setiap persoalan program linier lain
yang saling berkaitan yang disebut “dual”, sedemikian sehingga solusi pada
persoalan pada persoalan semula yang disebut “primal” juga memberi solusi
pada dualnya.

Setiap masalah program linier mempunyai satu masalah program

linier yang terkait, yang disebut dual. Program linier asalnya disebut primal. Jika
primal dan dual tersebut dicari penyelesaiannya, nilai optimum model primal
sama dengan nilai optimum model dual.
Untuk mentransformasikan masalah primal menjadi masalah dual,
bentuk masalah primal harus dalam bentuk standar.

1. Untuk masalah maksimasi, bentuk standar fungsi kendalanya adalah

fungsi kendala yang bertanda ≤

2. Untuk masalah minimasi, bentuk standar fungsi kendalanya adalah

fungsi kendala yang bertanda ≥

3. Pada bentuk standar primal dual, nilai ruas kanan boleh negatif.
Namun, saat akan mencari penyelesaian dengan metode simpleks,
bentuk yang akan dicari penyelesaiannya harus dalam bentuk standar untuk
metode simpleks, yaitu nilai ruas kanan harus ≥ 0.
2.2 Bentuk Umum Masalah Primal-Dual

Tabel berikut menunjukkan transformasi dan perbedaan antara masalah primal dan
masalah dual!

Primal Dual
Maksimasi FungsI Minimasi Fungsi
Minimasi Fungsi Maksimasi Fungsi
Nilai koefisien fungsi Nilai kanan fungsi
tujuan kendala
Matriks koefisien fungsi Transpose matriks koefisien
fungsi kendala

Fungsi kendala ke- i Variabel xi tidak terbatas

Variabel xi tidak terbatas Fungsi kendala ke- i

2.3 Hubungan Primal-Dual

1. Koefisien fungsi tujuan masalah primal menjadi konstanta nilai kanan

fungsi kendala dual. Sebaliknya, Konstanta nilai kanan fungsi kendala
primal menjadi koefisien fungsi tujuan dual.

2. Tanda pertidaksamaan fungsi kendala dibalik (pada primal ≤, pada dual ≥).
3. Tujuan berubah dari maksimasi pada primal menjadi minimasi pada dual,
 dan demikian pula berlaku sebaliknya.

4. Setiap kolom fungsi kendala pada primal berhubungan dengan suatu baris
pada fungsi kendala dalam dual. Sehingga banyaknya fungsi kendala dual
akan sama banyaknya dengan variabel keputusan primal.

5. Setiap baris pada fungsi kendala pada primal berhubungan dengan suatu
kolom dalam dual. Sehingga setiap fungsi kendala primal ada satu variabel
keputusan dual.
Zmaks = 3x1 + 5x2 + 4x3 Zmin = 6y1 +

8y2

Fungsi Kendala: Fungsi

Kendala:
2x1 − x2 + 3x3 ≤6 2y1 + y2 ≥ 3

x1 + 2x2 + 4x3 ≤ 8 –y1+2y2 ≥ 5

x1, x2, x3 ≥ 03 y1 + 4y2 ≥4

y1, y2 ≥ 0

Jika bentuk primalnya tidak dalam bentuk baku, maka perlu diubah

dulu ke bentuk baku sebelum dicari dualnya.

Contoh 2 :

Masalah Primal Masalah Dual

Zmaks = 5x1 + 6x2 Zmin = −5y1 − 3y2 +

8y3
 Fungsi Kendala:

x1 + 2x2 ≥ 5

−x1 + 5x2 ≥ 3

4x1 + 7x2 ≤8

x1+x2 ≥ 0

Yang tidak baku

diubah menjadi bentuk
baku Fungsi Kendala

−x1 − 2x2 ≤ −5 −y1 + y2 + 4y3

≥ 5
x1 − 5x2 ≤ −3 −2y1 − 5y2 +
7y3
≥6

4x1 + 7x2 ≤8 y1, y2, y3

≥ 0

Contoh 3 :

Masalah primal Masalah dual

Zmax = x1 + 2x2 + x3 Zmin = −2y1 + y2 + y3

Fungsi kendala: Fungsi Kendala:

x1 + 2x2 + x3 ≥ 2 −y1 + y3 ≥ 1

x2 + x3 ≤ 1 −2y1 + y2 ≥ 2

x1 + 2x3 = 1 −y1 + y2 + 2y3 ≥ 1

x1, x2, x3 ≥ 0 y1, y2 ≥ 0

Yang tidak baku

di ubah menjadi

bentuk baku

−x1 − 2x2 − x3 ≤ −2

2.4 Contoh Soal Primal-Dual

Contoh kasus terkait metode primal dual beserta langkah-langkah

6. Seorang agen sepeda bermaksud membeli 25 buah sepeda untuk

persediaan. Harga sepeda biasa Rp. 60.000/ buah, dan sepeda balap Rp.
80.000/ buah. Ia merencanakan untuk tidak mengeluarkan lebih dari
Rp.1.680.000 dengan mengharapkan keuntungan Rp. 10.000 dari tiap
sepeda biasa dan Rp. 12.000 dari tiap sepeda balap.
Jawaban:

Model matematika untuk kasus di atas adalah:

➢ Model primal

Primal : Maksimum : Z = 12.000x1 + 10.000x2

Fungsi kendala : X 1 + X2 ≤ 25
8x1 + 6x2 ≤ 168

x1, x2 ≥ 0
 Xj Ꝋ
(CB) X1 X2 X3 X4 bi
i (XB)i
0 X3 1 1 1 0 25 25

0 X4 8 6 0 1 168 21

Zj 0 0 0 0
Cj-Zj 12 0 0 0 0
0 X3 0 1 1 −1 4 16
4 8
12 X1 1 6 0 1 21 28
8 8
Zj 12 9 0 3 252
2
Cj-Zj 0 1 0 −3
2
10 X2 0 1 4 −1 16
2
12 X1 1 0 -3 1 9
2
Zj 12 10 4 1
Cj-Zj 0 0 -4 -1
 Model Dual

Fungsi tujuan : Meminimumkan : Z = 25y1 + 168y2

Fungsi kendala:

y + 8y2 ≥ 12.000
1

y1 + 6y2 ≥ 10.000
y1, y2 ≥ 0

Penyelesaian:

Fungsi tujuan: Z - 25y1 - 168y2 - 0S1 - 0S2 - MA1 -

MA2 = 0 Fungsi kendala:

y1 + 8y2 – S1+ A1 = 12.000

y1 + 6y2 – S2+ A2 = 10.000

Baris Z baru :
y1 y2 S1 S2 A1 A2 NK
 25 168 0 0 M 0

-M 1 8 -1 0 1 0 12.000 ]

-M 1 6 0 -1 0 1 10.000 ]
2M-25 14M-168 -M -M 0 0 22.000M

Variabel NK Ras
y1 y2 S1 S2 A1 A2
Z 2M- 14M-168 -M -M 0 0 22.000M
25

Variabel y1 y2 S1 S2 A1 A2 NK Rasio

Z 2M-25 14M-168 -M -M 0 0 22.000

M
A1 1 8 -1 0 1 0 12.000 1.500
A2 1 6 0 -1 0 1 10.000 10.000
6

Variabel y1 y2 S1 S2 A1 A2 NK Rasio
Z 1 0 6 -M 14 0 252.000 +
M-4 M- - M
4 8 8 1.000M
21
y2 1 1 −1 0 1 0 1.500 12.000
8 8 8
A2 1 0 6 -1 −6 1 10.000 8.000
4 8 8 6

Variabe y1 y2 S1 S2 A1 A2 NK Rasio
l
Z 3 0 0 -28 -M -M+28 280.00
 0
y2 1 1 0 −1 0 0 10.000/ 10.000
6 6 6
S1 1 0 1 −8 -1 8/6 8.000/6 4.000
3 6

Variabel 1
y y
2
S
1
S
2
A1 A2 NK
Z 0 0 -9 -16 -M+9 -M+16 268.000
y
2
0 1 -1/2 1 3 −1 1.000
2 6 2
1
y 1 0 3 -4 -3 4 4.000

Jadi solusinya dapat dilihat pada kolom NK dan didapatkan Zmax = 268.000 dengan y 1 =
1.000 dan y 2 = 4.000.

Latihan Soal :

1. Sebuah toko buku menjual tiga jenis buku yaitu buku IPA, buku IPS, dan buku Matematika.
Buku-buku tersebut di pajang dalam sebuah lemari. Lemari 1 terdapat 1 buku IPA, 2 buku IPS
dan 1 buku Matematika, dan hanya memuat 10 buku IPA, 1 buku IPA, dan 3 buku
Matematika dan hanya memuat 15 buku buku IPA, IPS dan Matematika. Berapakah maksimal
buku IPA, IPS dan Matematika yang harus disediakan agar kedua lemari terisi penuh dengan
fungsi tujuan 5 x 1 + 5 x 2 + 10 x 3.
 BAB III
PENUTUP

3.1 Kesimpulan

Suatu program linear dengan bentuk asli disebut sebagai primal. sedangkan
bentuk kedua yang berhubungan disebut dual yang merupakan sebuah
bentuk alternatif suatu program linear yang berisi informasi mengenai nilai-
nilai sumber yang biasanya merupakan pembatas dari suatu model. Dual
merupakan bentuk alternatif model sebagai pengembangan bentuk primal.
Bentuk dual dirumuskan dan diinterpretasikan untuk mendapatkan informasi
tambahan setelah menentukan solusi optimal suatu masalah program linear.
Tabel simpleks yang diperoleh dari pemecahan masalah program linear
primal mengandung informasi ekonomi tambahan yang tidak kalah penting dari
pada solusi optimum masalah tersebut, sehingga suatu solusi terhadap primal
juga memberikan solusi pada bentuk dualnya. Analisis pada bentuk primal
akan menghasilkan solusi-solusi dalam bentuk jumlah laba yang diperoleh,
sedangkan analisis pada bentuk dual akan memberikan informasi mengenai
harga dari sumber daya yang menjadi kendala tercapainya laba tersebut.

2. Koefisien fungsi tujuan masalah primal menjadi konstanta nilai kanan

fungsi kendala dual. Sebaliknya, koefisien fungsi tujuan masalah dual
menjadi nilai kanan fungsi kendala primal.
3. Tanda pertidaksamaan pembatas dibalik (pada primal ≤, pada dual

>)

4. Tujuan berubah dari minimiasi (maksimasi) pada primal menjadi

maksimasi (minimasi) pada dual, dan demikian pula berlaku
sebaliknya

5. Setiap kolom pada primal berhubungan dengan suatu baris (kendala /

pembatas) dalam dual. Sehingga banyaknya pembatas dual akan sama
banyaknya dengan variabel keputusan primal.
6. Setiap baris (pembatas) pada primal berhubungan dengan suatu kolom
dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan
dual.

7. Bentuk dual dari dual adalah bentuk primal.

3.2 Saran

Penulis menyadari bahwa makalah ini masih terdapat banyak kekurangan

oleh karena itu, kritik dan saran yang membangun sangat diperlukan untuk
menyempurnakan makalah ini agar lebih baik lagi. Semoga makalah ini dapat
memberikan pengetahuan dan wawasan mendalam bagi penulis khususnya
bagi pembaca umumnya.
 DAFTAR PUSTAKA

Akhlords, B. (2013, Oktober 10). Riset Operasi Contoh Soal. Retrieved from
[Link]

Amai, & Nacaisya, I. (2012). Contoh Soal Transformasi Dan Primal Dual. Retrieved
from [Link]
dan-primal- [Link]