§ 5. Другие прикладные задачи

Мы уже отмечали, что в настоящий момент вряд ли возможно дать исчерпывающую классификацию прикладных задач дискретного программирования. Здесь будет описано еще несколько моделей, различных по своему характеру, но базирующихся в основном на уже известных читателю идеях.

5.1. Рассмотрим следующую упрощенную задачу о наилучшем распределении памяти вычислительной машины. Пусть стандартная подпрограмма для вычисления функции в библиотеке подпрограмм Подпрограмма занимает ячеек памяти и требует для счета t сек.

Требуется составить «программу» которая определяется заданием некоторого набора индексов т. е. функций, подлежащих вычислению (наличием иных команд пренебрегаем). При этом следует для составления программы указать такой набор подпрограмм чтобы длина всей программы не превосходила ячеек, а время счета по ней было минимальным.

Как обычно в подобных случаях, вводим переменные

Тогда наша задача сведется к минимизации

при условиях

5.2. Некоторые задачи рационального раскроя материалов могут быть естественным образом описаны целочисленными моделями. В качестве примера приведем следующий вариант задачи линейного (одномерного) раскроя. Пусть имеется большое (практически неограниченное) число одномерных заготовок одинаковой длины Это могут быть трубы, прутки и т. п. Заготовки следует разрезать на полосы (детали) типов; длина полосы типа равна По данным числам можно составить матрицу всевозможных способов раскроя где каждое указывает количество полос типа получающееся из одной заготовки при раскрое ее по способу Таким образом, каждый способ раскроя изображается столбцом матрицы он характеризуется набором целых чисел подчиненных лишь условию

(суммарная длина выкраиваемых из заготовки полос не превосходит длины заготовки). Важно отметить, что

матрица А этой задачи не задана изначально, а строится, быть может, уже в ходе решения задачи.

Число способов раскроя даже в задачах с небольшим количеством полос может быть весьма внушительным. Так, например, при мы получим следующую матрицу:

Здесь, например, 5-й столбец означает, что из одной заготовки можно выкроить 2 полосы по 20 и 1 полосу по 15. Всего мы имеем 13 способов раскроя.

Пусть, кроме того, заданы потребности в полосах типа Требуется выполнить это плановое задание, раскроив минимальное число заготовок.

Если ввести переменные означающие количество заготовок, подлежащее раскрою по способу то эта задача сведется к минимизации -

при условиях

Постановку этой задачи можно несколько видоизменить, приняв в качестве критерия оптимальности минимизацию суммарной величины отходов при раскрое. Если обозначить отходы от одной полосы при способе раскроя через то целевая функция (5.5) заменится на

Отметим, что при заданной матрице А отходы легко вычисляются как разности между левой и правой частями (5.4).

5.3. Рассмотрим финансирование исследовательских проектов. Пусть на протяжении лет возможно

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

Формализация этой задачи очевидна: если обычным образом ввести переменные

то мы придем к задаче максимизации

при условиях

5.4. Многие задачи из области экономики сельского хозяйства приводят к целочисленным моделям. Рассмотрим, например, следующую упрощенную статическую модель распределения тракторных работ [12].

Имеется типов сельскохозяйственных машин и видов работ, подлежащих выполнению в объемах (будем считать, что все эти объемы выражены в гектарах). Заданы производительность машины на работе а также себестоимость обработки работы машиной Себестоимость самих машин (скажем, стоимость их покупки или аренды, взятая с некоторым коэффициентом приведения) составляет Следует найти оптимальный машинный парк для данного комплекса работ и указать его распределение по работам, чтобы выполнить задание и добиться минимальной суммарной себестоимости.

Обозначим через количество машин каждого типа, а через количество машин типа которое будет

выделено на работу Тогда наша задача сведется к минимизации

при условиях

Отметим, что накладывать условие целочисленности на не обязательно, так как нецелые здесь вполне поддаются разумной интерпретации.

Таким образом, перед нами еще один пример задачи с неделимостями. Модель эта существенно усложнится, если дополнительно потребовать выполнения каждой работы в отведенные для нее агротехнические сроки; здесь мы не будем на этом останавливаться.

Дискретность в сельскохозяйственных задачах может возникать и другими путями. Так, например, в рамках некоторой модели организации сельскохозяйственных работ для отдельных технологических процессов может оказаться разумным — в случае включения их в план — осуществлять их с интенсивностью не ниже заданной (скажем, посев некоторой культуры, если он будет осуществлен, целесообразно производить на площади не менее Другой вариант: возделывание некоторой культуры требует соответствующего объема затрат труда и техники, а без этих затрат она возделываться не может. Читатель, по-видимому, уже заметил, что первый из этих примеров должен рассматриваться в рамках альтернативных условий (п. 4.1 гл. 2), а второй — путем введения фиксированных доплат (§ 5 гл. 2). Деталей мы приводить здесь не будем, ибо они будут повторять ранее сказанное.