PERSOALAN PRIMAL-DUAL

MAKALAH

Diajukan Untuk Memenuhi Tugas Mata Kuliah Program Linear

Dosen Pengampu : Hartini, [Link]., [Link].

Disusun Oleh :
Kelompok 1

Dewi Kurniawati 2016.11.0852

Muli Aprida 2016.11.0856
Nita 2016.11.0860
Sofia Rizqi Norfitriana 2016.11.0863

PRODI PENDIDIKAN MATEMATIKA

SEKOLAH TINGGI KEGURUAN DAN ILMU PENDIDIKAN
(STKIP) PARIS BARANTAI
KOTABARU
2018

i
 KATA PENGANTAR

Assalamu’alaikum warahmatullahi wabarakatuh.

Segala puji bagi Allah SWT karena berkat-Nya lah kami sekelompok dapat
menyelesaikan makalah ini tepat dengan waktunya. Kami hanya bisa berusaha
dalam menyusun makalah ini dan Allah lah yang mempermudah urusan kami ini.
Sholawat serta salampun dihaturkan kepada junjungan kita Nabi Muhammad
SAW dan keluarga serta para sahabat, karena perjuangan mereka dalam
mendakwahkan Islam mampu membuat kita mengenal Islam, mengenal Allah
SWT, Tuhan seluruh alam. Ucapan terima kasih juga kami berikan kepada orang
tua dan dosen pengampu mata kuliah Program Linear atas bimbingannya selama
ini.

Makalah ini tentunya jauh dari kata sempurna, karena kesempurnaan hanya
lah milik Allah SWT dan kami hanyalah manusia biasa yang lemah, terbatas, dan
bergantung kepada Rabb sang Pencipta. Jadi, kami memohon maaf dengan segala
kekurangan yang terdapat dalam penyusunan makalah ini dan kami memohon
koreksinya dengan memberikan kritikan dan juga saran agar dalam penyusunan
makalah selanjutnya dapat lebih baik lagi.

Wassalamualaikum Warahmatullahi Wabarakatuh

Kotabaru, Juni 2018

Penyusun

ii
 DAFTAR ISI

Halaman

KATA PENGANTAR .................................................................................... ii

DAFTAR ISI ................................................................................................... iii

BAB I PENDAHULUAN
1.1 Latar Belakang ..................................................................................... 1
1.2 Rumusan Masalah ................................................................................ 1
1.3 Tujuan Pembahasan.............................................................................. 1

BAB II PEMBAHASAN

2.1 Definisi Dualitas................................................................................... 2

2.2 Hubungan Persoalan Primal dengan Dual............................................ 2
2.3 Ketentuan Bentuk Primal dan Dual ..................................................... 3
2.4 Persoalan Primal-Dual Simetris ........................................................... 4
2.5 Persoalan Primal-Dual Tak Simetris .................................................... 5
2.6 Bentuk Dual dari Dual ......................................................................... 8
BAB III PENUTUP

3.1 Kesimpulan .......................................................................................... 10

3.2 Saran ..................................................................................................... 10

DAFTAR PUSTAKA

iii
 BAB I
PENDAHULUAN

1.1 Latar Belakang

Setiap persoalan program linier mempunyai dua macam analisis, yaitu
Analisis Primal dan Analisis Dual yang biasanya disebut “Analisis Primal-Dual”.
Dalam perjalanannya teknik linier programming mengalami perkembangan dan
penyempurnaan, sehingga dapat ditemukan berbagai kelebihan-kelebihan yang
berguna dalam penerapan teknik ini. Salah satu manfaatnya yaitu dalam dunia
Linier Programming yang digunakan sebagai alat analisa dan pengambilan
keputusan. Teknik tersebut dikenal dengan teori dualitas.
Menurut teori ini, setiap persoalan linier programming saling berhubungan
timbal balik dengan persoalan linier programming yang lain yang merupakan
“dual”nya. Hubungan timbal balik antara suatu persoalan linier programming
yang asli (disebut primal) dengan persoalan linier programming yang lain (dual),
akan menimbulkan manfaat berupa memudahkan orang dalam mengkaji suatu
perhitungan dalam linier programming.

1.2 Rumusan Masalah

Rumusan masalah dari latar belakang makalah ini antara lain:
- Apa hubungan dari persoalan primal dengan persoalan dual?
- Bagaimana cara mengubah persoalan primal menjadi persoalan dual dan
sebaliknya?

1.3 Tujuan Pembahasan

Tujuan pembahasan dari makalah ini adalah agar para pembaca khususnya
mahasiswa pendidikan matematika STKIP Paris Barantai Kotabaru dapat lebih
memahami materi program linear terkait analisis primal dan dual

1
 BAB II
PEMBAHASAN

2.1 Definisi Dualitas

Dualitas adalah sebuah konsep dalam pemrograman linier yang menjelaskan
secara matematis bahwa sebuah kasus pemrograman linier mempunyai dua bentuk
yang saling berhubungan dan keterkaitan yaitu primal dan dual. Bentuk primal
adalah bentuk asli atau bentuk pertama dari persamaan program linear dan betuk
dual adalah bentuk kedua yang berkebalikan dari bentuk primal.
Bentuk dual dirumuskan dan diinterpretasikan untuk mendapatkan informasi
tambahan setelah menentukan solusi optimal suatu masalah program linear.
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.2 Hubungan Persoalan Primal dengan Dual

Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa
hubungan sebagai berikut:
a. Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan
pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi
koefisien fungsi tujuan dual.
b. Tanda pertidaksamaan pembatas dibalik (pada primal , pada dual )
c. Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada
dual.
d. Setiap kolom pada primal berhubungan dengan suatu baris (kendala)
dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya
dengan variabel keputusan primal.
e. Setiap baris (pembatas) pada primal berhubungan dengan suatu kolom
dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan
dual.
f. Bentuk dual dari dual adalah primal.

2
2.3 Ketentuan Bentuk Primal dan Dual
Ketentuan dalam perumusan persoalan program linier menyangkut bentuk
primal dan dual adalah :
Bentuk Primal Bentuk Dual
Memaksimumkan fungsi tujuan, dan Meminimumkan fungsi tujuan, dan
sebaliknya sebaliknya
Umumnya notasi fungsi tujuan Umumnya notasi fungsi tujuan
adalah Z adalah W
Umumnya notasi variabel keputusan Umumnya notasi variabel keputusan
dalam bentuk X adalah Y
Koefisien fungsi tujuan (Cj) Nilai Sebelah Kanan (NSK) fungsi
kendala
NSK fungsi kendala primal (bi) Koefisien fungsi tujuan
Koefisien peubah ke-j Koefisien kendala ke-j
Koefisien kendala ke-i Koefisien peubah ke-i
Peubah ke-j tandanya tidak dibatasi Kendala ke-j yang bertanda sama
dengan
Kendala ke-i yang bertanda sama Peubah ke-i tandanya tidak dibatasi
dengan
Kendala ke-i yang bertanda Peubah ke-i yang positif ()
ketidaksamaan ()

Untuk dapat menyusun suatu persoalan primal Program Linier kedalam

bentuk dual, maka selalu harus dirumuskan terlebih dahulu ke dalam bentuk
kanonik.
1. Untuk persoalan maksimasi, maka semua rumusan fungsi kendala mempunyai
tanda lebih kecil dari pada atau sama dengan ( ≤ ).
2. Untuk persoalan minimasi maka tanda fungsi syarat ikatannya harus lebih
besar dari pada atau sama dengan ( ≥ ) .
3. Jika suatu persoalan dalam rumusan Program Linier mempunyai fungsi
kendala kesamaan (nilai nsk-nya bertanda sama dengan), maka fungsi

3
 kendalanya tersebut dapat ditukar atau diganti dengan dua fungsi lainnya, yang
pertama, bertanda “lebih kecil dari pada atau sama dengan (≤)” dan yang
kedua, bertanda “lebih besar dari-pada atau sama dengan (≥)”. Salah satu
diantara kedua fungsi kendala lain tersebut (dipilih salah satu), kemudian
diambil, dan kalikan dengan (-1) untuk mendapatkan fungsi kendala yang
sesuai dengan aturan yang diminta oleh bentuk kanonik tersebut.

2.4 Persoalan Primal-Dual Simetris

Suatu program linear dikatakan berbentuk simetris jika semua konstanta ruas
kanan pembatas bernilai non negatif dan semua pembatas berupa pertidaksamaan,
dimana pertidaksamaan dalam masalah maksimasi berbentuk ≤, dan
pertidaksamaan dalam minimasi berbentuk ≥.
Contoh Soal:
1) Ubahlah bentuk primal berikut ke dalam bentuk dualnya!
Minimumkan Z = 5X1 + 2X2 + X3
Fungsi Kendala:
2X1 + 3X2 + X3  20
6X1 + 8X2 + 5X3  30
7X1 + X2 + 3X3  40
X1, X2, X3  0
Penyelesaian:
Untuk memudahkan mengubah persoalan primal menjadi persamaan dual,
kita buat ke dalam tabel seperti berikut.
X1 X2 X3
FK 1 2 3 1  20 Y1
FK 2 6 8 5  30 Y2
FK 3 7 1 3  40 Y3
  
Z 5 2 1
Sehingga didapat bentuk dualnya:
Maksimumkan W = 20Y1 + 30Y2 + 40Y3

4
 Fungsi Kendala:
2Y1 + 6Y2 + 7Y3  5
3Y1 + 8Y2 + Y3  2
Y1 + 5Y2 + 3Y3  1
Y1, Y2, Y3  0
2) Andaikan terdapat suatu persoalan Program Linier sebagai berikut :
Memaksimumkan: Z = 40000X1+ 50000X2 + 40000X3
Fungsi kendala:
4X1+ 4X2 + 6X3 ≤ 600
8X1+ 4X2 + 6X3 ≤ 800
X1 , X2 , X3 ≥ 0
Ubahlah ke dalam bentuk dualnya!
Penyelesaian
X1 X2 X3
FK 1 4 4 6  600 Y1
FK 2 8 4 6  800 Y2
  
Z 40000 50000 40000

Sehingga didapat bentuk dualnya:

Minimumkan:
W = 600Y1 + 800Y2
Fungsi kendala:
4Y1 + 8Y2  40000
4Y1 + 4Y2  50000
6Y1 + 6Y2  40000
Y1, Y2  0
2.5 Persoalan Primal-Dual Tak Simetris
Misalkan masalah primal yang tak simetris adalah sebagai berikut:
Maksimumkan Z = 5X1 + 2X2 + 3X3

5
X1 + 5X2 + 2X3 = 30
X1 ̶ 5X2 ̶ 6X3 ≤ 40
X1, X2, X3 ≥ 0
Apabila bentuk primal ini dianalogikan dengan persoalan sebelumnya, maka
apabila bentuk primal ini akan diubah kedalam bentuk dual, maka langkah
pertama yang perlu dilakukan adalah mengubah bentuk primal tak simetris
menjadi bentuk primal simetris. Pembatas pertama dalam contoh tersebut
merupakan suatu persamaan X1 + 5X2 + 2X3 = 30 dan harus diubah kedalam
bentuk ≤. Persamaan ini ekuivalen dengan dua pembatas berikut ini:
X1 + 5X2 + 2X3 ≤ 30
X1 + 5X2 + 2X3 ≥ 30
Artinya jika nilai pembatas lebih besar atau sama dengan 30 dan kurang dari
atau sama dengan 30, maka kuantitas yang memenuhi kedua pembatas tersebut
adalah 30. Tetapi pada pembatas tersebut tanda ≥ masih tetap ada, dan pembatas
ini dapat diubah dengan cara mengalikannya dengan (-1).
X1 + 5X2 + 2X3 ≥ 30 ... (-1)
-X1 ̶ 5X2 ̶ 2X3 ≤ -30
Sehingga model primal dalam bentuk normal adalah:
Maks Z = 5X1 + 2X2 + 3X3
X1 + 5X2 + 2X3 ≤ 30
-X1 ̶ 5X2 ̶ 2X3 ≤ −30
X1 ̶ 5X2 ̶ 6X3 ≤ 40
X1, X2, X3 ≥ 0
X1 X2 X3
FK 1 1 5 2  30 Y1
FK 2 -1 -5 -2  -30 Y2
FK 3 1 -5 -6  40 Y3
  
Z 5 2 3

6
Bentuk dual dari model ini diformulasikan sebagai:
Min W = 30Y1 ̶ 30Y2 + 40Y3
Y1 ̶ Y2 + Y3 ≥ 5
5Y1 ̶ 5Y2 ̶ 5Y3 ≥ 2
2Y1 ̶ 2Y2 ̶ 6Y3 ≥ 3
Y1, Y2, Y3 ≥ 0
Tetapi bentuk dual ini pun tidak sesuai dengan ketentuan hubungan primal
dual yang telah dikemukakan pada awal bagian ini. Ketidaksesuaian tersebut
terletak pada jumlah pembatas primal tak simetris yang tidak sesuai dengan
jumlah koefisien fungsi tujuan dual, padahal pada hubungan primal dual setiap
pembatas pada primal berhubungan dengan satu kolom pada dual, sehingga setiap
pembatas primal terdapat satu variabel keputusan dual. Sedangkan dalam contoh
ini pada bentuk primal tak simetris terdapat 2 pembatas tetapi setelah bentuk
primal tak simetris ini ditransformasikan menjadi primal normal lalu kemudian
dibuat bentuk dualnya, terdapat pada bentuk dual tersebut terdapat 3 variabel
keputusan.
Untuk menyelesaikan masalah tersebut, maka bentuk dual dapat dibentuk dari
primal tak simetris tanpa harus mentransformasikannya terlebih dahulu menjadi
primal normal.
Maksimumkan Z = 5X1 + 2X2 + 3X3
X1 + 5X2 + 2X3 = 30
X1 ̶ 5X2 ̶ 6X3 ≤ 40
X1, X2, X3 ≥ 0
Maka dengan mengikuti aturan tabel hubungan primal dual, bentuk dual dari
primal tak simetris itu adalah:
X1 X2 X3
FK 1 1 5 2 = 30 Y1
FK 2 1 -5 -6  40 Y2
  
Z 5 2 3

7
Min W = 30Y1 + 40Y2
Y1+ Y2 ≥ 5
5Y1 ̶ 5Y2 ≥ 2
2Y1 ̶ 6Y2 ≥ 3
Y1 tidak terbatas tanda
Y2 ≥ 0
Karena Y1 tidak terbatas tanda, Y1 disubstitusikan dengan Y1’ ̶ Y1” (Y1 = Y1’ ̶
Y1”) dimana Y1’ dan Y1” ≥ 0, sehingga bentuk dualnya menjadi:
Min W = 30Y1 + 40Y2 Min W = 30 (Y1’ − Y1”) + 40Y2
Y1+ Y2 ≥ 5 ( Y1’ ̶ Y1”) + Y2 ≥ 5
5Y1 ̶ 5Y2 ≥ 2 Disubstitusikan 5 (Y1’ ̶ Y1”) ̶ 5Y2 ≥ 2
2Y1 ̶ 6Y2 ≥ 3 2 (Y1’ ̶ Y1”) ̶ 6Y2 ≥ 3
Y1 tidak terbatas tanda (Y1’ ̶ Y1”) = Y1
Y2 ≥ 0 Y2 ≥ 0

Atau
Min W = 30Y1’ ̶ 30Y1” + 40Y2
Y1’ ̶ Y1” + Y2 ≥ 5
5Y1’ ̶ 5Y1” ̶ 5Y2 ≥ 2
2 Y1’̶ 2Y1” ̶ 6Y2 ≥ 3
Y1’ ≥ 0
Y1” ≥ Y1
Y2 ≥ 0

2.6 Bentuk Dual dari Dual

Salah satu hubungan antara primal dengan dual adalah bahwa bentuk dual
dari dual adalah primal.
Contoh soal:
Dari soal sebelumnya, didapat bentuk dual yaitu:
Minimumkan:
W = 600Y1 + 800Y2

8
 Fungsi kendala:
4Y1 + 8Y2  40000
4Y1 + 4Y2  50000
6Y1 + 6Y2  40000
Y1, Y2  0
Untuk mempermudah mengerjakannya, gunakan tabel seperti berikut.
Y1 Y2
FK 1 4 8  40000 X1
FK 2 4 4  50000 X2
FK 3 6 6  40000 X3
 
Z 600 800
Didapat bentuk primalnya adalah:
Maksimumkan Z = 40000 X1 + 50000 X2 + 40000 X3
Fungsi Kendala:
4 X1 + 4 X2 + 6X3  600
8 X1 + 4 X2 + 6X3  800
X1 , X2 , X3 ≥ 0

9
 BAB III
PENUTUP
3.1 Kesimpulan
Dari pembahasan yang telah dipaparkan sebelumnya, dapat disimpulkan
bahwa bentuk asli atau primal dari program linear dapat dibuat ke bentuk lainnya
yaitu bentuk dual yang saling keterkaitan dan berkebalikan. Hal ini bertujuan
untuk menambah informasi-informasi bagi pengambil keputusan. Apabila 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.
Untuk mengubah bentuk primal menjadi bentuk dual ada beberapa ketentuan
yang harus diikuti dan apabila bentuk dual didualkan kembali maka akang
menghasilkan bentuk primalnya.

3.2 Saran
Semua pembahasan pada makalah ini tentunya masih memiliki kekurangan.
Jadi, kami sarankan kepada para pembaca agar mempelajari materi ini dari
sumber yang lainnya juga. Teruslah belajar agar ilmu yang di dapat semakin luas,
dan ikatlah ilmu itu di dalam diri dengan berbagi ke teman-teman yang lain.

10
 DAFTAR PUSTAKA

[Link]
[Link]
[Link]
[Link]

11