Saturday, July 24, 2010

Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума 2

Пока искал информацию о свойстве реставрации упаковки, нашел следующую очень интересную работу:

(1) Залюбовский В.В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Труды XIII Байкальской школы-семинара. Иркутск. Том 1. 2005. С. 461-468.

В этой работе на странице 462 ставится вопрос, вынесенный в заголовок этого поста:

"4. Наилучший элемент в пространстве решений соответствует оптимальному решению
исходной задачи."

и на него дается ответ на стр. 463 в духе [1]:

"Лемма 2. Для любой допустимой упаковки $\mathcal{P}$ множества предметов $L$ существует $NF$-активная упаковка $\mathcal{P}'$ такая что
\[|\mathcal{P}'|\leq |\mathcal{P}|."\]

Приведем основные понятия в порядке их упоминания в работе (1) с авторскими комментариями.
  1. Понятие NF-активной упаковки. Собственно говоря, именно для алгоритма Next Fit и доказывается о принадлежности оптимума множеству кодов.
  2. Понятие регулярной перестановки и упаковки. Для регулярной упаковки доказывается лемма, аналогичная Лемме 2.
  3. Понятие максимальной упаковки. Для этой упаковки лемма, аналогична Лемме 2 не приводится, хотя из Теоремы 3 можно сделать вывод, что ее доказательство неявно предполагается.
Библиография
  1. Giffler J., Thompson G.L., “Algorithms for solving production scheduling problems,” Operations Research, Vol. 8, 1960, pp. 487–503.

1 comment:

  1. Вот эта статья точно в тему )

    ReplyDelete