METODE DUAL SIMPLEKS

METODE DUAL SIMPLEKS

Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.

Min z = 21x₁ + 18x₂ + 15x₃

Terhadap       90x₁ + 20x₂ + 40x₃ ≥ 200

                      30x₁ + 80x₂ + 60x₃ ≥ 180

                      10x₁ + 20x₂ + 60x₃ ≥ 150

                                 x₁, x₂, x₃ ≥ 0

semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:

Min z = 21x₁ + 18x₂ + 15x₃

Terhadap          -90x₁ - 20x₂ - 40x₃ ≤ -200

                         -30x₁ - 80x₂ - 60x₃ ≤ -180

                         -10x₁ - 20x₂ - 60x₃ ≤ -150 

                                   x₁, x₂, x₃ ≥ 0

Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.

Bentuk Baku/standar:

Min z = 21x₁ + 18x₂ + 15x₃ + 0s₁ + 0s₂ + 0s₃

Terhadap -90x₁ - 20x₂ - 40x₃ + s₁ = -200

-30x₁ - 80x₂ - 60x₃ + s₂ = -180

-10x1 - 20x2 - 60x3 + s3 = -150

x₁, x₂, x₃, s₁, s₂, s₃ ≥ 0

METODE DUAL SIMPLEKS

Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.

Min z = 21x₁ + 18x₂ + 15x₃

Terhadap       90x₁ + 20x₂ + 40x₃ ≥ 200

                      30x₁ + 80x₂ + 60x₃ ≥ 180

                      10x₁ + 20x₂ + 60x₃ ≥ 150

                                 x₁, x₂, x₃ ≥ 0

semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:

Min z = 21x₁ + 18x₂ + 15x₃

Terhadap          -90x₁ - 20x₂ - 40x₃ ≤ -200

                         -30x₁ - 80x₂ - 60x₃ ≤ -180

                         -10x₁ - 20x₂ - 60x₃ ≤ -150 

                                   x₁, x₂, x₃ ≥ 0

Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.

Bentuk Baku/standar:

Min z = 21x₁ + 18x₂ + 15x₃ + 0s₁ + 0s₂ + 0s₃

Terhadap -90x₁ - 20x₂ - 40x₃ + s₁ = -200

-30x₁ - 80x₂ - 60x₃ + s₂ = -180

-10x1 - 20x2 - 60x3 + s3 = -150

x₁, x₂, x₃, s₁, s₂, s₃ ≥ 0

Tabel di atas optimal tapi tidak layak (ingat, untuk fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode dual adalah: 1.

1.      Tentukan baris pivot. Baris pivot adalah baris dengan nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih salah satu sembarang.

2.       Tentukan kolom pivot. Kolom pivot diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot. Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0. Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang.

3.      Pembentukan tabel berikutnya sama dengan prosedur dalam primal simpleks.

Gunakan tabel awal simpleks di atas.

Ø  Baris pivot adalah baris S₁, baris dengan nilai kanan negatif terbesar.

Ø  Kolom pivot adalah kolom X₁

Ø  Iterasi-1

Ø  Iterasi-2

Ø  Iterasi-3

Sumber :

- http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

METODE DUA FASE

METODE DUA FASE

Metode dua fase digunakan jika variabel basis awal terdiri dari variabel buatan. Disebut sebagai metode dua fase, karena proses optimasi dilakukan dalam dua tahap. Tahap pertama merupakan proses optimasi variabel buatan, sedangkan proses optimasi variabel keputusan dilakukan pada tahap kedua. Karena variabel buatan sebenarnya tidak ada (hanya ada di atas kertas), maka tahap pertama dilakukan untuk memaksa variabel buatan bernilai 0. Perhatikan kasus berikut: 

Tahap 1

Min A = A₁ + A₂

Terhadap:           x₁ + x₂ + A₁ = 90

                  0.001x₁ + 0.002x₂ + s₁ = 0.9

                  0.09x₁ + 0.6x₂ - s₂ + A₂ = 27

                    0.02x₁ + 0.06x₂ + s₃ = 4.5 

                          x₁, x₂, s₁, s₂, s₃ ≥ 0

karena A₁ dan A₂ berfungsi sebagai variabel basis pada solusi awal, maka koefisiennya pada fungsi tujuan harus sama dengan 0. untuk mencapai itu, gantikan nilai A₁ dari fungsi kendala pertama (kendala yang memuat A₁) dan nilai A₂ dari fungsi kendala ketiga (kendala yang memuat A₂).

Dari kendala -1 diperoleh :

                                           A₁ = 90 - x₁ - x₂

Dari kendala-3 diperoleh: A₂ = 27 - 0.09x₁ - 0.6x₂ + s₂

 Maka fungsi tujuan tahap-1 menjadi:

Min A = (90 - x₁ - x₂) + (27 - 0.09x₁ - 0.6x₂ + s₂)

            =117 - 1.09x₁ - 1.6x₂ + s₂

Solusi awal

Iterasi

Iterasi 2          

Tahap 2

Min z = 2 x1 + 5.5 x2

Terhadap: tabel optimal tahap pertama

Dari tabel optimal tahap 1 diperoleh:

X1 = 52.94 – 17/12s2

X2 = 37.059 + 1.7542s2

Maka fungsi tujuan adalah:

Min z = 2(52.94 – 17/12s2) + 5.5 (37.059 + 1.7542s2)

= -17/6s2 + 9.6481s2 + 309.7045 = 6.814767s2 + 309.7045

Solusi awal            

Tabel di atas sudah optimal. Solusi optimal adalah :

X1 = 52.94; X2 + 37.059; dan z = 309.7045

Sumber : 

 - http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

METODE BIG M

METODE BIG M

Sering kita menemukan bahwa fungsi kendala tidak hanya dibentuk oleh pertidaksamaan ≤ tapi juga oleh pertidakasamaan ≥ dan/atau persamaan (=). Fungsi kendala dengan pertidaksamaan ≥ mempunyai surplus variable, tidak ada slack variables. Surplus variable tidak bisa menjadi variabel basis awal. Dengan demikian harus ditambahkan satu variabel baru yang dapat berfungsi sebagai variabel basis awal. Variabel  yang dapat berfungsi sebagai variabel basis awal hanya slack variables dan artificial variables (variabel buatan). 1.

1.      Jika semua fungsi kendala menggunakan pertidaksamaan ≤ maka variabel basis awal semuanya adalah slack variables. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan cara yang sudah diperkenalkan sebelumnya. 2.

2.      Jika fungsi kendala menggunakan pertidaksamaan ≥ dan/atau ≤ maka variabel basis awal adalah slack variables dan/atau variabel buatan. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan memilih antara metode Big M, Dua Fase atau Dual Simpleks.

3.      Jika fungsi kendala ada yang menggunakan persamaan maka variabel buatan akan ditemukan pada variabel basis awal. Penyelesaian solusi optimal untuk kasus seperti ini hanya dapat dilakukan dengan memilih antara metode Big M atau Dua Fase.

Kita akan bahas metode Big M dalam sub bab ini. Perbedaan metode Big M dengan primal simpleks biasa (teknik penyelesaian yang sudah dipelajari sebelumnya), terletak pada pembentukan tabel awal. Jika fungsi kendala menggunakan bentuk pertidaksamaan ≥, perubahan dari bentuk umum ke bentuk baku memerlukan satu variabel surplus. Variabel surplus tidak dapat berfungsi sebagai variabel basis awal, karena koefisiennya bertanda negatif. Sebagai variabel basis pada solusi awal, harus ditambahkan satu variabel buatan. Variabel buatan pada solusi optimal harus bernilai 0, karena variabel ini memang tidak ada.

Teknik yang digunakan untuk memaksa variabel buatan bernilai 0 pada solusi optimal adalah dengan cara berikut:

·         Penambahan variabel buatan pada fungsi kendala yang tidak memiliki variabel slack, menuntut penambahan variabel buatan pada fungsi tujuan.

·         Jika fungsi tujuan adalah maksimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien +M; jika fungsi tujuan adalah minimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien -M.

·         Karena koefisien variabel basis pada tabel simpleks harus bernilai 0, maka variabel buatan pada fungsi tujuan harus digantikan nilai dari fungsi kendala yang memuat variabel buatan tersebut.

Perhatikan contoh di bawah ini.

Bentuk Umum

Min. z = 4x₁ + x ₂

Terhadap:     3x₁ + x₂ = 3

4x₁ + 3x₂ ≥ 6

x₁ + 2x₂ ≤ 4

x₁, x₂ ≥ 0

Bentuk Baku:

Min. z = 4 x₁ + x₂

Terhadap:     3x₁ + x₂ = 3

4x₁ + 3x₂ - s₁ = 6

x₁ + 2x₂ + s₂ = 4 

x₁, x₂, s₁, s₂ ≥ 0

Kendala 1 dan 2 tidak mempunyai slack variables, sehingga tidak ada variabel basis awal. Untuk berfungsi sebagai variabel basis awal, pada kendala 1 dan 2 ditambahkan masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big M-nya adalah:

Min. z = 4 x₁ + x₂ + MA₁ + MA₂

Terhadap:   3x₁ + x₂ + A₁ = 3

4x₁ + 3x₂ - s₁ + A₂ = 6

x₁ + 2x₂ + s₂ = 4 

x₁, x₂, s₁, s₂ ≥ 0

1.      Nilai A digantikan dari fungsi kendala pertama.

A₁ = 3 - 3x₁ - x₂

MA₁ berubah menjadi M(3 - 3x₁ - x₂)             3M - 3Mx₁ - Mx₂

2.     Nilai A digantikan dari fungsi kendala ketiga.

A₂ = 6 - 4x₁ - 3x₂ + s₁

MA₂ berubah menjadi M(6 - 4x₁ - 3x₂ + s₁)

6M - 4Mx₁ - 3Mx₂ + Ms₁

3.      Fungsi tujuan berubah menjadi

Min z   = 4x₁ + x₂ + 3M - 3Mx₁ - Mx₂ + 6M - 4Mx₁ - 3Mx₂ + Ms₁

= (4 -7M)x₁ + (1 - 4M)x₂ + Ms₁ + 9M

Sumber :  
- http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b