Особенности задач целочисленного программирования

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

(3.10)

min{F(x)|x_j ³ 0; j = 1, 2,..., n; φ_i(x) ≤ 0; i = 1, 2,..., m}.

Однако специфика задач целочисленного программирования заключается в том, что переменные x_j и функции F(х), φ_i(x) могут принимать только дискретные значения. Специальными преобразованиями в подавляющем большинстве случаев можно свести эти дискретные значения к целочисленным.

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

Если все функции F(х), φ_i(x) в задаче (3.10) линейные, то имеет место линейная задача целочисленного программирования. Методы решения таких задач получили наибольшее распространение. Очевидно, что могут встречаться задачи с целочисленными переменными x_j и функциями F(х), φ_i(x) и целочисленными переменными и непрерывными функциями (рис. 3.6). Как правило, именно этот последний случай рассматривается в большинстве руководств. Кроме того, встречаются задачи частично и полностью целочисленные в зависимости от того, часть или все переменные x_j принимают целочисленные значения. Как уже отмечалось, допустимые дискретные значения, входящие во множество, могут быть даже нецелочисленными. В частности, это множество может быть бесконечным, конечным или даже состоящим всего из двух значений: 0 и 1. В этом случае имеет место целочисленное программирование с булевыми переменными, методы которого в значительной мере перекрываются логическим синтезом конечных автоматов.

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

Рис. 3.6. Классификация задач целочисленного программирования

Со значительными оговорками все методы решения задач целочисленного программирования можно разделить на четыре группы (рис. 3.7):

– методы отсечения;

– комбинаторные методы;

– приближенные методы;

– другие методы, которые нельзя отнести ни к одной из трех первых групп.

Рис. 3.7. Классификация методов решения задач целочисленного программирования

Первая группа использует процедуру линейного программирования для последовательности задач, в которые постепенно вводятся линейные ограничения, и тем самым реализуется процесс правильного отсечения. Основу всех методов этой группы составляют три алгоритма Гомори и их модификации.

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

Дискретное динамическое программирование по-прежнему успешно применяется для решения задач целочисленного програмирования и в приведенной на рис. 3.7 классификации содержится в разделе комбинаторных методов, так как по существу оно является направленным методом перебора. Значительно реже используется дискретный принцип максимума. Широкие возможности в части решения прикладных задач большой размерности открываются при использовании человеко-машинных методов оптимизации. По своей идеологии эти методы примыкают к лингвистическим с добавлением блоков эвристики, в качестве которых выступает человек при общении с ЭВМ.

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

Пример. Требуется найти решение следующей задачи целочисленного программирования:

1/2x₁ – x₂ ³ 2;

1/5x₁ + x₂ ³ 3;

x₁ – 1/3x₂ ³ 4;

x₁, x₂ ³ 0;

max z = 1/5x₁ + x₂.

При целочисленности переменных максимум z_опт = 13/5 достигается в точке х_1опт = 3, х_2опт = 2, в то время как при исключении этого требования z_опт = 3 в точке х_1опт = 10/7, х_2опт = 19/7. Округление результата до целых не дает оптимума исходной задачи, как это видно из рис. 3.8. Заметим, что условие целочисленности z при снятии этого требования к переменным х₁ и х₂ определяет оптимум при других значениях х₁ и х₂.

Рис. 3.8. К особенностям задач целочисленного программирования

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

min{F(x)|x_j ³ 0; j = 1, 2,..., n; φ_i(x) ≤ 0; i = 1, 2,..., m}.

Будем считать, что переменная x_j0 может принимать только одно из заданного множества значений

x_j0 Ì {k_j0¹, k_j0²,..., k_j0^p}.

Введем дополнительные булевы переменные у₁, y₂,..., y_p и запишем условие дискретности для x_j0 в виде:

(3.11)

x_j0 = k_j0¹у₁, k^j0₂y₂,...,

y_p;

y_j = 1 или 0, j = 1, 2,..., p;

у₁ + y₂ +... + y_p = 1.

Последнее соотношение требует, чтобы только одна переменная у_v была отлична от нуля. Нетрудно убедиться, что формулы (3.11) обеспечивают дискретность переменной x_j0. Таким образом, путем введения булевых переменных у_v можно всегда свести нецелочисленную дискретную задачу математического программирования к целочисленной. Как видно, соотношения (3.11) представляют собой p-кратную логическую альтернативу:

<<x_j0 = k₀¹, или x_j0 = k₀², или..., или x_j0 = k₀^p>>.

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

0 ≤ x_j0 ≤ k_j0;

(3.11а)

или x_j0 ≤ a или x_j0 ³ b;

0 ≤ a< b≤ k_j0.

Введем дополнительную булеву переменную y_j0, которую не будем включать в функцию цели, а заменим рассмотренные соотношения следующими:

(3.11б)

x_j0 – b + by_j0 ³ 0;

-x_j0 + ay_j0 + k_j0(1– y_j0) ≤ 0;

y_j0 = 1 или 0.

Очевидно, что соотношения (3.11а) и (3.11б) эквивалентны. Действительно, когда y_j0 = 1, то (3.11б) сводится к x_j0 ³ 0 и x_j0 ≤ a; когда y_j0 = 0, то x_j0 ³ b и x_j0 ≤ k_j0. Таким образом, многосвязность области допустимых значений легко учитывается введением дополнительных булевых переменных. Этот метод без труда распространяется на случай многих переменных.

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

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

x₁ + 1/4x₂ ≤ 2;

2/5x₁ – x₂ ³ –1;

x₁ – 1/3x₂ ≤ 3;

x₁, x₂ ³ 0.

Соответствующая область представлена на рис. 3.9. Первая и вторая пара неравенств образуют выпуклые подобласти x₁, x₂ с учетом неотрицательности переменных с верхними границами x_1макс, x_2макс, соответственно. Введение булевой переменной у приводит к дополнительным неравенствам:

x₁ – yx_макс ≤ 0;

x₂ – (1 – y)x_макс ≤ 0.

Здесь каждое условие относится ко всем неравенствам соответствующей области.