2X1 = 8
Maximize or Minimize
X2
Z = f (x,y) Subject to: C
5
g (x,y) 3X = =c15 2
D Daerah feasible
0
B A
X1
4 6X1 + 5X2 = 30
PENYELESAIAN MODEL LINEAR PROGRAMMING SECARA GRAFIK Prof. Dr. Ir. ZULKIFLI ALAMSYAH, M.Sc. PROGRAM STUDI AGRIBISNIS
FAKULTAS PERTANIAN UNIVERSITAS JAMBI
Prinsip dan Langkah-langkah Hanya dilakukan untuk model yang hanya terdiri dari 2 (dua) variabel keputusan. Gambarkan setiap fungsi kendala dalam bentuk kurva 1. Untuk kemudahan, ubah semua fungsi kendala dengan tanda ≥ atau ≤ menjadi tanda = sehingga memberikan persamaan garis lurus. 2. Gambarkan persamaan dalam bentuk garis tersebut dalam bentuk kurva dalam satu salib sumbu siku-siku yang sama. 3. Tentukan titik-titik perpotongan kurva dengan sumbu vertikal dan sumbu horizontal, dengan cara sbb: Untuk menentukan titik potong dengan sumbu vertikal, dimisalkan nilai pada sumbu horizontal sama dengan nol. Demikian juga berlaku sebaliknya. zulkifli_alamsyah
2
Prinsip dan Langkah-langkah 4. Tentukan daerah yang memenuhi persyaratan setiap kendala.
Tanda ≥ pada fungsi kendala menunjukkan daerah kendala dari fungsi tersebut berada mulai dari garis hingga daerah yang berada disebelah kanan garis.
Berlaku sebaliknya untuk tanda ≤ pada fungsi kendala
Tentukan daerah yang memenuhi persyaratan semua kendala (daerah kalayakan berproduksi; feasible region)
5. Tentukan koordinat titik-titik sudut daerah kelayakan (titik ekstrim) dengan cara menghitung titik potong 2 garis kendala pada titik tersebut.
6. Hitung nilai fungsi tujuan pada setiap titik ekstrim. 7. Nilai fungsi tujuan terbesar pada titik ekstrim menunjukkan solusi optimal untuk persoalan maksimisasi. Demikian sebaliknya untuk persoalan minimisasi, solusi optimal diperoleh pada titik ekstrim dengan nilai terendah. zulkifli_alamsyah
3
Prinsip dan Langkah-langkah Gambarkan setiap fungsi kendala dalam bentuk kurva 1. Tentukan titik-titik perpotongan kurva dengan sumbu vertikal dan sumbu horizontal, dengan cara sbb: Untuk menentukan titik potong dengan sumbu vertikal, dimisalkan nilai pada sumbu horizontal sama dengan nol. Demikian juga berlaku sebaliknya. 2. Tentukan daerah yang memenuhi persyaratan setiap kendala. Tanda ≥ atau ≤. Tentukan daerah yang memenuhi persyaratan semua kendala (daerah kalayakan berproduksi) dan tentukan titik-titik sudutnya (titik ekstrim). Cari koordinat pada setiap titik ekstrim dengan cara menentukan titik potong antara dua kurva kendala. Hitung nilai fungsi tujuan pada setiap titik ekstrim dan teteapkan titik yang memberikan nilai fungsi tujuan terbesar (utk maksimisasi) atau terkecil (utk minimisasi) zulkifli_alamsyah
4
Perhatikan kembali persoalan sebagai berikut Proses Perakitan Pemolesan Laba/unit
Waktu yang dibutuhkan per unit Meja Kursi 4 2 2 4 80.000 60.000
(Kuliah ke-2): Total jam tersedia 60 48
Model Linear Programming: Maks.: Laba = 8 M + 6 K 000) Dengan kendala: 4M + 2K ≤ 60 2M + 4K ≤ 48 M ≥ 0 K ≥ 0 5 Magister Agribisnis UNJA
(dlm satuan Rp.10.
Zulkifli Alamsyah
Penyelesaian secara grafik: Penentuan Solusi Optimal dengan persamaan Fungsi Tujuan. Gambarkan masing-masing fungsi kendala pada salib sumbu yang sama.
K Laba: Z = 8M + 6K
34
Pada A: M = 0, K = 12 Laba = 6 (12) = 72
32 28
4M + 2K ≤ 60
Pada B: M = 12, K = 6 Laba = 8(12) + 6(6) = 132
M=0 ⇒ K=30 K=0 ⇒ M=15
24 20 16 12
Pada C: M = 15, K = 0 Laba = 8 (15) = 120
Feasible Region
A(0,12)
8
Keputusan: M = 12 dan K = 6 Laba yg diperoleh = 1.320.000
M=0 ⇒ K=12 K=0 ⇒ M=24
B(12,6)
2M + 4K ≤ 48
4
C(15,0)
O
4
zulkifli_alamsyah
8
12
16
20
M 24
28
32 6
34
Penyelesaian secara grafik: Penentuan Titik Optimal dengan kurva Fungsi Tujuan. Laba: Z = 8M + 6K
K
atau 34
K = Z /6 – 8/6 M Slope kurva FT = - 8/6 = - 4/3
32 28
4M + 2K ≤ 60
• Gambarkan kurva FT pada sembarang titik dgn slope -4/3.
M=0 ⇒ K=30 K=0 ⇒ M=15
24 20 16 12
• Geser secara paralel kurva FT sampai pada titik ekstrim terluar dari daerah feasibel (titik B)
Feasible Region
A(0,12)
8
M=0 ⇒ K=12 K=0 ⇒ M=24
B(12,6)
• Titik yang diperoleh adalah kombinasi produksi yang optimal.
2M + 4K ≤ 48
4
C(15,0)
O
4
zulkifli_alamsyah
8
12
16
20
M 24
28 7
32
34
Contoh soal 2: Perusahaan Cat. Reddy Mikks Co. mempunyai sebuah pabrik kecil yang menghasilkan 2 jenis cat yaitu utk eksterior dan interior. Bahan baku utk cat tsb adalah bahan A dan bahan B, yg masing2 tersedia maksimum 6 ton dan 8 ton per hari. Kebutuhan masing2 jenis cat per ton thdp bahan baku disajikan pd tabel berikut: Bahan baku Bahan A Bahan B
Kebuthn bahan baku per ton cat Eksterior 1 2
Interior 2 1
Ketersediaan Maksimum (ton) 6 8
Permintaan harian cat interior lebih tinggi dari permintaan cat eksterior, tetapi tdk lebih dari 0.5 ton per hr. Sedangkan permintaan cat interior maksimum 2 ton per hari. Keuntungan per ton cat interior dan eksterior masing-masing Rp 3 juta dan Rp. 2 juta.. Berapa masing-masing cat harus diproduksi oleh perusahaan untuk memaksimumkan pendapatan kotor?
zulkifli_alamsyah
8
Perumusan persoalan kedalam model LP Definisi variabel keputusan: CE = jmlh cat eksterior yg diproduksi CI = jmlh cat interior yg diproduksi Perumusan fungsi tujuan: Maks.: Pdpt kotor, Z = 2 CE + 3 CI
(ton/hari) (ton/hari)
(dlm ribuan)
Perumusan Fungsi Kendala: Kendala ketersediaan bahan baku A: CE + 2 CI ≤ 6 Kendala ketersediaan bahan baku B: 2 CE + CI ≤ 8 Kendala Permintaan : CI - CE ≤ 0.5 : jml maks Kelebihan CI thdp CE CI ≤ 2 : permintaan maks CI Kendala non-negatif: CI ≥ 0; CE ≥ 0. zulkifli_alamsyah
9
Penyelesaian secara grafik: A (0, 0.5) B (1.5, 2) C (2, 2)
D (3.33, 1.84) E (4, 0)
Pada A: Z = 2(0) + 3(0.5) = 1.5
CI
Pada B: Z = 2(1.5) + 3(2) = 9
8
2CE + CI ≤ 8
7
Pada C: Z = 2(2) + 3(2)= 10
CI - CE ≤ 0.5
6
Pendapatan kotor: Z = 2 CE + 3 CI
Pada D: Z = 2(3.33)+3(1.84)= 12.17
5 4
Pada E: Z = 2(4) = 8
Feasible Region
3
CI ≤ 2
2
B
C D
CE + 2CI ≤ 6
1 A
O
1
zulkifli_alamsyah
2
3
E
4
5
7
8
10
Keputusan: CE = 3.33 dan CI = 1.87 Pendapatan kotor: Z = 12.17 juta. CE
Latihan 2: Perumusan model Seorang petani berusaha memanfaatkan lahan pertanian yang dimilikinya seluas 3 hektar secara swadaya. Ada 3 kemungkinan komoditi yang dapat diusahakan pada lahan tersebut, yaitu karet, kelapa sawit dan kakao. Pada saat ini modal yg tersedia pada petani sebanyak Rp. 10 juta dan jam kerja yg tersedia dlm keluarga sebanyak 60 jam per minggu. Kebutuhan sumberdaya dan keuntungan untuk setiap hektar komoditi adalah sbb:
Uraian
Karet
Kelapa Sawit
Kakao
Modal
Rp 4 juta
Rp 5 juta
Rp 8 juta
20 jam
24 jam
30 jam
Rp 6 juta
Rp 8 juta
Rp 10 juta
Jam Kerja/Mg Keuntungan/ha
Rumuskanlah persoalan tersebut kedalam model Linear Programming? zulkifli_alamsyah
11
Latihan 3: Penyelesaian soal secara grafik Carilah solusi dari persoalan berikut menggunakan grafik.
zulkifli_alamsyah
[a]
MAX 20 X1 + 25 X2 (dalam satuan Rp. juta) ST. 4 X1 + 5 X2 ≤ 40 3 X1 + 4 X2 ≤ 31 X1 + X2 ≤ 10 X2 ≤ 5 X1, X2 ≥ 0
[b]
MAX 12 X1 + 15 X2 ST. 3 X1 + 5 X2 ≤ 43 X1 + X2 ≤ 12 X1 ≥ 3 X2 ≥ 5 X1, X2 ≥ 0 12
Latihan 4: Penyelesaian soal secara grafik Carilah solusi dari persoalan berikut menggunakan grafik.
zulkifli_alamsyah
[a]
Max. 30X1 + 25X2 Subject to 2X1 + X2 ≤ 40 X1 + 3X2 ≤ 45 X1 ≤ 12 X1 , X2 ≥0
[b]
Max. 3X1 + 4X2 Subject to 2X1 + X2 ≤ 600 X1 + X2 ≤ 225 5X1 + 4X2 ≤ 1000 X1 + 2X2 ≥ 150 X1 , X2 ≥0 13
Beberapa konsep penting dalam penyelesaian persoalan Linear Programming secara Grafik Extreem points:
Titik-titik sudut daerah kelayakan (feasbile region) Infeasible Solution:
Tidak ada solusi karena tdk semua kendala terpenuhi. Unbounded Solution:
Solusi yang disbebabkan karena fungsi tujuan dibuat tanpa batas dan tdk melanggar funggsi kendala. Redundancy:
Redundancy terjadi karena adanya kendala yg tdk mempengaruhi daerah kelayakan. Alternative optima:
Solusi yang tdk memberikan nilai yang unik, terjadi bila garis fungsi tujuan berimpit dgn garis salah satu kendala. zulkifli_alamsyah
14
Persoalan Minimisasi: Contoh soal 3: Industri Meubel Bila pada contoh sebelumnya, biaya produksi setiap unit meja dan kursi masing-masing Rp.200.000 dan Rp. 80.000, dan perusahaan bertujuan utk meminimumkan biaya produksi, maka persoalan yang dihadapi adalah persoalan MINIMISASI. Dengan biaya minimum untuk menghasilkan output tertentu. Diperlukan batasan mengenai target yang akan dicapai Secara umum tanda ketidak-samaan adalah “≥” (harus ada)
Min.: Biaya = 20 M + 8 K (dlm satuan Rp.10. 000) Dengan kendala: 4M + 2K ≤ 60 (kendala sumberdaya) 2M + 4K ≤ 48 (kendala sumberdaya) M ≥ 2 (kendala target) K ≥ 4 (kendala target) zulkifli_alamsyah
15
K 34
Titik A ditentukan oleh perpotongan garis kendala: 2M + 4K = 48 dan M=2
M≥2
32 28
⇒
4M + 2K ≤ 60
K = (48-4)/4 = 11
M=0 ⇒ K=30 K=0 ⇒ M=15
24
Titik A (2;11)
20
Titik B (2;4) Feasible Region
16 12
A
8 4
O
2(2) + 4K = 48
D B 4
Titik C ditentukan oleh perpotongan garis kendala: 4M + 2K = 60 dan K=4
M=0 ⇒ K=12 K=0 ⇒ M=24
2M + 4K ≤ 48
C 8
12
⇒
K≥4
M = (60-8)/4 = 13
M 16
20
24
28
Biaya = 20M + 8K
32
34
Titik C (13;4) Titik D (12,6)
Pada titik A (2;11) = 20 (2) + 8 (11) = 128 Pada titik B (2;4) = 20 (2) + 8 (4) = 72 (minimum) Pada titik C (13;4) = 20 (13) + 8 (4) = 292 Pada titik D (12;6) = 20 (12) + 8 (6) = 288 zulkifli_alamsyah
4M + 2(4) = 60
16
Contoh soal 4: Campuran Ransum Suatu perusahaan makanan kucing menghasilkan produk Tuna-n-Stuff. Pada kemasan kaleng ditulis: Setiap ons Tuna-n-Stuff mengandung kandungan gizi yang lebih besar dari standar minimum (RDA).
Tuna-n-Stuff terbuat dari ramuan sbb: Bahan
% RDA per Ons
Biaya ($/Ons)
Protein
Thiamine
Niacin
Calsium
Iron
Albacore
20
0
0
6
5
0.15
Bonito
12
0
0
5
3
0.10
Suplemen C
0
42
18
22
7
0.20
Suplemen D
0
36
40
8
9
0.12
Filler
0
0
0
0
0
0.02
2,6
13,7
14,3
5,7
5,7
Standar RDA
Menurut peraturan pemerintah, kandungan albacore atau bonito atau campuran keduanya paling kurang 40%. Bagaimana perusahaan menentukan ransum secara optimal agar diperoleh biaya minimum? zulkifli_alamsyah
18
Perumusan Model: A = Ons albacore per ons produk B = Ons bonito per ons produk C = Ons suolemen C per ons produk D = Ons suplemen D per ons produk E = Ons filler per ons produk Fungsi Tujuan: Minimum
Biaya = 0.15 A + 0.10 B + 0.20 C + 0.12 D + 0.02 E
Fungsi Kendala: (target protein) 20 A + 12 B (target thiamine) 42 C + 36 D (target niacin) 18 C + 40 D (target calcium) 6A + 5 B + 22 C + 8 D (target iron) 5A+3B + 7C+ 9D (peraturan pemerintah) A+ B (alokasi per ons) A+ B+ C+ D +E
A, B, C, D, E ≥ 0
(kendala non-negatif) zulkifli_alamsyah
≥ 2,6 ≥ 13.7 ≥ 14.3 ≥ 5.7 ≥ 5.7 ≥ 0.4 ≥ 1
19
Latihan 6: Komposisi Makanan Ringan Suatu perusahaan memproduksi makanan ringan yang dibuat dari dua bahan pokok, yaitu X dan Y. Harga X per kg adalah Rp. 8.000.- dan harga per kg Y adalah Rp. 10.000. Setiap kg bahan pokok mengandung nutrisi sebagai berikut: Bahan Pokok
Nutrisi A
Nutrisi B
Nutrisi C
Nutrisi D
X
3
0
3
5
Y
2
8
4
0
Setiap kg makanan ringan tersebut harus mengandung paling tidak 18 unit nutrisi A, 12 unit nutrisi B, 24 unit nutrisi C, dan 10 unit nutrisi D. Pertanyaan: Dengan tujuan meminimalkan biaya produksi, (a) rumuskanlah persoalan diatas kedalam bentuk model linear programming (b) Hitunglah jumlah bahan pokok X dan Y yang harus dibeli untuk memproduksi 100 kg makanan ringan, dan Berapa biaya total? zulkifli_alamsyah
20
