4.2.4. Завдання про ранець

У ранець обсягуbнеобхідно упаковати предмети з наявної множини предметів різного типу так, щоб сумарна вага ранця була максимальною. Нехайj– тип предмета, який займає об'ємajі важитьcj.

Введемо керовані змінні

- кількість предметівj- го типу, які будуть у ранці. Загальна вага ранця

(4.19)

Обмеження за обсягом ранця

(4.20)

- ціле (4.21)

Це завдання ЛЦП за єдиного обмеження.

4.3. Алгоритм розв'язання задачі про ранець

Розглянемо спеціальний спосіб розв'язання завдання про ранце, т.к. у ній лише одне обмеження. У цьому методі буде запроваджено найважливіші поняття, необхідні розробки загального методу розв'язання завдань ЛЦП.

Будь-яке рішення задачі про ранець це вектор, наприклад:

. Візьмемо предмети з великою питомою вагою як пріоритетні. Упорядкуємо компоненти за питомою вагою.

Старша компонента – з великою питомою вагою.

Визначимо лексикографічний порядок таких векторів, це впорядкування векторів за першою компонентою, якщо вони рівні, то другою і т.д.

Більший вектор той – у якого старша компонента більша.

Максимальний лексикографічний вектор для задачі про ранець визначається так:

Наступний після максимального лексикографічному ряду буде вектор, який виходить так: останню ненульову компоненту зменшують на одиницю, а наступну збільшують на максимально можливу величину.

Незважаючи на те, що лексикографічно максимальний вектор дає близьку до оптимального значення вага ранця, цільова функція для векторів, що лежать нижче, ніж

, може бути більшою, ніж цільова функція для. У цьому виявляється специфікацілісності, т.к. якщо з ранця прибрати один «важкий» предмет, то в сумі два більш «легкі» можуть дати більшу вагу ( вони щільніше впакуються).

Якщо пройти всі лексикографічно впорядковані вектори, можна знайти найкраще значення z.

Розглянемо підхід, що дозволяє відсіяти деяке підмножина варіантів. Слід зазначити, що це методи дискретної оптимізації спрямовані скорочення перебору варіантів рішення. Для цього ми повинні бути впевнені, що всі ці варіанти, що відсіваються, в жодному разі не дадуть значення цільової функції краще, ніж вже отримане. Для цього використовується поняттяоцінкибезлічі варіантів.

Оцінкапідмножини варіантів - це величина, що має розмірність цільової функції, така, що жоден варіант цього підмножини не дасть значення цільової функції краще, ніж дана оцінка (δ).

Грубу оцінку зробити легко. Питання полягає в тому, щоб отримати оцінку якомога ближче до справжніх значень. Чим точніше оцінка, тим більше відсіватимемо варіантів.

Розглянемо в лексикографічному ряду вектор, що стоїть на i місці.

. Його остання ненульова компонента. Розглянемо вектор, який виходить із вектораxiтак: остання ненульова компонента зменшується на одиницю, усі подальші – нулі.

Порівняємо

та.

Дамо оцінку всіх варіантів, що знаходяться від

до. Для цього визначимо оцінку i - го множини у вигляді:

Перша сума – це вага упаковкиyi, а вираз у дужках –обсяг, що залишився після упаковкиyi, тому оцінка дає вагу щільно заповненого ранця, що з цілих предметах недосяжно.

Тепер, якщо всім векторів від

доотримано деяке найбільше,т.зв.рекорднезначення цільової функціїіце означає, що не треба розглядати вектори віддоі потрібно взяти відразу для аналізу вектор. Якщо, нічого сказати не можна, і беремо для аналізу наступний вектор, хоча у збереженому підмножині може бути кращого значення цільової функції.

Перевіримо співвідношення

і перевизначимо змінні.

Відповідь:

, з урахуванням перепозначення х'= (0,5,2,0)

Примітка:Якщо коефіцієнти цільової функції цілі, то справжнє значення z може бути тільки цілим, тому якщо оцінка вийшла дробовою, то її можна посилити (наблизити до істинної величини Z: для Zmax зменшити до найближчого цілого, а для Zmin збільшити до найближчого цілого).

---