Diketahui:
Fungsi tujuan: maksimum Z = 25X1 + 25X2, dan Batasan:
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
- X1, X2 ≥ 0
Contoh Penyelesaian Metode Simpleks vs. Grafik
A. Penyelesaian Metode Simpleks
1. Mengubah Fungsi Tujuan dan Batasannya
Diubah menjadi fungsi implisit, artinya semua CjXij digeser ke kiri.
Fungsi Tujuan:
Z = 25X1 + 25X2 menjadi → Z - 25X1 - 25X2 = 0
Fungsi Batasan:
Karena fungsi batasan berupa pertidaksamaan, maka cara merubahnya kebentuk implisit adalah dengan menambahkan Slack Variabel.
3X1 + 2X2 ≤ 6 menjadi → 3X1 + 2X2 + X3 = 6
2X1 + 4X2 ≤ 8 menjadi → 2X1 + 4X2 + X4 = 82. Menyusun Persamaan Ke Dalam Tabel
- Z - 25X1 - 25X2 = 0
- 3X1 + 2X2 + X3 = 6
- 2X1 + 4X2 + X4 = 8
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|-----|-----|----|----|----|
| Z | 1 | -25 | -25 | 0 | 0 | 0 |
| X3 | 0 | 3 | 2 | 1 | 0 | 6 |
| X4 | 0 | 2 | 4 | 0 | 1 | 8 |3. Memilih Kolom Kunci
Pada baris Z terdapat dua nilai (-) yang sama besarnya, jadi harus dipilih salah satunya, dan itu bebas. Pada kasus ini saya pilih -25 di kolom X1.
4. Memilih Baris Kunci
Sebelum menentukan baris kunci, terlebih dahulu menghitung index variabel dasarnya, kecuali baris Z. Sehingga diperoleh hasil sebagai berikut:
5. Mengubah Nilai-nilai Baris Kunci
Didapat nilai kunci = 3.
6. Mengubah nilai-nilai selain baris kunci
Maka diperoleh hasil:
Tabel pertama (putih) nilai lama dan tabel kedua (berwarna) nilai baru,
7. Re-Optimasi
Dikarenakan baris Z pada tabel ke dua (berwarna) masih terdapat nilai negatif (-), maka diperlukan lagi optimasi dengan cara mengulangi langkah 3 s/d. 6.
Tabel optimasi ke 1
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK | Indeks |
|----------------|---|----|-------|------|----|----|--------|
| Z | 1 | 0 | -25/3 | 25/3 | 0 | 50 | |
| X1 | 0 | 1 | 2/3 | 1/3 | 0 | 2 | |
| X4 | 0 | 0 | 8/3 | -2/3 | 1 | 4 | |7.3. Memilih Kolom Kunci
7.4. Memilih Baris Kunci
7.5. Mengubah Nilai-nilai Baris Kunci
7.6. Mengubah nilai-nilai selain baris kunci
Tabel yang diperoleh dari tabel pertama s/d. perbaikan / perubahan terakhir:
Kesimpulan
Karena pada baris fungsi tujuan (Z) sudah tidak ada yang bernilai negatif (-), maka sudah dianggap optimal dengan nilai X1 = 1, X2 = 3/2 dan Z max = 125/2.
Penyelesaian Metode Grafik
1. Menentukan Variabel
| - | Variabel |
|---|----------|
| - | X1 |
| - | X2 |2. Menentukan Fungsi Tujuan (Z)
Z = 25X1 + 25X2
3. Menentukan Fungsi Batasan
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
4. Minimalkan Z
Telah didapatkan 2 fungsi batasan, diantaranya;
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
1). 3X1 + 2X2 ≤ 6
Jika, X1 = 0, maka X2 = 6/2 = 3
Jika, X2 = 0, maka X1 = 6/3 = 2
Jadi, (X1, X2) = (2, 3)
2). 2X1 + 4X2 ≤ 8
Jika, X1 = 0, maka X2 = 8/4 = 2
Jika, X2 = 0, maka X1 = 8/2 = 4
Jadi, (X1, X2) = (4, 2)
5. Menggambar Grafik dan Mendeklarasikan Daerah Feasible
Menggambar Grafik dan Mendeklarasikan Daerah Feasible
6. Mencari Nilai Z Optimal
Studi kasus menanyakan tentang MAKSIMAL fungsi tujuan (Z).
Untuk mencari nilai Z optimal dapat digunakan 2 cara:
1. Dengan membandingkan nilai Z pada tiap-tiap titik alternatif
Caranya adalah dengan menghitung nilai Z pada tiap-tiap titik alternatif, dengan cara subtitusi.
Titik A
Karena titik A adalah perpotongan dari batasan 1 dan 2, maka perlu menggunakan kedua pertidaksamaan / fungsi tersebut,
Eliminasi:
3X1 + 2X2 ≤ 6 | kalikan 2
2X1 + 4X2 ≤ 8 | kalikan 1
------------------------------
6X1 + 4X2 ≤ 12
2X1 + 4X2 ≤ 8
------------------------------ (-)
4X1 + 0 = 4
X1 = 4/4
X1 = 1Subtitusi ke salah satu pertidaksamaan:
3X1 + 2X2 ≤ 6
3*1 + 2X2 ≤ 6
3 + 2X2 ≤ 6
2X2 ≤ 6 - 3
2X2 ≤ 3
X2 ≤ 3/2Sehingga diperoleh titik A (1, 3/2). Berikutnya subtitusikan ke fungsi tujuan (Z), maka;
Z = 25X1 + 25X2
Z = 25*1 + 25*3/2
Z = 25 + 75/2
Z = 50/2 + 75/2
Z = 125/2
Z = 125/2 (max)7. Membuat Kesimpulan
Maka bisa ditarik kesimpulan bahwa, X1 = 1 dan X2 = 3/2 dan Z Max = 125/2.
Panduan:
Metode Grafik vs Simpleks UTS Riset Operasi
Diketahui masalah PL:
Perusahaan Keripik Kentang Kemripik membuat dua macam keripik Nikmat dan Enak yang setiap kilonya (10 kemasan) dijual Rp.130.000,- dan Rp.120.000,- Dalam setiap kali produksi disediakan paling banyak 4kg kentang mutu sedang dan 4kg kentang mutu super.
Untuk membuat Keripik Nikmat dibutuhkan 1kg kentang mutu sedang dan 4kg kentang mutu super. Untuk membuat Keripik Enak dibutuhkan kentang mutu sedang 4kg dan kentang mutu super 1kg. Berapakah Keripik Kentang Nikmat dan Enak harus dibuat agar diperoleh keuntungan paling banyak jika diketahui biaya pembuatan masing-masing keripik Rp.100.000,-/kg.
Penyelesaian Metode Grafik vs Simpleks - UTS Riset Operasi
Selesaikan masalah PL diatas menggunakan:
- Metode Grafik
- Metode Simpleks
1. Penyelesaian Metode Grafik
1. Menentukan Variabel
| Keripik | Variabel |
|---------|----------|
| Nikmat | X1 |
| Enak | X2 |2. Menentukan Fungsi Tujuan (Z)
Z = ...X1 + ...X2
| Keripik | Jual | Keuntungan | Biaya |
|---------|--------------|-------------|--------------|
| Nikmat | Rp.130.000,- | Rp.30.000,- | Rp.100.000,- |
| Enam | Rp.120.000,- | Rp.20.000,- | Rp.100.000,- |Karena yang ditanyakan adalah berapa keuntungan paling banyak, maka nilai yang digunakan untuk variabel tujuan adalah nilai pada kolom keuntungan, sehingga menjadi;
Z = 30.000 X1 + 20.000 X2
Z = 3X1 + 2X2 → (Menggunakan skala 1:10.000).3. Menentukan Fungsi Batasan
| Bahan | Fungsi | Batasan |
|---------------------|----------|---------|
| Kentang mutu SEDANG | X1 + 4X2 | ≤ 4 |
| Kentang mutu SUPER | 4X1 + X2 | ≤ 4 |4. Minimalkan Z
Telah didapatkan 2 fungsi batasan, diantaranya;
- X1 + 4X2 ≤ 4
- 4X1 + X2 ≤ 4
1). X1 + 4X2 ≤ 4
Jika, X1 = 0, maka X2 = 4/4 = 1
Jika, X2 = 0, maka X1 = 4/1 = 4
Jadi, (X1, X2) = (4, 1)
2). 4X1 + X2 ≤ 4
Jika, X1 = 0, maka X2 = 4/1 = 4
Jika, X2 = 0, maka X1 = 4/4 = 1
Jadi, (X1, X2) = (1, 4)
5. Menggambar Grafik dan Mendeklarasikan Daerah Feasible
6. Mencari Nilai Z Optimal
Studi kasus menanyakan tentang keuntungan paling banyak (MAKSIMAL), maka fungsi tujuan (Z) optimal maksimal dapat dicari dengan cara:
Menggunakan titik alternatif (Titik A)
Karena titik A adalah perpotongan dari batasan 1 dan 2, maka perlu menggunakan kedua pertidaksamaan / fungsi tersebut,
Eliminasi:
X1 + 4X2 ≤ 4 || kalikan 4
4X1 + X2 ≤ 4 || kalikan 1
------------------------------
4X1 + 16X2 ≤ 16
4X1 + X2 ≤ 4
------------------------------ (-)
0 + 15X2 ≤ 12
X2 ≤ 12
X2 ≤ 12/15
X2 ≤ 4/5Subtitusi ke salah satu pertidaksamaan:
X1 + 4X2 ≤ 4
X1 + 4*4/5 ≤ 4
X1 + 16/5 ≤ 4
X1 ≤ 4 - 16/5
X1 ≤ (60 - 48) /15
X1 ≤ 12/15
X1 ≤ 4/5Sehingga diperoleh titik A (4/5,4/5). Berikutnya subtitusikan ke fungsi tujuan (Z), maka;
Z = 3X1 + 2X2
Z = 3*4/5 + 2*4/5
Z = 12/5 + 8/5
Z = 20/5
Z = 4 (max)7. Membuat Kesimpulan
Maka bisa ditarik kesimpulan bahwa, X1 = 4/5 dan X2 = 4/5 dan Z Max = 4. Dengan kata lain, untuk bisa memperoleh keuntungan maksimal pembuatan keripik dalam setiap kilogramnya cukup dengan 4/5 keripik Nikmat, 4/5 Keripik Enak dan keuntungan yang dihasilkan 4 x Rp.10.000,- = Rp.40.000,-
2. Penyelesaian Metode Simpleks
Diketahui fungsi tujuan (Z) = 3X1 + 2X2 (skala 1:10.000).
Fungsi batasan:
- X1 + 4X2 ≤ 4
- 4X1 + X2 ≤ 4
1. Mengubah Fungsi Tujuan dan Batasannya
Diubah menjadi fungsi implisit, artinya semua CjXij digeser ke kiri.
Fungsi Tujuan:
Z = 3X1 + 2X2 menjadi → Z - 3X1 - 2X2 = 0
Fungsi Batasan:
Karena fungsi batasan berupa pertidaksamaan, maka cara merubahnya kebentuk implisit adalah dengan menambahkan Slack Variabel.
X1 + 4X2 ≤ 4 menjadi → X1 + 4X2 + X3 = 4
4X1 + X2 ≤ 4 menjadi → 4X1 + X2 + X4 = 42. Menyusun Persamaan Ke Dalam Tabel
- Z - 3X1 - 2X2 = 0
- X1 + 4X2 + X3 = 4
- 4X1 + X2 + X4 = 4
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|----|----|----|
| Z | 1 | -3 | -2 | 0 | 0 | 0 |
| X3 | 0 | 1 | 4 | 1 | 0 | 4 |
| X4 | 0 | 4 | 1 | 0 | 1 | 4 |3. Memilih Kolom Kunci
Pada baris Z dipilih nilai negatif terbesar, sehingga dapat ditentukan bahwa kolom kunci jatuh pada kolom X1.
4. Memilih Baris Kunci
Sebelum menentukan baris kunci, terlebih dahulu menghitung index variabel dasarnya, kecuali baris Z. Sehingga diperoleh hasil sebagai berikut:
5. Mengubah Nilai-nilai Baris Kunci
Didapat nilai kunci = 4
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|-----|----|-----|----|
| Z | | | | | | |
| X3 | | | | | | |
| X1 | 0 | 1 | 1/4 | 0 | 1/4 | 1 |6. Mengubah nilai-nilai selain baris kunci
Maka diperoleh hasil:
Sehingga diperoleh Tabel Perubahan Pertama:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|------|----|------|----|
| Z | 1 | 0 | -5/4 | 0 | 3/4 | 3 |
| X3 | 0 | 0 | 15/4 | 1 | -1/4 | 3 |
| X1 | 0 | 1 | 1/4 | 0 | 1/4 | 1 |7. Re-Optimasi
Dikarenakan baris Z pada Tabel Perubahan Pertama masih terdapat nilai negatif (-), maka diperlukan lagi optimasi dengan cara mengulangi langkah 3 s/d. 6.
7.3. Memilih Kolom Kunci
7.4. Memilih Baris Kunci
7.5. Mengubah Nilai-nilai Baris Kunci
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|------|-------|-----|
| Z | | | | | | |
| X2 | 0 | 0 | 1 | 4/15 | -1/15 | 4/5 |
| X1 | | | | | | |7.6. Mengubah nilai-nilai selain baris kunci
Sehingga diperoleh Tabel Perubahan Kedua:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|-------|-------|-----|
| Z | 1 | 0 | 0 | 1/3 | 2/3 | 4 |
| X2 | 0 | 0 | 1 | 4/15 | -1/15 | 4/5 |
| X1 | 0 | 1 | 0 | -1/15 | 4/15 | 4/5 |Kesimpulan
Karena pada baris fungsi tujuan (Z) sudah tidak ada yang bernilai negatif (-), maka sudah dianggap optimal dengan nilai X1 = 4/5, X2 = 4/5 dan Z max = 4 * Rp.10.000,- = Rp.40.000,-. Hasil ini sama dengan metode Grafik, sehingga saling memperkuat hasil yang diperoleh.