5.pl-dual

7/21/2019 5.PL-Dual

1/28

Programa Linier : Dual i tas dan A nal is is Sensi t iv i tas

BAB VI

PROGRAMA LINIER : DUALITAS DAN ANALISIS

SENSITIVITAS

6.1 Teori Dualitas

Teori dualitas merupakan salah satu konsep programa linier yang

penting dan menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang

melatarbelakangi teori ini adalah bahwa setiap persoalan programa linier

mempunyai suatu programa linier lain yang saling berkaitan yang disebut

dual, sedemikian sehingga solusi pada persoalan semula (yang disebut

"primal) juga memberi solusi pada dualnya.

Pendefinisian dual ini akan tergantung pada jenis pembatas, tanda-

tanda variabel, dan bentuk optimasi dari persoalan primalnya. Akan tetapi,

karena setiap persoalan programa linier harus dibuat dalam bentuk standar

lebih dahulu sebelum modelnya dipecahkan , maka pendefinisian dibawah ini

akan secara otomatis meliputi ketiga hal di atas.

Bentuk umum masalah primal dual adalah sebagai berikut :

Primal :Maksimumkan : z = c1x1+ c2x2+ . + cnxn

Berdasarkan pembatas :

a11x1+ a12x2+ . + a1nxnb1

a21x1+ a22x2+ . + a2nxnb2

.

.

.

am1x1+ am2x2+ . + amnxnbm

x1, x2, ., xn 0

7/21/2019 5.PL-Dual

2/28


Dual :

Minimumkan : w = b1y1+ b2y2+ . + bmym


a11y1+ a21y2+ . + am1ymc1

a12y1+ a22y2+ . + am2ymc2

.

.

.

a1ny1+ a2ny2+ . + amnymcn

y1, y2, . , ym 0

Kalau kita bandingkan kedua persoalan di atas, ternyata terdapat

korespondensi antara primal dengan dual sebagai berikut :

1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan bagi dual,

sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan

bagi dual.

2. Untuk tiap pembatas primal ada satu variaebl dual, dan untuk setiap

variabel primal ada satu pembatas dual.

3. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi

tujuannya.

4. Fungsi tujuan berubah bentuk (maksimasi menjadi minimasi dan

sebaliknya).

5. Setiap kolom pada primal berkorespondensi dengan baris (pembatas) pada

dual.

6. Setiap baris (pembatas) pada primal berkorespondensi dengan kolom pada

dual.

7. Dual dari dual adalah primal.

7/21/2019 5.PL-Dual

3/28


6.2 Hubungan Primal Dual

Nilai tujuan dalam suatu pasangan masalah primal dan dual harus

memenuhi hubungan berikut ini :

1. Untuk setiap pasangan pemecahan primal dual yang layak

imasimasalahdalam

tujuannilai

maksimasimasalahdalam

tujuannilai

min

2. Di pemecahan optimum untuk kedua masalah

imasimasalahdalam

tujuannilai

maksimasimasalahdalam

tujuannilai

min

Untuk menjelaskan hubungan antara primal dan dual, perhatikan

ilustrasi berikut ini :

Primal

Minimumkan : z = 16x1+ 30x2+ 36x3


2x1+ 3x2+ 2x3 60

2x1+ 5x2+ 3x3 80

x1, x2, x3 0

Soal ini kita selesaikan melalui penyelesaian dualnya, yakni :

Maksimumkan : w = 60y1+ 80y2


2y1+ 2y2 16

3y1+ 5y2 30

2y1+ 3y2 36y1, y2, y3 0

7/21/2019 5.PL-Dual

4/28


Karena soal ini hanya terdiri dari dua choice variabel sehingga dapat

diselesaikan dengan metode grafis, namun soal ini kita selesaikan dengan

metode simpleks, sebab dengan cara ini dari tabel akhir dapat kita baca

jawaban untuk persoalan primalnya. Untuk ini bentuk constraint di atas diubah

dulu menjadi persamaan dengan memasukkan slack variable t1, t2, dan t3(untuk primal problem ; slack/surplus variable kita pakai lambang S), yakni :

2y1+ 2y2 + t1 = 16

3y1+ 5y2 + t2 = 30

2y1+ 3y2 + t3 = 36

Sedangkan fungsi objectivenya ditulis dalam bentuk :

w - 60y1- 80y2+ 0 t1+ 0 t2+ 0 t3= 0

Dengan demikian penyelesaian dari persoalan diatas adalah sebagai berikut :

Basis y1 y2 t1 t2 t3 Solusi

t1 2 2 1 0 0 16

t2 3 5 0 1 0 30

t3 2 3 0 0 1 36

w -60 -80 0 0 0 0

t1 4/5 0 1 -2/5 0 4

y2 3/5 1 0 1/5 0 6

t3 1/5 0 0 -3/5 1 18

w -12 0 0 0 0 480

y1 1 0 5/4 -1/2 0 5

y2 0 1 -3/4 1/2 0 3

t3 0 0 -1/4 -1/2 1 17

w 0 0 15 10 0 540

7/21/2019 5.PL-Dual

5/28


Karena pada tabek di atas tidak terdapat lagi entry negatif pada baris w, maka

tabel ini merupakan tabel akhir dan fungsi objective telah mencapai nilai

optimal, yakni :

wmax= 540 untuk y1 = 5 unit, y2 = 3 unit dan t3 = 17 unit, yakni bahan yang tidakterpakai dari konstraint ketiga, sedangkan t1 = t2= 0.

Dari tabel ini dapat kita baca nilai x1, x2, dan x3 dari primal problem, yakni :

x1 = entry dari kolom t1 pada baris w, sehingga x1= 15



Nilai shoice variable dari primal ini kalau kita masukkan pada fungsi objective

dari primal harus cocok = 540, yakni :

Z = 16x1+ 30x2+ 36x3

= 16 (5) + 30 (10) + 36 (0) = 540

zmin = wmax

6.3 Sifat-sifat Primal Dual yang Penting

Sifat-sifat primal dua penting untuk dipahami terutama pada saat kita

membicarakan masalah analisis sensitivitas. Dengan menggunakan sifat-sifat

ini kita dapat menentukan nilai variabel-variabel tertentu dengan cara yang

sangat efisien. Ada empat sifat yang perlu diketahui, yaitu :

Sifat 1 : Menentukan ko efisien fung si tuju an variabel-variabel basis awal.Pada setiap iterasi solusi simpleks, baik primal maupun dual, koefisien

fungsi tujuan variabel-variabel basis awalnya dapat dicari dengan cara :

7/21/2019 5.PL-Dual

6/28


a. Mengalikan fungsi tujuan yang original dari variabel-variabel basis pada

iterasi yang bersangkutan dengan matriks di bawah variabel basis awal

pada iterasi yang bersangkutan. Koefisien ini biasa disebut simplex

multiplier.

multiplier

simplex

bersangkuyang

iterasipadaawal

basisiabel

bawahdimatriks

bersangkuyang

iterasipadabasisabel

idarioriginalyang

tujuanfungsikoefisien

tan

var

tan

var

b. Kurangi nilai-nilai simplex multiplier ini dengan fungsi tujuan yang original

dari variabel-variabel basis awal.

Sifat 2 : Menentukan koef is ien fungs i tu juan variabel-variabel no nbasis

awal.

Pada setiap iterasi dari persoalan primal, koefisien fungsi tujuannya

dapat ditentukan dengan menyubstitusikan simplex multiplier pada variabel-

variabel pembatas dari dual, kemudian mencari selisih antara ruas kiri dan ruas

kanan dari pembatas dual tersebut.

Sifat 3 : Menentukan n ilai ruas kanan (solu si) dari variabel-variabel basis.

Pada setiap iterasi, baik primal maupun dual, nilai ruas kanan (kolom

solusi) variabel-variabel basis pada iterasi yang bersangkutan dapat ditentukan

dengan cara sebagai berikut :

basisiabel

kananruas

kolommatriks

original

kananruas

kolommatriks

bersangku

yangiterasipada

awalbasisiabel

bawahdimatrikas

var

tan

var

7/21/2019 5.PL-Dual

7/28


Sifat 4 : Menentukan ko efisien pembatas.

Pada setiap iterasi, baik primal maupun dual, koefisien pembatas dari

setiap variabel dapat ditentukan dengan cara sebagai berikut :

tantan

var

bersangkuyang

iterasipadapembatas

koefisienkolom

darikolommatriks

original

yangpembatas

koefisienkolom

darikolommatriks

bersangku

yangiterasipada

awalbasisiabel

bawahdimatriks

Contoh :

Maksimumkan : z = 4x1+ 6x2+ 2x3


4x14x2 5

-x1+ 6x2 5

-x1+ x2+ x3 5

x1, x2, x3 0

Salah satu iterasi dari persoalan di atas adalah sebagai berikut :

Basis x1 X2 x3 S1 S2 S3 Solusi

x1 j m q 6/20 4/20 0 g

x2 k n r 1/20 4/20 0 h

S3 l p s 5/20 0 1 i

z d e f a b c t

Tentukanlah harga-harga a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, dan t

dengan menggunakan sifat-sifat primal dual.

7/21/2019 5.PL-Dual

8/28

7/21/2019 5.PL-Dual

9/28


i = 25/4

4. Sifat 4 :

00

1

11

4

1020/5020/420/1

020/420/6

j = 1

k= 0

l = 0

01

0

16

4

1020/5020/420/1

020/420/6

m = 0

n = 1

p = 0

1

0

0

1

0

0

1020/5

020/420/1

020/420/6

q = 0

r = 0

s = 1

Dengan demikian, t dapat dicari dengan memasukkan harga-harga g, h dan i

ke dalam persamaan z, sehingga diperoleh :

t = 4 (5/2) + 6(5/4) _ 0(25/4)

t = 70/4

6.4 Metode Dual Simpleks

7/21/2019 5.PL-Dual

10/28


Apabila pada suatu iterasi kita mendapat persoalan programa linier yang

sudah optimum (berdasarkan kondisi optimalitas), tetapi belum fisibel (ada

pembatas nonnegatif yang tidak terpenuhi), maka persoalan tersebut harus

diselesaikan dengan menggunakan metode dual simpleks. Syarat

digunakannya metode ini adalah bahwa seluruh pembatas harus merupakanketidaksamaan yang bertanda ( ), sedangkan fungsi tujuan bisa berupa

maksimasi atau minimasi.

Pada dasarnya metode dual simpleks ini menggunakan tabel yang sama

seperti metode simpleks pada primal, tetapi leaving variable dan entering

variable-nya ditentukan sebagai berikut :

1. Leaving variable(kondisi fisibilitas)

Yang menjadi leaving variable pada dual simpleks adalah variabel basis

yang memiliki harga negatif terbesar. Jika semua variabel basis telah

berharga positif atau nol, berarti keadaan fisibel telah tercapai.

2. Entering variable(kondisi optimalitas)

a. Tentukan perbandingan (rasio) antara koefisien persamaan z dengan

koefisien persamaan leaving variable. Abaikan penyebut yang positif

atau nol. Jika semua penyebut berharga positif atau nol, berarti

persoalan yang bersangkutan tidak memiliki solusi fisibel.

b. Untuk persoalan minimasi, entering variable adalah variabel dengan

rasio terkecil, sedangkan untuk persoalan maksimasi, entering variable

adalah variabel dengan rasio absolut terkecil.

Contoh :

Minimumkan : z = 2x1+ x2


3 x1+ x23

7/21/2019 5.PL-Dual

11/28


4x1+ 3x26

x1+ 2x23

x1, x20

Langkah pertama yang harus dilakukan ialah mengubah arah ketidaksamaan

pembatas sehingga bertanda ( ), kemudian menambahkan variabel-variabel

slack.

Diperoleh formulasi baru sebagai berikut :

Minimumkan : z = 2x1+ x2


-3x1- x2 + S1 = -3

-4x1- 3x2 + S2 = -6x1+ 2x2 + S3 = 3

x1, x2, S1, S2, S30

Tabel simpleks awalnya adalah :

Iterasi Basis x1 x2 S1 S2 S3 Solusi

S1 -3 -1 1 0 0 -3

0 S2 -4 -3 0 1 0 -6S3 1 2 0 0 1 3

z -2 -1 0 0 0 0

Perhatikan bahwa variabel-variabel basis awalnya tidak memberikan solusi

awal yang fisibel (S1 dan S2 berharga negatif), tetapi koefisien persamaan z

sudah memenuhi kondisi optimalitas.

Pada iterasi di atas, S2 (= -6) terpilih sebagai leaving variable, sedangkan

entering variabledipilih berdasarkan :

x1 x2 S1 S2 S3

7/21/2019 5.PL-Dual

12/28


Koefisien persamaan z -2 -1 0 0 0

Koefisien persamaan S2 -4 -3 0 1 0

Rasio 1/2 1/3 - - -

Dengan demikian, x2terpilih sebagai entering variable.Langkah berikutnya dilakukan dengan cara seperti biasa.

Iterasi Basis x1 x2 S1 S2 S3 Solusi

S1 -5/3 0 1 -1/3 0 -1

1 x2 4/3 1 0 -1/3 0 2

S3 5/3 0 0 2/3 1 -1

z -2/3 0 0 -1/3 0 2

x1 1 0 -3/5 1/5 0 3/52 x2 0 1 4/5 -3/5 0 6/5

S3 0 0 -1 1 1 0

z 0 0 -2/5 -1/5 0 12/5

Solusi optimal telah tercapai.

Metode dual simpleks ini juga sangat penting untuk digunakan dalam

analisis sensitivitas. Sebagai contoh, hal ini akan terjadi apabila suatu

pembatas baru ditambahkan ke dalam persoalan semula setelah persoalan itu

mencapai solusi optimum. Apabila ternyata bahwa pembatas baru ini tidak

terpenuhi oleh solusi optimum yang telah dicapai itu, maka persoalannya akan

menjadi optimum, tetapi tidak fisibel, sehingga untuk menyelesaikan

ketidakfisibelannya ini perlu digunakan metode dual simpleks.

6.5 Analisis Sensitivitas dengan Tabel Simpleks

7/21/2019 5.PL-Dual

13/28


Analisis sensitivitas adalah analisis yang dilakukan untuk mengetahui

akibat/pengaruh dari perubahan yang terjadi pada parameter-parameter LP

terhadap solusi optimal yang telah dicapai.

Ada enam tipe perubahan dalam analisis sensitivitas dengan menggunakan

tabel simpleks yaitu :1. Perubahan koefisien fungsi tujuan untuk variabel nonbasis.

2. Perubahan koefisien fungsi tujuan untuk variabel basis.

3. Perubahan pada ruas kanan suatu pembatas.

4. Perubahan kolom untuk suatu variabel nonbasis.

5. Penambahan suatu variabel atau aktivitas baru.

6. Penambahan suatu pembatas baru.

Dalam perubahan kasus-kasus di atas digunakan soal LP berikut :

Maksimumkan : z = 60 x1+ 30 x2+ 20 x3

Berdasarkan :

8 x1 + 6 x 2+ x3 48

4 x1 + 2 x2+ 1,5 x3 20

2 x1 + 1,5 x2+ 0,5 x3 8

x1, x2, x3 0

Tabel optimalnya adalah sebagai berikut :

BV x1 x2 x3 S1 S2 S3 Solusi

S1 0 -2 0 1 2 -8 24

x3 0 -2 1 0 2 -4 8

x1 1 1,25 0 0 -0,5 1,5 2

z 0 5 0 0 10 0 280

Dari tabel ini dapat didefinisikan beberapa hal sebagai berikut :

BV = 322131 ,,;,, SSxNBVxxS

7/21/2019 5.PL-Dual

14/28


1;

3

2

2

1

3

1

xmvektormerupakanyang

S

S

x

x

x

x

S

x NBVBV

1. Perubahan koef is ien fungsi tu juan untuk variabel nonb asis.

Kasus ini terjadi karena adanya perubahan, baik pada kontribusi

keuntungan maupun pada kontribusi ongkos dari kegiatan yang

direpresentasikan oleh variabel nonbasis. Pada contoh soal di atas, satu-

satunya variabel keputusan nonbasis adalah x2. Saat ini koefisien fungsi tujuan

x2 adalah c2= 30. Jika c2berubah, bagaimana pengaruhnya terhadap solusi

optimal ? Harga-harga c2manakah yang menyebabkan BV = 131 ,, xxS tetap

optimal ?

Kita tahu bahwa perubahan c2 dari 30 menjadi ( 30 + ) tidak

mengubah harga B -1dan b. Karena itu, ruas kanan untuk tabel BV, yaitu B-1b,

tidak akan berubah sehingga BV tetap fisibel. Karena c2 adalah variabel

nonbasis, maka CBV juga tidak akan berubah. Satu-satunya variabel yang

koefisien baris 0-nya akan berubah karena perubahan c2ini adalah x2.

Dengan demikian, BV akan tetap optimal jika c2 0, dan BV akan

menjadi suboptimal jika c20. Dalam hal terakhir ini, harga z mungkin dapat

diperbaiki dengan memasukkan x2ke dalam basis.

Dari contoh soal, kita tahu bahwa :

5303530

5,1

26

10100

10100

5,15,00

420

821

60200

2

1

csehingga

BC VB

7/21/2019 5.PL-Dual

15/28


Agar c20 dan BV tetap optimal, maka ( 5 - ) harus 0 atau 5.

Sebaliknya, harga c2akan 0 jika 5 sehingga BV tidak lagi optimal. Artinya,

jika harga c2 naik atau turun sebesar 5 atau kurang, maka BV akan tetap

optimal, tetapi jika naik atau turunnya lebih dari 5, maka BV tidak lagi optimal.

Misalnya, jika c2 = 40, solusi basis saat ini akan menjadi suboptimalkarena c2= -5 sehingga x2akan menjadi entering variable. Untuk mengetahui

solusi optimal yang baru, lanjutkan perhitungan dengan menggunakan metode

simpleks seperti biasa.

2. Perubahan koef is ien fungsi tu juan untuk variabel basis.

Mengubah koefisien fungsi tujuan variabel basis artinya mengubah CBV

sehingga beberapa koefisien pada baris 0 dari tabel optimal akan berubah.

Misalkan c1 berubah dari 60 menjadi ( 60 + ). Maka CBV yang baru

adalah [ 0 20 (60 + )] sehingga :

25,1530

5,1

2

6

5,1105,0100

.

:0

5,1105,0100

5,15,00

420

821

60200

22

1

2

1

caBCca

menjadibarisKoefisien

BC

BV

BV

b. Koefisien S2= elemen kedua dari CBVB-1

= 100,5

c. Koefisien S3= elemen ketiga dari CBVB-1

= 10 + 1,5

Dengan demikian, BV akan tetap optimal jika :

5 + 1,25 0 atau -4

100,5 0 atau 20

7/21/2019 5.PL-Dual

16/28


10 + 1,5 0 atau -(20/3)

Hal ini berarti bahwa solusi basis saat ini akan tetap optimal sepanjang -4,

20, dan -(20/3). Jika digambarkan, daerah harga-harga c1 yang

menyebabkan solusi basis saat ini tetap optimal adalah sebagai berikut :

-20/3 -(20/3)

-4 -4

20 20

Dengan kata lain, solusi basis saat ini akan tetap optimal jika -4

20. Artinya, jika c1turun sebesar 4 atau kurang, atau c1naik hingga 20, maka

solusi basis saat ini akan tetap optimal. Atau, sepanjang 56 = (60 4 ) c

(60 + 20) = 80, solusi basis saat ini akan tetap optimal, tetapi jika c156 atau

c180, maka solusi basis saat ini tidak lagi optimal. Jika solusi basis saat ini

tetap optimal, maka harga variabel keputusannya juga tidak akan berubah

karena B-1 b tidak berubah. Namun, nilai z optimal tentu saja akan berubah.

Contoh : jika c1= 70, maka z = 70 (2) + 20 (8) = 300.

3. Perubahan pada ruas kanan suatu pembatas.

Dari sifat-sifat primal dual kita tahu bahwa perubahan ruas kanan

pembatas ini tidak akan mengubahn baris 0 pada tabel optimal sehingga solusi

basis saat ini tidak akan menjadi suboptimal. Yang mungkin berubah adalah

ruas kanan pada tabel optimal. Tetapi, sepanjang ruas kanan setiap pembatas

pada tabel optimal tetap nonnegatif, solusi basis saat ini tetap fisibel dan

optimal. Dalam hal ini, yang perlu kita lakukan adalah menyubstitusikan harga-harga baru dari variabel keputusan ke dalam persamaan garis z sehingga

diperoleh harga z yang baru.

7/21/2019 5.PL-Dual

17/28

7/21/2019 5.PL-Dual

18/28


Misalkan kita mengubah b2menjadi 30. Ruas kanan yang baru adalah

sebagai berikut :

Karena x1= -3, sedangkan koefisien fungsi tujuan untuk baris 0 tidak berubah

(tetap memenuhi syarat optimalitas), maka untuk memperoleh solusi optimal

yang baru, kita harus mengunakan metode dual simpleks.

4. Perubahan kolom untuk su atu variabel nonbasis.

Pada contoh soal, variabel nonbasis adalah x2yang mempunyai kolom :

5,1

2

6

2a

Apa yang terjadi jika kolom tersebut berubah menjadi :

2

2

5

2a

Kita tahu bahwa perubahan ini tidak akan mengubah baik B ataupun b

sehingga ruas kanan tabel optimal juga tidak akan berubah. Yang akan

berubah adalah c2, yaitu jika c20. Tetapi, jika c20, maka solusi basis saat

ini akan tetap optimal. Dengan berubahnya kolom a2, maka :

0343

2

2

5

101002

c

Karena c2 0, maka solusi basis saat ini tidak lagi optimal. Kolom a 2 untuk

pembatas pada tabel optimal menjadi :

1

12

28

8

22

48

5,15,00

420

8211

1

3

1

bB

x

x

S

7/21/2019 5.PL-Dual

19/28


2

4

7

2

2

5

5,15,00

420

821

2

1 aB

Karena c20, maka x2akan menjadi variabel basis pada solusi optimal yang

baru.Jika perubahan kolom terjadi pada variabel basis, maka B dan CBV

mungkin berubah sehingga baria 0 dan ruas kanan dari tabel optimal juga

mungkin berubah. Dalam hal ini, sebaiknya kita memecahkan kembali

persoalannya dari awal.

5. Penambahan suatu variabel atau aktivitas baru.

Pada situasi tertentu, kita mungkin memproleh kesempatan untukmelakukan satu atau beberapa aktivitas baru. Dalam hal ini, kita harus dapat

menentukan apakah aktivitas baru ini sebaiknya dilakukan atau tidak, dengan

mempertimbangkan kebaikan/keburukan aktivitas baru tersebut terhadap solusi

basis yang telah diperoleh.

Sebagai contoh, misalkan akan dibuat produk ke-4 sehingga formula

menjadi :

Maksimumkan : z = 60 x1+ 30 x2+ 20 x3 + 15 x4

Berdasarkan :

8 x1 + 6 x 2+ x3 + x4 48

4 x1 + 2 x2+ 1,5 x3 + x4 20

2 x1 + 1,5 x2+ 0,5 x3 + x4 8

x1, x2, x3, x40

Kita tahu bahwa ruas kanan seluruh pembatas dan koefisien baris 0 untuk

variabel yang lama tidak akan berubah. Karena itu, solusi basis saat ini akan

tetap optimal jika c4 0.

Dari formulasi di atas kita peroleh :

7/21/2019 5.PL-Dual

20/28


05151

1

1

101004

c

Karena c4 0, maka solusi basis saat ini tetap optimal sehingga produk ke-4

sebaiknya tidak dibuat. Alasannya adalah karena untuk setiap unit produk ke-4yang dibuat, kita hanya akan mengeluarkan ongkos sebesar 5, tanpa

memperoleh keuntungan apa-apa.

6. Penambahan suatu pemb atas baru.

Jika suatu pembatas baru ditambahkan, maka kita akan berada pada

salah saru dari ketiga kasus berikut ini :

Kasus 1 : Solusi optimal saat ini memenuhi pembatas baru.Kasus 2 : Solusi optimal saat ini tidak memenuhi pembatas baru, tetapi

persoalan tetap mempunyai solusi fisibel.

Kasus 3 : Pembatas baru menyebabkan persoalan tidak mempunyai solusi

fisibel.

Contoh kasus 1 :

Misalkan pada contoh soal ditambahkan pembatas baru x1 + x2 + x3 11.

Maka solusi basis saat ini, yaitu x1 = 2, x2 = 0, x3 = 8 dan z = 280 akan

memenuhi pembatas baru tersebut. Karena solusi basis saat ini tetap fisibel

dan z tetap 280, maka solusi ini tetap optimal.

Contoh kasus 2 :

Misalkan pada contoh soal ditambahkan pembatas x21. Karena saat ini x2=

0, maka solusi saat ini tidal lagi fisibel. Untuk menentukan solusi optimal yang

baru, ubahlah ketidaksamaan x21 menjadi persamaan x2S4= 1, kemudian

kalikan dengan (-1) sehingga diperoleh x2+ S4= -1. Tambahkan pembatas

ini ke dalam tabel sehingga diperoleh :

7/21/2019 5.PL-Dual

21/28


BV x1 x2 x3 S1 S2 S3 S4 Solusi

S1 0 -2 0 1 2 -8 0 24

x3 0 -2 1 0 2 -4 0 8

x1 1 1,25 0 0 -0,5 1,5 0 2

S4 0 -1 0 0 0 0 1 -1z 0 5 0 0 10 0 0 280

Lakukan dual simpleks sehinga diperoleh tabel optimal :


S1 0 0 0 1 2 -8 -2 26

x3 0 0 1 0 2 -4 -2 10

x1 1 0 0 0 -0,5 1,5 1,25 0,75x2 0 1 0 0 0 0 -1 1

z 0 0 0 0 10 10 5 275

Maka, jika pembatas x2 1 ditambahkan terhadap persoalan semula, solusi

optimal akan menjadi z = 275, x3= 10, x1= 0,75, dan x2= 1.

Contoh kasus 3 :Misalkan pada contoh soal ditambahkan pembatas x1 + x2 12 sehingga

diperoleh x1+ x2S4= 12 atau x1x2+ S4= - 12. Tabelnya menjadi :


S1 0 -2 0 1 2 -8 0 24

x3 0 -2 1 0 2 -4 0 8

x1 1 1,25 0 0 -0,5 1,5 0 2

S4 0 -1 0 0 0 0 1 -12

z 0 5 0 0 10 0 0 280

7/21/2019 5.PL-Dual

22/28

7/21/2019 5.PL-Dual

23/28

7/21/2019 5.PL-Dual

24/28


b. Bagaimana jawaban optimum yang baru jika koefisien ruas kanan

persamaan semula diubah

130

110

20

100

120

15

menjadidari

c. Bagaimana jika fungsi objectivenya menjadi

z = 6x1+ 5x2+ 9x3+ 12x4

d. Bagaimanakah jawaban optimum yang baru jika ditambahkan variabel

baru x5yang mempunyai koefisien sebagai berikut :

- dalam fungsi objective = 13 ?

- dalam fungsi konstrain :

18

1

1

2. Sebuah persoalan diformulasikan sebagai berikut :

Maksimumkan : z = 2x1+ 4x2+ x3

Berdasarkan :

2x1+ 3x2 - 2x3 12

2x1+ x2+ x3 10

2x1+ 2x2+ x3 16

x1, x2,x3 0

Pada suatu iterasi diperoleh keadaan sebagai berikut :

Basis x1 x2 x3 S1 S2 S3 Solusi

x2 1/2 0 0 6

S2 -1/2 1 0 4

S3 -1 0 1 4

z 2 0 0

7/21/2019 5.PL-Dual

25/28


Dengan mempergunakan sifat-sifat primal dual, lengkapilah iterasi di atas,

dan lanjutkan untuk mendapatkan nilai z maksimum. Tentukan variabel

basis optimum.

3. Perhatikan persoalan di bawah ini :Maksimumkan : z = 3x1+ 2x2

Berdasarkan :

x1+ 2x2 6

2x1+ x2 8

-x1+ x2 1

x2 2

x1, x2 0

Jika jawaban optimum persoalan di atas adalah :

Basis x1 x2 S1 S2 S3 S4 Solusi

x1 0 1 2/3 -1/3 0 0 4/3

x2 1 0 -1/3 2/3 0 0 10/3

S3 0 0 -1 1 1 0 3

S4 0 0 -2/3 1/3 0 1 2/3z 0 0 1/3 4/3 0 0 38/3

Bagaimanakah jawaban optimum yang baru jika :

a. Ruas kanan dari pembatas ke-1 dan ke-2 masing-masing menjadi 7 dan

4 ?

b. Ditambahkan pembatas baru x1 4 ?

c. Fungsi tujuan berubah menjadi z = 3x1+ 2x2d. Ditambahkan variabel baru x3 dengan koefisien pada fungsi tujuan

sebesar 3/2, sedangkan koefisien pada konstrain ke-1, ke-2, dan ke-3

masing-masing adalah 3/4, 3/4, dan1 dimana x2 0

7/21/2019 5.PL-Dual

26/28


4. Perhatikan persoalan program linier di bawah ini :


Berdasarkan :

x1+ 5x2 + 2x3 = 30

x1 - 5x2 - 6x3 40x1, x2,x3 0

Jika solusi optimum persoalan di ats adalah :

Basis x1 x2 x3 A1 S1 Solusi

x1 1 5 2 1 0 30

S1 0 -10 -8 -1 1 10

z 0 23 7 5+M 0 150

Bagaimanakah persoalan dualnya, dan berapakah solusi optimum variabel-

variabel dual tersebut ?

5. Formulasi suatu persoalan programa linier adalah sebagai berikut :

Maksimumkan : z = ax1+ bx2+ cx3+ dx4+ ex5

Berdasarkan :

a1x1+ b1x2+ c1x3+ d1x4+ e1x5 F

a2x1+ b2x2+ c2x3+ d2x4+ e2x5 G

a. Jika iterasi optimum dari persoalan di atas adalah :

Basis x1 x2 x3 x4 x5 S1 S2 Solusi

x5 -54/138 0 30/138 60/138 1 24/138 -1/23 114/138

x2 -15/23 1 16/23 9/23 0 -1/23 6/23 323/23

z 630/138 0 294/138 36/138 0 456/138 119/23 49362/138

Bagaimanakah formulasi persoalan ini yang sebenarnya ?

7/21/2019 5.PL-Dual

27/28


b. Jika pada solusi optimum itu ditambahkan konstrain baru

6x1+ 2x2 + 2x3 + 2x4 + 2x5 40 bagaimanakah solusi optimum yang

baru ?

6. Tentukan dual dari persoalan berikut :


Berdasarkan :

2x1+ 2x2 + 8x3 30

3x1+ 2x2 + 2x3 40

x1, x2,x3 0

Kemudian selesaikan soal ini dan tunjukkan marginal value dari bahan baku

pada konstraint pertama dan kedua.

7. Tentukan dual dari persoalan berikut :


Berdasarkan :

2x1+ 4x2 + 10x3 24

5x1+ x2 + 5x3 8

x1, x2,x3 0

Kemudian selesaikan dualnya dengan metode Simplex dan tunjukkan

marginal value dari konstraint pertama dan kedua.

8. Sebuah perusahaan memproduksi jaket dan tas kulit. Sebuah jaket

memerlukan 8 meter persegi kulit dan sebuah tas hanya menggunakan 3

meter persegi. Persyaratan kerja untuk kedua produk tersebut masing-

7/21/2019 5.PL-Dual

28/28


masing adalah 12 jam dan 4 jam. Harga pembelian kulit adalah $8 per

meter persegi dan biaya tenaga kerja diperkirakan sebesar $15 per jam.

Persediaan kulit mingguan saat ini dan tenaga kerja dibatasi sampai 1200

meter persegi dan 1800 jam. Perusahaan menjual jaket dan tas masing-

masing dengan harga $350 dan $ 120. Tujuannya adalah untukmenentukan jadwal produksi yang memaksimumkan pendapatan bersih.

Perusahaan sedang mempertimbangkan untuk mmeperluas produksinya.

Berapa harga pembelian maksimum yang harus dibayar perusahaan untuk

kulit ? Untuk tenaga kerja ?

9. Tentukan dual dari persoalan dibawah ini :


Berdasarkan :

2x1+ 6x2 + 5x3 4

4x1+ 2x2 + x3 10

x1+ x2 + 2x3 6

x1, x2,x3 0

10. Tunjukkan bahwa persoalan yang diberikan pada soal No. 9 memiliki nilai

optimal yang sama seperti dualnya dengan memecahkan kedua persoalan

ini secara langsung.

5.pl-dual

Documents