(5) basic simplex

LOGO

Dasar-dasarMetode Simplex

Amelia Kurniawati. ST., MT.Your Site Here

YOUR SITE HERE

Contents

1. Pendahuluan

2. Langkah Umum

3. Metode Simpleks dalam Bentuk Tabular

4. Pemecahan untuk masalah minimisasi

6. Solusi-solusi Alternatif

5. Masalah-masalah komputasi

YOUR SITE HERE

Memahami konsep pemecahan linear programming dengan metode simplex

Memahami solusi-solusi unik dan solusi alternatif

Goals

PENDAHULUAN

Metode Simplex

Dikembangkan oleh G.B. Dantzig

Merupakan prosedur iteratif untuk

memecahkan masalah LP dengan

mengekspresikannya dalam bentuk

standar

YOUR SITE HERE

PENDAHULUAN

Metode Simplex

Memerlukan kondisi dengan semua

pembatas dinyatakan dalam bentuk

sistem kanonik dimana suatu solusi

basis layak dapat langsung diperoleh.

YOUR SITE HERE

PENDAHULUAN

Ciri-ciri dari bentuk baku model LP adalah :

1. Semua kendala berupa persamaan dengan sisi kanan non negatif

2. Semua variabel non negatif 3. Fungsi tujuan dari maksimum

maupun minimum

YOUR SITE HERE

lihat kembali materi basic feasible solution

LANGKAH UMUM

YOUR SITE HERE

Berhenti jika suatu solusi layak basis tidak dapat diperbaiki lagi

maka solusi layak basis tersebut menjadi solusi optimal

Cari solusi-solusi layak basis yang dapat memperbaiki nilai fungsi tujuan

Perbaiki solusi awal jika mungkin

Cari solusi layak basis yang mempunyai nilai fungsi tujuan lebih baik

Mulai dengan suatu solusi layak basis

LANGKAH UMUM (CONTOH)

Kasus:Memaksimumkan Z = 3x1 + 2x2

dengan pembatas-pembatas: x1 + 2x2 6

2x1 + x2 8

– x1 + x2 1

x2 2

x1 ≥ 0, x2 ≥ 0

YOUR SITE HERE


Bentuk Standard:Memaksimumkan Z = 3x1+2x2 +0x3+0x4+0x5+0x6

dengan pembatas-pembatas: x1 + 2x2 + x3 = 6

2x1 + x2 + x4 = 8

– x1 + x2 + x5 = 1

x2 + x6 = 2

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0

YOUR SITE HERE


Penetapan Solusi Layak Basis Awal:

Variabel basis : x3, x4, x5, x6

Dengan menetapkan x1 = x2 = 0, maka

diperoleh solusi basis : x3 = 6, x4 = 8, x5 = 1, x6 = 2

Nilai fungsi tujuan Z = 3(0)+2(0)+0(6)+0(8)+0(1)+0(2)= 0

YOUR SITE HERE

LANGKAH UMUMMemperbaiki Solusi Layak Awal:

Dengan diberikan solusi basis layak, yaitu x1 = x2 = 0, x3 = 6, x4 = 8, x5 = 1, x6 = 2 dengan Z= 0, metode simpleks memeriksa apakah mungkin untuk mendapatkan solusi basis layak yang lebih baik dengan nilai Z yang lebih besar

Pemeriksaan dilakukan dengan pertama-tama memeriksa apakah solusi saat ini adalah optimal

YOUR SITE HERE

LANGKAH UMUM

Memperbaiki Solusi Layak Awal:

Jika solusi solusi belum optimal, metode simpleks mencari suatu solusi basis layak tetangga (adjacent basic feasible solution) dengan nilai Z yang lebih besar

Suatu solusi basis layak tetangga (adjacent basic feasible solution) berbeda dengan solusi basis layak (basic feasible solution) saat ini hanya tepat satu variabel basis

YOUR SITE HERE



Untuk mendapatkan solusi basis layak tetangga, metoda simpleks Membuat salah satu variabel basis menjadi

variabel non basis Menjadikan salah satu variabel non basis

menjadi variabel basis

Permasalahannya adalah memilih solusi basis dan solusi non basis yang pertukarannya memberikan perbaikan maksimum pada nilai fungsi tujuan.

YOUR SITE HERE



Dalam solusi basis layak Variabel basis dapat mempunyai nilai yang

positif Varibel non basis selalu mempunyai nilai nol

Membuat variabel non basis menjadi variabel basis adalah ekivalen dengan menaikkan nilainya dari nol ke positif.

YOUR SITE HERE



Tentu saja, pilihan yang harus dibuat adalah menentukan variabel non basis mana yang dapat memberikan perbaikan pada nilai Z

Ini dilakukan dengan menaikkan nilai variabel non basis menjadi satu unit dan memeriksa perubahannya pada nilai fungsi tujuan Z.

YOUR SITE HERE



YOUR SITE HERE

Misalkan variabel non basis x1 dinaikkan 1 unit

1x1 +x3 = 6 2x1 + x4 = 8–x1

+ x5 = 10x1 + x6 = 2 x1 = 1, x2 = 0, x3 = 5, x4 = 6, x5 = 2, x6 = 2


Perubahan nilai Z per peningkatan satu unit x1

Z = 3 – 0 = 3



YOUR SITE HERE


2x2 + x3 = 6 1x2 + x4 = 81x2 + x5 = 11x2 + x6 = 2 x1 = 0, x2 = 1, x3 = 4, x4 = 7, x5 = 0, x6 = 1



Z = 2 – 0 = 2



YOUR SITE HERE

Karena Z positif untuk x1 dan x2 nilai fungsi tujuan dapat dinaikkan.

Karena Z untuk x1 > Z untuk x2 maka menaikkan x1 lebih baik.

Sampai seberapa jauh x1 dapat dinaikkan?

Jika x1 dinaikkan maka nilai variabel basis : x3, x4, x5, x6 akan turun dan nilainya harus tak negatif agar tetap layak.



YOUR SITE HERE

Batas peningkatan x1:

x1 + x3 = 6 x1 = 6 2x1 + x4 = 8 x1 = 4– x1

+ x5 = 1 x1 = 0x1 + x6 = 2 x1 =

Maksimum peningkatan x1 = minimum (6, 4, , ) = 4



YOUR SITE HERE

x1 dinaikkan 4 unit, maka x4 menjadi variabel non basis

x1 = 4, x2 = 0, x3 = 2, x4 = 0, x5 = 5, x6 = 2 dan Z = 12

variabel masuk basis x1 dinaikkan 4 unit

1x1 +x3 = 6 2x1 + x4 = 8–x1

+ x5 = 10x1 + x6 = 2



YOUR SITE HERE

　 x1 + 2x2 + x3 　 = 6 2 x1 + x2 + x4 = 8– x1 + x2

+ x5 = 1 x2 + x6 = 2

3/2 x2 + x3 –1/2 x4 = 2 x1 + 1/2x2 + 1/2 x4 = 4 3/2 x2

+ 1/2 x4 + x5 = 5 x2 + x6 = 2

Variabel basis : x1, x3, x5, x6; Variabel non basis: x2, x4

Sistem Kanonik


VISUALISASI LANGKAH I

YOUR SITE HERE

(5)

(6)

(2)

(4)

(3) (1)

x1

x2

AB

CDE

F


Memperbaiki Solusi Layak 2:

YOUR SITE HERE

3/2 x2 + x3 = 2 x1 + 1/2 x2 = 4 3/2 x2 + x5 = 5 x2 + x6 = 2


x1= 7/2, x2 = 1, x3 = 1/2, x4 = 0, x5 = 7/2, x6 = 1

Nilai fungsi tujuan Z = 3(7/2)+2(1)+0(1/2)+0(0)+0(7/2)+0(1) = 121/2


Z = 121/2 – 12 = 1/2

YOUR SITE HERE



x3 – 1/2 x4 = 2 x1 + 1/2 x4 = 4

+ 1/2 x4 + x5 = 5 0 x4 + x6 = 2


x1= 7/2, x2 = 0, x3 = 5/2, x4 = 1, x5 = 9/2, x6 = 2

Nilai fungsi tujuan Z = 3(7/2)+2(0)+0(5/2)+0(1)+0(9/2)+0(2) = 101/2


Z = 101/2 – 12 = – 3/2

YOUR SITE HERE



Karena Z positif untuk x2 nilai fungsi tujuan dapat dinaikkan

Karena Z negatif untuk x4 nilai fungsi tujuan tidak dapat dinaikkan

Sampai seberapa jauh x2 dapat dinaikkan?

Jika x2 dinaikkan maka nilai variabel basis : x1, x3, x5, x6 akan turun dan nilainya harus tak negatif agar tetap layak.

YOUR SITE HERE



Batas peningkatan x2:

Maksimum peningkatan x2 = minimum (4/3, 8, 10/3, 2) = 4/3

3/2 x2 + x3 = 2 x2 = 4/3 x1 + 1/2 x2 = 4 x2 = 8 3/2 x2 + x5 = 5 x2 = 10/3 x2 + x6 = 2 x2 = 2

YOUR SITE HERE



x2 dinaikkan ke 4/3

maka x3 menjadi variabel non basis

x1 = 10/3, x2 = 4/3, x3 = 0, x4 = 0, x5 = 3, x6 = 2/3

dan Z = 122/3

YOUR SITE HERE

LANGKAH UMUM (CONTOH)Memperbaiki Solusi Layak 2:

3/2 x2 + x3 – 1/2 x4 = 2 x1 + 1/2 x2 + 1/2 x4 = 4 3/2 x2

+ 1/2 x4 + x5 = 5 x2 + x6 = 2

x2 + 2/3 x3 – 1/3 x4 = 4/3 x1 – 1/3 x3 + 2/3 x4 = 10/3

– x3 + x4 + x5 = 3

– 2/3 x3 + 1/3 x4 + x6 = 2/3

Variabel basis : x1, x2, x5, x6; Variabel non basis: x3, x4

Sistem Kanonik

YOUR SITE HERE


VISUALISASI LANGKAH II

29

(5)

(6)

(2)

(4)

(3) (1)

x1

x2

AB

CDE

F

YOUR SITE HERE


x2 + 2/3 x3 = 4/3 x1 – 1/3 x3 = 10/3

– x3 + x5 = 3 – 2/3 x3 + x6 = 2/3


x1= 11/3, x2 = 2/3, x3 = 1, x4 = 0, x5 = 4, x6 = 4/3

Nilai fungsi tujuan Z = 3(11/3)+2(2/3)+0(1)+0(0)+0(4)+0(4/3) = 121/3


Z = 121/3 – 122/3 = – 1/3

YOUR SITE HERE

LANGKAH UMUM (CONTOH)Memperbaiki Solusi Layak 3:Misalkan variabel non basis x4 dinaikkan 1 unit

x1= 8/3, x2 = 5/3, x3 = 0, x4 = 1, x5 = 2, x6 = 1/3

Nilai fungsi tujuan Z = 3(8/3)+2(5/3)+0(0)+0(1)+0(2)+0(1/3) = 111/3


Z = 111/3 – 122/3 = – 4/3

x2 – 1/3 x4 = 4/3 x1 + 2/3 x4 = 10/3

x4 + x5 = 3 1/3x4 + x6 = 2/3

YOUR SITE HERE


Karena Z negatif untuk x3 dan x4 nilai fungsi tujuan tidak dapat dinaikkan

Karena tidak ada variabel non basis yang dapat dinaikkan yang dapat memberikan peningkatan pada nilai fungsi tujuan Z maka solusi saat ini adalah optimal.

YOUR SITE HERE


Untuk masalah maksimasi:– Suatu solusi basis layak adalah optimal

jika profit relatif (Z) dari variabel non basis adalah negatif atau nol.

34

Metode Simpleks dalam Bentuk Tabular

(Simplex Method in Tabular Form)

Contoh masalah LP

Memaksimumkan Z = 3x1 + 2x2

dengan pembatas-pembatas: x1 + 2x2 6 2x1 + x2 8 – x1 + x2 1 x2 2 x1 ≥ 0, x2 ≥ 0

Metode simpleks dalam bentuk tabular

Bentuk kanonik


dengan pembatas-pembatas: x1 + 2x2 + x3 = 6 2x1 + x2 + x4 = 8 – x1 + x2

+ x5 = 1 x2 + x6 = 2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0,


Representasi tabel untuk solusi basis layak awal

cB

3 2 0 0 0 0Konstanta

x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

Basis

cj

c Baris


Nilai fungsi tujuan

konstantadan vektor dariproduct inner BcZ

0

2

1

8

6

0,0,0,0

Z


Pemeriksaan optimalitas

kanonik sistem dalam dengan berkaitan

yang kolomdan dari

j

Bjj x

cuctinner prodcc

Nilai fungsi tujuan relatif (profit relatif /ongkos relatif )untuk variabel non basis:

Kondisi optimal terjadi apabila semua nilai koefisienfungsi tujuan relatif untuk variabel non basis adalah tak positif [untuk masalah maksimasi]


Nilai fungsi tujuan relatif untuk variabel non basis

3

0

1

2

1

0,0,0,031

c

2

1

1

1

2

0,0,0,022

c


Tabel 1 (awal)

cB


x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris


Penentuan variabel yang masuk (entering variable)

Variabel non basis yang dipilih untuk masuk ke basis (entering variable) variabel yang memberikan peningkatan per unit pada Z yang terbesar, yaitu variabel non basis yang mempunyai nilai fungsi tujuan relatif terbesar (paling positif untuk masalah maksimasi).



cB


x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris


Penentuan variabel yang keluar (leaving variable)

Untuk menentukan variabel basis yang akan diganti (leaving variable), aturan rasio minimum (minimum ratio rule) digunakan untuk menentukan limit bagi tiap pembatas.



Nomor baris Variabel basisBatas atas bagi

x1

1 x3 6/1 = 6

2 x4 8/2 = 4 (minimum)

3 x5

4 x6



cB


x1 x2 x3 x4 x5 x6

0 x3 1 2 1 0 0 0 6

0 x4 2 1 0 1 0 0 8

0 x5 -1 1 0 0 1 0 1

0 x6 0 1 0 0 0 1 2

3 2 0 0 0 0 Z = 0

Basis

cj

c Baris


Tabel 2

cB


x1 x2 x3 x4 x5 x6

0 x3 0 3/2 1 -1/2 0 0 2

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

0 x5 0 3/2 0 1/2 1 0 5

0 x6 0 1 0 0 0 1 2

0 1/2 0 -3/2 0 0 Z = 12

Basis

cj

c Baris



cB


x1 x2 x3 x4 x5 x6

0 x3 0 3/2 1 -1/2 0 0 2

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

0 x5 0 3/2 0 1/2 1 0 5

0 x6 0 1 0 0 0 1 2

0 1/2 0 -3/2 0 0 Z = 12

Basis

cj

c Baris


Tabel 3 (Optimal)

cB


x1 x2 x3 x4 x5 x6

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

3 x1 1 0 -1/3 2/3 0 0 10/3

0 x5 0 0 -1 1 1 0 3

0 x6 0 0 -2/3 1/3 0 1 2/3

0 0 -1/3 -4/3 0 0 Z = 122/3

Basis

cj

c Baris


Output Tabel Simpleks dengan Software (WinQSB) (1)


Output Tabel Simpleks dengan Software (WinQSB) (2)


Pemecahan untuk masalah minimisasi

Koefisien fungsi tujuan relatif memberikan informasi perubahan dalam nilai Z per satu unit peningkatan variabel non basis.

Nilai yang negatif pada koefisien fungsi tujuan relatif untuk suatu variabel non basis mengindikasikan bahwa jika variabel non basis dinaikkan justru akan menyebabkan penurunan pada nilai Z.

Oleh karena itu, untuk masalah minimasi, hanya variabel non basis yang mempunyai koefisien fungsi tujuan relatif yang negatif saja yang memenuhi syarat sebagai calon variabel yang masuk basis (entering variable).

Variabel yang masuk basis (entering variable) adalah variabel yang mempunyai koefisien fungsi tujuan relatif paling negatif.

Sehingga kondisi optimalitas pada masalah minimasi terjadi apabila semua nilai koefisien fungsi tujuan relatif variabel non basis adalah tak negatif.


Alternatif lain untuk memecahkan masalah minimasi adalah dengan mengkonversikannya menjadi masalah maksimasi dengan memecahkan dengan metode simpleks untuk masalah maksimasi.Konversi dilakukan dengan mengalikan fungsi tujuan untuk masalah minimasi dengan minus satu. Pemecahan untuk masalah minimisasi

Meminimumkan Z = 4x1 + x2

dengan pembatas-pembatas: 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 4 x1 ≥ 0, x2 ≥ 0


Memaksimumkan Z’ = -4x1 - x2

dengan pembatas-pembatas: 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 4 x1 ≥ 0, x2 ≥ 0


Solusi optimal kedua permasalahan akan sama, tetapi nilai optimalnya berbeda dalam hal tanda.

Dengan kata lain:

Nilai minimum dari Z = - (Nilai maksimum dari Z’)


Masalah-masalah komputasiNilai yang sama pada koefisien fungsi tujuan relatif yang terbesar Pilih variabel non basis yang akan masuk (entering variable) secara sebarang.Nilai yang sama pada rasio minimum untuk dua atau lebih pembatas

Pilih variabel yang akan keluar (leaving variable) secara sebarang. Implikasi dari nilai yang sama ini adalah akan menghasilkan solusi yang degenerate.

Masalah-masalah komputasiSolusi optimal alternatif (alternate optimal solution)Solusi yang tak terbatas (unbounded solution)

Solusi optimum alternatif(Alternate optimum solution)


dengan pembatas-pembatas: x1 + 2x2 5 x1 + x2 4 x1 ≥ 0, x2 ≥ 0

Bentuk kanonik


dengan pembatas-pembatas: x1 + 2x2 + x3 = 5 x1 + x2 + x4 = 4 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Tabel 1

cB

2 4 0 0Konstanta

x1 x2 x3 x4

0 x3 1 2 1 0 5

0x4

1 1 0 1 4

2 4 0 0 Z = 0

Basis

cj

c Baris

Tabel 2 (Optimal)

cB

2 4 0 0Konstanta

x1 x2 x3 x4

4 x2 1/2 1 1/2 0 5/2

0x4

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

0 0 -2 0 Z = 10

Basis

cj

c Baris

Tabel 3 (Optimal alternatif)

cB

2 4 0 0Konstanta

x1 x2 x3 x4

4 x2 0 1 1 -1 1

2x1

1 0 -1 2 3

0 0 -2 0 Z = 10

Basis

cj

c Baris

Solusi secara grafis

x1

x2

Catatan

Solusi optimal alternatif dalam tabel simpleks dapat diidentifikasi dengan melihat apakah terdapat koefisien fungsi tujuan relatif yang nol untuk variabel non basis pada tabel optimal.

Dalam praktek, pengetahuan tentang optima alternatif adalah berguna karena ini memberikan manajemen untuk memilih solusi yang terbaik yang cocok dengan situasi tanpa terjadinya penurunan pada nilai fungsi tujuan.

Solusi tak terbatas(Unbounded solution)


dengan pembatas-pembatas: x1 – x2 2 -3x1 + x2 3 x1 ≥ 0, x2 ≥ 0

Bentuk kanonik


dengan pembatas-pembatas: x1 – x2 + x3 = 2 -3x1 + x2 + x4 = 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Tabel 1

cB

2 3 0 0Konstanta

x1 x2 x3 x4

0 x3 1 -1 1 0 2

0x4

-3 1 0 1 3

2 3 0 0 Z = 0

Basis

cj

c Baris

Tabel 2

cB

2 3 0 0Konstanta

x1 x2 x3 x4

0 x3 -2 0 1 1 5

3x2

-3 1 0 1 3

11 0 0 -3 Z = 9

Basis

cj

c Baris

Catatan

Tabel 2 belum optimalVariabel non basis x1 dapat menjadi

basis (entering variable) untuk menaikkan Z.

Tetapi, aturan rasio minimum gagal karena tidak ada elemen positif pada kolom x1.

Dengan kata lain, jika x1 meningkat maka kedua variabel basis x3 dan x2 juga meningkat sehingga tidak akan pernah mencapai nol sebagai batas peningkatan x1.

CatatanIni berarti bahwa x1 dapat dinaikkan

secara tak terbatas. Karena tiap peningkatan satu unit x1

akan meningkatkan Z sebesar 11 unit, maka fungsi tujuan dapat dinaikkan tak terbatas.

Oleh karena itu, solusi bagi masalah LP adalah solusi tak terbatas (unbounded solution).

Dengan demikian, kegagalan dalam aturan rasio minimum mengindikasikan bahwa masalah LP mempunyai solusi yang tak terbatas.


x1

x2

Degenerasi (Degeneracy)

Jika terjadi nilai yang sama pada rasio minimum, maka pemilihan variabel yang keluar basis (leaving variable) dapat dilakukan sebarang.

Akibatnya, satu atau lebih variabel basis akan mempunyai nilai nol pada iterasi berikutnya.

Dalam kasus ini, masalah LP dikatakan mempunyai solusi yang degenerate.

Degenerasi (Degeneracy)


dengan pembatas-pembatas: x1 + 4x2 8 x1 + 2x2 4 x1 ≥ 0, x2 ≥ 0

Bentuk kanonik


dengan pembatas-pembatas: x1 + 4x2 + x3 = 8 x1 + 2x2 + x4 = 4 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Tabel 1

cB

3 9 0 0Konstanta

x1 x2 x3 x4

0 x3 1 4 1 0 8

0x4

1 2 0 1 4

3 9 0 0 Z= 0

Basis

cj

c Baris

Tabel 2

cB

3 9 0 0Konstanta

x1 x2 x3 x4

9 x2 1/4 1 1/4 0 2

0x4

1/2 0 -1/2 1 0

3/4 0 -9/4 0 Z = 18

Basis

cj

c Baris

Tabel 3 (Optimal)

cB

3 9 0 0Konstanta

x1 x2 x3 X4

9 x2 0 1 ½ -1/2 2

0x1

1 0 -1 2 0

0 0 -3/2 -3/2 Z = 18

Basis

cj

c Baris

CatatanImplikasi praktek dari degenerasi?

Terdapat pembatas yang redundan.


x1

x2

CatatanDari sudut pandang teoritis, degenerasi mempunyai implikasi:

Fenomena cycling atau circling prosedur simpleks mengulangi iterasi yang sama tanpa memperbaiki nilai fungsi tujuan dan tanpa pernah berhenti.

LOGO

Selamat Belajar!

(5) basic simplex

Documents