Puspita, Ika and Sigit, Nugroho and Yulian, Fauzi (2009) SOLUTION OF KNAPSACK CONSTRAINED MAXIMUM SPANNING TREEE PROBLEM USING KRUSKAL ALGORITHM. Undergraduated thesis, Fakultas Matematika Dan Ilmu Pengetahuan Alam UNIB.
![[img]](http://repository.unib.ac.id/style/images/fileicons/text.png) |
Text
SKRIPSI IKA PUSPITA_F1A005028.pdf - Bibliography Restricted to Registered users only Available under License Creative Commons GNU GPL (Software). Download (3MB) |
Abstract
Knapsack Constrained Maximum Spanning Tree (KCMST) problem is optimization problem combining problem of Knapsack and maximum spanning tree. This problem of KCMST is used for maximizing profit with respect to limited price (cost). This research objective is to model a graph problem into KCMST using Lagrange Multiplier approach and finding its optimal solution using Bisection method and Kruskal algorithm. The graph case in which KCMST is modelled and solved is a graph with 10 vertices and 17 edges and Kanpsack capacity 400. So far this study has resulted in maximum profit of 518 and minimum cost of 381. The solution has been obtained through 12 iteration with error of 0.005. The other case using 20 vertices and 46 edges with capacity of Knapsack 600 has given a maximum profit of 1221 with price of 540 through 12 iteration with error 0.005.
| Item Type: | Thesis (Undergraduated) |
|---|---|
| Subjects: | Q Science > Q Science (General) |
| Divisions: | Faculty of Education > Department of Mathematics Education |
| Depositing User: | 014 Abd. Rachman Rangkuti |
| Date Deposited: | 05 Dec 2013 08:29 |
| Last Modified: | 05 Dec 2013 08:29 |
| URI: | http://repository.unib.ac.id/id/eprint/3331 |
Actions (login required)
 |
View Item |