Целочисленное программирование

Размещено на http://www.allbest.ru/

1. Целочисленное программирование. Основные понятия

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

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

Рекомендации по формулировке и решению ЦП

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

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

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

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

2. Метод Гомори

Задача целочисленного программирования может быть сформулирована следующим образом: найти максимум или минимум функции при условиях _Xj > 0, j = 1, 2,…, n, а также при дополнительном условии х_j - целые числа.

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

Для решения задач целочисленного программирования разработаны специальные методы. К ним относятся метод отсечений (метод Гомори) и метод ветвей и границ.

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

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

На шаге 2 решения задачи без ограничения целочисленности получаем оптимальный нецелочисленный план

X = (0, 0, 29/7, 13/7).

Поскольку обе базисные координаты X нецелочисленны, выбираем любую - первую или вторую - строку таблицы на шаге 2, а именно вторую, и строим добавочное ограничение

-5/7x₁-6/7x₂-1/7x₅+x₆=-6/7.

Вводя ограничение добавочной строкой на шаге 2, находим направляющий элемент в этой строке:

Осуществляя преобразование табл. 7.2 с направляющим элементом (-5/7), получаем на шаге 3 оптимальный план новой задачи, снова нецелочисленный. На шаге 3 добавляем очередное условие, получаем четыре строки ограничений. Поскольку на шаге 3 достигается

в столбце А₆, то х₆ становится базисной переменной на шаге 4. В соответствии с правилом сокращения таблицы на шаге 4 вычеркиваем строку и столбец, соответствующие х₆, добавляем новую строку, а на шаге 5 получаем псевдоплан X = (4, 0, 3, -1). Методом последовательного уточнения оценок на шаге 6 получаем план, но нецелочисленный. Оптимальный целочисленный план получаем лишь на шаге 7: X* = (О, 1, 4, 2), max Z(X)=-6.

3. Метод ветвей и границ

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

f(X) -> max,

Х€D

где D - конечное множество.

Сначала найдем оценку Ј(D) (границу) функции f(X), X е D: f(X) = Ј(D) для V X е D. Если для некоторого плана Х° задачи (7.9) - (7.10) справедливо равенствоf(X⁰) = Ј(D), то Х° = X^* является решением задачи. Если указанное условие не выполняется, то возможно разбиение (ветвление) множества D на конечное число непересекающихся подмножеств D¹_i: ?D¹_i. = D, ?D¹_i = ?, и вычисление оценки Ј(D¹_i) (границ), 1?i?m.

Если для некоторого плана X¹_i е Di¹, 1 ? / ? m выполняется условие f(X_k^l)= Ј(D¹_k)= Ј(D¹_i), 1?i?m то X_k¹=X^* является оптимальным планом (решением) задачи (7.9) - (7.10).

Если такого плана нет, то выбирается подмножество D_k^l с наибольшей оценкой Ј(D¹_i): и разбивается на конечное число непересекающихся подмножеств D²_kj: UD²_kj=D¹_k, ?D²_kj=?. Для каждого подмножества находится оценка Ј(D²_kj), 1?j?n.

Если при этом найдется план X²_j е D²_kJ, 1 ?j ?n, такой, что f(X²_r)= Ј(D²_kr)= Ј(D²_kj), 1?j?n, то X²_r= X* является решением задачи (7.9) - (7.10). Если такого плана нет, то процедуру ветвления осуществляют для множества D²_kj с наибольшей оценкой Ј(D²_kj), 1?j?n. Способ ветвления определяется спецификой конкретной задачи.

Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования.

Алгоритм метода ветвей и границ

1. Находим решение задачи линейного программирования без учета целочисленности.

2. Составляет дополнительные ограничения на дробную компоненту плана.

3. Находим решение двух задач с ограничениями на компоненту.

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

4. Циклический алгоритм целочисленного программирования

целочисленный гомори линейный программирование

Рассмотрим следующую задачу линейного программирования:

Максимизировать

X₀=a₀₀-a₀₁x₁-a₀₂x₂-……..-a_0nx_n,

при условии

x_n+1=a_n+1,0-a_n+1,1x₁-a_n+1,2x₂-…….-a_n+1,nx_n,

x_n+m=a_n+m,0 - a_n+m,1x₁-a_n+m,2x₂-…….-a_n+m,nx_n,

x_j?0 (j=1,……., n+1,……., n+m).

Заметим, что x_n+1., х_n+m - слабые переменные, a x₁…., х_n - исходные переменные задачи (1). Если наряду с ограничениями (1) потребовать, чтобы все х_j, (j'=1,…, т) были целыми, то задача будет называться задачей целочисленного программирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи целочисленного программирования.

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

Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперплоскостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.

Обычно в ограничения задачи (1) включаются в тривиальные соотношения xj= - (-X_j) (j'=1,…, n), а задача в матричной форме принимает вид

х = А (-х_n), (2)

где х - вектор-столбец с компонентами Х₀, x₁,…, x_n, x_n+1,…, x_n+m А - соответствующая матрица размера (п + т + 1) * (n + 1) и (-х_n) - вектор с компонентами (1, - x₁, - x₂,…, - x_n), представляющими собой небазисные переменные исходной таблицы. Задачу целочисленного программирования также можно записать в виде таблицы.

Причины представления переменных в виде (-x₁), (-x₂,……, (-x_n)) - чисто исторические, но это стало обычной практикой в целочисленном программировании. Будем использовать б_j(j ⁼ 0, 1,…, п) для обозначения j-го столбца текущей таблицы и a_ij (i = 0, 1,…, п + т; j = 0, 1,…, n) для обозначения элемента 1-й строки и 7-го столбца таблицы. Предполагается, что все a, ij в исходной таблице целые. Следовательно, все слабые переменные x_n+1,…, Х_n+m должны быть также неотрицательными целыми числами.

При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочисленного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма а_ij?0 (i = 1,……, п + т) и a_0j? 0 (j' = 1,…, n). (Для получения исходного двойственного допустимого решения введем дополнительное ограничение x_n+m+1 == М - X₁ - x₂ - … - x_n? 0, где M - достаточно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если а_i0? 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если а_i0? 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т.е. аi₀<О для i == п + т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi₀? 0. Если аi₀ получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi₀ (i = 1,…, n,…, n + m) не станут все целыми и неотрицательными.

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

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таблица также меняется. Будем использовать t для обозначения t-й. таблицы. Матричное уравнение (2) запишется как

Х^t = А^t (-х^t_n),

где х° - вектор-столбец с n + т + 1 компонентами, А° - матрица размера (п + т + 1)*(n + 1) и (-х⁰_n) - вектор с компонентами (1, - x₁,…, - x_n), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а0i?0 (j = 1,…, n), а₀₀ ? 0 (mod 1) ¹} и а_i0 ? 0 (i=1,…, п+т) - целые неотрицательные числа, то получено оптимальное решение целочисленной задачи. Если а_i0 не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (3), в котором а_i0m нецелое. Опуская индексы строки, имеем

(4) x=a₀+?a_j(-x_j)

где x_j в правой части - текущие небазисные переменные и a₀ - нецелое. Поскольку требуется, чтобы х было целым, или х ?0 (mod1), правая часть уравнения (4) также должна удовлетворять условию

0?a₀+?a_j(-x_j) (mod1).

Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы x_j, были целыми, можно алгебраически складывать с отношения 0?f₀+?_jf_i(-x_i) (mod1) (0<f₀<1, 0?f_j<1).

Размещено на Allbest.ru