penelitian operasional - programa linier - metode primal dual

PROGRAM LINIER-DUAL PRIMAL &

METODE SIMPLEKS METODE SIMPLEKS DUAL

Auditya Purwandini Sutarto, PhD

DUAL PRIMALDUAL PRIMAL

DUAL PRIMAL• Salah satu penemuan penting dalam awal pengembangan LP

adalah adanya konsep dualitas.

• Setiap masalah programa linier dapat dikaitkan dengan

masalah programa linier lain yang disebut DUAL.

• Suatu permasalahan maksimasi dapat dikaitkan dengan suatu• Suatu permasalahan maksimasi dapat dikaitkan dengan suatumasalah minimasi dan sebaliknya

• Masalah yang diberikan disebut dengan masalah primal, danmasalah yang berkaitan disebut masalah dual.

• Hubungan antara masalah original (primal) dengan dual

terbukti sangat bermanfaat dalam aplikasi LP.

• Untuk memahami masalah dual primal tinjau kasus berikut

Masalah Nutrisi

Setiap buahmengandung nutrienberbeda

Setiap buah harganyaberbedaberbeda

An apple a day keeps the doctor away – tapiharga apel mahal!

Tujuan customer adalahmemenuhi kebutuhannutrisi dengan hargatermurah

• Ambil kasus sederhana antara apel dan pisang

Kalori Vitamin Harga

($)

2 3 5

4 3 7

Min C = 5x1 + 7x2

s.t

2x1 + 4x2 100

3x1 + 3x2 90

• Konsumen harus mengkonsumsi minimal 100 unit kalori & 90 unit vitamin untuk mendapatkan nutrisiyang baik

• Tujuan konsumen adalah berapa banyak buah yang harus dibeli dengan harga termurah namunkebutuhan nutrisi terpenuhi

4 3 7 3x1 + 3x2 90

x1, x2 0

Jika dibawa ke dalam bentuk Matriks

Minimasi C = 5x1 + 7x2

s.t

2x1 + 4x2 100

Cj

Xj NiMi,j Xj

3x1 + 3x2 90

x1, x2 0

Primal

Tujuan konsumen membeli sejumlah buah yang mampu memenuhi kebutuhan nutrisi namunbiayanya minimal

Cj

NMHarga buahKebutuhan

XjNi

Mi,j Xj

Koefisien dalam tiapkolom yang menyatakanbanyaknya nutrisi dalamjenis makanan tertentu

Harga buahKebutuhan

harian

Banyaknya tiap jenisbuah

Dualitas

• Permasalahan Primal di atas dapatdipandang sebagai masalah dual.

• Misalkan tinjau dari sudut pandang seorang• Misalkan tinjau dari sudut pandang seorangsalesman yang bermaksud menjualsuplemen untuk setiap jenis buah

Dualitas

NiYi CjMj,i

YiNutrisi harianHarga tiap jenis buah

???

Koefisien dalamtiap barismenyatakanbanyaknya nutriendalam jenis buahtertentu

Apakah Yis dalammasalah dual?

Harga setiapnutrien!

???

•Masalah Primal : Tujuan konsumen adalahmembeli sejumlah buah tertentu dengan hargaminimum tetapi kebutuhan nutrisi terpenuhi

•Masalah Dual : Tujuan salesman adalahmenentukan harga setiap nutrien sehinggakeuntungannya maksimum namun harganya haruslebih murah daripada harga buahlebih murah daripada harga buah

Primal (Konsumen

Minimasi C = 5x1 + 7x2

s.t

2x1 + 4x2 100

3x1 + 3x2 90

x1, x2 0

Dual (Salesman)

Maksimasi P = 100y1 + 90y2

s.t

2y1 + 3y2 ≤ 5

4y1 + 3y2 ≤ 7

y1, y2 0

Masalah Primal

Maksimasi

s.t.

Minimasi

s.t.

n

jjj xcZ

1

,

m

iii ybW

1

,

n

ijij bxa , m

jiij cya ,

Masalah Dual

Masalah Dual menggunakan parameter yang tepat sama dengan parameter dalammasalah primal, namun lokasinya berbeda

j

ijij bxa1

,

i

jiij cya1

,

untuk untuk.,,2,1 mi .,,2,1 nj

untuk.,,2,1 mi

untuk .,,2,1 nj ,0jx ,0iy

Dalam Notasi Matriks

Masalah Primal

Maksimasi

subject to

Minimasi

subject to

bAx cyA

,cxZ ,ybW

Masalah Dual

.0x .0y

bAx cyA

Dimana dan merupakan vektor baris tapidan merupakan vektor kolom.

c myyyy ,,, 21 bx

CONTOH

Maks

s.t.

Min

s.t.

Masalah Primal Masalah Dual

,53 21 xxZ ,18124 321 yyyW

4x 33 yys.t.

1823 21 xx

122 2 x41x

0,0 21 xx

522 32 yy

33 3 y1y

0,0,0 321 yyy

Maks

s.t.

Masalah PrimalDalam bentuk Matriks

Masalah DualDalam bentuk Matriks

Min

s.t.

,5,32

1

x

xZ

401x

01

18

12

4

,, 321 yyyW

18

12

4

,

2

2

0

3

0

1

2

1

x

x

.0

0

2

1

x

x .0,0,0,, 321 yyy

5,3

2

2

0

3

0

1

,, 321

yyy

Primal-dual untuk Program linear Masalah Primal

Koefisien dari: SisiKanan

Masala

hD

ual

Ko

efi

sie

nd

ari

y

y

2

1

21

11

a

a

22

12

a

a

n

n

a

a

2

1

1x 2x nx

1b

2b

untu

kF

ung

siO

bye

kti

fM

inim

asi)

Sis

i

Kan

an

Masala

h

Ko

efi

sie

n

my

1c 2c ncVI VI VI

Koefisien untuk Fungsi Obyektif(Maksimasi)

mna2ma1ma

2

mb

Ko

efis

ien

untu

kO

bye

kti

f(M

inim

asi

Satu Masalah Masalah Lain

Konstrain Variabel

Fungsi Obyektif Sisi Kanan

i i

Hubungan antara Masalah Primal dan Dual

Minimasi MaksimasiMinimasi Maksimasi

Variabel

Variabel

Konstrain

Konstrain

0

0

0

0

Unrestricted

Unrestricted

• Solusi layak untuk masalah dual adalahkondisi yang menjadi solusi optimum padamasalah primal

• Nilai maksimum Z pada masalah primal merupakan masalah minimum W padamasalah dual

• Setiap pasang masalah primal dan dual dapat dikonversikan satu sama lain

• Dual dari suatu masalah dual selalumeurpakan masalah primal

Min W = yb,

s.t. yA c

y 0.

Dual Problem

Max (-W) = -yb,

s.t. -yA -c

y 0.

Converted to Standard Form

Min (-Z) = -cx,

s.t. -Ax -b

x 0.

Its Dual Problem

Max Z = cx,

s.t. Ax b

x 0.

Converted toStandard Form

CONTOH SOAL HUBUNGAN DUAL PRIMALDUAL PRIMAL

Minimasi

s.t.

64.06.0

65.05.0

7.21.03.0

21

21

21

xx

xx

xx

0,0 21 xx

21 5.04.0 xx

Minimasis.t.

][y 64.06.0

][y 65.05.0

][y 65.05.0

][y 7.21.03.0

321

-221

221

121

xx

xx

xx

xx

0,0 21 xx

21 5.04.0 xx

Maxs.t.

.0,0,0,0

5.04.0)(5.01.0

4.06.0)(5.03.0

6)(67.2

3221

3221

3221

3221

yyyy

yyyy

yyyy

yyyy

Maxs.t.

.0,edunrestrict :,0

5.04.05.01.0

4.06.05.03.0

667.2

321

321

321

321

yyy

yyy

yyy

yyy

Bawalah persamaan primal berikut kedalam bentuk dual dan pecahkanmenggunakan tabel simpleks

Maksimasi

s/t102 xxx

321 4125 xxxZ

0,,

832

102

321

321

321

xxx

xxx

xxx

Bentuk baku

Maksimasi

S.t.

832

102

321

321

Axxx

Sxxx

MASxxxZ 04125 321

[y1]

[ y2]

0

0

0

0

0

832

3

2

1

321

A

S

x

x

x

Axxx [ y2]

edunrestrict ,0

432

122

52

21

21

21

21

yy

yy

yy

yy

21 810 yyW

Bentuk baku

Minimasi

s/t

Minimasi

s/t

0,,

4 332

12 2

5 22

221

33221

22221

11221

yyy

Auyyy

Auyyy

Auyyy

32132121 000810 MAMAMAuuuyyW

[x1]

[ x2]

[ x3]

Tabel Simpleks awal dan akhir (optimum) untuk BentukPrimal

BasisBasis xx11 xx22 xx33 ss AA SisiSisi KananKanan

ZZ --5 5 –– 2M2M 12 + M12 + M --4 4 –– 3M3M 00 00 --8M8M

ss 11 22 11 11 00 1010

AA 22 --11 33 00 11 88AA 22 --11 33 00 11 88


ZZ 00 00 3/53/5 29/529/5 --2/5 + M2/5 + M 54 4/5 54 4/5

xx22 00 11 --1/51/5 2/52/5 --1/51/5 12/512/5

xx11 11 00 7/57/5 1/51/5 2/52/5 26/526/5

Tabel Simpleks Awal dan Akhir (Optimum) Bentuk Dual)

BasisBasis yy11 yy22’’ yy22”” uu11 uu22 uu33 AA11 AA22 AA33 SisiSisi

KananKanan

WW 10+4M10+4M --8+4M8+4M 8 8 –– 4M4M --MM --MM --MM 00 00 00 21M21M

AA11 11 22 --22 --11 00 00 11 00 00 55

AA22 22 --11 11 00 --11 00 00 11 00 1212

AA33 11 33 --33 00 00 --11 00 00 11 44AA33 11 33 --33 00 00 --11 00 00 11 44

BasisBasis yy11 yy22’’ yy22”” uu11 uu22 uu33 AA11 AA22 AA33 SisiSisi

KananKanan

WW 00 00 00 --26/526/5 --12/512/5 00 26/526/5--MM 12/512/5--MM --MM 54 4/554 4/5

uu33 00 00 00 --7/57/5 1/51/5 11 7/57/5 --1/51/5 --11 3/53/5

yy22”” 00 --11 11 2/52/5 --1/51/5 00 --2/52/5 1/51/5 00 2/52/5

yy11 11 00 00 --1/51/5 --2/52/5 00 1/51/5 2/52/5 00 29/529/5

Variabel Awal (Basis pada tabel simplekss A


ZZ 00 00 3/53/5 29/529/5 --2/5 + M2/5 + M 54 4/5 54 4/5

xx22 00 11 --1/51/5 2/52/5 --1/51/5 12/512/5

xx11 11 00 7/57/5 1/51/5 2/52/5 26/526/5

Tinjau kembali tabel simpleks akhir untuk BentukPrimal

• Oleh karena y1 - 0 = 29/5 dan y2 + M = -2/5 + M maka y1 = 29/5 dan y2 = -2/5 . Hal ini sama dengan hasil yang diperoleh pada tabel simpleks akhir bentuk dual

Variabel Awal (Basis pada tabel simpleksawal) Bentuk Primal

s A

Koefisien persamaan Z tabel optimum 29/5 -2/5 + M

Selisih koefisien sisi kiri dan sisi kananvariabel dual yang berhubungan denganvariabel basis awal bentuk primal

y1 - 0 y2 + M

Koefisien Fungsi Tujuan

Fungsi Tujuan Primal MAsxxxZ 04125 321

52 21 yy Konstrain Dual [x1]

edunrestrict

,0

432

122

2

2

1

21

21

y

My

y

yy

yy

[ x2]

[ x3]

[ s]

[ A]

BasisBasis yy11 yy22’’ yy22”” yy33 yy44 yy55 AA11 AA22 AA33 SisiSisi

KananKanan

WW 00 00 00 --26/526/5 --12/512/5 00 26/526/5--MM 12/512/5--MM --MM 54 4/554 4/5

yy55 00 00 00 --7/57/5 1/51/5 11 7/57/5 --1/51/5 --11 3/53/5

yy22”” 00 --11 11 2/52/5 --1/51/5 00 --2/52/5 1/51/5 00 2/52/5

yy11 11 00 00 --1/51/5 --2/52/5 00 1/51/5 2/52/5 00 29/529/5

Tinjau kembali tabel simpleks akhir untuk BentukDual

• Dengan mengabaikan M maka diperoleh x1 = 26/5 dan x2

=12/5, dan x3 = 0.

yy11 11 00 00 --1/51/5 --2/52/5 00 1/51/5 2/52/5 00 29/529/5

Variabel Awal (Basis) pada tabel simpleks awal Bentuk Dual

AA11 AA22 AA33

Koefisien persamaan W tabel optimum 26/5 - M 12/5 - M - M

Variabel dual yang berhubungan denganvariabel basis awal bentuk primal

x1 x2 x3

KOMPUTASI PRIMAL DUALKOMPUTASI PRIMAL DUAL

Iterasi 0 (awal) Bentuk Primal


ZZ --5 5 –– 2M2M 12 + M12 + M --4 4 –– 3M3M 00 00 --8M8M

ss 11 22 11 11 00 1010

AA 22 --11 33 00 11 88


ZZ --7/37/3 --40/340/3 00 00 4/3 +M4/3 +M 32/332/3

ss 1/31/3 7/37/3 00 11 --1/31/3 22/322/3

xx33 2/32/3 --1/31/3 11 00 1/31/3 8/38/3

Iterasi 1


ZZ --3/73/7 00 00 40/740/7 --4/7 + M4/7 + M 368/7368/7

xx22 1/71/7 11 00 3/73/7 --1/71/7 22/722/7

xx33 5/75/7 00 11 1/71/7 2/72/7 26/726/7

Iterasi 2


ZZ 00 00 3/53/5 29/529/5 --2/5 + M2/5 + M 54 4/5 54 4/5

xx22 00 11 --1/51/5 2/52/5 --1/51/5 12/512/5

xx11 11 00 7/57/5 1/51/5 2/52/5 26/526/5

Iterasi 3 (Optimum)

Representasi Skematis Tabel Simpleks

Variabel basis awal

Obyektif

MatriksInvers

Kolom konstrain

Konstrain

Perhitungan Kolom Konstrain

• Untuk setiap iterasi simpleks (primal atau dual), elemen di kolom sisi kiri atau kanan dari konstraintabel dapat dihitung sebagai:

original

model dalam

Kolom

iterasi

dalam Invers

iterasi

dalam

Kolom

ii

xi

• Ambil contoh bentuk primal. Variabel basis awaladalah s dan A. Untuk mencari koefisien x1 pada iterasi1, lihat matriks invers pada tabel simpleks iterasi 1


ZZ --7/37/3 --40/340/3 00 00 4/3 +M4/3 +M 32/332/3

ss 1/31/3 7/37/3 00 11 --1/31/3 22/322/3ss 1/31/3 7/37/3 00 11 --1/31/3 22/322/3

xx33 2/32/3 --1/31/3 11 00 1/31/3 8/38/3

32

31

2

1

310

311

original

model dalam

Kolom

1 iterasi

dalam Invers

1 iterasi

dalam

Kolom 1x

• Selanjutnya tinjau iterasi 2 dan kolom kanan yang bersesuaian


ZZ --3/73/7 00 00 40/740/7 --4/7 + M4/7 + M 368/7368/7

xx22 1/71/7 11 00 3/73/7 --1/71/7 22/722/7

xx33 5/75/7 00 11 1/71/7 2/72/7 26/726/7

726

722

8

10

7271

7173

original

model dalam

Kolom

iterasi

dalam Invers

iterasi

dalam

kanan Kolom

ii

Perhitungan Baris Obyektif

nbersesuaia yang dual

konstrain dari

kanan Ruas

nbersesuaia yang dual

konstrain dari

kiri Ruas

obyektif fungsi

dalam

Elemen j x

• Untuk setiap iterasi simpleks primal, elemen variabel xj

dalam persamaan fungsi obyektif dapat dihitung:

• Koefisien z dari x1 = y1 + 2y2 – 5

• Koefisien z dari x2 = 2y1 - y2 - 2

• Koefisien z dari x3 = y1 + 3y2 - 4

• Koefisien z dari s = y1 - 0

• Koefisien z dari A = y2 – (-M) = y2 + M

• Dengan menerapkan rumus ini pada pasangan masalahprimal dual diatas, diperoleh persamaan berikut

Konstrain Dual

iii

iterasi

dalam invers

iterasi dalam

primal basis variabel

original obyektifKoefisien

iterasi

dalam

dual variabelNilai

• Untuk menghitung koefisien diatas secara numerik, kitamemerlukan nilai numerik untuk variabel dual y1 dan y2 . Karena koefisien fungsi obyektif berubah-ubah pada tiapiterasi, kita mengharapkan nilai y1 dan y2 juga berubahpada tiap iterasi

iii

iterasi iterasi dalam iterasi

• Koefisien Obyektif Original (Awal) untuk variabel basis bentuk primal diatur dalam bentuk vektor baris dimanaelemen-elemennya diambil dalam urutan yang samadengan variabel basis di kolom basis pada tabel simpleks. Sebagai contoh, tinjau kembali tabel simpleks primal, maka vektor baris yang berhubungan dengan formula diatas (perhatikan urutan dalam setiap kasus)

Iterasi 1


ZZ --7/37/3 --40/340/3 00 00 4/3 +M4/3 +M 32/332/3

ss 1/31/3 7/37/3 00 11 --1/31/3 22/322/3

xx33 2/32/3 --1/31/3 11 00 1/31/3 8/38/3

• Iterasi 0 : (koefisien s, R) = (0, -M)

• Iterasi 1 (koefisien s, x3) = (0, 4)

• Iterasi 2 (koefisien x2, x3)= (12, 4)

• Iterasi 3 (koefisien x2, x1 )= (12, 5)

MASxxxZ 04125 321Fungsi Tujuan

• Sebagai contoh untuk mencari nilai variabel dual padaiterasi ke-i, tinjau koefisien persamaan fungsi obyekfit zpada iterasi ke-3 (optimum) dari tabel simpleks primal

3 iterasi

dalam invers

3 iterasi dalam ,,

original obyektifKoefisien

3 iterasi

dalam

dual variabelNilai

12 xx

,5/2,5/291/5-2/5

12,5dual Nilai yy

21 ,5/2,5/295/25/1

1/5-2/512,5dual Nilai yy

Dalam iterasi ke-3

• Koefisien x1 dalam z = y1 + 2y2 - 5 = 29/5+2(-2.5) – 5 = 0

• Koefisien x2 dalam z = 2y1 - y2 – 12 = 2(29/5) – (- 2/5) – 12 = 0

• Koefisien x3 dalam z = y1 + 3y2 – 4 = 29/5+3(-2/5) – 4 = 3/5

• Koefisien s dalam z = y1 – 0 = 29/5 – 0 = 29/5

• Koefisien A dalam z = y2 - (-M) = -2/5 + M

METODE SIMPLEKS DUALMETODE SIMPLEKS DUAL

Simpleks Dual

• Dalam metode simpleks dual, pemecahandimulai tidak layak (feasible) dan optimal (bandingkan dengan pemecahan awal(bandingkan dengan pemecahan awalmetode primal, yaitu layak tetapi tidakoptimal)

• Tinjau pemecahan secara grafis terlebihdahulu dari kasus di atas

Tinjau masalah LP berikut

• Minimasi

• S/t323 21

xx

21 23 xxZ

0,

33

634

21

21

21

xx

xx

xx

Bentuk baku

• Kalikan persamaan konstrain pertama dankedua dengan -1 untuk mengubah variabelsurplus menjadi variabel slack

• Minimasi 21 23 xxZ • Minimasi

• S/t

0,,,,

3 3

6 34

3 23

32121

321

221

121

sssxx

sxx

sxx

sxx

21

• Pemecahan dasar awal menghasilkan s1 = -1, s2 =- 6, dan s3=3. Pemecahan ini tidak layakTAPI optimal (bahkan lebih baik darioptimal!) karena nilai Z = 0

• Gagasan dari metode simpleks dual adalahberangkat dari interasi awal yang tidak layakberangkat dari interasi awal yang tidak layakdan (lebih baik daripada) optimal ke iterasiberikutnya ke arah ruang layak (feasible region) tanpa kehilangan sifat optimalitas

X2

3 Optimum

x1 = 3/5, x2 = 6/5,

A D C

A B C

X1

2

1

0

0 1 2

Z = 21/5

3

DA

C

B

Tabel awal simpleks

BasisBasis xx11 xx22 s1 s2 s3 RuasRuasKananKanan

ZZ --33 --22 00 00 00 00

s1 --33 --11 11 00 00 --33

s2 --44 --33 00 11 00 --66

• Baris tujuan telah memenuhi kondisi optimalitas namun tidaklayak (s1 dan s2 negatif)

s2 --44 --33 00 11 00 --66

s3 11 11 00 00 11 33

Pemilihan Variabel Masuk danVariabel Keluar

• Untuk menyingkirkan ketidaklayakan ini, variabel basis yang negatif kita keluarkan, yaitu s1 atau s2 . Pilih variabelyang paling negatif agar pemecahan yang layak tercapai

Variabel Keluar

lebih cepat s2 = -6

• Pemilihan variabel masuk dipilih dengan mengambil rasiokoefisien sisi kiri dari persamaan z dengan koefisien yang bersesuaian dalam persamaan variabel keluar. Rasiodengan penyebut positif atau nol disingkirkan agar kondisioptimalitas terjaga. Variabel masuk dipilih dari yang memiliki rasio terkecil

Variabel Masuk

BasisBasis xx11 xx22 s1 s2 s3 RuasRuas

VariabelVariabel xx11 xx22 s1 s2 s3

persamaan z --33 --22 00 00 00

persamaan s2 --44 --33 00 11 00

Rasio 3/43/4 2/32/3


ZZ --1/31/3 00 00 --2/32/3 00 44

s1 --5/35/3 11 11 --1/31/3 00 --11

x2 4/34/3 00 00 --1/31/3 00 22

s3 --1/31/3 00 00 1/31/3 11 11

RasioRasio 1/51/5 -- -- 22 --

Tabel simpleks final


ZZ 00 00 --1/51/5 --3/53/5 00 21/521/5

x1 11 00 --3/53/5 1/51/5 00 3/53/5

x 00 11 4/54/5 --3/53/5 00 6/56/5

• Tabel simpleks final menghasilkan pemecahanyang layak dan optimal yaitu x1 = 3/5, x2 =6/5, danZ = 21/5

x2 00 11 4/54/5 --3/53/5 00 6/56/5

s3 00 00 --1/51/5 2/52/5 11 6/56/5

• Kondisi Kelayakan

Leaving variable adalah variabel basis yang memiliki nilaipaling negatif (jika sama, tentukan secara sembarang). Jikasemua variabel basis adalah non negatif, proses berakhir

• Kondisi Optimalitas

Entering variable adalah variabel non basis yang berkaitandengan rasio terkecil jika meminimumkan atau nilaiabsolut terkecil dari rasio jika memaksimumkan (jikaabsolut terkecil dari rasio jika memaksimumkan (jikasama, tentukan secara sembarang). Rasio ditentukandengan membagi sisi kiri dari persamaan z dengankoefisien negatif yang bersesuaian dalam persamaandengan koefisien negatif yang bersangkutan denganvariabel keluar. Jika semua penyebut adalah nol ataupositif, tidak terdapat pemecahan yang layak

QUIZ PENELITIAN OPERASIONAL 1

1. Bawalah permasalahan primal berikut ke dalambentuk dual

2. Pecahkan masalah primal menggunakan Metodesimplekssimpleks

4

163

2532

321

321

321

xxx

xxx

xxx

Maksimasi

s.t.

321 34 xxxZ

edunrestrict ,0,0 321 xxx

penelitian operasional - programa linier - metode primal dual

Education