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

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

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

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

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

Запишем общую задачу целочисленного линейного программирования

Найти = (или min) (1)

при следующих ограничениях:

(2)

(3)

- целые, , () (4)

В том случае, когда условия целочисленности наложены на все переменные, мы имеем дело с полностью целочисленной задачей линейного программирования, при этом n₁ = n когда же требования целочисленности наложены на отдельные переменные - с частично целочисленной задачей линейного программирования, при этом n₁ ? n.

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

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

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

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

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

Определение. Каждое число Х можно единственным способом разложить на два слагаемы

, (5)

где - наибольшее целое число, не превосходящее Х,

а - дробная часть числа Х, удовлетворяющая условию 01.

Например, [5,6] = 5, {5,6} = 0,6, [-4,3] =-5, {-4,3}=0,7.

Рассмотрим алгоритм Гомори для решения полностью целочисленной задачи линейного программирования, то есть задачи (1)-(4). Этот алгоритм основан на теореме, позволяющей "отсекать" оптимальной нецелочисленной опорный план задачи линейного программирования, не "отсекая" ни одного целочисленного плана. Если найденный оптимальный план не является целочисленным, то составляется дополнительное линейное ограничение, которому удовлетворяет любое целочисленное решение из допустимого множества планов, но заведомо не удовлетворяет полученное. После введения этого ограничения в задачу план становится недопустимым, и решение опять продолжается до получения оптимума.

Алгоритм Гомори

1. Методами последовательного улучшения плана или последовательного уточнения оценок решаем задачу линейного программирования вида (1)-(4)

Найти = (или min) (1)

при следующих ограничениях:

(2)

(3)

- целые, , () (4)

до получения оптимального решения на "к"-ой итерации.

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

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

(5)

и единичным столбцом ln+m+1. В (5) Y_i является неотрицательной целочисленной переменной.

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

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

Последовательно преобразуем симплексную таблицу, полученную после окаймления ее строкой Y_i и столбцом l(n+m+1) методом последовательного уточнения оценок до тех пор, пока эта таблица не станет опять допустимой или не выявится несовместность исходных ограничений, то есть выполняем большую итерацию. При этом на первом шаге большой итерации из базиса обязательно выводится Y_i

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

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

Примечания ко второму пункту алгоритма:

а) Если все - целые, а - нецелое число, то к таблице приписываем вместо y_i строку y₀, то есть

, (6)

где y₀ имеет неотрицательное целочисленное значение;

б) В этом случае, когда в оптимальном нецелочисленном плане имеется несколько дробных свободных членов, то выбор числа i для введения соответствующего "отсекающего" неравенства (7) или (8), где

+ … + (7)

+ … + (8)

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

Примечания к третьему пункту алгоритма

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

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

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

Пример. Найти максимум функции цели

L (X) =16X₁ + 9X₂ (9)

при следующих ограничениях

5 (10)

.

(11)

и - целые (12)

Решение. Полное решение задачи приведено в таблице 1.

В первых трех таблицах решение проведено методом последовательного улучшения плана. Полученное оптимальное решение L (X) =72 при Х₁ = 2 и Х₂=3не удовлетворяет условию целочисленности.

Из нецелых чисел (72; 2; 3) первым по номеру является значение функции цели С₀. По этой строке формируем дополнительное ограничение вида (7), вводя неотрицательную целочисленную переменную у₀.

Полученным ограничением у₀, а также единичным столбцом (0;0;0;1) окаймляем третью таблицу. Теперь мы имеем дело с псевдо - планом, так как симплексная таблица стала недопустимой.

Таблица 1

Методом последовательного уточнения оценок на пересечении строки Уо и столбца x₃ находим генеральный элемент и осуществляем переход к следующей симплексной таблице, в четвертой таблице получено оптимальное решение L (X) = 68 при X₁= 2 и X₂ = 4, удовлетворяющее условию цело численности. Следовательно, исходная задача (10) решена полностью.

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

На рисунке (1) построен многоугольник решений ОАBС, соответствующий системе ограничений (9) - (11). Координаты вершины в точке (;) удовлетворяют нецелочисленному максимальному значению функции цели, равному 72.

x2 х2

10 10

8

6 A 6 А

Е(2;4)

B; В

C С

0 4 6 x1 0 4 6 х1

Рис. 1 Рис. 2

Построим дополнительное ограничение 0

На рис. 2 построена граничная прямая Е С, соответствующая уравнению + = 2. Дополнительное ограничение 0 отсекло от множества планов задачи нецелочисленный план с вершиной В, но не отсекло ни одного целочисленного плана. В результате получили многоугольник ОАЕС. Координаты вершины Е (2; 4) удовлетворяют наибольшему целочисленному значению функции цели, равному 68.

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

Ввиду трудности построения этой выпуклой оболочки строим промежуточный многогранник, охватывающий ее и содержащийся в .

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

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

Рассмотрим задачу целочисленного линейного программирования вида (1) - (4).

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

Найти (1)

при следующих ограничениях

+

+ (2)

………………….
+

(3)

- целые (4)

Определение. Градиентом функции заданной плоскости , называется вектор, показывающий направленно наискорейшего изменения некоторой величины, значение которой изменяется от одной точки плоскости к другой. Если величина выражается функцией то координаты градиента равны +

Длина градиента (скорость изменения величины L в направлении градиента) равна

(5)

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

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

Аналогично решается задача (1) - (4) при отыскании минимума. Целочисленному минимуму функции цели (1) будут соответствовать координаты вершины целочисленной решетки, лежащей в многоугольнике решений, наиболее близкой к началу координат в направлении градиента. Пример. Найти экстремумы функции цели

L (Х) =15 (6)

При следующих ограничениях:

+

(7)

+

+

(8)

- целые. (9)

Решение. На рис.(3) построен многоугольник решений АБСDE, градиент функции цели и целочисленная решетка.

Максимум функции цели достигается в вершине С (12,5;10,5). Он ранен 255,5. Целочисленный максимум функции цели достигается н точке М (12 ; 10), наиболее удаленной от начала координат в направлении градиента, и равен 240.

Минимум функции цели определяется координатами вершины А (3,5 ; 5,5). Он равен 85,5. Целочисленный минимум находится в вершине Р (4 ; 6) целочисленной решетки, в направлении градиента и равен 96.

Рис. 3

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