Задачи целочисленного программирования. Понятие о нелинейном программировании

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

Рассмотрим пример такой задачи. Пусть имеется ряд предметов (ценностей) П₁, П₂, … П_n, которые желательно увезти из угрожаемого района. Известны стоимости этих предметов: с₁, с₂,..., с_n и их веса q₁, q₂, …, q_n Количество и вид предметов, которые мы можем увезти, лимитируется грузоподъемностью Q машины. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в Q.

Введем в рассмотрение переменные х₁, х₂,..., x_n, определяемые условием: x_i = 1, если мы берём в машину предмет П _i и x_i = 0,— если не берем.

При заданных значениях х₁, х₂,..., x_n суммарный вес предметов, которые мы берем в машину, равен q₁x₁ + q₂x₂ +... + q_nx_n. Условие ограниченной грузоподъемности запишется в виде неравенства:

 

q₁x₁ + q₂x₂ +.... + q_nx_n Q. (11.1)

 

Теперь запишем общую стоимость предметов, которую мы хотим максимизировать:

 

(11.2)

 

Таким образом, задача на вид почти не отличается от обычной задачи линейного программирования: найти неотрицательные значения переменных х₁, х₂,..., х_n, которые удовлетворяют неравенству (11.1) и обращают в максимум линейную функцию этих переменных (11.2). На первый взгляд может показаться, что и решать ее надо как задачу линейного программирования, введя дополнительные ограничения-неравенства (каждый предмет — только один!):

x₁ 1, x₂ 1, …, x_n 1.

 

Ничуть не бывало! Найденное таким образом решение может оказаться не целым, а дробным, а значит неосуществимым (не можем же мы погрузить в машину треть рояля и половину шкафа!). Наша задача отличается от обычной задачи линейного программирования: она представляет собой задачу целочисленного программирования.

Вторая мысль, которая приходит в голову: а нельзя ли решить обычную задачу линейного программирования и округлить полученные значения х_i до ближайшего из целых чисел 0 или 1? К сожалению, и так в общем случае поступать нельзя. Полученное таким образом решение даже может не удовлетворять ограничению (11.1), т. е. «не влезет» в данный вес Q. А если и «влезет», то может быть совсем не оптимальным. В отдельных случаях такое округление допустимо; например, если мы в задаче 3 § 7 получим ответ:

«производством ткани первого вида надо занять 185,3 станков первого типа», то, разумеется, мы без зазрения совести округлим это решение до 185. Если же идет речь о ресурсах неделимых (особо ценных или же уникальных), то задачу надо ставить как задачу целочисленного программирования.

Надо заметить, что вообще задачи целочисленного программирования гораздо труднее, чем обычные задачи линейного программирования. На практике применяется ряд методов решения подобных задач; все они (при сколько-нибудь значительном числе переменных) очень сложны и трудоемки. Мы не будем пытаться излагать эти методы здесь, а отошлем интересующегося читателя к более подробным руководствам (например, [7, 8]).

В заключение скажем несколько слов о задачах нелинейного программирования.

Общая постановка задачи нелинейного программирования следующая. Найти неотрицательные значения переменных х₁, х₂,..., x_n, удовлетворяющие каким-то ограничениям произвольного вида. Например

 

(11.3)

 

и обращающие в максимум произвольную нелинейную функцию этих переменных:

 

W = W (x₁, х₂,..., х_n) => mах. (11.4)

 

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

Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут не пропорционально количеству закупленных или произведенных товаров (эффект «оптовости»), но многие нелинейные задачи могут быть приближенно заменены линейными (линеаризованы), по крайней мере в области, близкой к оптимальному решению. Если это и невозможно, все же обычно нелинейные задачи, возникающие на практике, приводят к сравнительно «благополучным» формам нелинейности. В частности, нередко встречаются задачи «квадратичного программирования», когда W есть полином 2-й степени относительно переменных х₁, x₂,..., х_n, а неравенства (11.3) линейны (см. [7, 8]). В ряде случаев при решении задач нелинейного программирования может быть с успехом применен так называемый «метод штрафных функций», сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще. Идея метода состоит в том, что вместо того, чтобы наложить на решение жесткое требование вида (x₁, х₂,..., x_n) 0, можно наложить некоторый достаточно большой «штраф» за нарушение этого условия и добавить к целевой функции W(.x₁, x₂,..., x_n) штраф вида a (x₁, x₂,..., x_n), где а— коэффициент пропорциональности (в случае, когда целевая функция максимизируется, а отрицательно, если минимизируется — положительно). Далее можно, увеличивая абсолютное значение a, посмотреть, как изменяется при этом оптимальное решение (), и, когда оно уже практически перестает меняться, остановиться на нем. В ряде случаев при решении задач нелинейного программирования оказываются полезными так называемые «методы случайного поиска», состоящие в том, что вместо упорядоченного перебора возможных вариантов решения применяется случайный розыгрыш. Со всеми этими методами (и некоторыми другими) читатель в случае надобности может ознакомиться по руководствам [7—9].

В последнюю очередь упомянем о так называемых задачах стохастического программирования. Особенность их в том, что ищется оптимальное решение в условиях неполной определенности, когда ряд параметров, входящих в целевую функцию W, и ограничения, накладываемые на решение, представляют собой случайные величины. Такое программирование называется стохастическим. Существуют задачи, где стохастическое программирование сводится к обычному, детерминированному. Например, когда оптимизация производится «в среднем», целевая функция W линейно зависит от элементов решения, случайны только коэффициенты при элементах решения, а накладываемые условия не содержат случайности. Тогда можно оптимизировать решение, забыв о случайном характере коэффициентов и заменив их математическими ожиданиями (ибо, как вы знаете, математическое ожидание линейной функции равно той же линейной функции от математических ожиданий аргументов). Гораздо более серьезен случай, когда на элементы решения накладываются стохастические ограничения. Проблемы стохастического программирования довольно полно освещены в монографии [31].

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

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

 

 

ГЛАВА 4