• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Thèse de Doctorat
DOI
10.11606/T.55.2004.tde-07072015-155114
Document
Auteur
Nom complet
Fabiano do Prado Marques
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2004
Directeur
Jury
Arenales, Marcos Nereu (Président)
Ferreira, Carlos Eduardo
Morabito Neto, Reinaldo
Souza, Cid Carvalho de
Yanasse, Horacio Hideki
Titre en portugais
O problema da mochila compartimentada e aplicações
Mots-clés en portugais
Não disponível
Resumé en portugais
Este trabalho aborda o Problema da Mochila Compartimentada que é uma variação do clássico problema da mochila e pode ser enunciado considerando-se a seguinte situação hipotética: um alpinista deve carregar sua mochila com possíveis itens de seu interesse. A cada item atribui-se o seu peso e um valor de utilidade (até aqui, o problema coincide com o clássico Problema da Mochila). Entretanto, os itens são de agrupamentos distintos (alimentos, medicamentos, utensílios, etc.) e devem estar em compartimentos separados na mochila. Os compartimentos da mochila são flexíveis e têm capacidades limitadas. A inclusão de um compartimento tem um custo fixo que depende do agrupamento com que foi preenchido, além de introduzir uma perda da capacidade da mochila. O problema consiste em determinar as capacidades adequadas de cada compartimento e como esses devem ser carregados, maximizando o valor de utilidade total, descontado o custo de incluir compartimentos. Neste trabalho propomos um modelo de otimização não linear inteiro para o problema e algumas heurísticas para sua resolução, para as quais apresentamos os resultados computacionais obtidos. Uma aplicação prática que surge no corte de bobinas de aço, sujeito à laminação é detalhada.
Titre en anglais
The compartimentalised knapsack problem and applications
Mots-clés en anglais
Npt available
Resumé en anglais
This work approaches the Compartmentalized Knapsack Problem which is a variation of the classical knapsack problem and it can be stated as the following hypothetical situation: a climber must load his/her knapsack with a number of items. Two numbers, an weight and a utility value are given for each item (so far, the problem coincides with the classical integer Knapsack Problem). However, the items are of different classes (food, medicine, utensils, etc.) and they have to be packed in separate compartments inside the knapsack. The compartments are flexible and have limited capacities. Each compartment has a fixed cost that depends on the class of items chosen to load it and, in addition, each new compartment introduces a loss of capacity of the knapsack. The Compartmentalized Knapsack Problem consists of determining suitable capacities of each compartment and how these compartments should be packed. The objective is to maximize a total utility value paid off the cost of the compartments. The problem can be modeled as an integer non-linear optimization problem and we have designed some heuristic methods for its solution, for which we present a computational study. A practical application arises in cutting steel rolls subject to a lamination process.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2015-07-07
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.