Релаксация линейного программирования

Математическая модель

Нижние оценки

Переменные задачи

при ограничениях

y_j, x_ij Î{0,1} i, j = 1,…, n.

Заменим условие Булевости переменных на условия:

0 £ y_j £ 1, j = 1,…, n

0 £ x_ij £ 1, i, j = 1,…, n.

Тогда одно из оптимальных решений имеет вид

,

что дает нижнюю оценку

(предметы можно резать произвольным образом).

Оценки Martello & Toth

Для примера L = {1,…, n }, 0 £ w_i < 1 и произвольного 0 £ a £ ½ положим

L ₁ = { i Î L | w_i > 1 – a } — крупные предметы

L ₂ = { i Î L | 1– a ³ w_i > ½ } — средние предметы

L ₃ = { i Î L | ½ ³ w_i ³ a } — мелкие предметы

Теорема. Для любого 0 £ a £ ½ величина

.

является нижней оценкой для OPT (L).
Доказательство. Каждый предмет из множества L ₁ È L ₂ требует отдельный контейнер. Поэтому в любом допустимом решении не менее | L ₁ | + | L ₂ | контейнеров. Предметы из множества L ₃ не лежат вместе с предметами из L ₁. Значит, они лежат либо вместе с предметами из L ₂ , либо в отдельных контейнерах. В контейнерах для L ₂ осталось свободного места. Следовательно, для предметов из множества L ₃ требуется как минимум отдельных контейнеров.

Теорема. Для любого 0 £ a £ ½ величина

является нижней оценкой для OPT (L).

Доказательство. Заменим вес каждого предмета из множества L ₃на a. Тогда в один контейнер войдет предметов, и для множества L ₃потребовалось бы дополнительных контейнеров. Но часть предметов из L ₃ можно уложить в контейнеры для L ₂. Каждый из них имеет 1– w_i, i Î L ₂ свободного места, где поместится предметов из L ₃.

Следствие 1. Величина

является нижней оценкой для OPT (L).

Следствие 2. .

Доказательство. При a = 0 получаем H ³ H ₁(0) = max{| L ₂|, H ₀}³ H ₀.

Следствие 3. Пусть V — множество всех различных значений w_i £ 0,5.

Тогда

т. е. после сортировки предметов получаем

Дополнительная литература

1. E.G. Coffman, M.R. Garey, D.S. Johnson. Approximation algorithms for bin packing: A survey. https://www.math.nsc.ru/LBRT/k5/bp-chapter.pdf

2. Э.Х. Гимади. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд–ние. 1988. с. 89–115.

3. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. с. 154–191.