Contoh Formulasi Program Linear

Contoh Formulasi Program Linear

Formulasi dan Bentuk Umum Program Linear

Tujuan dari penelitian operasional adalah mengatasi masalah yang berkaitan dengan penggunaan sumber daya yang terbatas. Pemecahan masalah dimulai dengan membangun model matematis sebagai representatif dari suatu sistem nyata.

Tujuan pembuatan model ini adalah untuk memudahkan dan menganalisis perilaku sistem nyata dalam rangka memperbaiki kinerjanya. Kompleksitas sistem nyata yang terdiri dari banyak variabel menyulitkan si pengambil keputusan untuk membuat model. Biasanya didalam suatu sistem nyata terdapat beberapa variabel yang dominan.

Oleh karena itu, representasi dari sistem nyata hanya akan mempertimbangkan elemen atau variabel yang mendominasi sistem nyata tersebut. Tahapan pembuatan model inilah yang disebut sebagai sebuah seni dalam riset operasi.

Dalam model program linear, dikenal dua macam fungsi yaitu : fungsi tujuan (objective function) dan fungsi-fungsi batasan (constraint function).

Fungsi tujuan adalah fungsi yang menggambarkan tujuan atau sasaran yang berkaitan dengan pengaturan secara optimal sumber daya untuk memperoleh keuntungan maksimal atau biaya minimal.

Sedangkan fungsi batasan merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.

Setelah masalah diidentifikasi, tujuan atau sasaran yang ingin dicapai ditetapkan, maka langkah selanjutnya adalah formulasi model matematis yang meliputi 3 tahap berikut :

  1. Menentukan variabel keputusan (unsur-unsur dalam persoalan yang dapat dikendalikan) dan kemudian nyatakan dalam simbol matematis.
  2. Membentuk fungsi tujuan sebagai hubungan linear dari variabel keputusan.
  3. Menentukan semua kendala atau batasan masalah tersebut dan ekspresikan dalam persamaan atau pertidaksamaan  yang merupakan hubungan linear dari variabel keputusan yang mencerminkan keterbatasan sumber daya masalah tersebut.

Sebagai ilustrasi, berikut ini akan disajikan contoh kasus yang menunjukkan langkah-langkah formulasi dalam model program linear.

Iklan

Contoh Formulasi Program Linear

Sebuah perusahaan kecil memproduksi empat jenis produk yang berbeda, yang masing-masing membutuhkan tiga macam bahan baku yaitu bahan A, B, dan C. Produk tersebut dikerjakan lewat 2 proses pengerjaan manual yaitu proses I dan II. Setiap unit produk ke I membutuhkan 10 ons bahan A, 6 ons bahan B, dan 12 ons bahan C. Setiap unit produk II membutuhkan 8 ons bahan A, 10 ons bahan B, dan 9 ons bahan C. Setiap unit produk III membutuhkan 6 ons bahan A, 8 ons bahan B, dan 5 ons bahan C. Produk IV membutuhkan 9 ons bahan A, 5 ons bahan B, dan 6 ons bahan C. Akibat keterbatasan gudang dan dana yang ada, maka bahan baku yang disediakan  tiap minggu adalah 120 kg bahan A, 90 kg bahan B, dan 125 kg bahan C.

Setiap unit produk I membutuhkan waktu 4 jam pada proses I dan 2 jam proses II. Produk II setiap unit 3 jam pada proses I dan 4 jam proses II. Setiap unit produk III membutuhkan 2 jam proses I dan 3 jam proses II. Sedangkan produk IV setiap unitnya membutuhkan 6 jam proses I dan 5 jam proses II. Jumlah karyawan pada proses I sebanyak 10 orang, pada proses II sebanyak 12 orang. Perusahaan bekerja dengan 1 shift, mulai dari jam 08.00 sampai jam 16.00 dengan istirahat 1 jam mulai pukul 12.00-13.00, dan enam hari kerja dalam 1 minggu. Keuntungan per unit produk I,II,III,dan IV masing-masing sebesar Rp.2.000, Rp.1.900, Rp.1.600, dan Rp.2.100. Informasi dari bagian pemasaran menyatakan berapa pun jumlah produk yang dibuat perusahaan akan terserap seluruhnya oleh pasar.

Formulasikan masalah tersebut !

Penyelesaian:

Satuan bahan baku dibuat dalam satuan ons. Jumlah jam kerja karyawan per minggu pada proses I sebesar : 10 orang x 7 jam kerja per hari x 6 jumlah hari kerja dalam 1 minggu = 420, dan pada proses II sebesar 12 orang x 7 jam kerja per hari x 6 jumlah hari kerja dalam 1 minggu = 504. Persoalan diatas dapat ditabulasikan sebagai berikut :

Sumber DayaProduk IProduk IIProduk IIIProduk IVKapasitas
Bahan A108691200
Bahan B61085900
Bahan C129561250
Jam Proses I4326420
Jam Proses II2435504
Laba/unit2000190016002100

Perumusan persoalan tersebut sebagai berikut:

1. Variabel Keputusan

Masalah tersebut terdiri dari 4 variabel yang menunjukkan jumlah produk I, II, III, dan IV yang harus diproduksi oleh perusahaan. Jumlah tersebut dapat ditunjukkan sebagai berikut:

  • X1 = jumlah produk I yang di buat
  • X2 = jumlah produk II yang di buat
  • X3 = jumlah produk III yang di buat
  • X4 = jumlah produk IV yang di buat

2. Fungsi Tujuan

Tujuan masalah di atas adalah memaksimumkan keuntungan total. Keuntungan total adalah jumlah keuntungan yang diperoleh dari masing-masing produk. Keuntungan produk I adalah perkalian jumlah produk I dengan keuntungan per unit produk I. Begitu pun keuntungan produk II adalah jumlah produk II dengan keuntungan per unit produk II, dan seterusnya. Sehingga fungsi tujuan masalah tersebut dapat dirumuskan sebagai berikut:

Maks Z= 2000 X1 + 1900 X2 + 1600 X3 + 2100 X4

3. Fungsi Kendala

Dalam masalah ini kendalanya adalah bahan baku A, B, dan C serta jam kerja pada proses I dan II. Untuk menghasilkan 1 unit produk I dibutuhkan 10 ons bahan A sehingga total bahan baku A yang dibutuhkan adalah 10 X1. Dengan cara yang sama produk II membutuhkan 8 X2, produk III sebanyak 6 X3, dan produk IV sebanyak 9 X4. Jumlah bahan baku A yang tersedia sebanyak 1200 ons (dari 120 kg menjadi ons).

Penggunaan bahan baku ini bisa luwes, artinya bisa digunakan secara penuh atau sebagian saja, atau secara matematis di tulis dengan tanda “≤”. Sehingga kendala bahan baku A dapat ditulis:

10 X1 + 8 X2 + 6 X3 + 9 X4  ≤  1200

Dan dengan cara yang sama kendala bahan baku B, C, jam kerja proses I dan II dapat ditulis sebagai berikut :

6 X1 + 10 X2 + 8 X3 + 5 X4 ≤ 900
12 X1 + 9 X2 + 5 X3 + 6 X4 ≤ 1250
4 X1 + 3 X2 + 2 X3 + 6 X4 ≤ 420
2 X1 + 4 X2 + 3 X3 + 5 X4 ≤ 504

4. Fungsi Non-Negativitas

Perlu diketahui bahwa masing-masing variabel perlu dibatasi hanya pada nilai positif, karena tidak mungkin menghasilkan produk dalam jumlah negatif. Kendala ini disebut kendala non-negativitas dan secara matematis dapat ditulis sebagai berikut:

X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0

Umumnya masalah program linear mempunyai kendala non negatif. Namun pada kasus tertentu nilai negatif bisa saja terjadi jika variabel itu merupakan suatu tingkat seperti: tingkat pertumbuhan dan tingkat inflasi yang dapat naik dan turun, nilai negatif menunjukkan penurunan.

Jadi masalah tersebut diatas dapat diformulasikan sebagai model matematis sebagai berikut:

Fugsi tujuan :
Maks Z= 2000 X1 + 1900 X2 + 1600 X3 + 2100 X4

Fungsi kendala :
10 X1 + 8 X2 + 6 X3 + 9 X4  ≤  1200
6 X1 + 10 X2 + 8 X3 + 5 X4 ≤ 900
12 X1 + 9 X2 + 5 X3 + 6 X4 ≤ 1250
4 X1 + 3 X2 + 2 X3 + 6 X4 ≤ 420
2 X1 + 4 X2 + 3 X3 + 5 X4 ≤ 504
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0

Setelah diformulasi, maka persamaan-persamaan yang didapat di atas dapat dimasukkan untuk perhitungan baik dengan metode grafik maupun metode simpleks. Untuk lebih jelas tentang teknik perhitungannya dapat dibaca di : Program Linear : Metode Grafik dan Simpleks

Penambahan Variabel Keputusan dan Kendala Baru Dalam Analisis Sensitivitas

Analisis Sensitivitas

Daftar Isi Bab Analisis Sensitivitas:

  1. Analisis Sensitivitas
  2. Perubahan Pada Koefisien Tujuan dan Kendala Dalam Analisis Sensitivitas
  3. Penambahan Variabel Keputusan dan Kendala Baru Dalam Analisis Sensitivitas
Iklan

Penambahan Variabel Keputusan Baru

Penambahan variabel keputusan yang baru digunakan jika suatu perusahaan ingin menambah produk baru dengan menggunakan sumber daya yang sudah ada sebelumnya dan tidak adanya penambahan sumber daya baru.

Untuk penambahan variabel keputusan baru akan menyebabkan bertambahnya variabel keputusan pada masing-masing kendala, jika terjadi  penambahan variabel keputusan baru maka yang bertambah pada kendala adalah :

2A + 2B + C + …D ≤ 250
5A + 4B + 3C + …D ≤ 350
6B + 5C + …D ≤ 500
A,B,C ≥ 0

Jadi, semakin banyak penambahan variabel keputusan baru akan menyebabkan semakin banyak variabel-variabel dalam suatu persamaan.

Contoh :

Misalnya terdapat penambahan variabel baru, yaitu D dengan kendala 1 jam pada kendala 1, 2 jam pada kendala 2, dan 3 jam pada kendala 3.

Kemudian tentukan berapa koefisien D yang ekonomis sehingga produk D layak diproduksi.

Pertama-tama carilah nilai kolom D dengan mengalikan matriks kunci dengan koefisien kendala D.

Contoh Penambahan Variabel Keputusan Baru D

Setelah itu carilah nilai interval dengan mengalikan koefisien variabel dasar dengan nilai kolom D:

Contoh Penambahan Variabel Keputusan Baru Nilai Interval

Untuk memastikan bahwa produk D layak diproduksi maka harus memenuhi syarat C4 ≤ 0.

Dengan demikian berdasarkan hasil perhitungan di atas yang menghasilkan 392 – C4 ≤ 0, maka diperoleh C4 ≥ 392

Jadi dapat disimpulkan bahwa perusahaan menetapkan besarnya keuntungan untuk produk D diatas atau sama dengan 392 agar dihasilkan nilai ekonomis, apabila keuntungan lebih kecil dari 392, maka lebih baik tidak ada penambahan produk baru.

Iklan

Penambahan Kendala Baru

Penambahan kendala baru digunakan jika suatu perusahaan ingin menambah sumber daya baru.

Dengan bertambahnya kendala baru, maka persamaan dalam suatu kendala akan semakin banyak sesuai dengan jumlah sumber daya yang ingin ditambah.

Contohnya, jika dilakukan penambahan kendala baru, maka perubahan pada kendala menjadi :

2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500
…A + …B + …C ≤ …
A,B,C ≥ 0

Dalam penambahan kendala baru, kita harus memastikan apakah dengan penambahan kendala tersebut dapat mempengaruhi hasil optimum yang telah ada.

Misalnya dilakukan penambahan kendala baru dengan persamaan : A + B + 3C ≤ 350.

Maka ujilah persamaan tersebut dengan mensubtitusikan nilai variabel optimum yang sudah didapatkan sebelum-sebelumnya dimana A = 10, B = 0, dan, C = 100 ke dalam persamaan kendala baru. Sehingga didapatkan : 10 + 0 + 3 (100) = 310.

Dapat disimpulkan perubahan kendala baru tidak mempengaruhi hasil optimum, hal ini disebabkan karena penambahan kendala tersebut masih dapat dipenuhi oleh kapasitas yang ada (310 ≤ 350).

Akan tetapi, jika kapasitasnya kita turunkan menjadi 300, otomatis penambahan kendala baru sudah tidak dapat dipenuhi kapasitas yang ada. Maka diperlukan optimasi lebih lanjut.

Pertama-tama yang harus dilakukan adalah mengubah kendala baru ke bentuk standar dan masukkan ke tabel optimum sebelumnya.

Kendala baru :

(Primal)
2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500  
A + B + 3C ≤ 350

(Standar)
2A + 2B + C + S1 ≤ 250
5A + 4B + 3C + S2 ≤ 350
6B + 5C + S3 ≤ 500  
A + B + 3C + S4 = 350

Setelah itu, masukkan kendala baru tersebut ke tabel simpleks optimal :

BasisZABCS1S2S3S4Solusi
Z1







S1000,6401-0,40,040130
A010,08000,2-0,12010
C001,21000,20100
S401130001300

Dari tabel di atas, yang menjadi variabel basis adalah A dan C, sehingga pada baris S4, kolom A dan C harus dijadikan 0 dengan cara menguranginya dengan variabel basis yang telah dikalikan dengan koefisien pada kendala barunya :

Langkah 1 :

Kurangkan baris S4 dengan baris A yang dikalikan dengan koefisien A pada kendala S4.

Langkah 1

Langkah 2 :

Kurangkah hasil dari langkah 1 dengan baris C yang dikalikan dengan koefisien C pada kendala S4.

Langkah 2

Langkah 3 :

Masukkan nilai S4 yang sudah dihitung pada langkah 2.

BasisZABCS1S2S3S4Solusi
Z10384001602468.000
S1000,6401-0,40,040130
A010,08000,2-0,12010
C001,21000,20100
S400-2,6800-0,2-0,481-10

Kesimpulan :

Walaupun nilai Z sudah positif semua sesuai dengan maksimasi simpleks. Hanya saja masih terdapat solusi yang bernilai negatif yakni solusi dari S4, sehingga masih diperlukan iterasi lebih lanjut agar tabel optimum.

Proses pemecahan dapat melakukan metode simpleks yang dapat anda pelajari di Pemecahan Program Linear Metode Simpleks.

BasisZABCS1S2S3S4SolusiIndeks
Z103840016024068.000
S1000,6401-0,40,040130203,13
A010,08000,2-0,12010125
C001,21000,2010083,33
S400-2,6800-0,2-0,481-105,95

Sehingga didapatkan tabel optimumnya :

BasisZABCS1S2S3S4Solusi
Z102500015005067.498
S1000,4201-0,4200,08129,2
A010,75000,250-0,2512,5
S3005,58000,421-2,0820,83
C000,0810-0,0800,4295,83

Maka dapat disimpulkan bahwa penambahan kendala baru dengan persamaan : A + B + 3C ≤ 300 akan mengubah tabel optimum dan solusi optimum dari Rp.68.000,- menjadi Rp.67.498,-

Perubahan Pada Koefisien Tujuan dan Kendala Dalam Analisis Sensitivitas

Analisis Sensitivitas

Daftar Isi Bab Analisis Sensitivitas:

  1. Analisis Sensitivitas
  2. Perubahan Pada Koefisien Tujuan dan Kendala Dalam Analisis Sensitivitas
  3. Penambahan Variabel Keputusan dan Kendala Baru Dalam Analisis Sensitivitas
Iklan

Perubahan Pada Koefisien Tujuan

Perubahan pada koefisien tujuan pada variabel dasar (basis)

Diketahui : Fungsi tujuan : Maksimumkan Z = 800A + 400B + 600C

Basis Z A B C S1 S2 S3 Solusi
Z1 0384001602468.000
S10 00,6401 -0,40,04130
A0 10,0800 0,2-0,1210
C0 01,210 0 0,2100

Pada tabel simpleks optimal diatas, yang menjadi variabel dasar (basis) adalah variabel A dan C, sedangkan yang bukan merupakan variabel dasar (basis) adalah B, S1, S2, dan S3.

Besarnya koefisien tujuan untuk variabel basis adalah 800 dan 600.

Apabila besarnya koefisien A (C1) dan C (C2) dinaikkan atau diturunkan dalam jumlah tertentu maka ada kemungkinan A atau C tidak menguntungkan untuk diproduksi.

Untuk itu pada bagian ini dianalisis seberapa besar kenaikan atau penurunan yang masih dapat ditolerir sehingga produk A dan C tetap diproduksi (dengan perubahan koefisien tujuan maka berpengaruh terhadap solusi optimal).

Urutan dalam variabel dasar pada tabel simpleks diatas adalah S1, A, dan C.

Dengan demikian urutan itu menjadi dasar perhitungan untuk mencari besarnya perubahan pada koefisien tujuan.

Jika terjadi perubahan pada koefisien fungsi tujuan A:

Perkalian matriks dilakukan dengan mengalikan vektor baris dengan vektor kolom pada variabel non-basis, hasil perkalian tersebut dikurangkan dengan koefisien non-basis tersebut. Angka yang berubah

Contoh Perubahan Pada Koefisien Tujuan B

Syarat tabel optimum adalah B ≥ 0, sehingga 0,08 C1 + 320 ≥ 0 atau C1 ≤ 4000

Contoh Perubahan Pada Koefisien Tujuan S1
Contoh Perubahan Pada Koefisien Tujuan S2
Contoh Perubahan Pada Koefisien Tujuan S3

Dari hasil perhitungan diatas dapat disimpulkan bahwa tabel akan tetap optimum jika koefisien C1 berada dalam interval 0 ≤ C1 ≤ 1000.

Tabel akan tetap optimum apabila koefisien C1 dinaikkan menjadi 1000 (dinaikkan 200) atau diturunkan menjadi 0 (diturunkan 800), akan tetapi tabel tidak lagi akan menjadi optimum apabila koefisien C1 dinaikkan melebihi 1000.

Contoh :

1. Koefisien C1 naik dari 800 menjadi 900

Contoh Kenaikan Koefisien 800 menjadi 900 B
Contoh Kenaikan Koefisien 800 menjadi 900 S1
Contoh Kenaikan Koefisien 800 menjadi 900 S2
Contoh Kenaikan Koefisien 800 menjadi 900 S3

Kesimpulan :

Dari hasil perhitungan variabel non-basis seluruhnya menghasilkan angka positif atau ≥ 0, berarti tabel optimum tidak berubah (tetap).

Dengan demikian besarnya nilai A = 10 dan C = 100 tidak berubah.

Perubahan terjadi pada Z sebagai akibat perubahan koefisien C1 dari 800 ke 900.

Nilai Z yang baru adalah :

Z = 900A + 400B + 600C
Z = 900(10) + 400(0) + 600(100)
Z = 69000  

2. Koefisien C1 naik dari 800 menjadi 1100

Contoh Kenaikan Koefisien 800 menjadi 1100 B
Contoh Kenaikan Koefisien 800 menjadi 1100 S1
Contoh Kenaikan Koefisien 800 menjadi 1100 S2
Contoh Kenaikan Koefisien 800 menjadi 1100 S3

Kesimpulan :

Dari hasil perhitungan variabel non-basis, pada variabel S3 didapatkan nilai negatif, dengan demikian tabel sudah tidak optimum lagi, oleh karena itu perlu dilakukan eksekusi pada kolom S3 tersebut.

Besarnya variabel semua, yaitu A = 10 dan C = 100 juga mengalami perubahan.

BasisZABCS1S2S3SolusiIndeks
Z1

-12

S1000,6401-0,40,041303.250
A010,08000,2-0,1210-83,33
C001,21000,2100500

Setelah itu, lakukan penyelesaian dengan metode simpleks seperti yang sudah dibahas pada topik sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

Sehingga didapatkan tabel simpleks optimum yang baru:

BasisZABCS1S2S3Solusi
Z10480600220077.000
S1000,4-0,21-0,40110
A010,80,600,2070
S30065001500

Dari tabel simpleks optimal yang baru diatas terdapat perubahan variabel, sebelumnya A = 10 dan C = 100 menjadi A = 70 dan C = 0.

Sementara itu nilai maksimum Z maksimum mengalami kenaikan semula Rp.68.000,- menjadi Rp.77.000,-

Jika terjadi perubahan pada koefisien fungsi tujuan C :

Caranya sama seperti perubahan pada koefisien fungsi tujuan A, hanya saja, angka yang berubah adalah koefisien dari fungsi tujuan C.

Contoh Perubahan Pada Koefisien Tujuan B
Contoh Perubahan Pada Koefisien Tujuan S1
Contoh Perubahan Pada Koefisien Tujuan S2
Contoh Perubahan Pada Koefisien Tujuan S3

Dari hasil perhitungan di atas dapat disimpulkan bahwa tabel akan tetap optimum jika koefisien C3 berubah menjadi C3 ≥ 480.

Tabel akan tetap optimum jika koefisien C3 berada dalam interval diatas, tetapi apabila C3 < 480 berarti tabel sudah tidak optimum lagi dan harus di eksekusi ulang.

Contoh :1. Koefisien C3 berubah dari 600 menjadi 500

Contoh Penurunan Koefisien 600 menjadi 500 B
Contoh Penurunan Koefisien 600 menjadi 500 S1
Contoh Penurunan Koefisien 600 menjadi 500 S2
Contoh Penurunan Koefisien 600 menjadi 500 S3

Kesimpulan :

Dari hasil perhitungan variabel non-basis seluruhnya menghasilkan angka positif berarti tabel optimum, jadi solusi optimum tidak berubah (tetap).

Dengan demikian besarnya nilai A = 10 dan C = 100 (tidak berubah). Perubahan terjadi pada nilai Z sebagai akibat perubahan koefisien C3 dari 600 ke 500.

Nilai Z yang baru adalah :

Z = 900A + 400B + 500C
Z = 900(10) + 400(0) + 500(100)
Z = 59000

2. Koefisien C3 turun dari 600 menjadi 450

Contoh Penurunan Koefisien 600 menjadi 450 B
Contoh Penurunan Koefisien 600 menjadi 450 S1
Contoh Penurunan Koefisien 600 menjadi 450 S2
Contoh Penurunan Koefisien 600 menjadi 450 S3

Kesimpulan :

Dari hasil perhitungan variabel non-basis, pada variabel S3 terdapat nilai negatif, dengan demikian tabel sudah tidak optimum lagi, oleh karena itu perlu dilakukan eksekusi pada kolom S3 tersebut.

Besarnya variabel semula, yaitu A = 10 dan C = 100 juga mengalami perubahan.

BasisZABCS1S2S3SolusiIndeks
Z1

-6

S1000,6401-0,40,041303.250
A010,08000,2-0,1210-83,33
C001,21000,2100500

Setelah itu dilakukan penyelesaian dengan metode simpleks seperti yang sudah dibahas pada topik sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

Sehingga didapatkan tabel simpleks optimum yang baru:

BasisZABCS1S2S3Solusi
Z10240300160056.000
S1000,4-0,21-0,40110
A010,80,600,2070
S30065001500

Dari tabel simpleks optimal yang baru di atas didapatkan perubahan variabel yang sebelumnya A = 10 dan C = 100 menjadi A = 70, dan C = 10.

Sementara itu, nilai Z maksimum mengalami penurunan semula Rp.68.000,- menjadi Rp.56.000,-

Perubahan pada koefisien tujuan pada bukan variabel dasar (non-basis)

Pada tabel sebelum-sebelumnya, dapat dilihat bahwa A dan C adalah variabel basis, variabel non-basis di tabel tersebut adalah variabel B.

Variabel non-basis biasanya memiliki keuntungan yang tidak ekonomis. Namun jika koefisien dari B dinaikkan dalam jumlah tertentu, maka ada kemungkinan variabel B akan diproduksi.

Perubahan pada koefisien tujuan pada bukan variabel dasar (non-basis)

Dari hasil perhitungan di atas, diketahui apabila variabel B dinaikkan sampai dengan 4240, maka variabel B masih belum ekonomis untuk diproduksi (Tabel optimum tidak berubah).

Tetapi, apabila dinaikkan diatas 4240 maka variabel ini akan ekonomis untuk diproduksi (tabel optimum akan berubah).

Contoh :

Koefisien B dinaikkan dari 400 ke 600

Contoh Kenaikan Koefisien 400 menjadi 600 B

Kesimpulan :

Koefisien B bernilai positif, berarti tabel yang ada telah optimal atau perubahan pada variabel non-basis tidak mempengaruhi tabel optimum.  

Koefisien B dinaikkan menjadi 4300

Contoh Kenaikan Koefisien 400 menjadi 4300 B

Kesimpulan :

Koefisien B bernilai negatif, jadi tabel sudah tidak optimum, maka itu diperlukanlah penyelesaian dengan melakukan eksekusi pada kolom variabel B dengan metode simpleks biasa.

Untuk teknik pemecahannya dapat dipelajari di Pemecahan Program Linear Metode Simpleks.

BasisZABCS1S2S3SolusiIndeks
Z1-60



S1000,6401-0,40,04130203,13
A010,08000,2-0,1210125
C001,21000,210083,33

Dengan perhitungan metode simpleks, maka didapatkan tabel optimumnya adalah sebagai berikut :

BasisZABCS1S2S3Solusi
Z1002.9130160627360.983
S1000-0,531-0,4-0,0776,67
A010-0,0700,2-0,133,33
B0010,83000,1783,33

Dari tabel simpleks optimal diatas, maka dapat dilihat bahwa, jika koefisien B dinaikkan menjadi 4.300, maka nilai Z akan berubah.

Dimana semula besarnya A = 10,  B = 0 dan C = 100 dengan nilai Z sebesar Rp.68.000,-.

Berubah menjadi A = 3,33, B = 83,33 dan C = 0 sehingga didapatkan nilai Z sebesar Rp. 360.983,-

Perubahan pada koefisien tujuan dan pengaruhnya terhadap variabel dual

Sebelum lanjut ke topik ini, ada baiknya anda pelajari lebih lanjut tentang Teori dualitas.

Seperti yang sudah dibahas sebelumnya bahwa perubahan pada koefisien tujuan baik basis atau non-basis dapat mempengaruhi besarnya variabel keputusan (Z) jika perubahan tersebut tidak sesuai dengan kondisi yang diisyaratkan.

Berbeda pada variabel dual, dimana perubahan pada koefisien tujuan berpengaruh langsung terhadap perubahan variabel dual (walaupun perubahan tersebut masih dalam rentang yang diisyaratkan).

Nilai variabel dual dapat dicari dengan cara mengalikan koefisien variabel dasar dengan matriks kunci.

Contoh :

Misalnya jika koefisien A dinaikkan menjadi 900 dan C menjadi 500. Berdasarkan hasil perhitungan diatas dimana :

A = C1 ≤ 1.000
C = C3 ≥ 480

Jadi, tabel optimum tidak akan berubah karena tidak perubahan masih dalam interval atau masih sesuai dengan syarat optimum.

Hanya saja, berbeda dengan variabel dual-nya, variabel dual akan mengalami perubahan dimana :

Semula :

Nilai Variabel Dual Semula

Nilai variabel dual semula Y1 = 0, Y2 = 160, dan Y3 = 24

Menjadi :

Nilai Variabel Dual Setelah

Dimana, nilai variabel dual menjadi Y1 = 0, Y2 = 180, dan Y3 = -8

Iklan

Perubahan Pada Kendala

Perubahan pada pembatas kanan kendala

Perubahan pada pembatas kanan kendala, yang dimaksud pembatas kanan kendala adalah angka yang menunjukkan batas dari suatu persamaan, dan letaknya di bagian kanan, misalnya seperti contoh dibawah :

Kendala :

2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500
A,B,C ≥ 0

Dimana yang warna hijau adalah pembatas kanan kendala. Jika terjadi perubahan pada pembatas kanan kendala maka akan berdampak pula pada nilai variabelnya dengan demikian nilai tujuan (Z) juga akan berubah.

Untuk menghitung nilai Z nya dapat dilakukan dengan mengalikan matriks kunci dengan pembatas kanan kendala.

Untuk mengetahui seberapa besar perubahan pada suatu kendala tanpa mengubah solusi optimalnya dapat dilakukan dengan cara berikut :

Perubahan Pada Pembatas Kanan Kendala

Maka :

  1. 270 – 0,4Δ ≥ 0
    Δ ≤ 675
  2. 0,2Δ – 60 ≥ 0
    Δ ≥ 300

Dari hasil perhitungan diatas, maka dapat disimpulkan bahwa kendala ke-2 dapat berubah menjadi 300 ≤ Δ ≤ 675 yang tidak mengubah tabel optimum.

Berdasarkan soal di atas dimana besarnya kendala ke-2 = 350, maka berdasarkan persamaan yang telah dicari, maka kendala ke-2 dapat dikurangi hingga 50 atau ditambah sampai dengan 325 agar tabel tetap optimum.

Tetapi, jika kendala ke-2 dikurangi atau ditambah lebih dari interval yang ada, maka penyelesaian tersebut sudah tidak optimum lagi.

Contoh :

Jika kendala ke-2 berubah menjadi 400, maka nilai variabel yang baru adalah :

Contoh Perhitungan Perubahan Pada Pembatas Kanan Kendala

Dengan perubahan pada kendala ke-2 maka terjadi perubahan tingkat produksi menjadi A = 100, B = 20, dan C =100.

Dengan demikian nilai Z meningkat pula dari yang sebelumnya Rp. 68.000,- menjadi :

Z = 800A + 400B + 600C
Z = 800 (110) + 400 (20) + 600 (100)
Z = 150.000

Kesimpulan :

Akibat dari kenaikan kendala pembatas ke-2 dari 350 menjadi 400, maka akan terjadi kenaikan Z menjadi Rp. 156.000,-.

Perubahan pada koefisien kendala

Yang dimaksud dengan koefisien kendala adalah angka-angka yang terletak pada suatu variabel. Dimana biasanya angka-angka ini terletak di sebelah kiri persamaan. Misalnya seperti contoh dibawah :

Z = 800A + 400B + 600C

Kendala :
2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500
A,B,C ≥ 0

Apabila terjadi perubahan pada koefisien kendala, misalnya pada variabel B yang semula memiliki koefisien 2, 4, dan 6 berubah menjadi 3,5 dan 4.

Langkah pertama yang harus dilakukan adalah memastikan apakah perubahan koefisien kendala tersebut berpengaruh terhadap hasil optimum atau tidak.

Untuk mengujinya dapat dilakukan dengan mengubahnya ke bentuk dual.

Z = 800A + 400B + 600C

Kendala B berubah menjadi 3,5, dan 4 :
2A + 3B + C ≤ 250
5A + 5B + 3C ≤ 350
4B + 5C ≤ 500
A,B,C ≥ 0  

W = 250 Y1 + 350 Y2 + 500 Y3

Bentuk dual :
2 Y1 + 5 Y2 ≥ 800
3 Y1 + 5 Y2 + 4 Y3 ≥ 400
Y1 + 3 Y2+ 5 Y3 ≥ 600

Untuk cara mengubah bentuk primal ke dual dapat dipelajari pada Teori Dualitas | Primal-Dual.

Dengan demikian, setelah diubah menjadi bentuk dual, maka persamaan B nya dalam bentuk dual menjadi : 3 Y1 + 5 Y2 + 4 Y3 ≥ 400.

Lakukan pengujuan dengan subtitusi nilai variabel dual ke dalam persamaan B dalam bentuk dual.

Seperti yang sudah dibahas sebelumnya dimana nilai variabel dualnya adalah :

perubahan pada koefisien kendala

Sehingga dapat dihitung nilai dualnya :

3 (0) + 5 (160) + 4 (24) – 400 = 496

Karena nilai dualnya bernilai positif, dapat disimpulkan bahwa perubahan koefisien kendala tidak berpengaruh terhadap hasil optimum.

Akan tetapi misalnya koefisien B berubah menjadi 3, 1, dan 9, maka nilai dualnya akan berubah menjadi :

3 (0) + 1 (160) + 9 (24) – 400 = -24

Berarti perubahan koefisien tujuan akan mengubah tabel optimum. Sehingga perlu dicari tabel optimum baru dimana angka-angka pada kolom B akan mengalami perubahan, dan setelah itu gunakan metode simpleks untuk membuat tabel tersebut optimum.

Nilai kolom B dicari dengan mengalikan matriks kunci dengan koefisien kolom B baru.

mencari nilai kolom B baru
BasisZABCS1S2S3SolusiIndeks
Z1-24



S1002,9601-0,40,0413043,92
A01-0,88000,2-0,1210-11,36
C001,81000,210055,55

Tabel optimalnya adalah :

BasisZABCS1S2S3Solusi
Z1000101522465.052
B00100,34-0,140,0143,92
A01000,30,08-0,1148,65
C0001-0,610,240,1820,94

Kesimpulan : Perubahan koefisien kendala B menjadi 3, 1, 9 akan mengubah tabel optimum dan hasil optimum dimana sebelum perubahan koefisien kendala nilai optimumnya adalah Rp. 68.000,- menurun menjadi Rp 65.052,-

Analisis Sensitivitas

Daftar Isi Bab Analisis Sensitivitas:

  1. Analisis Sensitivitas
  2. Perubahan Pada Koefisien Tujuan dan Kendala Dalam Analisis Sensitivitas
  3. Penambahan Variabel Keputusan dan Kendala Baru Dalam Analisis Sensitivitas
Iklan

Pengertian Analisis Sensitivitas

Apabila permasalahan dalam program linear telah diselesaikan dan telah menghasilkan solusi optimal belum berarti permasalahan telah selesai.

Masih terdapat kemungkinan-kemungkinan yang dapat terjadi sebagai akibat dari perubahan-perubahan pada bagian tertentu.

Misalnya perubahan pada pembatas (kapasitas) kendala, koefisien pada kendala, koefisien fungsi tujuan, penambahan variabel baru, dan penambahan kendala baru.

Semua perubahan tersebut tentunya berpengaruh  terhadap hasil solusi optimum yang telah ada.

Salah satu perubahan dapat terjadi tentunya proses eksekusi tahapan dalam metode simpleks akan kita lakukan kembali.

Kondisi demikian tentu memberikan waktu yang lama dan pekerjaan dimulai dari awal kembali.

Untuk mengatasi perubahan yang demikian maka diperlukan suatu analisis yang digunakan agar proses perhitungan tidak dilakukan dari awal apabila terjadi perubahan-perubahan seperti yang telah disebutkan di atas.

Alat analisis yang dapat digunakan adalah dengan menggunakan pendekatan analisis sensitivitas.

Pendekatan ini digunakan tanpa mengulang proses eksekusi dari awal akan tetapi persyaratan yang harus dipenuhi adalah tersedianya data tabel simpleks optimum.

Pada prinsipnya terdapat beberapa perubahan yang mungkin terjadi yang dapat dijawab melalui analisis sensitivitas, yaitu:

  1. Perubahan pada koefisien fungsi tujuan, baik pada koefisien dasar atau bukan dasar dan pengaruhnya terhadap variabel dual.
  2. Perubahan pada kendala, baik pada kapasitas atau koefisien.
  3. Penambahan variabel keputusan baru.
  4. Penambahan kendala/batasan baru.
Iklan

Contoh :

Untuk menerapkan analisis sensitivitas, perlu dimengerti terlebih dahulu tentang program linear metode simpleks.

Untuk langkah-langkah metode simpleks dapat dipelajari pada: Pemecahan Program Linear Metode Simpleks

Fungsi tujuan : Maksimumkan Z = 800A + 400B + 600C
Kendala :
2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500
A,B,C ≥ 0  

Formulasi :

2A + 2B + C + S1 = 250
5A + 4B + 3C + S2 = 350
6B + 5C + S3 = 500
A, B, C, S1, S2, S3 ≥ 0

Tabel simpleks :

Basis Z A B C S1 S2 S3 Solusi
Z1 -800-400-6000 0 0 0
S10 2211 0 0 250
S20 5430 1 0 350
S30 0650 0 1 500
IterasiBasis Z A B C S1 S2 S3 Solusi
1Z1 0240-12001600 56.000
S10 02/5-1/51 -2/50 110
A0 14/53/50 1/50 70
S30 0650 0 1 500
IterasiBasis Z A B C S1 S2 S3 Solusi
2Z1 0384001602468.000
S10 00,6401 -0,40,04130
A0 10,0800 0,2-0,1210
C0 01,210 0 0,2100
Iklan

Analisis Sensitivitas Untuk Mengisi Tabel Optimum

Analisis sensitivitas digunakan untuk menjawab nilai variabel dual disamping itu juga dapat mengisi tabel simpleks optimum yang kosong.

Hal ini dapat dilakukan dengan catatan tersedianya matriks kunci pada tabel simpleks optimum tersebut.

Misalnya diketahui :

Fungsi tujuan : Maksimumkan Z = 800A + 400B + 600C
Kendala :
2A + 2B + C ≤ 250
5A + 4B + 3C ≤ 350
6B + 5C ≤ 500
A,B,C ≥ 0  

Basis Z A B C S1 S2 S3 Solusi
Z1






S10


1 -0,40,04
A0


00,2-0,12
C0


00 0,2

Kita dapat mengisi kolom A, B, C dengan cara mengalikan matriks kunci dengan kendala variabel A/B/C.

Matriks Analisis Sensitivitas Nilai Kolom A
Matriks Analisis Sensitivitas Nilai Kolom B
Matriks Analisis Sensitivitas Nilai Kolom C

Untuk mengisi kolom solusi dapat dilakukan dengan mengalikan matriks kunci dengan pembatas.

Matriks Analisis Sensitivitas Nilai Variabel

Untuk mengisi nilai variabel dual (variabel pada baris Z kolom S1, S2, dan S3), dapat dihitung dengan mengalikan vektor baris dari variabel basis dengan matriks kunci:

Matriks Analisis Sensitivitas Nilai Variabel Dual

Setelah itu angka-angka tersebut dimasukkan ke dalam tabel simpleks, sehingga didapatkan:

Basis Z A B C S1 S2 S3 Solusi
Z1


016024
S10 00,6401 -0,40,04130
A0 10,0800 0,2-0,1210
C0 01,210 0 0,2100

Untuk menghitung sisanya, dapat dihitung dengan menggunakan perkalian dan penjumlahan biasa berdasarkan fungsi tujuannya.

Diketahui:

Fungsi tujuan : Maksimumkan Z = 800A + 400B + 600C

Untuk mengisi kolom solusi Z dapat dihitung dengan memasukkan solusi yang ada dimana A = 10, dan C = 100, sedangkan B = 0 karena tidak digunakan.

Z = 800 (10) + 400 (0) + 600 (100)
Z = 68000

Untuk mencari nilai Z kolom A,B,C, dapat dicari dengan rumus :

Cj – Zj

Jadi, Cj – Zj dicari dengan mengalikan variabel basis dengan angka-angka yang terdapat pada kolom A, B, dan C.

Setelah itu baru dikurangi dengan konstanta pada fungsi tujuan Z sesuai dengan konstanta variabel masing-masing.

Sehingga didapatkan :

A = ( 0 x 0 + 800 x 1 + 600 x 0 ) – 800 = 0
B = ( 0 x 0,64 + 800 x 0,08 + 600 x 1,2 ) – 400 = 384
C = ( 0 x 0 + 800 x 0 + 600 x 1 ) – 800 = 0

Jadi didapatkan tabel simpleks lengkapnya seperti berikut:

Basis Z A B C S1 S2 S3 Solusi
Z1 0384001602468.000
S10 00,6401 -0,40,04130
A0 10,0800 0,2-0,1210
C0 01,210 0 0,2100

Metode Dual Simpleks

Metode Dual Simpleks

Sebelum masuk ke materi dual simpleks ini ada baiknya anda memahami lebih lanjut mengenai Masalah Minimasi Metode Simpleks

Prosedur perhitungan yang pada bagian sebelumnya berkisar dari solusi dasar feasibel yang belum optimal menuju ke solusi feasibel optimal. Apakah proses tersebut akhirnya akan mencapai solusi feasibel optimal adalah tergantung pada kemampuan untuk mendapatkan suatu solusi dasar awal yang feasibel.

Dalam kaitan ini, variabel artificial R dapat digunakan untuk menemukan solusi awal feasibel. Jika formulasi program linear mengandung banyak variabel artificial, akan membutuhkan banyak perhitungan untuk memperoleh solusi awal feasibel.

Iklan

Untuk menghindari masalah tersebut dapat digunakan suatu prosedur yang disebut metode dual simpleks. Metode ini meskipun pada solusi awalnya tidak feasibel. Pada dasarnya metode dual simpleks menggunakan tabel yang sama seperti metode dual simpleks pada primal, tetapi leaving variabel dan entering variabelnya ditentukan sebagai berikut:

1. Leaving Variabel

Sebagai leaving variabel adalah variabel basis yang memiliki harga negatif angka terbesar. Jika semua variabel basis berharga positif atau nol berarti keadaan feasibel telah tercapai.

2. Entering Variabel

  • Tentukan rasio antara koefisien persamaan Z dengan koefisien persamaan leaving variabel. Abaikan penyebut positif atau nol. Jika semua penyebut berharga positif atau nol, berarti persoalan yang bersangkutan tidak memiliki solusi feasibel.
  • Untuk persoalan minimasi, entering variabel adalah variabel dengan rasio terkecil. Sedangkan untuk persoalan maksimasi entering variabel adalah variabel dengan rasio terkecil.

Contoh:

Minimumkan : Z = 16 X1 + 20 X2
Kendala :
6 X1 + 12 X2 ≥ 72
15 X1 + 6 X2 ≥ 90
6 X1 + 5 X2 ≤ 60
X1, X2 ≥ 0

Syarat digunakan metode dual simpleks jika ada kendala yang merupakan ketidaksamaan bertanda ≥. Jadi ubahlah variabel S menjadi positif.

Langkah 1: Formulasikan fungsi tujuan dan kendala

Formulasi diatas menjadi:

Minimumkan : Z – 16 X1 – 20 X2 = 0
Kendala:
-6 X1 – 12 X2 + S1 = -72
-15 X1 – 6 X2 + S2 = -90
6 X1 + 5 X2 + S3 = 60
X1, X2, S1, S2, S3 ≥ 0

Langkah 2: Tentukan leaving variabelnya

Seperti dalam metode simpleks, metode ini didasarkan pada optimality dan feasibility condition. Optimality condition menjamin bahwa solusi tetap optimum sedangkan feasibility condition memaksa agar solusi mencapai keadaan layak. Jadi, intinya metode dual simpleks mirip dengan metode simpleks biasa hanya saja ditranspose (baris jadi kolom & kolom jadi baris)

Jadi berdasarkan soal diatas didapatkan tabel awal sebagai berikut :

IterasiBasis Z X1 X2 S1 S2 S3 Solusi
0Z1 -16-200000
S10 -6-12100-72
S20 -15-6010-90
S30 6500160

Jadi, dalam metode dual simpleks, yang pertama ditentukan adalah leaving variabelnya dengan solusi yang memiliki angka negatif terbesar.

Langkah 3: Tentukan entering variabelnya

Basis Z X1 X2 S1 S2 S3 Solusi
Z1 -16-200000
S10 -6-12100-72
S20 -15-6010-90
S30 6500160
Rasio16/1520/6

Setelah itu baru hitunglah rasionya dengan membagi angka dari baris Z dengan leaving variabelnya dan pilih rasio yang terkecil. Abaikan rasio yang memiliki angka negatif atau nol.

Langkah 4: Tentukan persamaan pivot baru

Dari langkah ini sudah mirip dengan langkah metode simpleks biasa, untuk lebih jelasnya tentang metode simpleks dapat dilihat pada : Pemecahan Program Linear Metode Simpleks, jadi berdasarkan soal diatas didapatkan baris pivot barunya adalah :

Basis Z X1 X2 S1 S2 S3 Solusi
Z1
S1
X10 12/50-1/1506
S3

Langkah 5: Tentukan persamaan baru selain pivot baru

Setelah mendapat persamaan pivot baru, langkah selanjutnya adalah mengisi persamaan lainya yang masih kosong. Rumus untuk menentukan persamaan baru selain persamaan pivot baru adalah sebagai berikut:

Persamaan baru = (persamaan lama) – (persamaan pivot baru x koefisien kolom pivot)

Persamaan Z baru :
(-16) – (1 x -16) = 0
(-20) – (2/5 x -16) = -68/5
(0) – (0 x -16) = 0
(0) – (-1/15 x -16) = -16/15
(0) – (0 x -16) = 0
(0) – (6 x -16) = 96  

Persamaan S1 baru :
(-6) – (1 x -6) = 0
(-12) – (2/5 x -6) = -48/5
(1) – (0 x -6) = 1
(0) – (-1/15 x -6) = -2/5
(0) – (0 x -6) = 0
(-72) – (6 x -6) = -36  

Persamaan S3 baru :
(6) – (1 x 6) = 0
(5) – (2/5 x 6) = 13/5
(0) – (0 x 6) = 0
(0) – (-1/15 x 6) = 2/5
(1) – (0 x 6) = 1
(60) – (6 x 6) = 24

Setelah mencari persamaan Z, S1 dan S3 baru kemudian tabulasikan dalam tabel simpleks sebagai berikut :

IterasiBasis Z X1 X2 S1 S2 S3 Solusi
1Z1 0-68/50-16/15096
S100-48/51-2/50-36
X10 12/50-1/1506
S30013/502/5124

Langkah 6: Lanjutkan Perbaikan-Perbaikan

Setelah didapatkan persamaan baru, periksa kembali apakah solusi masih ada yang bertanda negatif atau tidak, jika masih ada berarti solusi belum optimal sehingga perlu diulangi kembali dari langkah ke-2.

Dari persamaan diatas didapatkan masih adanya solusi yang negatif, sehingga perlu dilakukan langkah-langkah perbaikan dengan mengulangi langkah ke-2.Sehingga didapatkan tabel berikut:

IterasiBasis Z X1 X2 S1 S2 S3 Solusi
2Z1 00-17/12-1/20147
X20 01-5/481/24015/4
X10 101/24-1/1209/2
S30 0013/487/24157/4

Berdasarkan iterasi awal terlihat bahwa meskipun koefisien persamaan Z sudah memenuhi kondisi optimal (barisan Z sudah nol atau negatif untuk kasus minimasi), tetapi variabel-variabel basis awalnya tidak memberikan solusi awal yang feasibel (S1, S2 berharga negatif).

Solusi optimal dan feasibel tercapai pada iterasi kedua. Selain untuk menghindari perhitungan yang rumit, metode dual simpleks sangat penting untuk digunakan pada analisis sensitivitas.

Hal ini terjadi apabila suatu pembatas baru ditambahkan (atau pembatas lama diubah), pada suatu persoalan yang sudah mencapai solusi optimal dan mengakibatkan solusi tidak feasibel, sehingga untuk menyelesaikannya digunakan metode dual simpleks.

Teori Dualitas | Primal-Dual

Teori Dualitas Primal-Dual

Tidak lama sesusudah program linear berkembang, baru disadari bahwa setiap kali sebuah persoalan program linear dirumuskan selalu terdapat sebuah persoalan program linear lainya yang mempunyai hubungan sangat erat dengan persoalan pertama.

Iklan

Konsep Dualitas

Konsep dualitas merupakan suatu konsep bagian dari program linear yang sangat penting dan menarik untuk dibahas. Konsep ini menyatakan dalam setiap masalah program linear mempunyai dua bentuk yang saling berhubungan dan keterkaitan.

Dapat pula diartikan sebagai “lawan dari”, maksudnya apabila terdapat persamaan mula-mula dalam bentuk primal maka mempunyai lawan dalam bentuk dual, jika bentuk dual itu dianggap sebagai primal maka bentuk dualnya adalah persamaan mula-mula tersebut diatas.

Bentuk pertama (asli) dinamakan primal, sedangkan bentuk kedua adalah dual. Apabila dalam solusi optimum pada tabel simpleks bentuk asli (primal) telah terpecahkan, maka tabel simpleks optimum tersebut dapat juga menjawab permasalahan dualnya.

Iklan

Ketentuan Bentuk Primal-Dual

Terdapat beberapa ketentuan awal yang harus dipahami sebelum masuk dalam konsep primal-dual untuk kasus program linear maksimasi dan minimasi.

Adapun ketentuan primal dan dualnya sebagai berikut:

No.Bentuk PrimalBentuk Dual
1Umumnya notasi fungsi tujuan adalah Z Umumnya notasi fungsi tujuan adalah W
2Umumnya notasi variabel keputusan dalam bentuk X Umumnya notasi variabel keputusan adalah Y
3Unsur koefisien matriks pembatas Transpose koefisien matriks pembatas
4Vektor ruas kanan pada kendalaKoefisien fungsi tujuan
5Koefisien fungsi tujuanVektor ruas kanan pada kendala
6Pembatas ke-i berupa “=”Yi tidak terbatas dalam tanda
7Xj tidak terbatas dalam tandaPembatas ke-j berupa “=”

Fungsi tujuan berbentuk maksimasi:

No.Bentuk PrimalBentuk Dual
1Fungsi tujuan berbentuk maksimasiFungsi tujuan berbentuk minimasi
2Pembatas ke-i berupa “≤”Yi ≥ 0
3Pembatas ke-i berupa “≥”Yi ≤ 0
4Xj ≥ 0Pembatas ke-j berupa “≥”
5Xj ≤ 0Pembatas ke-j berupa “≤”

Fungsi tujuan berbentuk minimasi:

No.Bentuk PrimalBentuk Dual
1 Fungsi tujuan berbentuk minimasi Fungsi tujuan berbentuk maksimasi
2 Pembatas ke-i berupa “≤” Yi ≤ 0
3 Pembatas ke-i berupa “≥” Yi ≥ 0
4 Xj ≥ 0 Pembatas ke-j berupa “≤”
5 Xj ≤ 0 Pembatas ke-j berupa “≥”
Iklan

Hubungan Persoalam Primal dengan Dual

  1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan persoalan dual. Sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi dual.
  2. Untuk setiap pembatas primal ada satu variabel dual. Dan untuk setiap variabel primal ada satu pembatas dual.
  3. Setiap variabel primal berkorespondensi dengan pembatas dual. Dan setiap pembatas primal berkorespondensi dengan variabel dual.
  4. Fungsi tujuan berubah bentuk yaitu maksimasi menjadi minimasi dan sebaliknya. Sedangkan tanda ketidaksamaan bergantung pada fungsi tujuan yaitu maksimum dual bertanda ≤, minimum dual bertanda ≥.
  5. Dual dari dual adalah primal.

Contoh 1:

Primal:

Kendala :
4 X1 + 8 X2 + 5 X3 ≤ 80
9 X1 + 6 X2 + 8 X3 ≤ 108
X1, X2, X3 ≥ 0

Bentuk Standar:

Maksimumkan : Z = 5 X1 + 8 X2 + 6 X3 + 0S1 + 0 S2
Kendala :
4 X1 + 8 X2 + 5 X3 + S1 = 80
9 X1 + 6 X2 + 8 X3 + S2 = 108
X1, X2, X3, S1, S2 ≥ 0

Dual:

Minimumkan : W = 80 Y1 + 108 Y2
Kendala :
4 Y1 + 9 Y2 ≥ 5
8 Y1 + 6 Y2 ≥ 8
5 Y1 + 8 Y2 ≥ 6
Y1 ≥ 0
Y2 ≥ 0

Contoh 2:

Primal:

Maksimumkan : Z = 4 X1 + 6 X2 + 5 X3
Kendala :
2 X1 + 4 X2 + X3 ≤ 40
X1 + X2 + 3 X3 = 48
X1, X2, X3 ≥ 0

Bentuk Standar :

Maksimumkan : Z = 4 X1 + 6 X2 + 5 X3 + 0 S1
Kendala :
2 X1 + 4 X2 + X3 + S1 = 40
X1 + X2 + 3 X3 = 48
X1, X2, X3, S1 ≥ 0

Dual:

Minimumkan : W = 40 Y1 + 48 Y2
Kendala :
2 Y1 + Y2 ≥ 4
4 Y1 + Y2 ≥ 6
Y1 + 3 Y2 ≥ 5
Y1 ≥ 0
Y2 tidak terbatas dalam tanda

Kasus Khusus Penggunaan Metode Simpleks

Kasus Khusus Metode Simpleks

Terdapat beberapa kasus pada metode simpleks yang menyebabkan perhitungan pada metode simpleks ini menjadi sangat rumit dan tidak selesai-selesai.

Kasus khusus dari penggunaan metode simpleks ini dapat berupa degenerasi, solusi optimum banyak, solusi tak terbatas, dan tidak ada solusi layak.

Berikut akan dibahas kasus khusus penggunaan metode simpleks, namun sebelum anda membaca lebih lanjut, bagi anda yang masih belum mengerti betul tentang metode simpleks, ada baiknya anda membaca artikel sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

Iklan

Berikut adalah kasus khusus dalam penggunaan metode simpleks :

1. Degenerasi

Suatu program linear bersifat degenerasi apabila satu atau beberapa variabel basis berharga nol, sehingga iterasi yang dilakukan selanjutnya menjadi suatu loop yang akan kembali ke bentuk sebelumnya. 

Contoh:

Maksimumkan : Z = 12 X1 + 4 X2
Kendala :
8 X1 + 2 X2 ≤ 16
6 X1 + 3 X2 ≤ 12
X1, X2 ≥ 0

Berdasarkan persamaan diatas, lakukan penyelesaian dengan metode simpleks seperti yang sudah dijelaskan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

IterasiBasis Z X1 X2 S1 S2 SolusiRasio
0Z1 -12-4000
S10 8210162
S20 6001122
IterasiBasis Z X1 X2 S1 S2 SolusiRasio
1Z1 0-13/2024
X10 11/41/8028
S20 03/2-3/4100
IterasiBasis Z X1 X2 S1 S2 Solusi
2Z1 0012/324
X10 101/4-1/62
X20 01-1/22/30

Pada tabel diatas (iterasi 0) terdapat dua rasio minimum, maka pemilihan leaving variabel atau kolom pivot dilakukan secara sembarang. Ini menjadi sebab variabel basis bernilai nol pada iterasi pertama, yang menghasilkan solusi dasar degenerasi.

Solusi optimal tercapai pada iterasi kedua (Z = 24) yang memberikan solusi sama dengan iterasi 1. Disini terlihat adanya prosedur simpleks uang berulang akan tetapi tidak memperbaiki nilai Z. Nilai variabel dan fungsi tujuan pada iterasi 1 dan 2 sama yaitu X1 = 2, X2 = 0, S1 = 0, S2 = 0, dan Z = 24.

Meskipun pada iterasi 1 dan 2 memberikan hasil yang sama, tetapi pada iterasi 1 tetap diteruskan sampai memenuhi kondisi optimal. Mengapa kita tidak menghentikan saja perhitungannya ? Karena tidak semua persoalan degenerasi menghasilkan degenerate yang tetap, tetapi ada juga yang sifatnya temporer dimana iterasi berikutnya menghilang. Seperti yang ditunjukkan pada contoh berikut ini :

Maksimumkan : Z = 3 X1 + 2 X2
Kendala :
4 X1 + 3 X2 ≤ 12
4 X1 + X2 ≤ 8
4 X1 – X2 ≤ 8
X1, X2 ≥ 0

IterasiBasis Z X1 X2 S1 S2 S3 SolusiRasio
0Z1 -3-20000
S10 43100123
S20 4101082
S30 4-100182
IterasiBasis Z X1 X2 S1 S2 S3 SolusiRasio
1Z1 0-5/403/406
S10 021-1042
X10 11/401/4028
S30 0-20-110
IterasiBasis Z X1 X2 S1 S2 S3 Solusi
2Z1 005/81/8017/2
X20 011/2-1/202
X10 10-1/83/803/2
S30 001-214

Pada tabel diatas, degenerasi muncul pada iterasi 1, tetapi kemudian menghilang pada iterasi kedua, dimana fungsi tujuan pun berubah dari Z = 6 menjadi Z = 17/2 pada iterasi kedua.

Degenerasi menghilang karena X2, yang menjadi entering variabel atau kolom pivot pada iterasi 1 mempunyai koefisien pembatas yang berharga negatif (= -2) yang berkorespondensi dengan basis S3 yang berharga nol.

Iklan

2. Solusi Optimum Banyak

Persoalan memiliki solusi lebih dari satu apabila fungsi tujuan paralel dengan fungsi pembatas, dimana paling sedikit salah satu dari variabel non-basis (persamaan Z pada iterasi terakhir) mempunyai koefisien berharga nol.

Akibatnya walaupun variabel tersebut dinaikkan harganya, harga Z tetap tidak berubah. Karena itu solusi-solusi optimum yang lain ini biasanya dapat dilakukan iterasi tambahan pada metode simpleksnya, dimana variabel-variabel non-basis berkoefisien nol itu selalu dipilih untuk menjadi entering variabel.

Contoh:

Maksimumkan : Z = 2 X1 + 4 X2
Kendala :
X1 + 2 X2 ≤ 5
X1 + X2 ≤ 4
X1, X2 ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

IterasiBasis Z X1 X2 S1 S2 Solusi
0Z1 -2-4000
S10 12105
S20 11014
IterasiBasis Z X1 X2 S1 S2 Solusi
1Z1 002010
X20 1/211/205/2
S20 1/20-1/213/2
IterasiBasis Z X1 X2 S1 S2 Solusi
TambahanZ1 002010
X20 011-11
X10 10-123

Pada tabel diatas, persamaan fungsi tujuan paralel dengan persamaan pembatas pertama. Pada iterasi 1 (optimum), koefisien variabel non-basis X1 adalah nol sehingga pada iterasi berikutnya (iterasi tambahan), X1 ini dipilih menjadi entering variabel tanpa mengubah harga Z, tetapi menyebabkan berubahnya harga variabel X1 tersebut.

Iklan

3. Solusi Tidak Terbatas

Penyelesaian dikatakan tidak terbatas, apabila nilai suatu fungsi tujuan dapat dibuat tak terhingga tanpa melanggar setiap batasan yang ada. Jika hal ini terjadi pada masalah maksimasi keuntungan, berarti dapat dicapai suatu tingkat keuntungan yang terbatas.

Kejadian ini dapat berarti bahwa masalah yang ada tidak dirumuskan dengan tepat. Kesalahan ini dapat berupa :

  • Adanya kendala tak berlebih yang diikut sertakan.
  • Adanya parameter dari beberapa kendala tidak diduga dengan benar.

Contoh:

Maksimumkan : Z = 6 X1 + 4 X2
Kendala :
2 X1 – 3 X2 ≤ 12
3 X1 ≤ 30
X1, X2 ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.

IterasiBasis Z X1 X2S1 S2 Solusi
0Z1 -6-4000
S10 2-31012
S20 300130

Pada tabel diatas X1 akan dipilih sebagai entering variabel atau kolom pivot karena memiliki koefisien negatif terbesar. Karena koefisien pembatas pada kolom X2 non-positif (negatif atau nol), berarti X2 dapat bertambah harganya secara tak terbatas, karena setiap unit penambahan X2 akan meningkatkan Z sebesar 4 (lihat persamaan fungsi tujuan) maka penambahan yang tak terbatas pada X2 akan meningkatkan harga Z secara tak terbatas.

Iklan

4. Tidak Ada Solusi Layak

Contoh:

Maksimumkan : Z = 4 X1 + 5 X2
Kendala :
3 X1 + 5 X2 ≤ 12
X1 ≤ 6
X2 ≥ 0
X1, X2 ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks minimasi seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Masalah Minimasi Metode Simpleks

IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
0Z1(-M-4) -M-50M0M0-10M
S10 351000015
R10 100-11006
R20 01000-114
IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
1Z1-2/5M-101/5M+1M0M0-7M+15
X20 3/511/500003
R10 100-11006
R20 -3/50-1/500-111
IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
2Z102/3M+5/3(M+4)/3M0M0-5M+20
X10 15/31/300005
R10 0-5/3-1/3-11001
R20 01000-114

Pada tabel terlihat bahwa pada iterasi kedua (tabel optimum), artificial variabel berharga positif (R1 = 1 dan R2 = 4). Ini sebagai indikasi ruang solusi tidak layak, dan solusi tersebut merupakan solusi optimum samaran  (pseudo optimal).