Том 13, серия 2, номер 2, 2006 г., Стр. 56-73
УДК 519.854
А. Ю. Чирков, В. Н. Шевченко
О приближении оптимального решения целочисленной задачи о ранце оптимальными решениями целочисленной задачи о ранце с ограничением на мощность
Аннотация:
Рассматриваются целочисленная задача о ранце и целочисленная минимизационная задача о ранце. Под$k$ -оптимальным значением рассматриваемых задач понимается оптимальное значение соответствующей задачи с ограничением на мощность решения. Вводятся понятия гарантированной точности$k$ -оптимального решения целочисленной задачи о ранце$\alpha_{kn}$ и для целочисленной минимизационной задачи о ранце$\beta_{kn}$ , равные точной нижней грани отношения$k$ -оптимального значения к оптимальному значению.
Получены формулы, позволяющие вычислять значения$\alpha_{1n}$ и$\alpha_{n-1n}$ . Указаны задачи, на которых эти значения достигаются. Вычислены значения$\beta_{1n}$ и$\beta_{n-1n}$ , которые в отличие от целочисленной задачи о ранце недостижимы на конкретных задачах. Построены соответствующие серии примеров. Для$k=2,\dots,n-2$ доказаны неравенства $(2^{k+1}-2)/(2^{k+1}-1)\geqslant\alpha_{kn}\geqslant(2^n-2^{n-k})/(2^n-1)$ и $1-2^{-k}\geqslant\beta_{kn}\geqslant(1-2^{1-n})\dotsb(1-2^{-k})$.
Библ. 8.
Чирков А. Ю. 1
Шевченко В. Н. 1
1. Нижегородский гос. университет, фак-т вычислит. матем. и кибернетики,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: shevgru@mail.ru, shev@uic.nnov.ru
Статья поступила 17 марта 2006 г.
