Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

откуда видно, что вектор а;- — аотличается от rs скалярным мно­ жителем.

Таким образом, можно представить процесс решения с помощью прямого алгоритма как построение последовательности пере­

в полупространстве содержатся только такие векторы ау-, у кото­ рых a0j ^ 0. Более подробную картину сдвигов в полупростран­ стве, происходящих от таблицы к таблице (которую мы не будем описывать здесь), можно получить, анализируя (24), (25) и (26).

Этот параграф заканчивается выводом соотношений (22) — (26). Формула (22) следует из (19), (20) и (21); (22) фактически является просто векторной формой скалярных уравнений из (2 0 ).

Для получения (23) воспользуемся формулами симплексного преобразования, используемыми в прямом алгоритме:

Остается заметить, что (23) является векторной формой соотно­ шения (32).

24 т. ху

ГЛАВА 18

ЗАДАЧА О РЮКЗАКЕ

18.1. Задача о рюкзаке (Гилмор, Гомори [75], Гомори [84])

Рассмотрим простейшую задачу целочисленного программиро­ вания, а именно задачу только с одним ограничением. Эта задача, как и задача о кратчайшем пути, имеет многочисленные практи­ ческие приложения и часто возникает при решении различных задач оптимизации. Она имеет простую структуру и поэтому может быть решена методом динамического программирования ([15], [16], [74]). Мы обсудим этот метод, а в следующей главе рассмотрим его обобщение для решения общей задачи целочислен­ ного программирования.

Название «задача о рюкзаке» появилось благодаря следующей гипотетической ситуации. Турист, собираясь в поход, должен выбрать, какие предметы ему взять с собой. Каждый предмет имеет свой вес и свою ценность. Требуется, чтобы общий вес рюкзака с выбранными предметами не превышал некоторой задан­ ной величины, а их общая ценность была максимальной.

Обозначим через aj вес одного предмета /-го типа, через Cj — его ценность, через х} — число выбранных предметов /-го типа (т. е. таких предметов, которые турист берет с собой), через Ъ — за­ данную величину, ограничивающую вес рюкзака. Тогда задача примет вид

П

Здесь a,j и b—положительные целые числа, с,-—неотрицательные целые числа.

2 4 *

То есть фй (у) — это максимальное значение целевой функции, когда предметы выбираются из первых к типов, а общий вес выбранных предметов ограничен величиной у. Полагаем ф0 (г/) = О для всех у (0 ^ у ^ Ь), это соответствует случаю, когда не выбрано ни одного предмета; фй (0 ) = 0 для всех к (0 ^ к ^ п) (случай,

когда общий вес рюкзака равен 0). Очевидно, чтоф! (у) — [y/a^-Ci, так как в рюкзак следует положить как можно больше предметов 1-го типа. Вообще при к ^ 1 для функции фй (у) справедливо следующее рекуррентное соотношение:

Обоснование этого соотношения просто. Когда при получении фй (у) предметы выбираются из первых к типов, то предмет &-го типа может оказаться либо выбранным, либо нет. Если он не выбран, то фй (у) =фй_1 (г/). Если же предмет к-то типа выбран

хотя бы один раз, то общий вес остальных предметов ограничи­ вается величиной у — ah. Очевидно, что этот вес у — ah следует

использовать наилучшим образом. Максимальное значение целе­ вой функции, которое можно получить, используя предметы пер­ вых к типов, при ограничении у — ah на вес рюкзака, у нас полу­ чило обозначение фй (у — ak). (Заметим, что мы берем фй {у — ah), а не фй_1 (у — ak), потому что предмет к-то типа может быть выбран

несколько раз.)

Можно составить таблицу, содержащую п строк и Ъ столбцов,

ния (1 ) величины фй {у) можно подсчитать в следующем порядке:

п X Ъ.

При получении некоторой величины фй (у) в первой таблице,

сразу находится во второй таблице соответствующий элемент

*) Нетрудно видеть, что величины % ( у ) (к < п ) зависят от того, как занумерованы предметы. Н о величина фп (Ь) не зависит от этой нумерации (этот факт следует из определения функции фп (6 )).— П р и м , перев .