Metode Simpleks

Berikut penjelasannya:

Metode simpleks digunakan untuk memecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan.

Prosedur metode simpleks

Ø  Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

Ø  Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

Ø  Membuat Table Simpleks Awal

Ø  Algoritma metode simpleks

Bentuk Standar dari program linear

1)    Ruas kanan (RK) fungsi tujuan harus nol (0)

2)    Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.

3)    Fungsi kendala dengan tanda “£ ” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

4)    Fungsi kendala dengan tanda “³ ” diubah ke bentuk “£ ” dengan cara mengalikan dengan –1, lalu diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1, karena bertanda negatif.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar dengan cara :

ü  Ada tiga bentuk fungsi kendala:  £, ≥, dan =.

ü  Konversi fungsi kendala bertanda £: menambahkan slack variable pada fungsi kendala tersebut.

ü  Untuk kendala berbentuk ‘³’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.

ü  Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.

ü  Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala.

Contoh Metode Simpleks  Masalah Maksimasi

v  Maksimumkan Z = 3X₁ + 5X₂

v  Berdasarkan kendala (constrain)             

                                (1)          2X₁                                    £ 8

                                (2)                        3X₂                     £ 15

                                (3)          6X₁ + 5X₂                        £ 30

                                (4)          X₁ ³ 0,  X₂ ³ 0

Contoh Soal

Perusahaan Mebel Ais memproduksi lemari jenis A, B, dan C. Produk tersebut diproses melalui tiga departemen: pertukangan, pengecatan, dan penyelesaian. Setiap unit lemari A membutuhkan 3 jam tenaga kerja di departemen pertukangan, 2 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Setiap unit lemari B membutuhkan 4 jam tenaga kerja di departemen pertukangan, 5 jam tenaga kerja di departemen pengecatan, dan 2 jam tenaga kerja di departemen penyelesaian. Dan, setiap unit lemari C membutuhkan 3½ jam tenaga kerja di departemen pertukangan, 1 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Kapasitas yang tersedia pada departemen pertukangan, departemen pengecatan, dan departemen penyelesaian adalah 400 jam, 360 jam, dan 250 jam, masing-masing. Harga jual masing-masing produk adalah Rp 10 (lemari A), Rp 15 (lemari B), dan Rp 12 (lemari C). Bagaimana usul Anda dalam memproduksi lemari, agar diperoleh keuntungan yang maksimal ?

Formulasikan Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

Variabel keputusan:

X1 = lemari A yang dijual (diproduksi) 

X2 = lemari B yang dijual (diproduksi)

X3 = lemari C yang dijual (diproduksi)

Fungsi Tujuan:

Maks : Z = 10 X1 + 15 X2 + 12 X3

dengan Z adalah keuntungan.

Fungsi Kendala :

3 X1 + 4 X2 + 3 1/2 X3   ≤ 400

2 X1 + 5 X2 + 1 X3         ≤ 360

1 X1 + 2 X2 + 1 X3         ≤ 250

     X1, X2, X3 ≥ 0

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar

Z - 10 X1 - 15 X2 - 12 X3    + 0S1 + 0S2 + 0S3   = 0

       3 X1 + 4 X2 + 3 1/2 X3 +  S1                     = 400

       2 X1 + 5 X2 + 1 X3               +    S2           = 360

       1 X1 + 2 X2 + 1 X3                           + S3  = 250

X1, X2, X3, S1, S2, S3 ≥ 0

Tabel Awal Simpleks Awal (Iterasi 0) dan Iterasi 1

Hasil yang dicapai menggunakan metode Simpleks 

Tampak pada tabel Simpleks awal (iterasi 0), x2 terpilih sebagai entering v. (koef. = -15) dan x5 terpilih sebagai leaving v. (ratio terkecil = 360/5=72). Selanjutnya pada iterasi 1, x3 terpilih sebagai entering v. (koef. = -9) dan x4 terpilih sebagai leaving v. (ratio terkecil = 112/2.7).

Selanjutnya tampak pada tabel Simpleks iterasi 2, koef. Pers./baris Z sudah positip atau nol, sehingga masalah PL ini telah optimal dengan Z atau keuntungan yang maksimum sebesar 1453 rupiah (dibulatkan), dengan hanya memproduksi lemari jenis B sebanyak 64 unit (dibulatkan) dan lemari jenis C sebanyak 41 unit (dibulatkan).

 Langkah- Langkah Metode Simpleks  Masalah Minimasi

1. Pada umumnya masalah PL dengan fungsi tujuan minimasi mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, dan £, dan ini diselesaikan dengan teknik variabel artifisialPada umumnya masalah PL dengan fungsi tujuan minimasi mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, dan £, dan ini diselesaikan dengan teknik variabel artifisial
2. PL dengan fungsi tujuan minimasi, dan koefisiennya bertanda +, diselesaikan dengan metode dual Simpleks, karena pada iterasi 0 telah tercapai kondisi optimal tapi belum fisibel.
3. Untuk menyelesaikan masalah PL dengan fungsi tujuan meminimumkan Z (minimasi), ada 2 cara :                                                                                                                                                           v   Merubah fungsi tujuan menjadi masalah maksimasi,  kemudian menyelesaikannya                  dengan metode Simpleks  masalah maksimasi.                                                                  v    Memodifikasi langkah 3 metode Simpleks :
         Jika semua variabel non basis pada baris/pers. Z mempunyai  koef. berharga  0, maka                 solusi basis fisibel telah optimal.  Akan tetapi jika baris Z masih ada variabel                           dengan koef.  positip,

   Dengan catatan koef. fungsi tujuan Z masih ada yang bertanda negatip (-), jika tidak  gunakan metode dual Simpleks.

Contoh Masalah PL Minimasi

v  Minimumkan Z = 2X1 – 3X2

                                berdasarkan kendala :

                                                X1 + X2 < 4

                                                X1 – X2  < 6

                                                X1, X2 > 0

v  Penyelesaian :

                Jika dilakukan cara 1, fungsi tujuan menjadi

                 maksimumkan – Z = - 2X1 + 3X2, dan semua kendala tidak berubah. Selanjutnya                                diselesaikan menggunakan metode Simpleks masalah maksimasi.

                Jika diselesaikan dengan cara 2, tabel Simpleks masalah itu adalah sbb. :

 













 

Teknik Artificial Variable

Pembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda  ≥ dan atau bertanda =

Untuk menyelesaikan kasus tersebut kita memerlukan variable dummy(variable palsu) atau artificial var. sehingga basis awal bisa tetap ada .

Untuk tanda ≥ masih menggunakan variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.

Model program linear

Model kombinasi Produk
 
Quick-Screen merupakan perusahaan garmen yang khusus memproduksi kaus dalam pertandingan akbar, seperti misalnya World Cup. Perusahaan ini telah dikontrak untuk membuat kaos standar dengan gambar negara pemenang. Kaos yang diproduk si terdiri dari dua jenis, yakni kaos lengan panjang dengan gam bar di satu sisi (depan) dan dengan gambar di dua sisi (depan dan belakang), jenis kedua adalah kaos lengan pendek dengan bentuk gambar serupa. Perusahaan harus menyelesaikan seluruh produksinya 72 jam setelah pertandingan final usai, di mana akan datang truk untuk mengangkut kaos tersebut. Perusahaan harus menyelesaikan produksi tepat waktu. Truk pengangkut memiliki kapasitas muatan sebanyak 1200 kardus ukuran standar. Satu box ukuran standar berisi 12 kaos lengan pendek, sementara satu kardus lengan panjang berukuran 3 kali lebih besar. Perusahaan memiliki dana $25.000 untuk memproduksi kaos, dan juga memiliki kaos lengan pendek & panjang polos masing2 500 lusin yang siap disablon. Persyaratan sumber daya, biaya, dan keuntungan per lusin untuk tiap jenis kaos disajikan pada tabel berikut :

Model Kombinasi Produk Lanjutan

                              Waktu Proses (hr)   Biaya ($)  Keuntungan ($)

                                   per lusin            per lusin        per lusin

Kaos lengan panjang

Satu sisi                                    0,10                   36                90

Kaos lengan panjang

Dua sisi                                     0,25                   48               125

Kaos lengan pendek

Satu sisi                                    0,08                   25                45

Kaos lengan pendek

Dua sisi                                     0,21                   35                65

Perusahaan ingin mengetahui berapa lusin (kardus) tiap jenis kaos harus diproduksi untuk memaksimalkan keuntungan ?

 Formulasinya:

v  Variabel keputusan

            Masalah ini memiliki 4 variabel keputusan, yakni :

            X1 = jumlah produksi kaos l. panjang gambar 1 sisi (lusin)

            X2 = jumlah produksi kaos l. panjang gambar 2 sisi (lusin)

            X3 = jumlah produksi kaos l. pendek gambar 1 sisi (lusin)

            X4 = jumlah produksi kaos l. pendek gambar 2 sisi (lusin)

v  Fungsi tujuan

            Maksimalkan Z = $ 90X1 + 125X2 + 45X3 + 65X4

            dengan Z adalah keuntungan.

v  Berdasarkan kendala

            0.1X1+0.25X2+0.08X3+0.21X4 £ 72         waktu produksi

               3X1+    3X2+      X3+      X4  £ 1200     kapasitas truk

            36X1 +   48X2+  25X3+  35X4  £ 25000   dana yang tersedia

               X1  +      X2                         £ 500      sediaan kaos panjang

                                X3+      X4  £ 500      sediaan kaos pendek

            X1, X2, X3, X4 ³ 0

Contoh kombinasi investasi :

Kathleen Allen mempunyai dana $70.000 untuk diinvestasikan dalam beberapa pilihan, yakni : obligasi pemerintah sertifikat deposito dengan tingkat pengembalian, treasury bill, dan obligasi pendapatan, masing2 dengan tingkat pengembalian berturut-turut 8,5%, 5%, 6,5%, dan 13%. Jumlah waktu jatuh tempo sama untuk setiap pilihan. Akan tetapi, setiap pilihan mempunyai perbedaan risiko yang terlihat oleh investor. Oleh karena itu, investor sebaiknya melakukan diservifikasi. Investor ingin mengetahui berapa jumlah yang harus diinvestasikan pada setiap pilihan sehingga dapat memaksimalkan tingkat pengemba lian. Berikut ini pedoman dalam melakukan disersivikasi yang akan mengurangi risiko : 1) Tidak lebih dari 20% dari total investasi dalam bentuk obligasi pendapatan; 2) Jumlah yang diinvestasikan dalam sertifikat deposito tidak melebihi jumlah yang diinvestasikan dalam ketiga pilihan yang lain; 3) Paling sedikit 30% investasi dalam bentuk treasury biil; 4) Agar aman, perbandingan investasi pada sertifikat deposito dan treasury bill dengan investasi dalam obligasi pemerintah dalam saham harus paling tidak 1,2 : 1.

            Kathleen merencanakan untuk menginvestasikan seluruh dana.

Formulasi investasi

v  Variabel keputusan

            X1 = jumlah yang diinvestasikan dalam obligasi pemerintah ($)

            X2 = jumlah yang diinvestasikan dalam sertifikat deposito ($)

            X3 = jumlah yang diinvestasikan dalam treasury bill ($)

            X4 = jumlah yang diinvestasikan dalam obligasi pendapatan ($)

v  Fungsi tujuan

            Maksimalkan Z = $ 0.085X1 + 0.05X2 + 0.065X3 + 0.13X4

                        Z = total pengembalian investasi

v  Berdasarkan kendala :

            1) X1 £  14,000   ®               (tidak lebih dr. 20% total investasi)

            2) X2 £ X1 + X3 + X4 atau X1 – X2+X3+X4 ³ 0  ® jumlah yang diinvestasi-          kan dalam sertifikat deposito tidak melebihi jumlah ke 3 pilihan yg lain

            3) X2 + X3 ³ 21,000   ® jumlah yang diinvestasikan dalam sertifikat deposito        dan treasury bill paling tidak 30% dari dana yang tersedia

            4) (X2+X3)/(X1+X4) ³ 1.2 atau X2 + X3 ³ 1.2(X1 + X4) atau

                        – 1.2X1 + X2 + X3 – 1.2X4 ³ 0  ® perbandingan jumlah diinvestasikan      dalam sertifikat deposito dan treasury bill dengan obligasi pemerintah             dan obligasi pendapatan paling tidak 1.2 : 1

            5) X1 + X2 + X3 + X4 £ 70,000 ® dana yang akan diinvestasikan

            6) X1, X2, X3, X4 ³ 0