Metode Simplex

Penyelesaian Persoalan LP Secara Matematis (Metode Simpleks)
Metode Simpleks adlh suatu metode yg secara matematis dimulai dr suatu pemecahan dasar yg feasibel (basic feasible solution) ke pemecahan dasar feasibel lainnya dan dilakukan secara berulang-ulang (iteratif) sehingga akhirnya diperoleh suatu pemecahan dasar yang optimum. ( dikembangkan oleh George B Dantzig )
 Langkah 1:
Ubah model LP kedalam bentuk kanoniknya, semua fungsi kendala berupa persamaan, dg cara menambahkan slack variabel
 Setiap fungsi kendala mempunyai slack variabel.
Þ jumlah slack variable = jumlah fungsi kendala
 Nilai sebelah kanan (right-hand side) semua kendala tidak boleh negatif.
Bentuk Kanonik Program Linier
Aktifitas Kebutuhan Resources / unit Jml. Res.
yang dapat
digunakan
Resources 1 2 3 . . . n
1
2
3
..
M
Z
Aktifitas
Terminologi Penyelesaian
• Penyelesaian feasible
suatu penyelesaian yang memenuhi seluruh kendala, dalam hal ini berbentuk suatu daerah yang dibatasi oleh kendala-kendala yang diberikan dan biasa disebut daerah feasible
• Suatu Titik Sudut dari Penyelesaian Feasibel
suatu titik dalam daerah feasibel dimana jika ditarik sembarang garis yang menghubungkan 2 titik lain dalam daerah tersebut tidak akan melalui titik sudut itu. Titik ini disebut juga dengan nama Titik Ekstrim, yang merupakan penyelesaian simultan dari suatu sistem dari 2 pers. kendala batas, dan pers. kendala batas itu disebut dengan pers. pendefinisi .
Dua titik ekstrim disebut adjacent jika garis yang menghubungkannya terletak pada batas daerah feasibel .
• Penyelesaian Optimal
suatu penyelesaian feasible yang memberikan nilai terbaik bagi fungsi obyektif . Dalam suatu permasalahan dimungkinkan adanya lebih dari satu penyelesaian yang optimal (Multiple Optimal Solution) .
Batas persamaan kendala yang ada yang bertanda < , = atau > dirubah menjadi tanda , sehingga :
aj xj £ b Þ aj xj + ks = b , s ³ 0
s disebut variabel slack.
aj xj ³ b Þ aj xj - kt = b , t ³ 0
t disebut variabel surplus .
k : konstanta
• Penyelesaian Augmented
suatu penyelesaian masalah pertidaksamaan dengan n variabel yang telah ditambah oleh m variabel slack sehingga menjadi bentuk persamaan dengan n+m variabel .
Suatu Penyelesaian Basis
• merupakan titik ekstrim dari penyelesaian augmented .
• Setiap titik ekstrim adalah penyelesaian simultan dari suatu sistem dari n pers. kendala batas (yang disebut pers. pendefinisi) .
• Suatu variabel defining dari penyelesaian basis adalah variabel yang mengindikasi suatu titik ekstrim dari tiap pers. pendefinisi .
• Jadi setiap penyelesaian basis mempunyai himpunan n variabel defining (biasa disebut var. non basis) yang disama-dengankan nol. Nilai dari m variabel sisanya (disebut var. basis) adalah penyelesaian simultan dari sistem m pers. untuk masalah dalam bentuk pers. (setelah var. non basisnya disama-dengankan nol).
• Suatu penyelesaian basis feasibel adalah suatu penyelesaian basis dimana seluruh m var. basisnya adalah non negatif ( > 0). Suatu penyelesaian basis feasibel dikatakan degenerate, jika m var. basis itu sama dengan nol
Sifat -sifat penyelesaian feasible
• Sifat 1 :
a. Jika terdapat satu penyelesaian optimal, maka penyelesaian itu merupakan suatu titik ekstrim .
b. Jika terdapat beberapa penyelesaian optimal, maka paling tidak 2 diantaranya adalah adjacent .
• Sifat 2 :
Hanya terdapat berhingga titik ekstrim .
Jika terdapat m persamaan kendala dengan n variabel, maka akan
ada paling banyak titik ekstrim
• Sifat 3 :
Jika terdapat suatu titik ekstrim yang memberikan nilai Z yang lebih baik dari seluruh adjacent, maka titik ekstrim itu adalah penyelesaian yang optimal .








Persoalan Perencanaan Produksi
Perusahaan Halston Farina memasarkan biji-bijian merk HW dalam tiga ukuran: besar (large), raksasa (giant) dan jumbo.
Rencana produksi bulan depan:
11.500 kotak jumbo,
15.400 kotak raksasa
2.000 kotak besar.
Produksi sebenarnya dapat bervariasi dari target ini asalkan tidak lebih dari 10 persen.
Persediaan gandum panggang yang siap diolah ada dalam jumlah tak terbatas.
Proses produksi meliput penggilingan dan pengepakan.
Persoalan Perencanaan Produksi








Grafis











BV x1 x2 S1 S2 S3 CV
x2 0 1 2 -1 0 2
x1 1 0 -1 1 0 13
S3 0 0 -3 1 1 3
Z 0 0 1 1 0 43