Оптимизационных задач.

1. Постановка задачи целочисленного линейного программирования. Под задачей целочисленного линейного программирования (ЦЛП) понимается задача линейного программирования, в которой некоторые (а возможно, и все) переменные должны принимать целые значения. Задача ЦЛП называется полностью (частично) целочисленной, если все (некоторые) переменные должны быть целочисленными. В общем виде задача ЦЛП математически формулируется так:

найти точку минимума целевой функции

(4.1)

при заданной системе ограничений

(4.2)

и условии, что x_j = 0, 1, 2, ¼, j = 1, 2, ¼, l, l £ n.

Задачу ЦЛП можно решить, например, как задачу линейного программирования без учета условий целочисленности переменных, а затем округлить полученное решение с избытком или недостатком. При этом получается некоторое целочисленное решение. Использование такого подхода требует проверки допустимости полученного решения. Таким методом часто пользуются при решении практических задач, особенно когда значения переменных настолько велики, что можно пренебречь ошибками округления. Однако при решении задач, в которых целочисленные переменные принимают малые значения, округление может привести к далекому от истинного оптимума целочисленному значению. Кроме того, при решении задач большой размерности такой метод слишком трудоемок. Например, пусть оптимальное решение соответствующей задачи линейного программирования имеет вид х ₁ = 2, 4; х ₂ = 3, 5. Для получения приближенного оптимального целочисленного решения необходимо рассмотреть четыре точки (2, 3), (2, 4), (3, 3), (3, 4) и выбрать среди них допустимую точку с наилучшим (наименьшим) значением целевой функции. Если в задаче имеются 10 целочисленных переменных, то следует рассмотреть 2¹⁰ вариантов целочисленного решения. Но даже рассмотрение всех вариантов не гарантирует получения оптимального целочисленного решения задачи.

Перейдем к построению моделей целочисленного программирования для наиболее важных практических задач.

2. Задача о рюкзаке. Пусть имеется n предметов, a_j - вес, а c_j - ценность j -го предмета, a_j > 0, c_j > 0. Требуется загрузить рюкзак, выдерживающий вес b, набором предметов, суммарная ценность которых максимальна.

Введем переменную x_j, принимающую значение 1, если j -й предмет грузится в рюкзак, и 0 - в противном случае, j = 1, …, n. Переменные, принимающие значения 0, 1, называются булевыми. Задача имеет вид

Эта задача является частным случаем целочисленной задачи (4.1), (4.2). Задачу (4.1), (4.2) в данном случае можно трактовать как обобщенную задачу о рюкзаке, если отказаться от предположений о том, что каждый предмет имеется в наличии в единственном экземпляре и может загружаться в рюкзак в единственном экземпляре, заменив условие x_j Î {0, 1} условием x_j Î {0, 1, 2, ¼ } (j = 1, ¼, n). При этом единственное ограничение на вес заменяется совокупностью m ограничений (ограничиваются суммарный вес, объем и т. д.).

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

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

В массовом производстве при поступлении одинаковых кусков материала (например, бревна или листы стального проката одинакового размера), если можно перечислить все i = 1, 2, …, N доступные способы раскроя одного куска материала на некоторые из j = 1, 2, …, m нужных видов заготовок, задача раскроя формулируется следующим образом:

найти интенсивность применения (количество раз) x_i ³ 0 каждого из раскроев, при которых

и соблюдены условия

где a_ij - количество j-х заготовок в i-м раскрое, а b_j - необходимое на одно изделие количество этих заготовок.

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

4. Задача о комивояжере. Пусть имеется n городов, занумерованных числами 1, …, n. Для любой пары городов (i, j) задано расстояние c_ij ³ 0 между ними (c_ij может означать не только расстояние, но и время, путевые расходы и прочее, поэтому в общем случае не предполагается, что c_ij = c_ji). Выехав из исходного города, комивояжер должен вернуться в него, побывав во всех остальных городах ровно по одному разу. В качестве исходного может быть выбран любой город. Требуется найти маршрут минимальной длины.

Иными словами, необходимо минимизировать функцию

на множестве Х допустимых маршрутов x = (i ₁, …, i_n, i ₁), где (i ₁, …, i_n, i ₁) - произвольная перестановка чисел 1, 2, …, n. Заметим, что множество Х содержит n! элементов, поэтому решить задачу методом полного перебора при достаточно больших n нереально.

Описанная задача относится к классу так называемых комбинаторных задач, т. е. задач оптимизации функции, заданной на конечном множестве, элементами которого служат выборки из n объектов. Различные ее варианты возникают, например, при отыскании оптимальных маршрутов доставки готовой продукции потребителям.

Величину c_ij можно интерпретировать и как стоимость перестройки гибкого автоматизированного производства при переходе от изготовления партии изделий i- го типа к изготовлению партии изделий j- го типа. Требуется минимизировать суммарные издержки при производстве n партий изделий различных типов.

Покажем, что задача о комивояжере сводится к некоторой задаче ЦЛП. Введем переменную x_ij, принимающую значение 1, если комивояжер из города i преезжает в город j, и 0 - в противном случае, i, j = 1, …, n. Тогда задача о комивояжере принимает вид задачи ЦЛП: минимизировать целевую функцию

при ограничениях

(4.3)

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

5. Некоторые рекомендации по формулировке и решению задач ЦЛП. Приведенные ниже рекомендации не следует рассматривать как обязательные. Тем не менее их применение на практике часто позволяет уменьшить время вычислений, которое существенно зависит от исходной математической постановки задач ЦЛП.

1. Количество целочисленных переменных следует уменьшать насколько возможно. Например, целочисленные переменные, значения которых должны быть не менее 20, можно рассматривать как непрерывные.

2. В отличии от непрерывных задач ЛП добавление новых ограничений, особенно включающих целочисленные переменные, обычно уменьшает время решения задач ЦЛП.

3. Если нет острой необходимости отыскания точного целочисленного оптимума, можно ограничиться получением целочисленного решения, отличающегося от решения соответствующей непрерывной задачи ЛП, например, не более чем на 3%. Это ведет к значительной экономии машинного времени.

4. Для эффективного решения задач целочисленного программирования с булевыми переменными разработан ряд специальных методов, основанных на неявном переборе допустимых точек.