Metode Simpleks Kelompok 2.doc

MAKALAH PROGRAM LINEAR “METODE SIMULASI”

Disusun Oleh : Kelompok 2 (Dua) Sri Lestari Sabrina Makagiantang Fajar Saputra Tubagus Yesinta Kezia Tilaar Sintia Rondonuwu Anggreany F. Sulaeman T

(15101103008) (17101103037) (17101103039) (17101103059) (17101103065) (17101103071)

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SAM RATULANGI MANADO 2019 0

KATA PENGANTAR Puji syukur kami panjatkan kepada Tuhan Yang Maha Esa atas berkat dan rahmat-Nya sehingga kami dapat menyusun makalah “Metode Simpleks”. Kami ucapkan terima kasih kepada dosen pengampu mata kuliah PROGRAM LINEAR yang telah menuntun kami untuk menyelesaikan makalah ini. Terakhir kami ucapkan terimakasih kepada teman – teman dan semua pihak yang telah membantu dalam diskusi untuk menyelesaikan makalah ini. Kami berharap makalah ini dapat membantu dalam menyelesaikan tugas ataupun pekerjaan yang kita lakukan.

Manado, Maret 2019

Kelompok 2

1

DAFTAR ISI

KATA PENGANTAR..............................................................................................................0 DAFTAR ISI............................................................................................................................2 BAB I PENDAHULUAN........................................................................................................3 A. Latar Belakang.................................................................................................................3 B. Rumusan Masalah............................................................................................................4 C. Tujuan..............................................................................................................................4 BAB II PEMBAHASAN.........................................................................................................5 1.

Masalah Maksimasi.........................................................................................................5

2.

Kendala (Syarat) Bertanda “ = ”..................................................................................... 14

3.

Masalah Minimumisasi.................................................................................................. 20

4.

Masalah Primal dan Dual............................................................................................... 24

5.

Degeneracy.................................................................................................................... 30

BAB III PENUTUP............................................................................................................... 32 1.

Kesimpulan.................................................................................................................... 32

2.

Saran.............................................................................................................................. 32

DAFTAR PUSTAKA............................................................................................................. 33

2

BAB I PENDAHULUAN A. Latar Belakang Salah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah manajemen sains adalah pemrograman linear. Pemrograman linear merupakan kelompok teknik analisis kuantitatif yang mengandalkan model matematika atau model simbolik sebagai wadahnya. Artinya, setiap masalah yang kita hadapi dalam suatu sistem permasalahan tertentu perlu dirumuskan dulu dalam simbolsimbol matematika tertentu, jika kita inginkan bantuan pemrograman linear sebagai alat analisisnya. Metode grafik merupakan salah satu metode yang dapat digunakan untuk menyelesaikan masalah pemrograman linear yang melibatkan dua peubah keputusan. Membahas mengenai

masalah meminimumkan fungsi kendala

bertanda ≥, fungsi kendala bertanda = tidak ada penyelesaian layak, tidak ada penyelesaian optimal, beberapa alternatif optimal, dan wilayah kelayakan yang tidak terikat dapat terjadi saat menyelesaikan masalah pemrograman linear dengan menggunakan prosedur penyelesaian grafik. Kasus-kasus ini juga dapat terjadi saat menggunakan metode simpleks. Metode simplek untuk linier programming dikembangkan pertama kali oleh George Dantzing pada tahun 1947, kemudian digunakan juga pada penugasan di Angkatan Udara Amerika Serikat. Dia mendemonstrasikan bagaimana menggunakan fungsi tujuan (iso-profit) dalam upaya menemukan solosi diantara beberapa kemungkinan solosi sebuah persoalan linier programming. Proses penyelesaiaanya dalam metode simplek, dilakukan secara berulangulang (iterative) sedemikian rupa dengan menggunakan pola tertentu (standart) sehingga solusi optimal tercapai. Ciri lain dari metode simplek adalah bahwa setiap solusi yang baru akan menghasilkan sebuah nilai fungsi tujuan yang lebih besar daripada solosi sebelumnya.

3

B. Rumusan Masalah Adapun rumusan masalah yang akan dibahas dalam makalah ini adalah sebagai berikut: 1. Bagaimana cara mencari nilai maksimum dengan menggunakan metode simpleks? 2.

Bagaimana cara menyelesaikan masalah/kendala (syarat) bertanda “=”?

3.

Bagaimana cara mencari nilai minimum dengan menggunakan metode simpleks?

4. Bagaimana cara membedakan antara asalah primal dan dual dalam program linear? 5. Kapan pemrograman linear dikatakan mengalami degenerasi? C. Tujuan Adapun tujuan dari penulisan makalah ini antara lain : 

Dapat menyelesaikan masalah maksimasi dalam program linear



Dapat menyelesaikan masalah / kendala (syarat) bertanda “=” pada program linear



Dapat menyelesaikan masalah minimasi dalam program linear



Dapat mengetahui dan membedakan antara masalah primal dan dual dalam program linear



Dapat menyelesaikan masalah degeneracy / kemerosotan dalam program linear

4

BAB II PEMBAHASAN 1. Masalah Maksimasi Untuk menyelesaikan masalah maksimasi maka programasi linear harus lebih dahulu ditulis dalam bentuk standar. Dengan bentuk standar dimaksudkan adalah permasalahan programasi linear yang berwujud permasalahan maksimasi dengan batasan-batasan (kendala) yang bertanda kurang dari atau sama dengan ( ≤

) yang menunjukkan keterbatasan sumber daya yang tersedia. Untuk bentuk-

bentuk lain seperti masalah minimisasi maupun penyimpangan–penyimpangan lain dalam batasan-batasan yang berlaku akan dibicarakan tersendiri. Berikut merupakan langkah-langkah menggunakan metode simpleks yaitu : 

Mengubah fungsi tujuan dan batasan-batasan



Menyusun persamaan-persamaan di dalam table



Memilih kolom kunci



Memilih baris kunci



Merubah nilai-nilai pada baris kunci



Mengubah nilai-nilai selain pada baris kunci

 Melenjutken pereeikenepeneuleneeneitere si Contoe ee

Maksimumkan Batasan (constrain)

=31+52

(1) 2 (2) (3)

1≤

8

3 2 ≤ 15 6 1 + 5 2 ≤ 30

Langkah 1: Mengubah fungsi tujuan dan batasan-batasan 

Fungsi tujuan 5



= 3 1 + 5 2 diubah menjadi − 3 1 − 5 2 = 0

Fungsi batasan (diubah menjadi kesamaan & di + slack variabel) (1) 2 1 ≤ 8 menjadi 2 1 +

3

=8

(2) 3 2 ≤ 15 menjadi 3 2 + 4 = 15 (3) 6 1 + 5 2 ≤ 30 menjadi 6 1 + 5 2 + 5 = 30

Fungsi tujuan : Maksimumkan

Fungsi batasan

(1) 2

1

(2) 3

2+ 4

(3) 6

1

−31−52 +

3

=0

=8 = 15

+52+

5=

30

Langkah 2: Menyusun persamaan-persamaan di dalam tabel Beberapa istilah dalam Metode Simpleks yaitu : 

NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan ( = ). Untuk batasan 1 sebesar 8, batasan 2 sebesar 15, dan batasan 3 sebesar 30.



Variabel dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada persamaan 2 1 + 3 = 8, kalau belum ada kegiatan apa-apa, berarti nilai 1 = 0, dan semua kapasitas masih menganggur, maka pengangguran ada 8 satuan, atau nilai 3 = 8. Pada tabel tersebut nilai

variabel dasar 3, 4, 5 pada fungsi tujuan pada tabel permulaan ini harus 0, dan nilainya pada batasan-batasan bertanda positif

= 3 1 + 5 2 diubah menjadi − 3 1 − 5 2 = 0.

(1) (2) (3)

2 1 ≤ 8 menjadi 2 1 +

3=

3 2 ≤ 15 menjadi 3 2 +

4

8

= 15

6 1 + 5 2 ≤ 30 menjadi 6 1 + 5 2 + 5 = 30

6

Maka tabel simpleks yang pertama yaitu sebagai berikut : Variabel Dasar

3

4

5

1

2

3

4

NK

5

1

-3

-5

0

0

0

0

0

2

0

1

0

0

8

0

0

3

0

1

0

15

0

6

5

0

0

1

30

Langkah 3: Memilih kolom kunci Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel simplek. Pilihlah kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar. Dalam hal ini kolom 2 dengan nilai pada baris persamaan tujuan –5. Berilah tanda segi empat pada kolom 2, seperti tabel berikut

Tabel simpleks: pemilihan kolom kunci pada tabel pertama Variabel 1

Dasar

1

2

-3

3

-5

4

0

NK

5

0

0

0

7

3

4

5

0

2

0

1

0

0

8

0

0

3

0

1

0

15

0

6

5

0

0

1

30

Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi (sudah optimal). Langkah 4: Memilih baris kunci Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci. =

(

(

)

8

)

15

30

Untuk baris batasan 1 besarnya indeks = 0 = ∞, baris batasan 2 = 3 = 5, dan baris batasan 3 = 5 = 6. Pilih baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2 yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam baris kunci disebut angka kunci.

Langkah 5: Mengubah nilai-nilai baris kunci Nilai baris kunci diubah dengan cara membaginya dengan angka kunci,

seperti tabel dibawah ini. bagian bawah

0 3

5

=0;

3 3

=1;

0 3

=0;

1 3

=

1 3

;

0 3

= 0;

15 3

=

. Gantilah variabel dasar pada baris itu dengan variabel yang terdapat di bagian atas kolom kunci ( 2).

Tabel simpleks: Cara mengubah nilai baris kunci

8

Keterangan Variabel Dasar

3

4

5

Z

1

2

3

4

5

NK

(indeks)

1

-3

-5

0

0

0

0

0

2

0

1

0

0

8

8/0 = ∞

0

0

3

0

1

0

15

15/3 = 5

0

6

5

0

0

1

30

30/5 = 6

0

1/3

0

15/3

Z 3

5

2

0

0

1

Langkah 6: Mengubah nilai-nilai selain pada baris kunci Dengan menggunakan rumus berikut ×

=

−

Baris pertama (Z) [-3

-5

0

0

0,

0]

9

Nilai baru

(-5)

[0

1

0

1/3

0,

5]

(-)

=

[-3

0

0

5/3

0,

25]

[2

0

1

0

0,

8]

(0)

[0

1

0

1/3

0,

5]

=

[2

0

1

0

0,

8]

[6

5

0

0

1,

30 ]

(5)

[0

1

0

1/3

0,

5 ]

=

[6

0

0

-5/3

1,

5 ]

Baris ke-2 (batasan 1)

Nilai baru

(-)

Baris ke-4 (batasan 3)

Nilai baru

(-)

Tabel pertama nilai lama dan tabel kedua nilai baru Variabel Dasar Z

3

4

NK

1

2

3

4

5

1

-3

-5

0

0

0

0

0

2

0

1

0

0

8

0

0

3

0

1

0

15

10

5

Z

3

2

5

0

6

5

0

0

1

30

1

-3

0

0

5/3

0

25

0

2

0

1

0

0

8

0

0

1

0

1/3

0

5

0

6

0

0

-5/3

1

5

Langkah 7: Melanjutkan perbaikan Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif

Variabel 2

3

4

5

1

-3

0

0

5/3

0

25

0

2

0

1

0

0

8

0

0

1

0

1/3

0

5

0

6

0

0

-5/3

1

5

Dasar Z

3

4

5

Z

NK

1

Keterangan (Indeks)

= 8/2 = 4

= 5/6 (minimum)

1

11

3

2

1

0 0 0

6/6

0

0

-5/18

1/6

5/6

Nilai baru Baris ke-1

Nilai baru

[-3

0

0

5/3

0,

25 ]

(-3)

[1

0

0

-5/18

1/6,

5/6]

=

[0

0

0

5/6

½,

27 /2]

(-)

1

Baris ke-2 (batasan 1)

Nilai baru

[2

0

1

0

0,

8]

(2)

[1

0

0

-5/18

1/6,

5/6]

=

0

0

1

5/9

-1/3,

61/3]

(-)

Baris ke-3 tidak berubah karena nilai pada kolom kunci = 0

(0)

[0

1

0

1/3

0,

5]

[1

0

0

-5/18

1/6,

5/6]

(-)

12

Nilai baru

=

0

1

0

1/3

0,

5]

Tabel simpleks final hasil perubahan Variabel Dasar

1

Z

3

2

1

2

3

4

NK

5

1

27 /2

1

0

0

0

5/6

½

0

0

0

1

5/9

-1/3

0

0

1

0

1/3

0

5

0

1

0

0

-5/18

1/6

5/6

1

6 /3

Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal Dari tabel final didapat

1

2

=

5 6

=5

= 27 1 2

13

Kendala (Syarat) Bertanda “ = ”

2.

Kendala berbentuk sama dengan (=) juga tidak memiliki variabel basis. Oleh karena itu tambahkan satu variabel basis semu, agar table awal simpleks dapa dibentuk. Misalkan,2 1 + 4 2 = 20 , dapat diubah menjadi 2 1 + 4 2 + = 20, dimana Q adalah variabel basis semu.

Meskipun semua kendala telah memiliki variabel basis, tetapi penambahan

variabel semu tersebut bukan penyelesaian yang fisibel bagi masalah aslinya. Variabel semu harus dikurangi nilainya hingga menjadi nol. Ada dua metode yang dapat dilakukan untuk mengnolkan variabel semu yaitu : 1. Metode M besar 2. Metode dua fase (dua tahapan) Metode M Besar Dalam metode ini, koefisien fungsi tujuan untuk variabel semu diberi nilai yang sangat besar yaitu negatif M atau – M untuk fungsi tujuan maksimum dan positif M atau + M untuk fungsi tujuan minimum.

Contoh 2 Masalah variabel semu Model LP yang telah diformulasikan berbentuk sebagai berikut : Maksimum d.k 1. 2. 3. 4.

1

2 1

1, 2

≥ 20

+

2

≥ 0

≤ 40

= 50 1 + 80 2

= 50

Model LP yang telah diformulasikan berbentuk sebagai berikut: Maksimum d.k

1.

3. 4.

1

+

1

+

1, 2

1

2

= 50 1 + 80 2 + 0 1 − 0 2 −

+ 0 2 + 0 1 + 0 2 = 40 2.

+01+02+01+

, 1,

2, 1,

2

≥0

2

= 50

2

+01−

2

+

1

+ 0 2 = 20

1–

2

14

Tabel awal simpleks dapat dibuat seperti berikut ini: Tabel awal simpleks Metode M besar 50 CB

Vrb. basis

Cj

M

bj

X1 Q2

80

0

0

-M

Indeks

x2

s1

s2

Q1

0

S1

40

1

0

1

0

0

0 40/0 = ~

-M

Q1

20

0

1

0

-1

1

0 20/1

-M

Q2

50

1

1

00

0

1 20

Z j - Cj

-70M

-M-50 -2M-80

0

M

=

0 50/1

0

=

50

Nilai yang terdapat pada baris Zj – Cj Tabel di atas diisi dengan menggunakan cara sebagai berikut: Z = [0, -M, -M] Z1 = [0, -M, -M] Z2 = [0, -M, -M] Z4 = [0, -M, -M] Dan seterusnya.

40

20 - 0 = 0 – 20M – 50M = - 70M 50 1

0 - 50 = 0 – M – 50 = - M - 50 1 0

1 - 80 = 0 – M – M - 80 = - 2M - 80 1 0

−1 - 0 = 0 + M + 0 = M 0

Dengan mengikuti langkah-langkah metode simpleks terdahulu, penyelesaian contoh ke-2 dapat dilihat berikut ini.

Tabel iterasi 1

15

50 CB

Vrb. basis

Cj

M

bj

x1

80 0

0

-M

Indeks

x2

s1 s2

Q1

Q2 0 S1

40

1

0

1

0

0

0 40/0 = ~

80 x2 -M Q2

20

0

1

0

-1

1

0 20/-1=-20

30

1

0

0

1

-1

1 30/1 = 30

-

-M-50 0

Z j - Cj

0

-M-80

2M+80

30M+1.600 0

Tabel Iterasi 2 (Optimum) Cj 50

80

0

0

-M

bj

x1

x2

s1

s2

Q1

Q2

0 S1

40

1

1 0

0

0

80 x2

50

1

0

0

s2

30

1

Z j - Cj

4000

30

CB

0

Vrb. basis

Solusi optimum dicapai apabila

1

= 0 dan

2

0 1 0 0

0

0

-M

Indeks

1

0 1

-1

1

0

M

M+80

= 50, dengan nilai Z = 4.000

Metode dua fase Dalam metode dua fase, penyelesaian dipisahkan menjadi dua tahapan. Setiap tahapan menggunakan tabel simpleks dan proses kerjanya tetap menggunakan langkah-langkah metode simpleks. Fase 1 Tahapan pertama bertujuan untuk mngnolkan/menghilangkan variabel semu, dengan cara membuat fungsi tujuan semu. Fungsi tujuan semu memiliki jumlah variabel sama dengan jumlah variabel semuanya. Kemudian fungsi tujuan semu dimaksimumkan dengan table simpleks. Koefisien fungsi tujuan untuk variabel semu diberi nilai minus satu atau (-1) jika fungsi tujuan maksimum dan

16

plus satu atau (+1) jika fungsi tujuan minimum. Fase satu berakhir apabila fungsi tujuan semu memiliki nilai nol. Proses dilanjutkan ke fase ke-dua. Lihat kembali Contoh 2 di atas. Jumlah variabel semu ada dua yaitu Q 1 dan Q2. Oleh karena itu fungsi tujuan semunya adalah maksimum Z= - Q 1 - Q2. Fungsi tujuan semu ini kita maksimumkan , sehingga penyelesaian fase pertama nampak sebagai berikut. Tabel Awal

CB

Vrb. basis

Cj

0

0

0

x1

x2

s1 1

0

-1

s2

Q1

-1 Q2

Indeks

bj 0

S1

40

1

0

-1

Q1

20

0

1

-1

Q2

50

1

1

Z j - Cj

-70

-1

-2

0

0

x1

x2

s1 1

0

0

0

0

40/0 = ~

-1

1

0

20/1 = 20

0

0

1

50/1 = 50

1

0

0

-1

-1

0 0

Tabel Iterasi 1 Fase Pertama

CB

Vrb. basis

Cj

0

0 s2

Q1

Q2

Indeks

bj 0

S1

40

1

0

0

x2

20

0

1

- 1 Q2

30

1

0

-30

-1

0

Z j - Cj

0

0

0

-1

0 0

1

0 0

40/0 = ~ 20/-1 = -20

1

-1

1

-1

2

0

30/1 = 30

Tabel Iterasi 2 Fase Pertama (Optimum) CB

Vrb. basis

Cj

0

0

0

0

x1

x2

s1

s2

-1 -1 Q1

Q2

Indeks

17

bj 0 S1

40

1

0

1

x2

50

1

1

0

0 s2

30

1

0

0

1

-1 1

30

1

0

0

0

1

0

Z j - Cj

0

0

0

0 1

1 1

Pada table di atas (optimum) fungsi tujuan semu sudah di optimumkan, dan variabel semu Q1 dan Q2 sudah keluar dari basis. Proses dapat dilanjutkan ke fase ke-dua. Apabila variabel semu masih berada dalam basis dengan nilai positif, maka persoalan tersebut tidak layak. Mungkin kesalahan dalam proses perhitungan atau kesalahan dalam formulasi LP. Proses tahap kedua tidak perlu dilanjutkan. Fase 2 Tabel akhir fase pertama merupakan tabek awal fase kedua. Kemudian dioptimalkan dengan memasukkan fungsi ujuan aslinya. Karena pada fase pertama kita telah mengnolkan variabel semu, maka pada fase kedua variabel semu tidak perlu disertakan lagi dalam table (dihilangkan). Lihat table awal fase kedua berikut ini. Tabel awal fase kedua CB

Cj 50

80

0

0

bj

x1

x2

s1

s2

Vrb. basis

0

S1

40

1

0

1

0

80

x2

50

1

1

0

0

0

s2

30

1

0

0

1

Z j - Cj

4.000

30

0

0

Indeks

0

Setelah koefisien fungsi tujuan asli dimasukkan ke dalam table awal fase kedua, secara langsung table awal tersebut menunjukkan table optimum. Karena nilai yang terdapat pada baris Zj – Cj ≥ 0. Solusi optimum adalah x1 = 0 dan x2 = 50.

18

Membandingkan metode M besar dengan metode dua fase, dapat disimpulkan bahwa kedua metode sama-sama menggunakan variabel semu. Perbedaan terletak pada tahapan penyelesaian. disamping itu Metode M besar perhitungannya lebih rumit. Hal ini yang perlu diperhatikan dalam penggunaan metode M besar dan dua fase adalah : 1.

Variabel semu hanya ditambahkan untuk mendapatkan pemecahan awal yang fisibel. Jika kita menggunakan program komputer seperti QSB (Quantitative System for Business), maka penambahan variabel semu tidak perlu dilakukan, karena QSB sudah diprogram sedemikian rupa dalam menghadapi berbagai macam bentuk kendala.

2. Apabila variabel semu telah keluar dari dalam basis, maka pada abel berikutnya variabel semu tidak perlu muncul kembali. 3.

Pada tabel optimum semua variabel semu harus keluar dari dalam basis. Jika variabel semu masih terdapat dalam basis dengan nilai positif, maka persoalan tidak layak.

19

3. Masalah Minimumisasi Masalah minimisasi sangat mungkin ditemui di dalam formulasi LP (Linear Program). Bagaimana menyelesaikan masalah LP jika fungsi tujuannya berbentuk minimisasi? Misalkan fungsi tujuannya adalah : . = 40 1 + 30 2

Untuk menangani masalah ini, ada dua metode yang dapat dilakukan, yaitu: Meode 1

Mengubah fungsi tujuan minimum menjadi maksimum. Caranya adalah mengalikan fungsi tujuan minimum dengan minus satu. Misalkan, fungsi tujuan . = 40 1 + 25 2, diubah maksimum menjadi: − ∗ . = = 40 1 + 25 2.

Jika cara ini dilakukan , maka berlaku ketentuan sebagai berikut ini. 1.

Tabel simpleks berakhir (optimal) apabila nilai yang terdapat pada baris Zj – Cj ≤ 0.

2.

Pada table awal, nilai pada baris Zj – Cj yang berkorespondensi dengan variabel keputusan bertanda positif.

3. Kolom kunci dipilih dari nilai positif terbesar. 4.

Baris kunci tetap mengikuti aturan perbandingan minimum dan bukan negatif.

Proses iterasi selanjutnya sama dengan cara terdahulu. Contoh 1. Masalah Minimisasi Produk Mix Sebuah masalah LP yang telah diformulasikan berbentuk sebagai berikut : Minimum d.k

= 40 1 + 25 2

3 1 + 2 2 ≤ 150 8 1 + 2 2 ≤ 200 1≥0 2 ≥0

Formulasi LP di atas dapat diubah menjadi bentuk standar dengan fungsi tujuan diubah menjadi bentuk maksimum.

20

– ∗ = = − 40 1 − 25 2 + 0 1 + 0 2 d.k 3 1 + 2 2 + 1 + 0 2 = 150

81+22+01+ 1, 2,

u.h

2

1, 2 ≥ 0

= 200

Dengan mengikuti langkah-langkah metode simpleks, penyelesaian masalah minimisasi produk mix adalah sebagai berikut. Tabel awal Simpleks Masalah Minimisasi Vrb. CB basis

Cj

-40

-25 0

0

X1

x2

s1

s2

Indeks

2

1

0

150/3 = 50

1

200/8 = 25

bj 0

S1

150

3

0

S2

200

8

Z j - Cj

0

40

25

0

0

Cj -40

-25

0

0

2

0

Tabel Iterasi 1 CB

Vrb.

Indeks

basis

bj

X1

x2

s1

s2

0

S1

75

0

1,25

1

-3/8

75/1,25 = 60

-40

X1

25

1

0,25

0

1/8

25/0,25 = 100

Z j - Cj

-1000

0

15

0

-5

Tabel Iterasi 2 (Optimum) CB

Cj -40

Vrb.

-25

0

0

Inde ks

basis

bj

X1

x2

s1

s2

-25

X2

60

0

1

0,8

-0,3

-40

X1

10

1

Z j - Cj

-1.900

0

0 0

-0,2 -12

0,2 -0,5

Hasil tabel iterasi ke-2, menunjukkan bahwa solusi optimum adalah:

21

1 = 10,

2 = 60.

dan

= − ∗ = −40(10) – 25(60)

= −(−1.900) = 1.900

Metode 2 Dalam metode ini, kita tidak melakukan perubahan bentuk fungsi tujuan, tetapi secara langsung fungsi tujuan minimum dimasukkan dalam table (tetap seperti aslinya). Jika cara ini dilakukan, maka berlaku ketentuan sebagai berikut: 1.

Tabel simpleks berakhir (optimal) apabila nilai yang terdapat pada baris Zj Cj ≥ 0

2.

Oleh karena fungsi tujuan berbentuk minimum, maka kolom kunci dipilih nilai negatif terkecil yang terdapat pada baris Zj - Cj

3.

Baris kunci tetap mengikuti aturan perbandingan minimum dan bukan negatif.

4. Proses iterasi selanjutnya sama dengan cara terdahulu. Lihat kembali contoh 1 di atas. Bentuk standar masalah minimisasi produk mix adalah sebagai berikut: = 40 1 + 25 2 + 0 1 + 0 2

31+22+

d.k

u.h

1

+ 0 2 = 150

81+22+01+ 1, 2,

1, 2

2

≥0

= 200

Jika bentuk standar tersebut diselesaikan menurut metode 2, hasilnya adalah sebagai berikut: Tabel awal Simpleks Masalah Minimisasi Cj

-40

-25

bj

X1

x2

s1 s2

2

1 0

CB Vrb. basis

0

0

0

S1

150

3

0

S2

200

8

2

0

1

Z j - Cj

0

-40 -25

0

0

Indeks 150/2 = 75 200/2 = 100

22

Tabel Iterasi 1 Cj -40

-25

bj

X1

x2

1,5

1

CB Vrb. basis 0

X2

75

0

S2

50

Z j - Cj

1.875

5 0 -5/2

0

0 s1

0 Indeks s2

0.5

0

75/1,5 = 50

-1

1

50/5 = 10

12,5

0

Tabel Iterasi 2 (optimum) CB Vrb. basis

Cj

-40

-25

0

0

X1

x2

s1

s2

1

0,8

-0,3

-0,2

0,2

12

0,5

Indeks

bj 25

X2

60

0

40

X1

10

1

Z j - Cj

1.900

0

0 0

Tabel optimum kedua metode tersebut menunjukkan hasil yang sama, yaitu 1 = 10 unit dan 2 = 60 unit dengan total nilai = 1.900,00.

23

4. Masalah Primal dan Dual 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 :

24

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.

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

2. Di pemecahan optimum untuk kedua masalah

25

Untuk menjelaskan hubungan antara primal dan dual, perhatikan ilustrasi berikut ini :

Soal ini kita selesaikan melalui penyelesaian dualnya, yakni :

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 :

Sedangkan fungsi objectivenya ditulis dalam bentuk :

Dengan demikian penyelesaian dari persoalan diatas adalah sebagai berikut :

26

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 : = 540 untuk 1 = 5 unit, 2 = 3 unit dan 3 = 17 unit, yakni bahan yang tidak terpakai dari konstraint ketiga, sedangkan 1 = 2 = 0.

Dari tabel ini dapat kita baca nilai

1, 2

,

3 dari

primal problem, yakni :

1 = 1 , sehingga 1 = 15 2 = 2 , sehingga 2 = 10 3 = 3 , sehingga 3 = 0

Nilai shoice variable dari primal ini kalau kita masukkan pada fungsi objective dari primal harus cocok = 540, yakni : =

= 16 1 + 30 2 + 36 3 = 16 (5) + 30 (10) + 36 (0) = 540

27

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

b. 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 :

28

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 : Berdasarkan pembatas :

=41+62+23 41−42≤5

−1+62≤5

−1+2+3≤5 1, 2, 3 ≥ 0

Salah satu iterasi dari persoalan di atas adalah sebagai berikut :

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.

29

5. Degeneracy Suatu pemrograman linear dikatakan mengalami degenerasi jika satu atau lebih peubah dasarnya memiliki nilai nol. Untuk melihat bagaimana terjadinya degenerasi pemrograman linear, perhatikan perubahan nilai sisi sebelah kanan dari kendala waktu perakitan pada masalah PT. Maju Terus. Modifikasi linearnya diperlihatkan sebagai berikut: Maksimumkan Z = 50x1 + 40x2 Dengan kendala 3x1 + 5x2 ≤ 175 waktu perakitan x2 ≤ 20 monitor portable 8x1 + 5x2 ≤ 300 kapasitas gedung x1, x2 ≥ 0 tak negatif Tabel 2.7. Tabel simpleks setelah iterasi pertama x1

x2

S1

S2

S3

50

40

0

0

0

B

Dasar

CB

S1

0

0

25/8

1

0

-3/8

125/2

S2

0

0

1

0

1

0

20

x1

50

1

5/8

0

0

1/8

75/2

zj

50

250/8

0

0

0

1875

cj – zj

0

70/8

0

0

0

Entri dalam baris evaluasi bersih menunjukkan bahwa x2 harus memasuki dasar itu. Maka kita hitung rasio yang tepat untuk

menentukan baris pivot,

diperoleh:

b

 125 / 2

/ 1

a

12

25 / 8  20, b

/ 2

a 22  20 /1  20, b

 75 / 2

/ 3

a

32

5 / 8  60 , maka terlihat

hubungan antara baris pertama dan kedua. Ini merupakan indikasi bahwa kita akan memiliki suatu degenerasi penyelesaian layak dasar pada iterasi berikutnya. Tabel 2.8. Tabel simpleks setelah iterasi berikutnya 30

Dasar

x1

x2

S1

S2

S3

50

40

0

0

0

CB

x2

40

0

1

8/25

0

-3/25

20

S2

0

0

0

-8/25

1

3/25

0

x1

50

1

0

-5/25

0

5/25

25

Zj

50

40

70/25

0

130/25

2050

cj – zj

0

0

-70/25

0

-130/25

Bilamana kita memiliki hubungan dalam rasio minimum b i / a

ij

, akan

selalu ada peubah dasar yang sama dengan nol dalam tabel berikutnya. Oleh karena itu, kita tidak merekam endosikan untuk memperkenalkan langkah-langkah khusus ke dalam metode simpleks guna menghapus kemungkinan terjadinya degenerasi. Jika saat melakukan iterasi algoritma simpleks muncul suatu hubungan untuk rasio minimum b

i

/ a

ij

, maka kita hanya

merekomendasikan untuk memilih baris atas sebagai baris pivot.

31

BAB III PENUTUP 1. Kesimpulan Dengan demikian dapat disimpulkan bahwa program linier programming digunakan

sebagai

alat

bantu

dalam

pengambilan

keputusan

untuk

memaksimalkan ataupun meminimalkan hasil yang didapat.

2. Saran Penulis menyadari tentang penyusunan makalah, tentu masih banyak kesalahan dan kekurangannya, karena terbatasnya pengetahuan dan kurangnya rujukan atau referensi yang ada hubungannya dengan judul makalah ini. Penulis banyak berharap para pembaca yang budiman sudi kiranya memberikan kritik dan saran yang membangun kepada penulis demi sempurnanya makalah ini dan penulisan makalah di kesempatan-kesempatan berikutnya. Semoga makalah ini berguna bagi penulis pada khususnya juga para pembaca yang budiman pada umumnya.

32

DAFTAR PUSTAKA Fitriani. Metode Simpleks. UPI : Bandung Hartanto, Eko. Metode Simpleks Dan BIG-M. Universitas Indonesia : Jakarta Tim Dosen. Modul Program Linear . Universitas Negeri Medan : Medan Widasari, Dian. Metode Simpleks Dalam Program Linear. STMIK Triguna

Dharma : Medan http://lambang.files.wordpress.com/2010/03/03_metode-simplex.pdf http://mathematica.aurino.com/wp-content/uploads/2008/10/simplex.pdf

33