Metode Grafik Program Linear
CCR-314 Riset Operasional
LINEAR PROGRAMMING METODE GRAFIK
Metode Grafik • Setelah membuat formulasi model matematika, langkah selanjutnya dalam penerapan program linear untuk mengambil keputusan adalah menentukan pemecaham dari model. • Karena hubungannya linear, beberapa model pemecahan dapat di ilustrasikan secara grafik. • Metode grafik terbatas untuk model-model yang hanya mempunyai dua variabel, yang dapat digambarkan dalam dua dimensi grafik. CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
2
1
Metode Grafik Program Linear
CCR-314 Riset Operasional
Sistem dan Bidang Kerja Sistem untuk menyatakan hubungan antara aljabar (model matematika) dan geometri (grafik) adalah bidang yang dibagi menjadi empat oleh sumbu tegak (absis) dan sumbu datar (ordinat). Bidang tersebut dikenal sebagai kuadran. CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
3
Langkah-langkah Metode Grafik 1.
2.
3.
Gambarkan model batasan (fungsi kendala) sebagai persamaan pada grafik, kemudian dengan mempertimbangkan ketidaksamaan batasan, tunjukkan daerah memenuhi kendala (DMK). a) Gambarkan fungsi tujuan, lalu geser menjauh dari titik awal (0,0) ke titik solusi yang optimal, atau: b) Selesaikan persamaan-persamaan pada titik tiap sudut untuk memperoleh nilai solusi pada tiap sudut. a) Selesaikan persamaan-persamaan pada titik solusi untuk menemukan nilai solusi yang optimal, atau: b) Masukkan nilai-nilai ke dalam fungsi tujuan untuk menentukan kumpulan nilai yang menghasilkan nilai Z yang optimal.
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
4
2
Metode Grafik Program Linear
CCR-314 Riset Operasional
Menentukan Titik Koordinat • Misal: X1 + 2X2 ≤ 40 • Ubah pertidaksamaan (≤) menjadi persamaan (=), maka: X1 + 2X2 = 40 • Mencari nilai X1 dan X2 dengan mengasumsikan salah satu variabel bernilai 0 (nol).
X2 40 30
– Jika X1 = 0, maka: (0) + 2X2 = 40 2X2 = 40 X2 = 20 – Jika X2 = 0, maka: X1 + 2(0) = 40 X1 = 40
20
X1 + 2X2 = 40
10 0
• Jadi titik koordinatnya adalah: X1 = 40 dan X2 = 20
0
CCR--314 Riset Operasional CCR
10
20
30
40
X1
6623 - Taufiqurrahman
5
Menggambar Daerah Penyelesaian • Persamaan (≤) misal: X1 + 2X2 ≤ 40
• Persamaan (≥) misal: X1 + 2X2 ≥ 40
• Persamaan (=) misal: X1 + 2X2 = 40
X2 40
X2 40
X2 40
30
30
30
20
20
20
10
10
10
0
0 0
10
20
30
40 X1
X1 + 2X2 ≤ 40 CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
0 0
10
20
30 40
X1 + 2X2 ≥ 40 6623 - Taufiqurrahman
X1
0
10
20 30
40
X1
X1 + 2X2 = 40 6
3
Metode Grafik Program Linear
CCR-314 Riset Operasional
Daerah Memenuhi Kendala (DMK) • Persamaan (≤), misal: X1 + 2X2 ≤ 40 4X1 + 3X2 ≤ 120
• Persamaan (≥), misal: X1 + 2X2 ≥ 40 4X1 + 3X2 ≥ 120
• Persamaan (≥ dan =) X1 + 2X2 ≥ 40 X1 = 40 X2 = 40
X2
X2
40
40
30
30
20
20
30
10
20
0
10
10
DMK
0 0
10
20
30
X2 40 DMK
40 X1
0
10
20
30 40 X1
DMK
0 0
CCR--314 Riset Operasional CCR
10
20 30
6623 - Taufiqurrahman
40 X1 7
Contoh #2 – 1 Metode Grafik • Fungsi Tujuan : Maksimalkan Z
40 X1
50X2
• Fungsi Kendala : (1) Tenaga kerja :
X1
+
2X2
≤
40
(2) Tanah liat
:
4X1
+
3X2
≤
120
(3) NonNon-negatif :
X1
;
X2
≥
0
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
8
4
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Grafik Contoh #2 – 1 1. Menggambar fungsi kendala (Langkah 1) X2
X2
40
40
30
30
4X1 + 3X2 ≤ 120
20
C
20
10
X1 + 2X2 ≤ 40
0
10
B
DKM
A
0 0
10
20
30
40
X1
CCR--314 Riset Operasional CCR
0
10
20
30
40
X1
6623 - Taufiqurrahman
9
Solusi Grafik Contoh #2 – 1 2. Menggambar garis fungsi tujuan (Langkah 2.a) X2
X2
40
40 800 = 40X1 + 50X2
30
30
1200 = 40X1 + 50X2 C
20
1600 = 40X1 + 50X2 (Berada di luar DMK)
10
A 0
10
20
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
800 = 40X1 + 50X2 Titik Optimal
10
B
0
C
20
30
B A
0 40
X1
0 6623 - Taufiqurrahman
10
20
30
40
X1 10
5
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Grafik Contoh #2 – 1 3. Menyelesaikan persamaan-persamaan pada titik solusi untuk nilai solusi optimal (Langkah 3.a) X2 40
X1 + 2X2 = 40 X1 = 40 − 2X2
4X1 + 3X2 = 120
30
40 − 2X2 = 30 − (3X2/4) 5X2/4 = 10 X2 = 8 ⇛ X2B
C
20
B
10 X2B 10
20
X1 = 40 − 2X2 X1 = 40 − 2(8) X1 = 24 ⇛ X1B
X1 + 2X2 = 40 A
0 0
4X1 + 3X2 = 120 4X1 = 120 − 3X2 X1 = 30 − (3X2/4)
30
X1
40
X1B CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
11
Solusi Grafik Contoh #2 – 1 2. Menyelesaikan persamaan-persamaan pada titik tiap sudut untuk memperoleh nilai solusi pada tiap sudut. (Langkah 2.b) X2
3. Masukkan nilai-nilai ke dalam fungsi tujuan untuk menentukan kumpulan nilai yang menghasilkan nilai Z yang optimal. (Langkah 3.b)
40 X1 = 0 X2 = 20
30 C
20 8
X1 = 24 X2 = 8
10
X1 = 30 X2 = 0
B A
0 0
10
20
30
40
X1
• • • •
24 CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
Pada titik A → Z = 1000 Pada titik B → Z = 1360 Pada titik C → Z = 1200 Maka solusi optimal adalah pada titik B dengan laba $1360 12
6
Metode Grafik Program Linear
CCR-314 Riset Operasional
Contoh #2 – 2 Metode Grafik Variabel Keputusan
• X1 = jumlah pupuk SG yang dibeli • X2 = jumlah pupuk CQ yang dibeli
• Minimalkan Z = 6X1 + 3X2 • Z = total biaya pemupukan • 6X1 = harga/biaya dari SG • 3X2 = harga/biaya dari CQ
Fungsi Tujuan
• 2X1 + 4X2 ≥ 16 • 4X1 + 3X2 ≥ 24 • X1 ; X2 ≥ 0
Fungsi Kendala CCR--314 Riset Operasional CCR
(kendala nitrogen) (kendala fosfat) (kendala non-negatif)
6623 - Taufiqurrahman
13
Solusi Grafik Contoh #2 – 2 X2
X2
8
8 DKM
6
C
DKM
6
X1 = X1B X2 = X2B
4
4
2
2 X2B
0 0
2
4
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6
X1 = 0 X2 = 8
8
X1
X1 = 8 X2 = 0
B
A
0 0
6623 - Taufiqurrahman
2
4 X1B
6
8
X1 14
7
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Grafik Contoh #2 – 2 • Pada titik B, koordinat X1 dan X2 adalah: 2X1 + 4X2 = 16 4X1 + 3X2 = 24
*2 *1
4X1 + 8X2 = 32 4X1 + 3X2 = 24 5X2 = 8 X2 = 8/5 ≈ 1,6 → X2B
2X1 + 4X2 = 16 2X1 + 4(1,6) = 16 2X1 = 16 − 6,4 X1 = 4,8 → X1B CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
15
Solusi Grafik Contoh #2 – 2 X2 C
8
• Pada titik A → Z = 48
X1 = 0 X2 = 8 DKM
6
2 1,6
X1 = 8 X2 = 0
B
k B → Z = 33,6
• Pada
k C → Z = 24
• Maka solusi optimal terletak pada titik C dengan total biaya $24
X1 = 4,8 X2 = 1,6
4
• Pada
A
0 0
2
4 4,8
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6
8
X1 6623 - Taufiqurrahman
16
8
Metode Grafik Program Linear
CCR-314 Riset Operasional
Latihan #3 – 1 Perusahaan sepatu membuat 2 macam sepatu. Yang pertama merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan 3 macam mesin. Mesin 1 membuat sol karet, mesin 2 membuat sol kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merek I1 mula-mula dikerjakan di mesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2 selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja maksimum setiap hari mesin 1 adalah 8 jam, mesin 2 adalah 15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap laba setiap lusin sepatu merek I1=Rp.30.000 sedang merek I2=Rp.50.000. Masalahnya adalah menentukan berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa memaksimumkan laba. CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
17
Solusi Latihan #3 – 1 (Bentuk Tabel) I1 (x1)
I2 (x2)
Kapasitas Maksimum
1
2
0
8
2
0
3
15
3
6
5
30
3
5
Merek Mesin
Sumbangan laba CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
18
9
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Latihan #3 – 1 (Bentuk Matematis) • Maksimumkan Z = 3x1 + 5x2 • Batasan (constrain) (1) 2X1 8 (2) 3X2 15 (3) 6X1 + 5X2 30
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
19
Solusi Latihan #3 – 1 Fungsi Batasan (1) -> 2 X1 8 x2
Gambar tersebut merupakan bagian yang memenuhi batasanbatasan: 2X1 8 dan X1 0, X2 0
0
X2 0, dan 2X1 8
4
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
X1 0,
2X1 = 8
x1 6623 - Taufiqurrahman
20
10
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Latihan #3 – 1 (Fungsi Batasan/All) 6X1 + 5X2 = 30
x2
6 D 5
2X1 = 8
C
Daerah feasible
B A 4 5
0 CCR--314 Riset Operasional CCR
3X2 = 15
x1
6623 - Taufiqurrahman
21
Solusi Latihan #3 – 1 (Titik Optimal) X2 2X1 = 8
6X1 + 5X2 = 30
Titik C: Titik D: Pada titik ini nilai X2 = 5; X1 = 0 Nilai Z = 3(0) + 5(5) = 25
6 D
5
X1 = 4. Substitusikan batasan (3), maka 6(4) + 5X2 = 30. Jadi nilai X2 = (30 –24)/5 = 6/5. Nilai Z = 3(4) + 5(6/5) =18
3X2 = 15
Titik A: Pada titik ini nilai X1 = 4; X2 = 0 Nilai Z = 3(4) + 0 = 12
B 0
6623 - Taufiqurrahman
C
Daerah feasible
Titik B:
CCR--314 Riset Operasional CCR
X2 = 5. Substitusikan batasan (3), maka 6X1 + 5(5) = 30. Jadi nilai X1 = (30 –25)/6 = 5/6. Nilai Z = 3(5/6) + 5(5) = 27,5
A 4 6623 - Taufiqurrahman
5
X1 22
11
Metode Grafik Program Linear
CCR-314 Riset Operasional
Latihan #3 – 2 Produk yang dihasilkan oleh sebuah perusahaan adalah meja dan kursi. Dengan Bahan mentah dalam satu minggu yang tersedia adalah sebanyak 10 gelondong kayu dan jumlah jam kerja buruh yang tersedia adalah 36 jam kerja. Informasi mengenai penggunaan sumber daya dan hara jual per unit, dijelaskan dalam table dibawah ini :
CCR--314 Riset Operasional CCR
Jenis Produk
6623 - Taufiqurrahman
23
Kebutuhan sumber daya Buruh(jam/unit)
Bahan(kg/unit)
Harga ($/unit)
6 6
1 2
4 5
Meja Kursi
• Dengan melihat kepada informasi diatas, berapakah jumlah Meja dan Kursi yang harus dihasilkan agar keuntungan yang didapat perusahaan maksimum? • Variabel keputusan X1 = Jumlah Meja yang dihasilkan X2 = Jumlah Kursi yang dihasilkan • Fungsi Tujuan Jumlah keuntungan yang di dapat adalah sebesar :
Z
4X 1 5X 2
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
24
12
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Latihan #3 – 2 (Sistem Kendala) a.
Kendala Jam Kerja
6 X b.
6 X
2
36
Kendala Bahan Baku
X c.
1
2X
1
2
10
Jumlah X1, X2 yang harus dihasilkan
X
1
0;
X
2
0
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
25
Solusi Latihan #3 – 2 (Kendala) X2
X1 = 0 X2 = 5
6 5
Titik temu antara Kendala 1 dengan Kendala 2 : 6X 1 6X X 1 2X
C B
4
36 1 6X 1 6X 2 36 10 3 3X 1 6X 2 30 2 2
3X1 = 6 X1 = 2
3 2
X1 = 6 X2 = 0
DMK
1
A
0 0
1
2
CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
3
4
5
6
7
8
9
6623 - Taufiqurrahman
10
X1
X1 + 2X2 = 10 2 + 2X2 = 10 2X2 = 8 X2 = 4
26
13
Metode Grafik Program Linear
CCR-314 Riset Operasional
Solusi Latihan #3 – 2 (Titik Optimal) • Pada titik A → X1 = 6 ; X2 = 0 ; Z = 24 • Pada titik B → X1 = 2 ; X2 = 4 ; Z = 28 • Pada titik C → X1 = 0 ; X2 = 5 ; Z = 25 • Dari hasil diatas dapat disimpulkan bahwa keuntungan yang terbesar didapatkan apabila memproduksi Meja sebanyak 2 unit dan memproduksi Kursi sebanyak 4 unit dengan mendapatkan keuntungan sebesar $28. CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
27
SEKIAN & TERIMA KASIH CCR--314 Riset Operasional CCR
6623 - Taufiqurrahman
6623 - Taufiqurrahman
28
14