линейное программирование ослаблено для МКП - PullRequest
Новая
       11

линейное программирование ослаблено для МКП

0 голосов
/ 27 июня 2010

как рассчитать, чтобы найти это расслабление.Что я должен знать, чтобы найти это.Предположим, у меня есть n предметов и рюкзак.Так что я хотел узнать количество м релаксации.Кто-нибудь может дать мне хоть какую-то идею?Я искал это какое-то время.В интернете есть статья, но не очень понятная.Пожалуйста, по крайней мере, кто-то скажет мне, что вы должны прочитать это, вы должны знать это, и я буду очень благодарен

Спасибо

1 Ответ

1 голос
/ 23 июня 2011

Я думаю, что ваш реальный вопрос - «каково точное определение линейно-расслабленной задачи о ранце?», Поэтому я собираюсь ответить, если это так.

Краткий ответ таков: a линейно-ослабленный KP является дробной версией 0-1 KP [1] .

Математически, все, что вам нужно сделать, - это преобразовать ограничение «x_i принадлежит набору {0, 1}» и преобразовать его в «x_i должно быть любым действительным числом от 0 до 1», где x_i - это количество i-й предмет в вашем рюкзаке с решением.

Название происходит от того факта, что 0-1 KP является проблемой целочисленного программирования. «Линейный» термин означает, что переменные решения могут принимать непрерывные значения.

Хотя не все релаксации линейны. Вы можете проверить эту страницу Википедии для них.

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

...