operations research -...
TRANSCRIPT
Fakultas Teknik
Universitas Pasundan
Jurusan Teknik Industri
Tjutju T Dimyati
OPERATIONS RESEARCH – I
MODEL-MODEL DETERMINISTIK
Jurusan Teknik Industri FT Unpas
PEMROGRAMAN LINIER
Tjutju T. Dimyati
PENYELESAIAN PERSOALAN DENGAN METODE GRAFIS
Jurusan Teknik Industri FT Unpas
Tujuan Pembelajaran
Menguasai penyelesaian persoalan Pemrograman Linier dengan metode grafis
Tjutju T. Dimyati
Jurusan Teknik Industri FT Unpas
Capaian Pembelajaran
Di akhir perkuliahan mahasiswa:
Mampu menyelesaikan persoalan Pemrograman Linier dengan dua variabel melalui penerapan konsep Fungsi dan Grafik untuk persamaan linier
Tjutju T. Dimyati
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
METODE GRAFIS
• Hanya dapat digunakan untuk menyelesaikan persoalan LP dengan dua variabel keputusan
• Fungsi tujuan maksimasi atau minimasi
• Fungsi-fungsi pembatas berupa persamaan atau pertaksamaan
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
TERMINOLOGI
• Seluruh titik (nilai variabel keputusan) yang memenuhi seluruh fungsi pembatas dan pembatas tanda disebut daerah fisibel
• Setiap titik pada daerah fisibel yang memberikan nilai fungsi tujuan terbaik (nilai terbesar untuk persoalan maksimasi atau terkecil untuk persoalan minimasi) disebut solusi optimal
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Langkah Penyelesaian Metode Grafis
1. Buat sumbu horizontal dan sumbu vertikal, nyatakan masing-masing sebagai variabel keputusan
2. Buat skala ukuran panjang pada masing-masing sumbu
3. Gambarkan garis setiap fungsi pembatas
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Langkah Penyelesaian Metode Grafis
4. Nyatakan arah daerah berlakunya setiap garis dan tentukan daerah fisibel, jika ada
5. Tentukan titik-titik ujung dari daerah fisibel, jika ada
6. Gambarkan garis fungsi tujuan
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Langkah Penyelesaian Metode Grafis
7. Geser garis fungsi tujuan (tidak boleh berubah arah) pada daerah fisibel hingga menyentuh titik ujung daerah fisibel yang dapat memberikan nilai fungsi tujuan terbaik (nilai terbesar untuk persoalan maksimasi atau terkecil untuk persoalan minimasi)
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Langkah Penyelesaian Metode Grafis
8. Tetapkan nilai koordinat dari titik ujung pada langkah 7 dan nyatakan titik tersebut sebagai titik optimal
9. Buat kesimpulan mengenai solusi persoalan yang diselesaikan
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Model LP untuk Persoalan Tabung Panas
MAX: 350X1 + 300X2
S.T.:
1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0 ; X2 >= 0
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 200)
(200, 0)
Garis pembatas pompa
X1 + X2 = 200
Pembatas Pertama
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 261)
(174, 0)
Garis pembatas waktu
9X1 + 6X2 = 1566
Pembatas Kedua
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 180)
(240, 0)
Garis pembatas tabung
12X1 + 16X2 = 2880
Daerah Fisibel
Pembatas Ketiga
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
X2 Menggambar Garis Fungsi Tujuan
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 116.67)
(100, 0)
Fungsi tujuan
350X1 + 300X2 = 35000
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Menggeser Garis Fungsi Tujuan X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 175)
(150, 0)
Nilai fungsi tujuan
350X1 + 300X2 = 35000
Nilai fungsi tujuan 350X1 + 300X2 = 52500
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Menentukan Lokasi Solusi Optimal X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
objective function
350X1 + 300X2 = 35000
objective function
350X1 + 300X2 = 52500
Solusi Optimal
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Menentukan Nilai Fungsi Tujuan
• Solusi optimal terjadi pada perpotongan garis pembatas “pompa” dan “waktu”.
• Kedua garis tersebut adalah:
X1 + X2 = 200 (1)
dan 9X1 + 6X2 = 1566 (2)
• Dari (1) diperoleh,
X2 = 200 -X1 (3)
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Menentukan Nilai Fungsi Tujuan
• Substitusi (3) tehadap X2 pada (2) diperoleh,
9X1 + 6 (200 -X1) = 1566
sehingga X1 = 122
• Maka solusi optimal adalah:
X1=122, X2=200-X1=78
Total Profit = $350*122 + $300*78 = $66,100
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Enumerasi Titik-titik Sudut X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 180)
(174, 0)
(122, 78)
(80, 120)
(0, 0)
Nilai FT = $54,000
Nilai FT = $64,000
Nilai FT = $66,100
Nilai FT = $60,900 Nilai FT = $0
Note: This technique will not work if
the solution is unbounded.
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Kondisi Khusus pada Models LP
Beberapa kondisi khusus dapat terjadi pada persoalan LP:
Solusi Optimal Alternatif
Pembatas Redundant
Solusi Unbounded
Tidak Fisibel
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh Solusi Optimal Alternatif X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
450 X1 + 300 X2 = 78300
Fungsi tujuan
Solusi optimal alternatif
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
ALTERNATIVE OPTIMAL SOLUTIONS
The case of alternative optimal solutions can be recognize graphically when the isoprofit line last hits an entire line segment before leaving the feasible region (Winston, 1987)
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh Pembatas Redundant X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
Batas garis pembatas tabung
Feasible Region
Batas garis pembatas pompa
Batas garis pembatas waktu
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh Solusi Unbounded X2
X1
1000
800
600
400
200
0
0 200 400 600 800 1000
X1 + X2 = 400
X1 + X2 = 600
Fungsi tujuan
X1 + X2 = 800
Fungsi tujuan
-X1 + 2X2 = 400
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh Tidak Fisibel X2
X1
250
200
150
100
50
0
0 50 100 150 200 250
X1 + X2 = 200
X1 + X2 = 150
Daerah fisibel untuk
pembatas kedua
Daerah fisibel
untuk pembatas
pertama
Jurusan Teknik Industri FT Unpas
MENYELESAIKAN PERSOALAN MINIMASI
1.
Min Z = 5 X1 + 14 X2
dengan pembatas
X1 + 2 X2 6
X1 + 4 X2 8
X1 , X2 0
2.
Min Z = 2 X1 - 3 X2
dengan pembatas
X1 + X2 4
X1 - X2 6
X1 , X2 0
Tjutju T. Dimyati
Selesaikan dengan metoda grafis dua contoh soal
berikut:
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Pertanyaan
1. Bagaimanakah solusi dari soal no.1? Apa sebabnya?
2. Mengapa solusi soal no.2 tidak seperti soal no.1?
3. Apa yang terjadi jika salah satu (yang mana saja) dari fungsi pembatas soal no.1 dirubah menjadi bertanda ?
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Pertanyaan
4.Jika kedua fungsi pembatas pada soal no.1 bertanda bagaimanakah daerah fisibelnya? Bagaimana solusinya?
5.Jika kedua fungsi pembatas pada soal no.1 bertanda dan fungsi tujuannya maksimasi, bagaimanakah daerah fisibelnya? Bagaimana solusinya?
6.Apa yang dapat disimpulkan dari eksperimen ini?
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Catatan
• Untuk persoalan minimasi, jika seluruh koefisien fungsi tujuan bertanda positif maka sekurang-kurangnya harus ada satu fungsi pembatas yang bertanda agar solusi dari persoalan tersebut bukan nol.
• Daerah fisibel yang bersifat unbounded pada persoalan minimasi, tidak menimbulkan masalah bagi pencarian solusi optimal.
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Catatan
• Daerah fisibel yang bersifat unbounded pada persoalan maksimasi, menyebabkan solusi optimalnya tidak dapat ditentukan. Karena itu untuk persoalan maksimasi harus ada sekurang-kurangnya satu fungsi pembatas yang bertanda agar tidak terjadi kasus unbounded.