penyelesaian model linear programming · pdf fileprogram studi agribisnis. ... contoh soal 3:...

19
Prof. Dr. Ir. ZULKIFLI ALAMSYAH, M.Sc. PROGRAM STUDI AGRIBISNIS FAKULTAS PERTANIAN UNIVERSITAS JAMBI Maximize or Minimize Z = f (x,y) Subject to: g (x,y) = c PENYELESAIAN MODEL LINEAR PROGRAMMING SECARA GRAFIK B C 2X 1 = 8 4 D A Daerah feasible X 2 X 1 0 3X 2 = 15 5 6X 1 + 5X 2 = 30

Upload: trinhduong

Post on 01-Mar-2018

387 views

Category:

Documents


15 download

TRANSCRIPT

Page 1: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Prof. Dr. Ir. ZULKIFLI ALAMSYAH, M.Sc.

PROGRAM STUDI AGRIBISNISFAKULTAS PERTANIAN UNIVERSITAS JAMBI

Maximize or MinimizeZ = f (x,y)

Subject to:g (x,y) = c

PENYELESAIAN MODEL LINEAR PROGRAMMING SECARA GRAFIK

B

C

2X1 = 8

4

D

A

Daerah feasible

X2

X10

3X2 = 155

6X1 + 5X2 = 30

Page 2: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

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 dengantanda ≥ atau ≤ menjadi tanda = sehinggamemberikan persamaan garis lurus.

2. Gambarkan persamaan dalam bentuk garis tersebutdalam bentuk kurva dalam satu salib sumbu siku-sikuyang sama.

3. Tentukan titik-titik perpotongan kurva dengan sumbuvertikal dan sumbu horizontal, dengan cara sbb:

Untuk menentukan titik potong dengan sumbuvertikal, dimisalkan nilai pada sumbu horizontalsama dengan nol. Demikian juga berlakusebaliknya.

zulkifli_alamsyah 2

Page 3: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Prinsip dan Langkah-langkah

4. Tentukan daerah yang memenuhi persyaratan setiapkendala.

Tanda ≥ pada fungsi kendala menunjukkan daerahkendala dari fungsi tersebut berada mulai dari garishingga 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 (titikekstrim) dengan cara menghitung titik potong 2 gariskendala pada titik tersebut.

6. Hitung nilai fungsi tujuan pada setiap titik ekstrim.

7. Nilai fungsi tujuan terbesar pada titik ekstrim menunjukkansolusi optimal untuk persoalan maksimisasi. Demikiansebaliknya untuk persoalan minimisasi, solusi optimal diperoleh pada titik ekstrim dengan nilai terendah.

zulkifli_alamsyah 3

Page 4: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Prinsip dan Langkah-langkah

Gambarkan setiap fungsi kendala dalam bentuk kurva1. 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 dengannol. Demikian juga berlaku sebaliknya.

2. Tentukan daerah yang memenuhi persyaratan setiapkendala. Tanda ≥ atau ≤.

Tentukan daerah yang memenuhi persyaratan semuakendala (daerah kalayakan berproduksi) dan tentukantitik-titik sudutnya (titik ekstrim).

Cari koordinat pada setiap titik ekstrim dengan caramenentukan titik potong antara dua kurva kendala.

Hitung nilai fungsi tujuan pada setiap titik ekstrim danteteapkan titik yang memberikan nilai fungsi tujuanterbesar (utk maksimisasi) atau terkecil (utk minimisasi)

zulkifli_alamsyah 4

Page 5: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

5Magister Agribisnis UNJA Zulkifli Alamsyah

ProsesWaktu yang dibutuhkan per unit Total jam

tersediaMeja KursiPerakitan 4 2 60Pemolesan 2 4 48Laba/unit 80.000 60.000

Model Linear Programming:Maks.: Laba = 8 M + 6 K (dlm satuan Rp.10. 000)Dengan kendala:

4M + 2K ≤ 60 2M + 4K ≤ 48

M ≥ 0K ≥ 0

Perhatikan kembali persoalan sebagai berikut (Kuliah ke-2):

Page 6: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Penyelesaian secara grafik:

Gambarkan masing-masing fungsi kendala pada salib sumbu yang sama.

34

32

28

24

20

16

12

8

4

4 8 12 16 20 24 28 32 34M

K

4M + 2K ≤ 60

2M + 4K ≤ 48B(12,6)

C(15,0)

A(0,12)

Pada A: M = 0, K = 12Laba = 6 (12) = 72

Laba: Z = 8M + 6K

Pada B: M = 12, K = 6Laba = 8(12) + 6(6) = 132

Pada C: M = 15, K = 0Laba = 8 (15) = 120

O

Feasible Region

M=0 ⇒ K=12K=0 ⇒ M=24

M=0 ⇒ K=30K=0 ⇒ M=15

Keputusan:M = 12 dan K = 6Laba yg diperoleh = 1.320.000

zulkifli_alamsyah 6

Penentuan Solusi Optimal dengan persamaan Fungsi Tujuan.

Page 7: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Penyelesaian secara grafik:

Penentuan Titik Optimal dengan kurva Fungsi Tujuan.

34

32

28

24

20

16

12

8

4

4 8 12 16 20 24 28 32 34M

K

4M + 2K ≤ 60

2M + 4K ≤ 48B(12,6)

C(15,0)

A(0,12)

O

Feasible Region

M=0 ⇒ K=12K=0 ⇒ M=24

M=0 ⇒ K=30K=0 ⇒ M=15

Laba: Z = 8M + 6K

atau

K = Z /6 – 8/6 M

Slope kurva FT = - 8/6 = - 4/3

• Gambarkan kurva FT pada sembarang titikdgn slope -4/3.

• Geser secara paralelkurva FT sampai padatitik ekstrim terluar daridaerah feasibel (titik B)

• Titik yang diperolehadalah kombinasiproduksi yang optimal.

zulkifli_alamsyah 7

Page 8: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Reddy Mikks Co. mempunyai sebuah pabrik kecil yang menghasilkan 2 jenis cat yaitu utk eksterior dan interior. Bahanbaku 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:

Contoh soal 2: Perusahaan Cat.

Bahan bakuKebuthn bahan baku per

ton cat KetersediaanMaksimum (ton)

Eksterior InteriorBahan A 1 2 6Bahan B 2 1 8

Permintaan harian cat interior lebih tinggi dari permintaan cateksterior, tetapi tdk lebih dari 0.5 ton per hr. Sedangkanpermintaan cat interior maksimum 2 ton per hari. Keuntunganper ton cat interior dan eksterior masing-masing Rp 3 juta danRp. 2 juta..Berapa masing-masing cat harus diproduksi oleh perusahaanuntuk memaksimumkan pendapatan kotor?

zulkifli_alamsyah 8

Page 9: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Definisi variabel keputusan: CE = jmlh cat eksterior yg diproduksi (ton/hari)CI = jmlh cat interior yg diproduksi (ton/hari)

Perumusan persoalan kedalam model LP

Perumusan fungsi tujuan: Maks.: Pdpt kotor, Z = 2 CE + 3 CI (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_alamsyah9

Page 10: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

8

7

6

5

4

3

2

1

1 2 3 4 5 7 8 CE

CI

2CE + CI ≤ 8

CE + 2CI ≤ 6

Pada A:Z = 2(0) + 3(0.5) = 1.5

Pendapatan kotor:Z = 2 CE + 3 CI

O

Keputusan:CE = 3.33 dan CI = 1.87Pendapatan kotor:

Z = 12.17 juta.

CI - CE ≤ 0.5

CI ≤ 2

A (0, 0.5) D (3.33, 1.84)B (1.5, 2) E (4, 0)C (2, 2)

Pada B:Z = 2(1.5) + 3(2) = 9

Pada C:Z = 2(2) + 3(2)= 10

Penyelesaian secara grafik:

zulkifli_alamsyah 10

D

E

Pada D:Z = 2(3.33)+3(1.84)= 12.17

Pada E:Z = 2(4) = 8

B

A

C

Feasible Region

Page 11: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Seorang petani berusaha memanfaatkan lahan pertanian yangdimilikinya seluas 3 hektar secara swadaya. Ada 3 kemungkinankomoditi yang dapat diusahakan pada lahan tersebut, yaitu karet,kelapa sawit dan kakao. Pada saat ini modal yg tersedia pada petanisebanyak Rp. 10 juta dan jam kerja yg tersedia dlm keluarga sebanyak60 jam per minggu.

Kebutuhan sumberdaya dan keuntungan untuk setiap hektar komoditiadalah sbb:

Rumuskanlah persoalan tersebut kedalam model Linear Programming?

Uraian Karet Kelapa Sawit KakaoModal Rp 4 juta Rp 5 juta Rp 8 jutaJam Kerja/Mg 20 jam 24 jam 30 jamKeuntungan/ha Rp 6 juta Rp 8 juta Rp 10 juta

Latihan 2: Perumusan model

zulkifli_alamsyah 11

Page 12: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Carilah solusi dari persoalan berikut menggunakan grafik.

Latihan 3: Penyelesaian soal secara grafik

MAX 12 X1 + 15 X2ST.

3 X1 + 5 X2 ≤ 43X1 + X2 ≤ 12X1 ≥ 3

X2 ≥ 5X1, X2 ≥ 0

MAX 20 X1 + 25 X2 (dalam satuan Rp. juta)ST.

4 X1 + 5 X2 ≤ 403 X1 + 4 X2 ≤ 31

X1 + X2 ≤ 10X2 ≤ 5

X1, X2 ≥ 0

[a]

[b]

zulkifli_alamsyah 12

Page 13: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Carilah solusi dari persoalan berikut menggunakan grafik.

Latihan 4: Penyelesaian soal secara grafik

[a]

[b] Max. 3X1 + 4X2Subject to

2X1 + X2 ≤ 600X1 + X2 ≤ 2255X1 + 4X2 ≤ 1000X1 + 2X2 ≥ 150X1 , X2 ≥ 0

Max. 30X1 + 25X2Subject to

2X1 + X2 ≤ 40X1 + 3X2 ≤ 45X1 ≤ 12X1 , X2 ≥0

zulkifli_alamsyah 13

Page 14: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Beberapa konsep penting dalam penyelesaianpersoalan 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 tanpabatas dan tdk melanggar funggsi kendala.

Redundancy: Redundancy terjadi karena adanya kendala yg tdkmempengaruhi daerah kelayakan.

Alternative optima:Solusi yang tdk memberikan nilai yang unik, terjadi bilagaris fungsi tujuan berimpit dgn garis salah satu kendala.

zulkifli_alamsyah 14

Page 15: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Persoalan Minimisasi:

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)

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)

Contoh soal 3: Industri Meubel

zulkifli_alamsyah 15

Page 16: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

34

32

28

24

20

16

12

8

4

4 8 12 16 20 24 28 32 34M

K

4M + 2K ≤ 60

2M + 4K ≤ 48

A

O

M=0 ⇒ K=12K=0 ⇒ M=24

M=0 ⇒ K=30K=0 ⇒ M=15

K ≥ 4

M ≥ 2

B C

D

Feasible Region

Titik A ditentukan olehperpotongan garis kendala:

2M + 4K = 48dan M = 2

2(2) + 4K = 48K = (48-4)/4 = 11

Titik A (2;11)

Titik B (2;4)

Titik C ditentukan olehperpotongan garis kendala:

4M + 2K = 60dan K = 4

4M + 2(4) = 60M = (60-8)/4 = 13

Titik C (13;4)

Titik D (12,6) Biaya = 20M + 8KPada 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) = 292Pada titik D (12;6) = 20 (12) + 8 (6) = 288

zulkifli_alamsyah 16

Page 17: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Suatu perusahaan makanan kucing menghasilkan produk Tuna-n-Stuff. Pada kemasan kaleng ditulis: Setiap ons Tuna-n-Stuff mengandungkandungan gizi yang lebih besar dari standar minimum (RDA).

Contoh soal 4: Campuran Ransum

Tuna-n-Stuff terbuat dari ramuan sbb:

Bahan% RDA per Ons Biaya

($/Ons)Protein Thiamine Niacin Calsium IronAlbacore 20 0 0 6 5 0.15Bonito 12 0 0 5 3 0.10Suplemen C 0 42 18 22 7 0.20Suplemen D 0 36 40 8 9 0.12Filler 0 0 0 0 0 0.02Standar RDA 2,6 13,7 14,3 5,7 5,7

Menurut peraturan pemerintah, kandungan albacore atau bonito ataucampuran keduanya paling kurang 40%. Bagaimana perusahaanmenentukan ransum secara optimal agar diperoleh biaya minimum?

zulkifli_alamsyah 18

Page 18: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Perumusan Model:

Fungsi Tujuan:

Fungsi Kendala:

A = Ons albacore per ons produkB = Ons bonito per ons produkC = Ons suolemen C per ons produkD = Ons suplemen D per ons produkE = Ons filler per ons produk

Minimum Biaya = 0.15 A + 0.10 B + 0.20 C + 0.12 D + 0.02 E

(target protein) 20 A + 12 B ≥ 2,6 (target thiamine) 42 C + 36 D ≥ 13.7

(target niacin) 18 C + 40 D ≥ 14.3 (target calcium) 6A + 5 B + 22 C + 8 D ≥ 5.7 (target iron) 5 A + 3 B + 7 C + 9 D ≥ 5.7(peraturan pemerintah) A + B ≥ 0.4 (alokasi per ons) A + B + C + D + E ≥ 1 (kendala non-negatif) A, B, C, D, E ≥ 0

zulkifli_alamsyah 19

Page 19: PENYELESAIAN MODEL LINEAR PROGRAMMING · PDF filePROGRAM STUDI AGRIBISNIS. ... Contoh soal 3: Industri Meubel ... rumuskanlah persoalan diatas kedalam bentuk model linear programming

Latihan 6: Komposisi Makanan Ringan

Suatu perusahaan memproduksi makanan ringan yang dibuat dari duabahan pokok, yaitu X dan Y. Harga X per kg adalah Rp. 8.000.- danharga per kg Y adalah Rp. 10.000.

Setiap kg bahan pokok mengandung nutrisi sebagai berikut:

Bahan Pokok Nutrisi A Nutrisi B Nutrisi C Nutrisi DXY

32

08

34

50

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