Tugas Pertemuan 12 | Logika dan Algoritma (Metode Greendy)

 TUGAS PERTEMUAN 12

Tugas : Logika dan Algoritma (Metode Greedy)


Diketahui bahwa ada 3 barang disimpan di tempat dengan kapasitas maksimal sebesar 25 Kg. Berat masing‐masing barang tersebut adalah:                                            

Barang pertama          : 20 Kg

Barang kedua             : 17 Kg

Barang ketiga              : 12 Kg

Masing-masing barang memiliki profit (keuntungan):

Barang pertama          : 27

Barang kedua             : 26

Barang ketiga              : 17     

Tentukan berapa profit maksimalnya?

Jawab : Diketahui bahwa kapasitas M = 25 Kg Dengan jumlah barang n=3                                   

Berat Wi masing-masing barang (W1, W2, W3) = (20, 17, 12)

Nilai Pi masing-masing barang (P1, P2, P3) = (27, 26, 17)

1. Penyelesaian Secara Matematika

Penyelesaian soal :

Fungsi tujuannya adalah mencari profit nilai maksimal. ∑ PiXi 

Fungsi Pembatas : ∑ Wi Xi <= 25

Dengan nilai-nilai Batasan :

0<=Xi<=1 (batas bawah=0, batas atas=1)

Pi > 0

Wi > 0

 

Penyelesaian Soal :

(W1, W2, W3) = (20, 17, 12)

(P1, P2, P3) = (27, 26, 17)

1. Tentukan solusi yang mungkin: 2n = 6

2. Hitung berat masing-masing : 20X1+17X2+12X3 <= 25

 

1.   Untuk x1=0, x2=1

20.0+17.1+12X3 <= 25

0 + 17 + 12X3 <= 25

12X3 <= 25-17

12X3 <= 8

X3 = 8/12 = 2/3

 

2.   Untuk x1=1, x2=0

20.1+17.0+12X3 <= 25

20 + 0 + 12X3 <= 25

12X3 <= 25-20

12X3 <= 5

X3 = 5/12

 

3.   Untuk x1=0, x3=1

20.0+17X2+12.1 <= 25

0 + 17X2 + 12 <= 25

17X2 <= 25-12

17X2 <= 13

X2 = 13/17

 

4.   Untuk x1=1, x3=0

20.1+17X2+12.0 <= 25

20 + 17X2 + 0 <= 25

17X2 <= 25/20

17X2 <= 5

X2 = 5/17

 

5.   Untuk x2=0, x3=1

20X1+17.0+12.1 <= 25

20X1 + 12 <= 25

20X1 <= 25-12

20X1 <= 13

X1 = 13/20

 

6.   Untuk x2=1, x3=0

20X1+17.1+12.0 <= 25

20X1 + 17 <= 25

20X1 <= 25-17

20X1 <= 8

X1 = 8/20 = 2/5


Tabel kemungkinan solusi :

(W1, W2, W3) = (20, 17, 12)                        

(P1, P2, P3) = (27, 26, 17)

 

Solusi Ke 

X1, X2, X3

Wi Xi

Pi Xi

1

0,1,2/3

25

37,3

2

1,0,5/12

25

34,08

3

0,13/17,1

25

36,88

4

1,5/17,0

25

34,64

5

13/20,0,1

25

34,55

6

2/5,1,0

25

36,8


Contoh Solusi 1 :

Pi Xi     = 27X1 +  26X2 + 17X3

               27(0) + 26(1) + 17(2/3)

               0 + 26 + 11,3 = 37,3

 

Kesimpulan Solusi 1:

Komposisi dari ketiga barang yang dapat termuat dalam ransel dgn profit maksimal 37,3 adalah :                                               

Barang jenis 1 tidak dimuat (X1 = 0)                                        0 Kg

Barang jenis 2 dimuat semua (X2 = 1)                                   17 Kg

Barang jenis 3 dimuat  dua sepertiga (X3 = 2/3)                     8 Kg

Total Max Kapasitas Knapsack adalah                                  25 Kg

 

2. Peyelesaian secara kriteria Greedy

Contoh :                                 

Diketahui bahwa kapasitas M = 25 Kg Dengan jumlah barang n=3                        

Berat Wi masing-masing barang (W1, W2, W3) = (20, 17, 12)

Nilai Pi masing-masing barang (P1, P2, P3) = (27, 26, 17)                                      

1)    Pilih barang dengan Nilai Profit Maksimal :

P1 = 27 → X1 = 1, dimisalkan sebagai atas nilai

P2 = 26 → X2 = 13/17, dihitung dengan Fungsi Pembatas

P3 = 17 → X3 = 0, dimisalkan sebagai batas bawah nilai

 

Rumus fungsi pembatasan :

20.0+17X2+12.1 <= 25

0 + 17X2 + 12 <= 25

17X2 <= 25-12

17X2 <= 13

X2 = 13/17

                                                           

2)    Pilih barang dengan Berat Minimal :

W1 = 20 → X1 = 1, sebagai batas bawah

W2 = 17 → X2 = 5/17,dihitung dgn Fungsi Pembatas

W3 = 12 →X3 = 0, sebagai batas atas

 

Rumus fungsi pembatasan :

20.1+17X2+12.0 <= 25

20 + 17X2 + 0 <= 25

17X2 <= 25/20

17X2 <= 5

X2 = 5/17

           

3)    Pilih barang dengan menghitung perbandingan yang terbesar dari Profit dibagi Berat (Pi/Wi) yang diurut secara tidak naik, yaitu :

P1/W1 = 27/20 = 1,35 → karena terkecil maka X1 = 0

P2/W2 = 26/17 = 1,52 → karena terbesar maka X2 = 1

P3/W3 = 17/12 = 1,41 → dengan Fungsi pembatas X3 = 2/3

 

Rumus fungsi pembatasan :

20.0+17.1+12X3 <= 25

0 + 17 + 12X3 <= 25

12X3 <= 25-17

12X3 <= 8

X3 = 8/12 = 2/3

 

Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy :

(W1, W2, W3) = (20, 17, 12)                                     

(P1, P2, P3) = (27, 26, 17)

 

Solusi ke

X1,X2,X3

WiXi

PiXi

Pi Max

0,13/17,1

25

36,88

Wi Min

1,5/17,0

25

34,64

Pi/Wi Max

0,1,2/3

25

37,3


Nilai profit diambil yg paling besar :

Pi / Wi max     = 27(0) + 26(1) + 17(2/3)

                        = 0 + 26 + 11,33

                        = 37,33

Nilai profit maksimal = 37,3 dengan komposisi yang sama

 

Komentar

Posting Komentar

Postingan populer dari blog ini

TUGAS KELOMPOK PERTEMUAN 1 | MENGANALISIS BASIS DATA APLIKASI AKADEMIK

Gambar
  MENGANALISIS BASIS DATA APLIKASI AKADEMIK     Soal: Buatlah analisis basis data sesuai dengan tema project yang di dapatkan di matakuliah aplikasi  basis data. (kelompok di buat sesuai dengan kelompok aplikasi basis data)   Kami akan menganalisis Aplikasi Basis Data/Database dengan tema Aplikasi Akademik Sederhana,yang di dalamnya terdapat Model Concept Data dan Tabel Relasi, berikut Model Concept Data Aplikasi Akademik Sederhana dan Tabel Relasi Aplikasi Akademik Sederhana: A. Concept Data Model              B. Tabel Relasi Akademik Mahasiswa Dosen Filed Type Filed Type id_mahasiswa Primary Key id_dosen Primary Key nama_mahasiswa   nama_dosen   Jenis_kelamin   no_telp foreign ...
Baca selengkapnya

TUGAS PERTEMUAN 3 | Membuat Contoh Program Operator Penugasan, Logika, Bitwise, Identitas, Keanggotaan Menggunakan Bahasa Pyton

Gambar
 TUGAS PERTEMUAN 3 Membuat Contoh Program Operator Latihan 1 • Buatlah 1 Contoh Operator Penugasan • Buatlah 1 Contoh Operator Logika • Buatlah 1 Contoh Operator Bitwise • Buatlah 1 Contoh Operator Identitas • Buatlah 1 Contoh Operator Keanggotaan Latihan 2 • Buatlah program seperti gambar dibawah ini 1.  Buatlah 1 Contoh Operator Penugasan Program Operator Penugasan (Input) Output Operator Penugasan 2.  Buatlah 1 Contoh Operator Logika Program Operator Logika (Input) Output Operator Logika 3. Buatlah 1 Contoh Operator Bitwise Program Operator Bitwise (Input) Output Operator Bitwise 4.  Buatlah 1 Contoh Operator Identitas Program Operator Identitas (Input) Output Operator Identitas 5. Buatlah 1 Contoh Operator Keanggotaan Program Operator Keanggotaan (Input) Output Operator Keanggotaan Latihan 2 Program Toko Mainan Anak (Input)   Output Toko Mainan Anak 
Baca selengkapnya

TUGAS KELOMPOK PERTEMUAN 4 | Membuat ERD dan LRS informasi Akademik

Gambar
 Sistem Basis Data Pertemuan 4 Membuat ERD dan LRS Informasi Akademik P ada kesempatan kali ini kelompok kami akan membuat Tahapan Pembuatan ERD dan LRS ERD (Entity Relationship Diagram) adalah pemodelan basis data relasional, pemodelan ini banyak digunakan karena cukup mudah untuk menggambarkan basis data yang akan dibuat baik terutama jika dalam skala kecil. ERD terdiri dari notasi atau simbol-simbol seperti pada tabel berikut ini: 1. Tahapan Pembuatan ERD Terdapat 4 tahap pembuatan ERD sebagai berikut: 1      Menentukan entitas 2.     Menentukan atribut (termasuk atribut kunci & multivalue) 3.     Idetifikasi relasi 4.     Menentuknan kardinalitas relasi   1)     Menentukan Entitas Pada kasus ini terdapat Entitas Mahasiswa, Jurusan, Matakuliah, Dosen, Jadwal. Gambar ERD Sementara                ...
Baca selengkapnya