PROGRAM LINIER
TEORI DUALITAS (PRIMAL-
Oleh Kelompok 6
DUAL)
Dosen pengampu : Arezqi Tunggal Asmana,
[Link]., [Link].
NAMA KELOMPOK:
Dinda Khusnul Khotimah
(22031043)
Selvi Aulia (22031014)
Siti Faidah (23031005)
Ahmad Nur Shodiq (22031017)
Lukmanul Hakim ( )
PENGERTIAN
• Dari sudut pandang teoritis dan praktis, teori dualitas adalah salah satu
konsep penting dan menarik dalam program linear.
• Rumus permasalahan program linear terdiri dari primal dan dual, adapun
pada teori dualitas setiap masalah program linear memiliki program linear
yang diasosiasikan yang disebut dual
• Solusi pada model dual akan memberikan informasi tentang sumber yang
digunakan
• Model primal akan menghasilkan solusi dalam bentuk jumlah laba
• Model dual akan menghasilkan informasi mengenai nilai(harga)
BENTUK TEORI
DUALITAS
Bentuk dalam analisis program linier ada dua, yaitu :
1. Bentuk primal yaitu bentuk awal persamaan program linier (memberikan
solusi berupa besarnya keuntungan dari pembuatan barang atau biaya yang
diperlukan untu pembuatan barang tersebut)
2. Bentuk dual yaitu bentuk ganda dari persamaan program linier
(menghasilkan informasi mengenai nilai (harga) dari sumber-sumber yang
membatasi pencapaian keuntungan )
Bentuk teori dualitas
Kemudian bentuk standar (baku) program linear primal-dual, yaitu
Primal Dual
Fungsi tujuan : Maksimumkan Fungsi tujuan : Minimumkan
Z = c1 x1 +c2 x2 + … +cn xn W = b1y1 +b2y2 +… +bmym
Fungsi Kendala : α11y1 + α21y2 + … + αm1 ym ≤ c1
Fungsi Kendala : α11x1 + α12x2 + … + α n xn ≤ b1 α12y1 + α 22y2 + … + αm2ym ≤ c2
αm1y1 + αm2 x2 + … + αmnxm ≤ cm
α21x1 + α 22x2 + … + a2nxn ≤ b2
y1, y2, …, ym ≥ 0
αm1x1 + αm2 x2 + … + αmnxn ≤bm y1, y2, dan ym disebut variable ganda. Masalah asli disebut masalah primal.
x1, x2, …, xn ≥ 0
Matriks standar (baku) program linear primal ganda
Dual
Primal Fungsi tujuan ; Minimumkan
Fungsi tujuan : Maksimumkan W = yb
Z = cx Fungsi kendala : yA ≤ c
Fungsi kendala : Ax ≤ b y≥0
X≥0 Dimana A adalah matriks ( m x n ), x adalah vector kolom
( n x 1 ), b adalah vector kolom (m x 1), dan c adalah vector
baris (1 x n).
Bukti teorema 1
Misalkan xº adalah Solusi fisibel (layak) dari
permasalahan primal.
Misalkan yº adalah Solusi fisibel dari permasalahan dual
Karena xº adalah Solusi fisibel dari primal maka
Teorema 1 A xº ≤ b dengan xº ≥ 0
Memaksimumkan karena yº adalah Solusi fisibel dari dual maka
Z = cx ; A x ; ≤ b ; x ≥ 0 yºA ≥ c dengan yº ≥ 0
Dan meminimumkan kita peroleh
yºAxº ≤ yºb dan yºAxº ≥ cxº
W = yb ; yA ≥ c ; y ≥ 0
maka
yºb ≥ yºAxº ≥ cxº
dengan demikian
yºb ≥ cxº sehingga w ≥ z
jadi w ≥ z terbukti
Teorema 2 Bukti teorema 1
misalkan x adalah sebarang solusi fisibel dari prim
‘’Jika ada solusi xº dan yº untuk
maka
program linear dual simetris
cx ≤ yº b
sehingga nilai yang sesuai dari
padahal dari hipotesis diperoleh
fungsi objektifnya adalah sama,
cxº = yº b
maka solusi yang sebenarnya
Sehingga untuk semua solusi fisibel primal berlaku
merupakan solusi optimal untuk
cx ≤ cxº
masalah mereka masing-masing’’
Jadi, xº adalah solusi optimal dari primal
Bukti teorema 3
Ketika kedua masalah primal dan ganda dimungkinkan, maka
dengan akibat 1 dan 2 dari teorema 1, kita memiliki batas bawah
Teorema 3
pada nilai minimum w dan batas atas pada nilai maksimum z
‘’jika masalah primal dan dual
Oleh karna itu primal dan dual harus mempunyai solusi optimal,
layak, maka keduanya memiliki
tetapi untuk menunjukkan bahwa pada optimal kedua masalah akan
solusi optimal sehingga nilai
memiliki nilai yang sama untuk fungsi tujuan.
optimal fungsi objektifnya sama’’
Bentuk-bentuk dalam primal
Bentuk simetris
dan dual
• Bentuk primal-dual simetris adalah persamaan linear yang disusun
dengan rapi dan memperhatikan keseimbangan bentuk.
• Program linear dikatakan simetri jika semua variabel dibatasi menjadi
non-negatif dan semua kendala adalah pertidaksamaan
• Dalam masalah maksimasi pertidaksamaan harus berada dalam bentuk
≤ , sedangkan dalam masalah minimasi harus berada dalam bentuk
≥
BENTUK-BENTUK DALAM PRIMAL
DAN DUAL
Contoh Bentuk simetris
PT maju jaya adalah sebuah perusahaan yang memproduksi meja dan kursi yang harus diproses
melalui perakitan dan pemolesan. Proses perakitan membutuhkan paling lama 60 jam kerja dan
proses pemolesan membutuhkan paling lama 48 jam kerja. Untuk menghasilkan 1 meja
dibutuhkan masing-masing 4 jam perakitan dan 2 jam untuk pemolesan, sedangkan untuk
menghasilkan 1 kursi dibutuhkan masing-masing 2 jam perakitan dan 6 jam pemolesan. Laba
untuk tiap meja $ 8 dan tiap kursi $ 6. tentukan laba maksimal yang diperoleh oleh PT Maju
Jaya !
ALTERNATIF JAWABAN :
PRODUK PROSES LABA $
Perakitan Pemolesan
Meja (x1) 4 2 8
kursi (x2) 2 6 6
Waktu yang dibutuhkan (jam) 60 48
A. Bentuk Simetris Primal
Fungsi Tujuan : Maksimumkan Bentuk Standar :
Z= + Fungsi Tujuan : Maksimumkan
Fungsi Kendala : Z= +
+ ≤ 60 Fungsi Kendala :
+ ≤ 48
, ≥0 + + = 60
+ + + = 48
,,, ≥0
Tabel 1 : Solusi Awal
8 6 0 0
Konstanta
Basis
Bentuk Kanonik :
Fungsi Kendala :
+ + = 60 0 4 2 1 0 60
+ + + = 48
,,, ≥0
0 2 6 0 1 48
8 6 0 0 Z=0
Tabel 2 : Ubah Basis Tabel 3 : Solusi Optimal
8 6 0 0 8 6 0 0
Konstanta Konstanta
Basis Basis
8 1 0 15 8 1 0 -
0 0 5 - 1 18 6 0 1 -
0 2 -2 0 Z = 120 0 0 - - Z=
Didapat Z = = 127,2
Jadi, laba sebesar $ 127,2 tidak bisa menjadi solusi optimal karena
meja dan kursi merupakan satuan utuh.
B. Bentuk Simetris Dual
Fungsi Tujuan : Minimumkan Bentuk Standar :
W= + Fungsi Tujuan : Minimumkan
W= +
Fungsi Kendala :
+ ≥8 Fungsi Kendala :
+ ≥6
, ≥0 + + =8
+ + +=6
,,, ≥0
Tabel 1 : Solusi Awal
60 48 0 0
Konstanta
Bentuk Kanonik : Basis
Fungsi Kendala :
+ + =8
+ + +=6 0 4 2 1 0 8
,,, ≥0
0 2 6 0 1 6
60 48 0 0 W=0
Tabel 2 : Ubah Basis Tabel 3 : Solusi Optimal
60 48 0 0 60 48 0 0
Konstanta Konstanta
Basis Basis
60 1 0 2 60 1 0 -
48 0 1 -
0 0 5 - 1 2
0 0 - - W=
0 18 -2 0 W = 120
Didapat Z = = 127,2
2. BENTUK ASIMETRIS
Tidak semua program linear berbentuk
simetris artinya ada yang asimetris. Bentuk Primal
primal-dual asimetris adalah sistem Fungsi Tujuan :
persamaan linear yang disusun dengan acak Z= + + + + +
atau tidak rapi dan tidak memperhatikan
keseimbangan bentuk. Misalkan :
Fungsi Kendala :
++ ≤ 300
+ ≤ 600
+ ≥ 200
+ ≥300
+ ≥400
,,,,≥0
PRIMAL
Fungsi Tujuan : Maksimumkan
Z= + + + + +
DUAL
FUNGSI KENDALA : Fungsi Tujuan : Minimumkan
≥ - 300 W= + +
- 600
+ ≥ 200 FUNGSI KENDALA :
+ ≥300 ≤2
+ ≥400 + ≤4
+ ≤3
,,,,≥0 ≤5
≤3
≤4
,,,, ≥0
KESIMPULAN
• Program linear dalam bentuk dualitas digunakan untuk melihat
keterkaitan masalah primal dan dualnya seperti pada hubungan
variabel, nilai tengah, dan fungsi batasan.
• Primal adalah bentuk asli dari suatu model program linear.
• Dual adalah bentuk alternatif dari model program linear yang
telah dibuat dan berisi informasi mengenai nilai-nilai sumber yang
biasanya membentuk sebagai fungsi kendala
• Masalah dualitas sendiri dapat diselesaikan oleh dua solusi, yaitu
commplementary basic solution dan dual simplek.
TERIM
KASIH
A