programmation linéaire détendue pour MKP

Question

comment calculer pour trouver cette relaxation. Que devrais-je savoir pour le trouver. Supposons que j'ai n objets et m sac à dos. Donc je voulais connaître le nombre de m relaxation. Quelqu'un peut-il me donner une idée au moins? Je l'ai cherché pendant tout ce temps. Il y a un article sur internet mais pas très clair. S'il vous plaît au moins quelqu'un me dire que vous devriez lire cette chose, vous devez savoir cette chose ei je vais donc très apprécier

Merci

Answer 1

Je pense que votre vraie question est « quelle est la définition exacte d'un Linear Problème de sac à dos détendu? ", Donc je vais répondre en supposant que c'est.

La réponse courte est que une linéaire détendue KP est la version d'un 0-1 fractionnaire KP [1]. Mathématiquement, tout ce que vous avez à faire est de convertir la restriction "x_i appartient à l'ensemble {0, 1}" et de le convertir en "x_i doit être un nombre réel entre 0 et 1", où x_i est la quantité du i-ème article dans votre sac à dos de solution.

Le nom vient du fait que le 0-1 KP est un problème de programmation d'entiers. Le terme «linéaire» signifie que les variables de la solution peuvent prendre des valeurs continues.

Cependant, toutes les relaxations ne sont pas linéaires. Vous voudrez peut-être vérifier this page Wikipedia pour eux.

[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation