Modul 3 – PEMROGRAMAN LINIER METODE SIMPLEKS


Dalam menggunakan metode simpleks, hal yang perlu diperhatikan adalah mengonversi constraint yang masih dalam bentuk pertidaksamaan menjadi persamaan menggunakan bantuan variabel slack. Dan nilai di sisi kanan harus non negatif.

Dalam constraint yang menggunakan tanda ≤ dapat dipikirkan merupakan representasi batas ketersediaan sumber daya, dimana sisi kiri adalah representasi penggunaan sumber daya oleh aktivitas (variabel) model. Perbedaan antara sisi kanan dan sisi kiri tanda ≤ merupakan sejumlah sumber daya yang belum digunakan atau slack.

Langkah-langkah awal sebelum menggunakan metode simpleks :

1. Mengonversi pertidaksamaan (≤ atau ≥) menjadi persamaan

Untuk mengonversi pertidaksamaan (≤) menjadi persamaan, sebuah variabel slack nonnegative ditambahkan pada sisi kiri constraint. Misalnya pada kasus Reddy Mikks, constraint yang menyatakan penggunakan bahan baku M1 diberikan oleh :

6x1 + 4x2 ≤ 24

Definisikan s1 sebagai variabel slack dari M1, maka constraint dapat dikonversi menjadi :

6x1 + 4x2 + s1 = 24, s1 ≥ 0

Selanjutnya, untuk constraint dengan tanda ≥, menyatakan batas terendah aktivitas model program linear, sehingga jumlah yang dinyatakan disisi kiri melewati batas minimal yang direpresentasikan sebagai surplus. Konversi dari ≥ ke = dicapai dengan mengurangi dengan variabel surplus non negatif dari sisi kiri pertidaksamaan. Misalnya, dalam kasus Ozark Farm, constraint yang menyatakan kebutuhan makanan :

x1 + x2 ≥ 800

Definisikan r1 sebagai variabel surplus, constraint dapat dikonversi menjadi persamaan berikut :

x1 + x2 – r1 = 800, r1 ≥ 0

Sedangkan untuk kasus dimana sisi kanan constraint bernilai negatif, maka harus dilakukan perkalian kedua sisi dengan -1 setelah langkah diatas dilakukan. Misalnya constraint :

-x1 + x2 ≤ -3

Maka bentuk persamaannya menjadi :

-x1 + x2 + r1 = -3, r1 ≥ 0

Selanjutnya kedua sisi dikalikan dengan -1, sehingga sisi kanan bernilai positif :

x1 – x2 – r1 = 3

2. Menambahkan variabel slack ke fungsi tujuan dengan koefisien nol

Pada kasus model Reddy Mikks, fungsi tujuan Z = 5x1 + 4x2 dengan 4 variabel slack menjadi Z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4.

3. Memindahkan komponen sisi kanan fungsi tujuan ke sisi kanan

Pada kasus model Reddy Mikks, fungsi tujuan Z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4 menjadi Z – 5x1 – 4x2 – 0s1 – 0s2 – 0s3 – 0s4 = 0.

Dalam menyelesaikan kasus pemrograman linier, metode simpleks memberikan langkah-langkah penyelesaian sebagai berikut :

  1. Menentukan awal basis solusi layak
  2. Memilih variabel masuk menggunakan syarat keoptimalan. Berhenti jika tidak ada lagi variabel masuk, solusi terakhir adalah solusi optimal. Jika tidak maka ke langkah 3.
  3. Memilih variabel keluar menggunakan syarat kelayakan.
  4. Menentukan solusi dasar yang baru menggunakan perhitungan Gauss-Jordan. Kembali ke langkah 2.

Syarat keoptimalan (optimality condition). Variabel masuk dalam kasus pemaksimalan (peminimalan) adalah variabel nonbasis yang mempunyai koefisien negatif terbesar (pemaksimalan) atau positif terbesar (peminimalan) dalam baris ­z-row. Syarat optimal dicapai pada iterasi dimana semua koefisien z-row dari variabel nonbasis tidak negatif (pemaksimalan) atau tidak positif (peminimalan)

Syarat kelayakan (feasibility condition). Untuk kedua masalah pemaksimalan dan peminimalan, variabel keluar adalah variabel basis yang dikaitkan dengan rasio non negatif terkecil.

Operasi baris Gauss-Jordan :

1. Menentukan baris kunci :

a.       Gantilah variabel keluar dalam kolom basis dengan variabel masuk

b.      Baris kunci baru = Baris kunci ¸ elemen kunci.

2. Mengganti nilai baris yang lain :

Baris baru = Baris lama – koefisien kolom kunci ´ Baris kunci baru

Variabel basis adalah variabel yang berkontribusi (mempunyai nilai) memberikan solusi yang diminta. Variabel nonbasis adalah variabel yang tidak berkontribusi (bernilai 0) dalam pemberian solusi. Inisialisasi dalam metode simpleks :

  1. x1, x2, … adalah variabel non basis
  2. s1, s2, … adalah variabel basis

Dalam iterasi metode simpleks, satu persatu variabel slack akan berubah menjadi variabel non basis karena keluar dari solusi dasar (variabel keluar), dan variabel keputusan akan berubah menjadi variabel basis karena masuk ke basis solusi (variabel masuk).

Download file materi lengkap : MS2011 – Modul 3 – Pemrograman Linier metode simpleks

Download file persentasi :MS2011-Modul 3-Pemrograman Linear-Simpleks – ppt

Soal Latihan

3.1Perhatikan constraint dibawah ini

x1 + 2x2 + 2x3 + 4x4 40

2x1 – x2 + x3 + 2x4 8

4x1 – 2x2 + x3 – x4 10

x1, x2, x3, x4 ≥ 0

Selesaikan masalah setiap fungsi tujuan dibawah ini dengan metode simpleks:

(a)Maksimalkan Z = 2x1 + x2 – 3x3 + 5x4

(b)Maksimalkan Z = 8x1 + 6x2 + 3x3 – 2x4

(c)Maksimalkan Z = 3x1 – x2 + 3x3 + 4x4

(d)Maksimalkan Z = 5x1 – 4x2 + 6x3 – 8x4

3.2Perhatikan Linear Programming dibawah ini

Maksimalkan Z = 16x1 + 15x2

Fungsi kendala :

40x1 + 31x2 124

-x1 + x2 1

x1 3

x1, x2 ≥ 0

(a)Selesaikan masalah dengan metode simpleks, dimana variabel masuk yang terpilih adalah variabel nonbasis dengan koefisien z-row negatif terbesar.

(b)Selesaikan ulang masalah dengan metode simpleks, dimana variabel masuk yang terpilih adalah variabel nonbasis dengan koefisien z-row negatif terkecil.

(c)Lakukan analisis perbandingan hasil (a) dan (b).

3.3Gutchi Company memproduksi purses, shaving bag dan backpack. Konstruksi barang terbuat dari kulit. Proses produksi membutuhkan dua jenis keterampilan kerja : sewing dan finishing. Tabel dibawah ini menginformasikan ketersediaan sumber daya, penggunaan oleh tiga produk dan keuntungan per unit.

Sumber daya

Kebutuhan sumber daya per unit

Kapasitas harian

Purse

Bag

Backpack

Kulit (ft2)

2

1

3

42 ft2

Sewing (hr)

2

1

2

40 hr

Finishing (hr)

1

5

1

45 hr

Harga jual ($)

24

22

45

(a)Formulasikan masalah menjadi pemrogram linear dan carilah solusi optimal dengan metode simpleks

(b)Dari solusi optimal yang didapatkan tentukan status dari setiap sumber daya.

3.4Perhatikan Linear Programming berikut :

Maksimalkan Z = x1 + x2 + 3x3 + 2x2

Constrain :

x1 + 2x2 – 3x3 + 5x4 4

5x1 – 2x2 + 6x4 8

2x1 + 3x2 – 2x3 + 3x4 3

-x1 + x3 + 2x4 0

x1, x2, x3, x4 ≥ 0

(a)Formulasikan masalah menjadi pemrogram linear dan carilah solusi optimal dengan metode simpleks

(b)Dari solusi optimal yang didapatkan tentukan status dari setiap sumber daya.

3.5Perhatikan constraint Linear Programming berikut :

-2x1 + 3x2 = 3              (1)

4x1 + 5x2 ≥ 10             (2)

x1 + 2x2 5                 (3)

6x1 + 7x2 3               (4)

4x1 + 8x2 ≥ 5               (5)

x1, x2 ≥ 0

Untuk setiap masalah dibawah ini, dapatkan nilai Z :

(a)Maksimalkan Z = 5x1 + 6x2 dengan kendala (1), (3), dan (4)

(b)Maksimalkan Z = 2x1 – 7x2 dengan kendala (1), (2), (4) dan (5)

(c)Minimalkan Z = 3x1 + 6x2 dengan kendala (3), (4), dan (5)

(d)Minimalkan Z = 4x1 + 6x2 dengan kendala (1), (2), dan (5)

(e)Minimalkan Z = 3x1 + 2x2 dengan kendala (1) dan (5)

3.6Perhatikan constraint berikut :

x1 + x2 + x3 = 7

2x1 – 5x2 + x3 ≥ 10

x1, x2, x3 ≥ 0

Selesaikan masalah untuk setiap fungsi tujuan berikut :

(a)Maksimalkan Z = 2x­1 + 3x2 – 5x2

(b)Minimalkan Z = 2x1 + 3x2 – 5x3

(c)Maksimalkan Z = x1 + 2x2 + x3

(d)Minimalkan Z = 4x1 – 8x2 + 3x2

3.7Perhatikan masalah berikut :

Maksimalkan Z = x1 + 5x2 + 3x3

Kendala :

x1 + 2x2 + x3 = 3

2x1 – x2 = 4

x1, x2, x3 ≥ 0

Variabel x3 bisa dianggap memainkan peran sebagai slack. Sehingga, tidak ada variabel buatan yang dibutuhkan di constraint pertama. Di constraint kedua, variabel buatan masih diperlukan. Coba gunakan solusi awal ini (x3 dalam constraint pertama dan R2 dalam constraint kedua) untuk menyelesaikan masalah.

3.8Tunjukkan bagaimana metode M akan menunjukkan bahwa masalah dibawah ini tidak punya solusi yang layak.

Maksimalkan Z = 2x1 + 5x2

Kendala :

3x1 + 2x2 ≥ 6

2x1 + x2 2

x1, x2 ≥ 0

1.1Perhatikan constraint dibawah ini

x1 + 2x2 + 2x3 + 4x4 £ 40

2x1 – x2 + x3 + 2x4 £ 8

4x1 – 2x2 + x3 – x4 £ 10

x1, x2, x3, x4 ≥ 0

Selesaikan masalah setiap fungsi tujuan dibawah ini dengan metode simpleks:

(a)Maksimalkan Z = 2x1 + x2 – 3x3 + 5x4

(b)Maksimalkan Z = 8x1 + 6x2 + 3x3 – 2x4

(c)Maksimalkan Z = 3x1 – x2 + 3x3 + 4x4

(d)Maksimalkan Z = 5x1 – 4x2 + 6x3 – 8x4

1.2Perhatikan Linear Programming dibawah ini

Maksimalkan Z = 16x1 + 15x2

Fungsi kendala :

40x1 + 31x2 £ 124

-x1 + x2 £ 1

x1 £ 3

x1, x2 ≥ 0

(a)Selesaikan masalah dengan metode simpleks, dimana variabel masuk yang terpilih adalah variabel nonbasis dengan koefisien z-row negatif terbesar.

(b)Selesaikan ulang masalah dengan metode simpleks, dimana variabel masuk yang terpilih adalah variabel nonbasis dengan koefisien z-row negatif terkecil.

(c)Lakukan analisis perbandingan hasil (a) dan (b).

1.3Gutchi Company memproduksi purses, shaving bag dan backpack. Konstruksi barang terbuat dari kulit. Proses produksi membutuhkan dua jenis keterampilan kerja : sewing dan finishing. Tabel dibawah ini menginformasikan ketersediaan sumber daya, penggunaan oleh tiga produk dan keuntungan per unit.

Sumber daya

Kebutuhan sumber daya per unit

Kapasitas harian

Purse

Bag

Backpack

Kulit (ft2)

2

1

3

42 ft2

Sewing (hr)

2

1

2

40 hr

Finishing (hr)

1

5

1

45 hr

Harga jual ($)

24

22

45

(a)Formulasikan masalah menjadi pemrogram linear dan carilah solusi optimal dengan metode simpleks

(b)Dari solusi optimal yang didapatkan tentukan status dari setiap sumber daya.

1.4Perhatikan Linear Programming berikut :

Maksimalkan Z = x1 + x2 + 3x3 + 2x2

Constrain :

x1 + 2x2 – 3x3 + 5x4 £ 4

5x1 – 2x2 + 6x4 £ 8

2x1 + 3x2 – 2x3 + 3x4 £ 3

-x1 + x3 + 2x4 £ 0

x1, x2, x3, x4 ≥ 0

(a)Formulasikan masalah menjadi pemrogram linear dan carilah solusi optimal dengan metode simpleks

(b)Dari solusi optimal yang didapatkan tentukan status dari setiap sumber daya.

1.5Perhatikan constraint Linear Programming berikut :

-2x1 + 3x2 = 3              (1)

4x1 + 5x2 ≥ 10             (2)

x1 + 2x2 £ 5                 (3)

6x1 + 7x2 £ 3               (4)

4x1 + 8x2 ≥ 5               (5)

x1, x2 ≥ 0

Untuk setiap masalah dibawah ini, dapatkan nilai Z :

(a)Maksimalkan Z = 5x1 + 6x2 dengan kendala (1), (3), dan (4)

(b)Maksimalkan Z = 2x1 – 7x2 dengan kendala (1), (2), (4) dan (5)

(c)Minimalkan Z = 3x1 + 6x2 dengan kendala (3), (4), dan (5)

(d)Minimalkan Z = 4x1 + 6x2 dengan kendala (1), (2), dan (5)

(e)Minimalkan Z = 3x1 + 2x2 dengan kendala (1) dan (5)

1.6Perhatikan constraint berikut :

x1 + x2 + x3 = 7

2x1 – 5x2 + x3 ≥ 10

x1, x2, x3 ≥ 0

Selesaikan masalah untuk setiap fungsi tujuan berikut :

(a)Maksimalkan Z = 2x­1 + 3x2 – 5x2

(b)Minimalkan Z = 2x1 + 3x2 – 5x3

(c)Maksimalkan Z = x1 + 2x2 + x3

(d)Minimalkan Z = 4x1 – 8x2 + 3x2

1.7Perhatikan masalah berikut :

Maksimalkan Z = x1 + 5x2 + 3x3

Kendala :

x1 + 2x2 + x3 = 3

2x1 – x2 = 4

x1, x2, x3 ≥ 0

Variabel x3 bisa dianggap memainkan peran sebagai slack. Sehingga, tidak ada variabel buatan yang dibutuhkan di constraint pertama. Di constraint kedua, variabel buatan masih diperlukan. Coba gunakan solusi awal ini (x3 dalam constraint pertama dan R2 dalam constraint kedua) untuk menyelesaikan masalah.

1.8Tunjukkan bagaimana metode M akan menunjukkan bahwa masalah dibawah ini tidak punya solusi yang layak.

Maksimalkan Z = 2x1 + 5x2

Kendala :

3x1 + 2x2 ≥ 6

2x1 + x2 £ 2

x1, x2 ≥ 0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: