5.

Definisi masalah dual

Masalah dual adala sebuah masalah LP yang diturunkan secara matematis dari satu model
LP primal. Masalah dual dan primal sangat berkaitan erat sedemikian rupa sehingga rupa
sehingga pemecahan simpleks optimal dari salah satu masalah akan secara otomatis
menghasilkan pemecahan optimum untuk masalah lainnya.
Bentuk standar yang umum dari masalah primal didefinisikan sebagai
Maksimumkan atau minimumkan

dengan batasan

Tujuan Primal Standar

Dual

Tujuan

Batasan

Variabel

Maksimasi

Minimisasi

Tidak dibatasi

Minimisasi

Maksimisasi

Tidak dibatasi

1. Untuk setiap batasan primal terdapat sebuah variabel dual.

2. Untuk setiap variabel primal terdapat sebuah batasan dual.
3. Koefisien batasan dari sebuah variabel primal membentuk koefisien sisi kiri dari batasan
dual yang bersesuaian; dan koefisien tujuan dari variabel yang sama menjadi sisi kanan
dari batasan dual.
Bila masalah primal dan dual dibandingkan, terlihat beberapa hubungan sebagai berikut:
1. Koefisien fungsi tujuan primal menjadi konstan sisi kanan masalah dual, sebaliknya, konstan
sisi kanan primal menjadi koefisien fungsi tujuan dual.
2. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi tujuannya
3. Tujuan diubah dari minimalisasi (maksimalisasi) dalam primal menjadi maksimalisasi
(minimalisasi) dalam dual.
4. Setiap kolom pada primal berhubungan dengan suatu baris (batasan) dalam dual sehingga
banyaknya batasan dalam dual sama dengan banyaknya variable primal.
5. Setiap baris (batasan) pada primal berhubungan dengan suatu kolom dalam dual, sehingga ada
satu variable dual untuk setiap batasan primal.
6. Bentuk dual dari dual adalah bentuk primal.

Untuk mengubah persoalan maksimasi/minimasi yang tidak normal menjadi persoalan normal,
dapat dilakukan dengan langkah-langkah sebagai berikut :

1. Kalikan setiap pembatas bertanda

(untuk maksimasi) atau (untuk minimasi) dengan

bilangan -1.
2. Setiap pembatas bertanda = diganti menjadi dua ketidaksamaan ( bertanda dan ) kemudian
kembali melakukan langkah 1.
3. Setiap variabel xj yang tidak terbatas dalam tanda dengan

dimana

dan

Contoh
Maksimumkan
dengan batasan

Primal Standar
Maksimumkan
dengan batasan

Perhatikan bahwa

adalah variabel slack dalam batasan pertama; jadi, variabel ini memiliki

koefisien nol dalam fungsi tujuan dan dalam batasan kedua.

Dual
Minimumkan
dengan batasan

(menyiratkan bahwa

tidak dibatasi
Perhatikan bahwa tidak dibatasi didominasi oleh
dengan

, batasan dual yang berkaitan

. Jadi, untuk menyingkirkan batasan yang berlebihan ini, masalah dual tersebut

sebaiknya ditulis
Minimumkan
dengan batasan

tidak dibatasi
Contoh
Primal
Minimumkan
Dengan batasan

Masalah primal di atas dapat dipecahkan baik dengan metode simpleks primal atau secara
langsung dengan metode simpleks dual.Pemilihan metode pemecahan tertentu memiliki
pengaruh terhadap bagaimana pemecahan dual yang optimal diperoleh dari pemecahan optimal
dari masalah primal.
Model Standar Ketika Simpleks Primal Dipergunakan untuk Memecahkan Masalah Primal
Minimumkan
Dengan batasan

Dual
Maksimumkan
Dengan batasan

Kedua masalah dual ini konsisten, karena koefisien

dalam satu masalah dual memiliki

tanda yang berlawanan dengan koefisien yang sama dalam masalah dual lainnya. Tetapi,
perbedaan ini diperlukan karena hasil tabel simpleks (yang dipergunakan untuk
menginterpretasikan pemecahan masalah dual) secara langsung bergantung pada cara bagaimana
bentuk standar tersebut didefinisikan sebelum metode simpleks primal atau dual diterapkan.
Perincian yang halus ini kemungkinan akan hilang jika kita mencoba menggunakan definisi
umum yang diberikan dalam pembahasan LP lainnya.
Contoh
PRIMAL
Maksimumkan
Dengan batasan

tidak dibatasi

PRIMAL STANDAR
Anggaplah
Maksimumkan
Dengan batasan

, dimana

. Maka masalah primal standar menjadi

DUAL
Minimumkan
Dengan batasan

(menyiratkan

bahwa

(menyiratkan bahwa

tidak dibatasi
tidak dibatasi (berlebihan)
Amati bahwa batasan pertama dan kedua dapat (tetapi tidak harus) digantikan dengan
persamaan

. Ini akan selalu terjadi ketika variabel primal tidak dibatasi, yang

berarti bahwa variabel primal yang tidak dibatasi akan selalu mengarah pada persamaan dual
(daripada pertidaksamaan). Hasil ini berlaku baik masalah primal tersebut merupakan sebuah
maksimisasi atau minimisasi.

5.2 PEMECAHAN MASALAH DUAL

5.2.1 HUBUNGAN ANTARA NILAI TUJUAN PRIMAL DAN DUAL

Nilai tujuan dalam satu pasangan masalah primal dan dual harus memenuhi hubungan berikut
ini:
1. Untuk setiap pasangan pemecahan primal dan dual yang layak

2. Di pemecahan optimum untuk kedua masalah

Untuk membuktikan keabsahan kedua hasil ini, dengan menganggap (XI,XII) dan Y
merupakan pemecahan primal dan dual yang layak yang bersesuaian dengan definisi primaldual yang diberikan dalam bentuk matriks.

Primal Standar
Maksimumkan z = CI XI + CIIXII
dengan batasan :
A XI + IXII = b
XI,XII 0
Dual
Minimumkan w= Yb
dengan batasan :
YA CI
Y CII
Y vektor yang tidak dibatasi
Dengan mengalikan sebelumnya batasan-batasan primal dengan Y, maka diperoleh :
YA XI + Y XII = Yb
Setelah menggalikan batasan dual dengan XIdan XII , maka diperoleh

YA XI CI XI
YXII CIIXII
Jumlahkan kedua batasan tersebut sehingga menghasilkan :
YA XI + YXII
Karena YA XI + YXII = Yb

CI XI + CIIXII

dan CI XI + CIIXII= z dapat disimpulkan bahwa

Jadi terbukti untuk setiap pasangan pemecahan primal dan dual yang layak.
Untuk membuktikan hasil yang kedua yaitu di pemecahan optimum untuk kedua
masalah, yang memperlihatkan bahwa

di pemecahan optimum, z berkaitan dengan kasus

maksimisasi yang berarti bahwa z mengusahakan nilai tertinggi di antara XI,XIIyang layak,
sedangkan w berkaitan dengan kasus minimisasi yang berarti bahwa w mengusahakan nilai
terendah di antara semua Y yang layak. Karena z w untuk semua pemecahan yang layak
(termasuk pemecahan optimal), kedua masalah tersebut akan mencapai optimalitas pada saat
max z= min w.

Contoh:
Maksimumkan z = 5x1 + 12x2 + 4x3
dengan batasan
x1 + 2x2 + x3 10
2x1 x2 + 3x3 = 8
x1,x2,x3 0
Bentuk standar :
Maksimumkan : z = 5x1 + 12x2 + 4x3 + 0S1- MR2
berdasarkan pembatas : x1 + 2x2 + x3 + S1 = 10

2x1 x2 + 3x3

+ R2 = 8

x1,x2,x3,S1,R2 0

Tabel simpleks persoalan primal

Iterasi

X1

Basis

X2

X3

S1

R2

Solusi

-(2M+5)

(M-12)

-(3M+4)

-8M

10

-1

-7/3

-40/3

4/3+M

32/3

1/3

7/3

-1/3

22/3

2/3

-1/3

1/3

8/3

-3/7

40/7

-4/7+M

36 8/7

1/7

3/7

-1/7

22/7

5/7

1/7

2/7

26/7

3/5

29/5

-2/5+M

274/5

-1/5

2/5

-1/5

12/5

7/5

1/5

2/5

Dilihat dari Iterasi 3 koefisien R2 pada persamaan z optimum (= -2/5 + M-M = -2/5)

Dual dari persoalan

Minimumkan

Berdasarkan pembatas :

Bentuk standar :
Minimumkan :
berdasarkan pembatas :

26/5

Tabel Simplek Persoalan Dual

Itera Basis
si

Solusi
(4M-10)

(4M-8)

(-4M+8) -M

-M

-M

21M

-2

-1

-1

-1

12

-3

-1

8/3M22/3

-M

-M

(1/3M-8/3) 0

(-4/3M+

47/3M+

8/3)

32/3

1/3

-1

2/3

-2/3

7/3

7/3

-1

-1/3

1/3

40/3

1/3

-1

-1/3

1/3

4/3

(-8M +22) (8M-22)

-M

-M

(3M-10)

(-4M+ 10) (5M+40)

-1

-1

-1

-7

-1

-2

-3

-1

-M

-1/7M-22/7

(5/7M-26/7) 0

(-8/7M

(12/7M

3/7M+

Pada Iterasi 4 nilai

+22/7)

+26/7)

368/7

-1

1/7

5/7

-1/7

-5/7

3/7

-1

-1/7

2/7

1/7

-2/7

4/7

-3/7

-1/7

3/7

1/7

40/7

-26/5

-12/5

26/5-M 12/5-M

-M

274/5

-7/5

1/5

7/5

-1/5

-1

3/5

-1

2/5

-1/5

2/5

1/5

2/5

-1/5

-2/5

1/5

2/5

29/5

Dari tabel simplek persoalan primal dan dual dapat disimpulkan bahwa hubungan primal
dengan dual adalah sebagai berikut :
1. Solusi fisibel persoalan minimasi adalah batas atas dari solusi fisibel persoalan
maksimasi.
2. Kedua persoalan sudah mencapai solusi optimum, maka maks z = min w.
3. Nilai optimum variabel-variabel solusi awal pada primal sama dengan nilai optimum
variabel-variabel dual yang berkorespondensi dengan persamaan pembatas pada primal.
Dengan kata lain:
a. Jika variabel dual berkorespondensi dengan variabel slack awal pada persoalan
primal, maka nilai optimum variabel tersebut sama dengan koefisien variabel slack
pada persamaan z yang optimum.
Bukti : y1 berkorespondensi dengan S1 pada primal, maka nilai optimum y1 (= 29/5)
sama dengan koefisien S1 pada persamaan z optimum (=29/5).
b. Variabel dual berkorespondensi dengan variabel arti fisial awal pada primal, maka
nilai optimum variabel tersebut sama dengan koefisien variabel artifisial pada
persamaan z yang optimum setelah menghilangkan konstanta M.
Bukti: y2 berkorespondensi dengan R2 pada primal, maka nilai optimum y2 (= -2/5)
sama dengan koefisien R2 pada persamaan z optimum (= -2/5 + M-M) = -2/5

5.2.2 SIFAT-SIFAT DUAL YANG PENTING

Sifat 1: Menentukan koefisien fungsi tujuan variabel-variabel basis awal.
Pada saat iterasi solusi simpleks, baik primal maupun dual, koefisien fungsi
tujuan variabel-variabel basis awalnya yang dapat dicari dengan cara:
1. 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.

2. Kurangi nilai-nilai simplex multiplier ini dengan fungsi tujuan yang original
dari variabel-variabel basis awal.
Sifat 2 : Menentukan koefisien fungsi tujuan variabel-variabel nonbasis 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 nilai ruas kanan (solusi) 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:

Sifat 4 : Menentukan koefisien pembatas

Pada setiap iterasi, baik primal maupun dual, koefisien pembatas dari setiap
variabel dapat ditentukan dengan cara sebagai berikut:

Contoh:
Maksimumkan :
Dengan batasan :

Salah satu iterasi dari persoalan di atas adalah sebagai berikut:

Basis

Pemecahan
j

6/20

4/20

1/20

4/20

5/20

Tentukan nilai-nilai dari 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 dan dual!

Penyelesaian :
1. Sifat 1:

a = 3/2 0 = 3/2
b=20=2
c=0-0=0
2. Sifat 2:

4(3/2) (2) 0 4 = 0

d=0

(3/2) + 6(2) 0
e=0

0 2=
f=

3. Sifat 3

g = 5/2
h= 5/4
i= 25/4

4. Sifat 4 :

j=1
k= 0
l=0

=0

m=0
n=1
p=0

q=0
r=0
s=1
Dengan demikian, t dapat dicari dengan memasukkan nilai-nilainya g, h dan i ke dalam
persamaan z, sehingga diperoleh:
t = 4(5/2) + 6(5/4)- 0(25/4)
t = 70/4

5.2.2 PEMECAHAN DUAL OPTIMAL

Pemecahan dual yang optimal dapat ditentukan secara langsung dari tabel primal optimal.
Primal Standar
Maksimumkan z = CI XI + CIIXII
dengan batasan :
A XI + IXII = b
XI,XII 0

Dual
Minimumkan w= Yb

dengan batasan :
YA CI
Y CII
Y vektor yang tidak dibatasi
B dianggap basis primal yang optimal dan CBdianggap koefisien fungsi tujuan yang berkaitan
maka:Y= CBB-1 adalah pemecahan dual yang optimal.
Untuk membuktikannya dapat memeriksa dua persyaratan berikut :
1. Y= CBB-1adalah pemecahan dual yang layak.
2. Max z dalam primal sama dengan min w dalam dual.
Pemecahan dual Y= CBB-1 disebut layak apabila pemecahan tersebut memenuhi batasan dual
YA CIdanY CII . Dengan optimalitas masalah primal, memiliki zj cj 0 untuk semua j yaitu :
CBB-1A - CI 0 dan CBB-1- CII 0
Dengan menganggap Y= CBB-1,maka dapat dilihat bahwa kedua batasan dual ini terpenuhi.
Persyaratan kedua diverifikasi dengan memperlihatkan bahwa z = w untuk Y= CBB-1.Hal ini
langsung berlaku karena
w = Yb = CBB-1b
z = CBXB =CBB-1b

Pemecahan dual yang optimal dapat diperoleh secara langsung dari baris tujuan dari tabel
primal optimal
Dasar

XI

XII

Pemecahan

CBB-1A-CI

CBB-1-CII

CBB-1b

XB

B-1A

B-1

B-1b

Koefisien XII dalam baris z diketahui berdasarkan CBB-1-CII.Jadi, jika vektor dasar awal XII
terdiri dari semua variable slack, CII = 0dan koefisien baris z dari XIIakan menghasilkan nilai-

nilai dual secara langsung.Jika tidak, maka harus menambahkan CIIpada CBB-1-CIIuntuk
memperoleh pemecahan dual.
Contoh:
Primal
Maksimumkan z = 5x1 + 12x2 + 4x3
dengan batasan

x1 + 2x2 + x3 10
2x1 x2 + 3x3 = 8
x1,x2,x3 0
Tabel primal
XI

XII

x1

x2

x3

x4

3/5

29/5

-2/5 + M

274/5

x2

-1/5

2/5

-1/5

12/5

x1

7/5

1/5

2/5

26/5

Dasar

Pemecahan

Karena XII = ( x4, R)T dan CII= (0, -M), dari tabel diatas didapat:
CBB-1 CII = (29/5, -2/5 + M)
Sehingga memperoleh
Y= (y1, y2) = CBB-1= (29/5, -2/5 + M) + (0,-M)
= (29/5, -2/5)
Hasil yang sama akan diperoleh jika menggunakan perhitungan simpleks yang direvisi sebagai
berikut

Y C B B 1 12, 5 5
1

1

5 29 , 2
2 5
5

5.3 INTERPRETASI EKONOMI DARI MASALAH DUAL

Secara spesifik, kita menyatakan bahwa harga dual mewakili nilai per unit dari sumber
daya LP. Sebaliknya pengurangan biaya mewakili kenaikan dalam pengembalian marginal atau
penurunan dalam biaya per unit sumber daya yang diperlukan untuk membuat sebuah kegiatan
LP

(variabel)

sekedar

menguntungkan.

Pada bagian ini kita menggunakan masalah primla dual untuk menerangkan makna
ekonomi yang pasti dari harga dual dan pengurangan biaya. Interpretasi ini akan terbukti berguna
dalam dua aspek:
1. Memberikan pemahaman mendasar akan model LP sebagai sistem masukan keluaran
ekonomi.
2. Memungkinkan implementasi analisi sensitivitas atau analisis pasca optimal secara
efisien
Aspek pertama dibahas dalam bab ini. Analisis sensitifitas akan diliput dalam bagian berikutnya.
Untuk maksud penyediaan interpretasi ekonomi dari masalah dual, kita menggunakan definisi
(nonmatriks) berikut ini untuk masalah primal dan dual.

Primal

Dual

Maksimumkan

Minimumkan

dengan batasan

dengan batasan
j = 1,2, ..... , n
tidak dibatasi, i = 1,2,...., m

Secara ekonomi kita dapat memandang model primal dengan cara demikian. Koefisien
mewakili laba mrginal dari kegiatan j yang tingkat kegiatannya sama dengan

tujuan

unit. Jadi fungsi

mewakili laba dari semua kegiatan. Model tersebut memiliki m sumber

daya.Sumber daya i memiliki tingkat

kegiatan j. Sisi kiri

yang dialokasikan dengan tingkat

unit per unit

mewakili penggunaan sumber daya i oleh semua kegiatan.Kita

sekarang menggunakan definisi di atas untuk menerangkan makna indikator ekonomi harga dual
dan penggunaan biaya.

5.3.1 HARGA DUAL

Pada pemecahan optimal dari masalah primal maupun dual, kita memiliki
z=w
atau

Interpretasi ekonomi dari variabel dual yidengan menggunakan analisis dimensional berikut ini.
Karena sisi kiri dari persamaan tersebut mewakili nilai uang (pengembalian) dan bimewakili unit
(jumlah) sumber i, maka yi, berdasarkan persamaan diatas, pastilah mewakili nilai uang per unit
sumber daya iseperti diperlihatkan analisis dimensional berikut ini:
$ (pengembalian)
Jadi variabel dual yi mewakili nilai per unit sumber daya i. Dalam literatur, yi biasanya disebut
sebagai harga dual(kadang kadang istilah harga bayanganjuga dipergunakan).
Analisis dimensional di atas mengarahkan kita pada sebuah observasi menarik. Kami
telah menerangkan bahwa untuk pemecahan primal dan dual yang layak dan tidak optimal, kita
memiliki
z<w

Berdasarkan interpretasi ekonomi yang diberikan untuk nilai dual diatas, pertidaksamaan ini
menunjukkan bahwa

Atau
(laba) < (nilai sumber daya)
Pertidaksamaan ini mengatakan bahwa selama pengembalian total dari semua kegiatan adalah
lebih kecil dari nilai sumber daya dari model tersebut, pemecahan (primal dan dual) yang
bersangkutan tidak dapat optimal. Optimalitas (pengembalian maksimum) dicapai hanya
bilamana sumber daya dimanfaatkan sepenuhnya: yaitu, ketika pengembalian total sama dengan
nilai total dari sumber daya (z = w). Model LP ini dianggap sebagai sebuah sistem masukan
keluaran dengan sumber daya dan pengembalian yang secara berturut turut mewakili unsur
unsur masukan dan keluaran.Sistem ini tetap tidak stabil (tidak optimal) selama masukan (nilai
sumber daya) melebihi keluaran (pengembalian), dengan stabilitas terjadi ketika keduanya setara.
Contoh soal 5.3.1
1. Sebuah perusahaan memproduksi celana dan rok. Ketersediaan kain untuk membuat
celana dan rok adalah batasnya sampai

dengan batas waktu kerja 1800 jam.

Laba penjualan celana dan rok masing-masing $136 dan $26. Kebutuhan kain dan waktu
kerja disajikan dalam tabel berikut:
Celana

Rok

12

Ketersediaan
maksimum

Kain
(
Waktu kerja
(jam)

1200
1800

Tentukan harga pembelian maksimum yang harus dibayar untuk kain? dan tenaga kerja?

Penyelesaian

Fungsi tujuan
Maksimumkan

(primal)

dengan batasan

Bentuk standar
Fungsi tujuan
Maksimumkan
dengan batasan

Ini menggunakan metode simpleks (primal) direvisi

Pemecahan awal

Iterasi Pertama
Langkah 1 : Perhitungan

(primal)

Vektor masuknya adalah

Langkah 2 : Penentuan vektor keluar dengan diketahui bahwa

memasuki basis

Dalam bentuk tabel dalam Bab 3, perhitungan untuk langkah 1 dan 2 dapat diringkaskan sebagai
berikut:

Dasar
Z

-136

Pemecahan
0

Rasio (
-

1200

150

12

1800

150

Vektor keluarnya adalah

yang akan digantikan oleh

Langkah 3: Penentuan inversi basis berikutnya. Karena

, kita memiliki

dan

Basis baru ini berkaitan dengan vektor dasar

Iterasi kedua
Langkah 1 : perhitungan

untuk variabel nondasar

menggantikan

dan

Karena semua
Harga dual

, basis terakhir ini optimal

memberikan nilai per unit kulit dan waktu kerja masing-masing

adalah $17 dan $0. Harga dual tersebut jadi menunjukkan bahwa untuk setiap kenaikan satu unit
kulit, nilai laba z akan meningkat dengan $17. Sebaliknya, menaikkan satu jam waktu kerja tidak
memberi manfaat, karena nilai per unitnya $0. Jadi mau dinaikkan atau diturunkan, tidak
berpengaruh pada laba.
Harga unit maksimum dari kulit dan waktu kerja masing-masing adalah $25 dan $17

5.3.2 PENGURANGAN BIAYA

Dari perincian metode simpleks yang direvisi bahwa koefisien persamaan tujuan dari
variabel

dalam setiap iterasi diketahui

Alternatif lain dengan menggunakan

sebagai nilai dual yang berkaitan kita memiliki

Hubungan ini mengatakan bahwa koefisien persamaan tujuan

dari variabel

dalam tabel

primal sama dengan selisih antara sisi kiri dan sisi kanan dari batasan dual ke-j. Persamaan
tersebut menghasilkan interpretasi ekonomi yang menarik dalam model LP tersebut, yang akan
diungkapkan dengan analisis dimensional.

Karena

dari masalah primal mewakili pengembalian per unit kegiatan j, unit dari

variabel ini kemungkinan diwakili dengan dollar per unit kegiatan j. Untuk konsistensi, jumlah
juga harus memiliki dimensi dollar per unit kegiatan j. Tetapi karena
tampil dengan tanda yang berlawanan, jumlah
berdasarkan definisinya,
Sebagai hasilnya

dan

harus berarti biaya. Sekarang,

adalah jumlah sumber daya i yang dipakai oleh 1 unit kegiatan j.

pastilah mewakili biaya bayangan per unit sumber daya i dan dapat

dipandang

sebagai biaya bayangan total dari semua sumber daya yang dipergunakan

untuk memproduksi satu unit kegiatan j. Sekarang , bergantung pada biaya

melebihi pengembalian
persamaan untuk

, penjelasan di atas mengarah pada analisis dimensional berikut ini dari

:

$ (laba atau rugi)/unit = $(biaya)/unit - $(pengembalian)/unit

Kondisi optimalitas maksimisasi dari metode simpleks (yang direvisi) menyatakan bahwa
tingkat kegiatan yang tidak dipergunakan saat ini (yaitu,nondasar
melewati tingkat nol hanya jika koefisien tujuannya

adalah negatif. Kondisi ini dapat

dibenarkan secara ekonomi sebagai berikut: Dari interpretasi ini

menetapkan bahwa

= 0) harus dinaikkan

, kondisi optimalitas

Atau

Jadi selama pengembalian per unit melebihi biaya bayangan dari sumber daya yang
dipergunakan, lebih banyak sumber daya harus dialokasikan untuk kegiatan tersebut untuk
memanfaatkan potensi laba tersebut.Pada intinya, ini berarti bahwa tingkat kegiatan j,

harus

dinaikkan melewati tingkat nol.

Akan terlihat bahwa ketika menerima sebuah kegiatan j ke dalam pemecahan
(membuatnya menjadi variabel dasar), menaikkannya sampai ke titik di mana

menjadi nol.

Ini adalah setara dengan memanfaatkan profitabilitas dari kegiatan ini sebanyak mungkin, karena
kenaikan lebih lanjut akan semata mata menghasilkan kenaikan dalam biaya bayangan
melewati potensi pengembalian dari kegiatan tersebut.
Untuk kegiatan kegiatan yang berada di tingkat nol di pemecahan optimal (variabel
nondasar), jumlah

disebut dalam literatur disebut sebagai pengurangan biaya (reduced

cost) per unit kegiatan j. Sesuai penjelasan yang diberikan di atas, jumlah ini mewakili jumlah
seberapa banyak posisi ekonomi dari kegiatan tersebut harus diperbaiki untuk membuatnya lebih
menarik secara ekonomi (yaitu, menaikkan tingkatnya dari nol ke satu nilai positif tertentu).
Hasil seperti itu dapat terjadi dalam dua cara:
1. Menaikkan pengembalian marginal dari kegiatan tersebut, cj.
2. Menurunkan konsumsi sumber daya yang terbatas oleh kegiatan tersebut,
Pilihan pertama tidak selalu layak, karena margin laba biasanya ditentukan oleh pasar dan
kondisi persaingan.Pilihan kedua sebenarnya mencerminkan komitmen kesatuan ekonomi
tersebut pada perbaikan operasi terutama melalui penurunan penggunaan sumber daya yang
terbatas.Pada intinya, pilihan kedua berkaitan dengan penyingkirkan inefisiensi yang mungkin
dalam operasi sistem yang bersangkutan.
Nilai dual yi dapat dipergunakan dengan indikator di mana pilihan kedua tersebut
sebaiknya diterapkan.Pada intinya, karena yi mewakili biaya bayangan dari penggunaan 1 unit

sumber daya i per unit kegiatan j, sumber daya yang memiliki nilai yi yang relatif tinggi harus
memperoleh prioritas dalam studi peningkatan efisiensi.
Contoh
Pertimbangkan masalah bauran produk di mana masing-masing dari ketiga produk diolah di tiga
operasi yang berbeda. Batas atas waktu yang tersedia untuk ketiga operasi itu adalah 430, 460,
dan 420 menit per hari dan laba per unit untuk ketiga produk adalah $3,$2,dan $5. Waktu dalam
menit per unit di ketiga operasi tersebut diketahui sebagai berikut:

Operasi 1
Operasi 2
Operasi 3

Produk 1
1
3
1

Produk 2
2
0
4

Produk 3
1
2
0

Contoh soal
Pertimbangkan masalah bauran produk di mana masing-masing dari ketiga produk diolah di tiga operasi
yang berbeda. Batas atas waktu yang tersedia untuk ketiga operasi itu adalah 430, 460, dan 420 menit per
hari dan laba per unit untuk ketiga produk adalah $3,$2,dan $5. Waktu dalam menit per unit di ketiga
operasi tersebut diketahui sebagai berikut:
Produk 1

Produk 2

Produk 3

Operasi 1

Operasi 2

Operasi 3

Model LP ini ditulis sebagai

Maksimumkan
Dengan batasan
Operasi 1:
Operasi 2:
Operasi 3:

Bentuk standar
Maksimumkan
Dengan batasan

Penyelesaian dengan menggunakan simpleks primal yang direvisi

Pemecahan awal

Iterasi pertama
Perhitungan

Dipilih

untuk non dasar

sebagai vektor masuk

dasar

pemecahan Rasio
-3

Sehingga

-2

-5

430

430

460

230

420

sebagai vektor keluar digantikan oleh

Basis baru dengan vektor dasar

Iterasi kedua
Perhitungan

untuk non dasar

Dipilih

sebagai vektor masuk

dasar

pemecahan Rasio
9/2

Sehingga

-2

5/2

200

100

230

420

105

sebagai vektor keluar digantikan oleh

Iterasi ketiga
Perhitungan

untuk non dasar

Karena semua

, basis terakhir ini optimal

Pemecahan optimal

Terlihat bahwa bauran optimal tidak mencakup produk 1 (

. Ini berarti bahwa produk 1

tidak menguntungkan, yang terjadi karena harga bayangan dari produk 1 adalah lebih besar daripada laba
per unitnya, yaitu
dengan menurunkan nilai

. Karena

dan

, dapat membuat

menguntungkan

. Hasil ini dapat dicapai dengan mengurangi penggunaan ketiga waktu operasi

oleh produk 1. Penggunaan ini diketahui berdasarkan koefisien

dalam penyajian untuk

Harga dual

berarti bahwa penurunan penggunaan operasi 3 tidak

akan efektif, karena biaya bayangan per unitnya,

dan 2, terlihat bahwa

adalah nol. Jadi dengan mempertimbangkan operasi 1

adalah lebih besar daripada

. Sebagai hasilnya akan lebih menarik

untuk memberikan prioritas yang lebih tinggi untuk usaha mengurangi penggunaan operasi 2.
Anggaplah bahwa kita tertarik untuk menentukan jumlah penurunan dalam penggunaan operasi 2
yang akan membuat produk 1 sekedar menguntungkan. Untuk melakukan hal ni, anggaplah

mewakili

penurunan dalam menit per unit produk 1 berada dalam operasi 2. Dalam kasus ini,

Produk 1 menjadi sekedar menguntungkan ketika

, yang menghasilkan

tepat melewati

; yaitu

atau

. Ini berarti bahwa penggunaan operasi 2 harus dikurangi dengan

lebih dari 2 menit untuk membuat produk 1 menguntungkan.

Latihan:
Dalam contoh kasus sebelumnya, anggaplah bahwa penggunaan per unit operasi 2 tidak dapat dikurangi
dengan lebih dari 1,75 menit. Tentukan pengurangan tambahan dalam penggunaan operasi 1 yang akan
membuat

tepat menguntungkan.

Penyelesaian:
Untuk membuat produk
operasi-operasi pada

sekedar menguntungkan, yaitu dengan menurunkan konsumsi per unit dari

Produk 1 menjadi sekedar menguntukan ketika

yang menghasilkan

tepat melewati

; yaitu

atau

. Ini berarti bahwa penggunaan operasi 1 harus dikurangi dengan lebih dari

0,5 menit untuk dapat membuat produk 1 menguntungkan.

5.4 NILAI SLACK KOMPLEMENTER

Berdasarkan versi matriks dari tabel simpleks, didapatkan hasil yang berhubungan
dengan pemecahan primal dan dual optimal.

1. Jika dipemecahan optimum sebuah variabel primal

memiliki

, maka

pastilah nondasar dank arena itu berada ditingkat nol.

2. Jika di pemecahan optimum sebuah variabel dual
primal ke-

memiliki nilai positif, batasan

pastilah dipenuhi karena dalam bentuk persamaan karena

nilai slack yang berkaitan dengannya pastilah nol.

Untuk penjelasan mengenai pernyataan diatas secara matematis.Telah diketahui bahwa
mewakili selisih antara sisi kiri dan sisi kanan dari batasan dual dan karena itu pastilah mewakili
variabel surplus dual. Jika diasumsikan bahwa
batasan dual

dan primal

, maka

Hasil tersebut dapat diringkas menjadi :

Ketika

Ketiak

Untuk pemecahan primal dan dual optimal,

adalah variabel surplus dan slack untuk

dan untuk semua i dan j

Dengan cara setara, didapatkan

Dengan pengamatan diatas dapat menunjukan teorema ini :

Teorema Nilai Slack Komplementer : sepasang pemecahan primal dan dual yang layak
adalah optimal untuk masalah masing-masing jika dan
hanya jika kondisi ini terpenuhi :

Dimana

Contoh soal :
Pertimbangkan model dalam contoh 5.3-2. Kita dapat meggunakan teorema nilai senggang
komplementer untuk memeriksa bahwa vector dasar

adalah optimal

Penyelesaian :
Pemecahan primal dari permasalahan tersebut adalah

Sesuai dengan hasil nya maka (

Pemecahan dual dari pemasalahan tersebut adalah

Sesuai dengan penyelesaian pemecahan dual

maka,

Dan didapatkan
Untuk selanjutnya kita akan memriksa apakah pemecahan ini layak dengan mencari hasil dari

Dengan asumsi :

Kita akan mencari

. Karena i = 1,2,3 maka,

Setelah mencari nilai slack selanjutnya kita mencari nilai surplusnya dengan (j = 1,2,3) yaitu
menggunakan asumsi :

Kita akan mencari

Maka,

Yang semua nonnegatif. Pemecahan

dan

adalah optimal, karena memenuhi kondisi nilai senggang komplementer

dan

PEMROGRAMAN LINIER
DUALITAS

Oleh Kelompok 5

Valeria Trisna Yunita

(1408405001)

Ni Kadek Yuni Dewiantari

(1408405013)

Made Andriani

(1408405023)

A. A. Dwi Marsita Anggraeni

(1408405035)

Ni Putu Rina Anggreni

(1408405042)

Jurusan Matematika
Fakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Udayana
2015