Работа По теме: «Целочисленное программирование» - реферат

Российский Государственный Торгово-Экономический Университет

Ивановский филиал

Курсовая работа

По теме: «Целочисленное программирование»

Выполнила: студентка 2 курса УФФ

Прозорова В.С.

Проверила: Малеж Л.Н.

Груздева Н.Н.

Иваново 2003г.

План:

Введение.

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

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

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

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

5.Полностью целочисленный алгоритм.

6.Задача о рюкзаке.

7.Задача о назначении.

8.Задача коммивояжера.

Заключение.

Список используемой литературы.

Ведение.

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

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации ,прежде всего линейного программирования. Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

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

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

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

Метод Гомори

Задача целочисленного программирования может быть сформули­рована следующим образом: найти максимум или минимум функции

(7.1)

при условиях

(7.2)

_Xj > 0, j = 1, 2, ..., n, а также при дополнительном условии

х _j — целые числа.

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

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

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

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

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

(7.5)

Далее введем понятие целой и дробной частей чисел а _r0 и а _rj , для чего запишем эти числа в виде:

Здесь [а _r0 ] и [ a_rj ] - целые части, a q_t , q_{r ]} - дробные части чисел а _{r j} и a_r j.

Например, ³⁷ /₃ =12 +1/3 , так как [³⁷ /₃ ] = 12, a -^s /, = -3 + 1/3„ так как [-8/3] = -3.

Из уравнения (7.5) найдем х _r

x_r =а _r0 -

Теперь числа а_ю и а_rj заменим суммами целых и дробных частей:

x_r =

Предположим, что все x_j - целые числа. Тогда разность

является целым числом.

Чтобы оказалось целым числом и х _r , необходима целочисленность разности

Но О<q_г <1, 0< g_rj <1, a (7.6)

Если допустить, что разность (7.6) больше нуля, то

Однако в этом случае разность (7.6) не может быть целым числом. Сле­довательно, условие целочисленности разности может быть обеспечено только неравенством

(7.7)

Условие (7.7) и является добавочным ограничением в задаче линей­ного программирования. Для использования его в симплексном методе требуется ввести дополнительную переменную х_п+≥0 , после чего не­равенство превращается в уравнение

Обычно это ограничение записывают в следующем виде:

(7.8)

Последовательно добавляя новые ограничения к решению очеред­ных задач, получаем целочисленные координаты оптимального плана задачи (7.1)—(7.4), если только не выясняется в какой-либо момент, что текущая задача не имеет решения. Это означало бы отсутствие цело­численного решения задачи (7.1)—(7.4).

Пример 1. Найти оптимальный целочисленный план задачи Z(X) = х₁ - Зх₂ + 5х₃ + 2х₄ -max

при условия

x₁ +x₂ +x₃ =15

2x₁ + 3x₃ +x₄ =8,

х_j , > 0, х_j — целые числа, j = 1, 2, 3, 4.

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

Таблица 7.1

Оптимальный план задачи без условия целочисленности

X = (0, 37/3, 8/3, 0)- для дальнейшего решения задачи к таблице опти­мального плана добавлено условие

-2/3x₁ -1/3x₄ ≤-2/3.

Номер индекса г выбран из условия большей дробной части компоненты а_i0 . Имеем г = 2; j = 0: [8/3] = 2, 2 – 8/3 = -² /₃ ; j=1: [² /₃ 1 = О, О - ² /₃ ⁼ -² /₃ ; j = 2: [0] = 0, 0 - 0 = 0; j = 3: [0]= 0, 0 - 0 = 0; j ⁼ 4: [1/₃ ] = 0, 0 — 1/₃ = -1/₃ . Сделав один шаг (в общем случае для получения целочисленного решения одной итерации, конечно, недоста­точно) метода последовательного уточнения оценок, получили оптимальный план целочисленной задачи Х*= (О, 13, 2, 2)

Трудоемкость решения целочисленной задачи обусловлена вводом но­вых добавочных ограничений и новых переменных. В связи с этим необ­ходимо придерживаться следующего правила, позволяющего при опре­деленных условиях сокращать текущие таблицы. Дополнительная пере­менная х_п+1 вводится в процессе решения с добавочным ограничением как базисная переменная очередного псевдоплана и сразу, на этой же итерации, переводится в число небазисных компонент. Если на дальней­ших итерациях, согласно правилу преобразования таблицы, переменная х_п+1 снова окажется базисной, ее значение станет несущественным для основных переменных задачи, так что строка и столбец текущей табли­цы, отвечающие х_п +_] вычеркиваются. Правило сокращения таблиц огра­ничивает их размеры: не более n строк и не более (2n -m) столбцов.

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

Пример 2. Получить целочисленный оптимальный план задачи

Z(X) = x₁ — 4х₂ — 2х₃ + Зх₄ —> max при условиях

3x₁ +x₂ +8x₃ +x₄ =35

x₁ +x₃ +x₄ ≤6

x_j ≥ 0, х_j — целые числа, j = 1, 2, 3, 4.

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

Таблица 7.2

На шаге 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.

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

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

f(X) -> max, (7.9)

Х€D (7.10)

где 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 (рис 7.1)

Рис. 7.1

Если для некоторого плана 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 (рис 7.2)

(рис. 7.2).

Если при этом найдется план 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 . Способ ветвления определяется спецификой конкретной задачи.

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

Пример.

Контейнер объемом 5 м³ помещен на контейнеровоз грузо­подъемностью 12 т. Контейнер требуется заполнить грузом двух наиме­нований. Масса единицы груза m_j (в тоннах), объем единицы груза V_j (в м³ ), стоимости Cj (в условных денежных единицах) приведены в табл. 7.3.

Таблица 7.3

Требуется загрузить контейнер таким образом, чтобы стоимость пе­ревозимого груза была максимальной.

Решение. Математическая модель задачи имеет вид

Z(X) = 10x₁ +12x₂ →max, (7.11)

3x₁ +x₂ ≤12,

x₁ +2x₂ ≤5

x₁ ≥0 (7.12)

x₂ ≥0

x₁ , x₂ - целые числа (7.13)

где x₁ , x₂ - число единиц соответственно первого и второго груза.

Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (рис. 7.3).

Рис. 7.3

Сначала решаем задачу (7.11)—(7.13) без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптималь­ном плане Х° = (¹⁹ /₅ , ³ /₅ ):

ТочкаXнеявляется оптимальным планом задачи (7.1 1)— (7.13). По­этому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x₁ =19/5=34/5 и разобьем множество D на два непересекающихся подмножества D¹ ₁ и D² ₂ . Линии x₁ =3 (L₃ ) и x₄ = (L₃ ) являются линиями разбиения.

Рис. 7.4

Найдем оценки £(D¹ ₁ ) и £(D¹ ₂ ), для чего решим задачи линейного программирования

Z(X)=10x₁ +12x₂ →max,

3x₁ +x₂ ≤12

x₁ +2x₂ ≤5

x₁ ≤3

x₁ ≥0, x₂ – целые числа

Z(X)=10x₁ +12x₂ →max,

3x₁ + x₂ ≤12

x₁ +2x₂ ≤5

x_1≥ 4

x₁ ≥0, x₂ – целые числа

Например, графическим методом:

X¹ ₁ eD¹ ₁ →X⁰ ₁ = (3,1); £(D¹ ₁ )=42; X¹ ₂ eD¹ ₂ →X⁰ ₂ = (4,0); £(D¹ ₂ )=40.

Результат ветвления приведен на рис. 7.5

План X⁰ ₁ удовлетворяет условиям задачи (7.11)-(7.13), и для него выполняется условие: Z(X¹ ₁ )= £(D¹ ₁ )=42 >

£(/)/) = 42 >£(D¹ ₂ ) = 40. Следовательно, план X°₁ = (3, 1) является решением задачи (7.11)-(7.13),

т.е. надо взять три единицы первого груза и одну единицу второго груза.

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

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

ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

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

X₀ =a₀₀ -a₀₁ x₁ -a₀₂ x₂ -……..-a_0n x_n ,

при условии

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

_.

_.

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

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

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

Ограничения (1) определяют выпуклую область OABCD в n-мер­ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­положенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Оптималь­ные решения задачи линейного программирования всегда распола­гаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна. Предположим, что область допу­стимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­лая оболочка показана затененной областью OEFGH. Эту зате­ненную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­деляющей допустимую область OABCD, добавить ограничение типа RR', как показано на рис. 13.1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений. Такая вновь полученная область обладает двумя важными свой­ствами: во-первых, она содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области — целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линей­ного программирования имеет своими компонентами целые числа и является оптимальным ре­шением исходной задачи цело­численного программирования.

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

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

Рис, 13.1.

Обычно в ограничения задачи (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_{0 j} ≥ 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 ), (3)

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

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

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

0≡a₀ +∑a_j (-x_j ) (mod1). (5)

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

Условие (6) эквивалентно следующему:

∑f_j x_j ≡f₀ (mod1). (7)

В соотношении (7) f₀ – константа, меньшая единицы ,и поскольку f_j ≥0 и x_j ≥, левая часть всегда положительна. Т.к. (7) – отношение сравнения по модулю 1, левая часть может принрмать только значения вида f₀ , f₀ +1,……, т.е.

∑f_j x_j ≥f₀ (8)

Неравенство (8) можно представить в виде уравнения с помощью введения неотрицательной целочисленности слабой переменной

S=-f₀ +∑f_jxj ≥0. (9)

Это уравнение можно приписать внизу таблицы и использовать в качестве ведущей строки. Таким образом, переменная s войдет в базис с отрицательным значением (—fо)- После итерации слабая переменная s станет небазисной с нулевым значением. Ведущая строка превратится в тождество s ≡ (—1) (—s) и может быть исключена. Будем называть переменную s в уравнении (9) слабой переменной Гомори. Ниже будет обсуждено, что произойдет, если сохранять все дополнительные строки, соответствующие слабым переменным Гомори.

Дадим доказательство конечности алгоритма. Доказательство будет проведено в предположении, что известна некоторая нижняя граница значения Х₀ , т. е. если существует целочисленное решение, то оно больше, чем наперед заданная величина М (М может быть достаточно большой по абсолютной величине отрицательной кон­стантой). Такое предположение не слишком обременительно и всегда выполняется, если выпуклое множество, определяемое условиями (2), ограничено. Сначала изложим сам алгоритм.

Шаг 1. Решить задачу целочисленного программирования так, как если бы это была линейная программа, т. е. с помощью прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то a_{i 0} ≥0 (i=1, . . ., m + n) и a_{0 i} ≥0(j = 1, . . ., n). Требуется также, чтобы а^t _j > 0 (j = 1, . . ., n).

Шаг 2. Если а_i0 — все целые, то задача решена, и решение получено без использования дополнительных ограничений. В про­тивном случае пусть а^t _i0 — первая нецелочисленная компонента в α^t ₀ . Тогда i-я строка называется производящей строкой. Записать внизу таблицы уравнение

s=-f^t _i0 -∑f^t _ij (-x^t _j ). (10)

Уравнение (10) называется отсечением Гомори. Проделать шаг двойственного симплекс-метода, используя в качестве ведущей строки отсечение Гомори (10). При этом таблица останется двой­ственно допустимой. Повторять до тех пор, пока все а_i0 (i = 1, . . ., m+n) не станут целыми неотрицательными. Если а_i0 на некотором шаге остается отрицательным, следующий шаг двойственного метода производится без введения отсечения Гомо­ри. (Если а_i0 становится отрицательным, нулевая строка не выби­рается в качестве производящей. Если a₀₀ становится нецелым, следует выбрать нулевую строку в качестве производящей.)

Изменение элементов а_ij (i = 0, 1, . . ., n+m; j = 0, . . . . . ., n) в таблице за одну итерацию называется циклом. Для обозначения циклов используется буква t. Для доказательства конечности не достаточно условий α^t ₀ >α₀ ^t+1 >М, поскольку a₀₀ может изменяться каждый раз на ε(t), а ∑ ε (t) = с.

Примером этого может служить ε (t) =1/2t. Другой возможностью является то, что а₀₀ остается равным фиксированному значению, большему нижней границы, в то время как некоторое а_i0 неогра­ниченно уменьшается. Чтобы увидеть, как преодолеваются эти трудности, необходимо в деталях рассмотреть шаги итерации.

При доказательстве будет показано, что либо после конечного числа шагов все компоненты 0-го столбца становятся неотрица­тельными целыми, либо не существует целого решения. Если a₀₀ остается постоянным для всех t ≥ t₀ , то a^t ₀₀ должно быть целым.

Предположим, что а^t ₀₀ —нецелое. Пусть а^t ₀₀ =n^t ₀₀ +f^t _00, где n^t ₀₀ — целое и 0 < f^t ₀₀ < 1. Тогда 0-я строка становится производящей и требуется ввести дополнительное ограничение

S=-f^t ₀₀ -∑f^t ₀ (-x^t _j ).

Если s-й столбец является ведущим, то

a^t+1 ₀₀ =a^t ₀₀ -a^t _0s* f^t ₀₀ /f^t _os

или

Другими словами, a₀₀ уменьшится по крайней мере до ближайшего целого. Следовательно, a₀₀ не может уменьшаться на ε(t) при

∑ε (t)<c

Если a₀₀ каждый раз уменьшается до ближайшего целого или на целую величину, то после конечного числа шагов оно станет меньше любого наперед заданного М (М — предпола­гаемая нижняя граница). Если алгоритм бесконечен, то a₀₀ должно оставаться некоторым фиксированным целым числом для t> t₀ . Предположим, что это произошло.

Тогда рассмотрим а₁₀ . Так же как и a₀₀ , a₁₀ не может оставаться нецелым значением. Если бы это было так, то, поскольку a₀₀ — целое, первая строка стала бы производящей и после введения отсечения Гомори и итерации симплекс-метода мы получили бы

A^t+1 ₁₀ =a^t ₁₀ -a^t _1s *f^t ₁₀ /f^t _1s ,

где 0<f^t _1s <l и 0<f^t _1s <1. Здесь a^t _{1 s} —неотрицательное число, большее f^t _{1 s.} (Если a^t _{1 s} —отрицательно и α^t _s —лексикографически положителен, то а^t _{0 s} положительно и, следовательно, а^t ₀₀ не может

не измениться.) Отсюда

a^t+1 ₁₀ ≤a^t ₁₀ -f^t ₁₀ =[a^t ₁₀ ],

т. е. а₁₀ уменьшается по крайней мере до ближайшего целого. Поэтому а₁₀ либо будет оставаться некоторым фиксированным целым числом, либо после конечного числа шагов станет отрица­тельным. Если а₁₀ станет отрицательным, то первая строка будет ведущей и

α₀ ^t+1 =α^t ₀ -a₁₀ /a_1s *α^t _s ,

Из того, что α^t _s > 0 и a_{1 s} <. О, следует, что a_{0 s} > 0, т. е. зна­чение a₀₀ строго уменьшится, что противоречит допущению о неиз­менности значения a₀₀ . Если a_{1 j} ≥ 0 для всех j = 1, . . ., s, ... . . ., n, то задача не имеет допустимых решений. (Заметьте, что ведущий элемент должен быть отрицательным.)

Таким образом, остается единственная возможность—а₁₀ через конечное число шагов должно стать некоторым неотрица­тельным целым числом и больше не меняться.

Аналогичные рассуждения можно провести и для остальных компонент вплоть до (n+m)-й, что завершит доказательство конечности. Заметим, что нам надо, чтобы только первые n + 1 компонент вектора α₀ были целыми неотрицательными числами, a₀₀ <> 0 и a_ij (i = n+1,…..,n+m) — неотрицательные.

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

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

ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Здесь будет описан другой алгоритм для решения задач целочисленного программирования. Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элементы. Подобно двойственному симплекс-мето­ду, алгоритм начинает работать с двойственно допустимой таблицы. Если а_i0 (i = 1, . . ., n+m) — неотрицательные целые, то зада­ча решена. Если для какой-нибудь строки а_i0 < 0, то составляется новое уравнение и записывается внизу таблицы. Эта строка затем служит ведущей. После этого используется двойственный сим­плекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен —1. Введенная таким образом ведущая строка сохранит таблицу целочисленной. Заме­тим, что в предыдущем алгоритме в качестве производящей строки выбиралась строка с нецелым а_i0 . В данном случае производящей строкой становится строка с отрицательным а_i0.

Пусть дана задача целочисленного линейного программи­рования:

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

при условиях

(1)

Условия (1) могут быть записаны как

(2)

Предположим, что для t = 0 (т. е. для исходной таблицы) все а_ij — целые и столбцы α_j (j = 1, . . ., n) — лексикографиче­ски положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосхо­дящее х. Для любого числа у (положительного или отрицатель­ного) и положительного λ можно записать

(3)

где 0≤r_y < λ (r_y — неотрицательный остаток от деления нацело у на λ). В частности, 1 = [1/ λ ]λ + г. Поэтому если λ> 1, то [1/λ] = 0 и г = 1. Если λ = 1, то [1/λ,] = 1 и г == 0.

Так же как и ранее, вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (1). Рас­смотрим некоторое уравнение в t-таблице (опуская индекс строки) с a₀ < 0:

(4)

где х — соответствующая компонента вектора х, a x^t _j — текущие небазисные переменные. Можно выразить x, a₀ и а_j , используя введенное выше представление (З):

(5) и (6)

(j=0,1….,n)

Подставив выражения (5) и (6) в (4), и переставив члены, получим

(7)

Поскольку r_j ≥0, r≥0 и на переменные х и x^t _j наложено требование неотрицательности, левая часть уравнения (7) всегда неотрицательна. Рассмотрим выражение в правой части, заклю­ченное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требо­ванию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т. е.

(8)

Целочисленная слабая переменная s является неотрицатель­ной. Действительно, если бы s было отрицательным, т. е. прини­мало значения —1, —2, . . ., то умножение на λ (λ > r₀ ) сделало бы всю правую часть уравнения (7) отрицательной, в то время как левая часть неотрицательна.

Рассмотрим два случая λ=1 и λ>1. Подставляя в уравнение (8) выражение для x из (4), получим:

S=[a₀ ]+∑[a_j ] (-x^t _j )-{a₀ +∑a_j (-x^t _j )}=-f₀ -∑f_j (-x^t _j ). (9)

Полученное уравнение есть не что иное, как отсечение Гомори. Для λ>1 имеем [1/λ]=0[2] и уравнение (8) приобретает вид

(10)

Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если а₀ < О,. то [a₀ /λ] < 0 в уравнении (10). Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном сим­плекс-методе. В частности, всегда можно выбрать λ достаточно большим, так чтобы ведущий элемент [a_j /λ] в строке (10) стал:

равным —1, что позволит сохранить целочисленность таблицы. Выбор соответствующего λ будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве началь­ного необходимо взять двойственно допустимое решение, которое-можно получить добавлением ограничения x_{n + m+1} = М — x₁ — ... ... —x_n , где М — достаточно большая константа, и про­ведением одной итерации с добавленной строкой и с лексикогра­фически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов.

Ш а г 0. Начать с двойственно допустимой матрицы А° в урав­нении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А° может содержать и нецелые элементы).

Шаг 1. Среди строк с а_i0 < 0 (i = 1, . . ., n+m) выбрать строку с наименьшим значением i; эта строка станет производя­щей. (Если а_i0 ≥ 0 (i= 1, . . ., n + m), то задача решена.)

Ш а г 2. Выбрать λ > 0 (правило выбора будет описано даль­ше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Ш а г 3. Провести шаг двойственного симплекс-метода, вычерк­нуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности. Доказательство конечности про­водится в предположении, что существует нижняя граница целевой функции x₀ . Использование двойственного метода гарантирует выполнение условия

Если a₀₀ уменьшается, то уменьшается на целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов a₀₀ станет меньше x₀ . Если алгоритм бесконечен, то a₀₀ должно оставаться Неизменным для всех t > to. Рассмотрим тогда компоненту a₁₀ , столбца α₀ . Если a₁₀ уменьшается, то на целое число. Когда a₁₀ становится отрицательным, первая строка должна быть выбрана в качестве производящей. Если а_{1 j} < О для всех j, то задача неразрешима.

Теперь опишем правило выбора λ в шаге 2 полностью цело­численного алгоритма. Пусть производящая строка имеет вид

и дополнительная строка

Для любого а_j <0 всегда можно выбрать λ достаточно большим, чтобы [a_j /λ]|==—1. Согласно лексикографическому двойственному симплекс-методу, ведущий столбец α_s выбирается по правилу

Поскольку [a_s /λ]=-1 и [a_j /λ] – отрицательные числа, т.е. -1, -2,…….., -μ_j , имеем

(11)

Таким образом, α_s должен быть лексикографически минималь­ным столбцом. Последнее означает, что среди всевозможных столбцов (с a_vj < 0) ведущий столбец должен быть лексикографи­чески минимальным вне зависимости от того, какое значение λ выбирается.

Теперь рассмотрим два значения К, при каждом из которых выполняется условие [a_s /λ₁ ]=—l и [a_s /λ₂ ]=—l. Столбец α₀ изменяется следующим образом:

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

Шаг 0. Пусть строка с номером v является производящей.

Шаг 1. Пусть α_s , — лексикографически минимальный стол­бец среди столбцов с α_vj < 0.

Шаг 2. Для каждого с α_vj < 0 , пусть μ_i —наибольшее целое, такое ,что α_s <α_j /μ_j

Шаг 3. Пусть [μ_j =-a_vj /λ_j ]. Тогда

Шаг 4. Положить λ = max λ_j для а_vj < 0.

Правило выбора λ, описанное выше, позволяет сделать веду­щий элемент равным —1, при этом будет сохраняться двойствен­ная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться. Следует заметить, что отсечение Гомори не является самым «сильным» возможным неравенством. Оно также может быть «сильнее» или «слабее» самого производящего неравенства. Например, пусть производя­щей строкой будет

X= -4-3 (-x₁ ) – 5 (-x₂ ) (12)

Если использовать λ=2, то получим отсечение

S= -2-2 (-x₁ ) – 3 (-x₂ )≥0 (13)

Для λ=3 имеем

S= -2-1 (-x₁ ) – 2 (-x₂ )≥0 (14)

Для λ=4

S=-1-1 (-x₁ )-2 (-x₂ )≥0 (15)

Как видно, неравенство (14) сильнее, чем (12), (12) сильнее, чем (13), а (13) сильнее, чем (15).

Другое замечание касается того, что если величина λ, полу­чаемая указанным выше способом, может быть увеличена так, чтобы [a₀ /λ] и [a_j /λ] (а_j > 0) оставались без изменения, то отсече­ние Гомори можно усилить, несмотря на то, что нулевой столбец -уменьшится на ту же величину.

Выпишем производящую строку

Чем больше величина λ, тем меньше абсолютная величина коэффи­циентов отсечения. Естественно, что мы хотели бы иметь абсо­лютную величину [a₀ /λ] большой, а абсолютные величины [a_j /λ] — малыми. Если значение λ (полученное по приведенному выше правилу) может быть увеличено так, чтобы значения [a_j /λ [] и [a₀ /λ] не изменялись, то используется большее значение для λ. Тем самым по возможности уменьшится абсолютная величина [a_j /λ] для некоторых j, и отсечение станет сильнее.

Например, пусть целевая функция имеет вид

X₀ = - 20 – x₁ - 2x₂ – 3x₂ – x₄ ,

И производящая строка

X= -20+ (-7) (-x₁ )+ (-8) (-x₂ )+ (-15) (-x₃ )+18 (-x₄ ).

Используя описанную выше процедуру выбора λ, получим λ = 7. Соответствующее отсечение

s = -3 + x₁ + 2x₂ + Зx₃ — 2x₄ ≥ 0.

Если использовать λ = 9 вместо λ = 7, получим отсечение

s* = -3 + x₁ + x₂ + 2x₃ — 2x₄ ≥ О,

являющееся более сильным .

Интересная особенность полностью целочисленного алгоритма состоит в том, что для его использования не обязательно требовать целочисленности всех а_ij . Пусть задача целочисленного програм­мирования имеет вид

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

при условиях

x_n+i = a_i0 - ∑a_ij x_j ≥0 (i=1,………,m)

x_j ≥0 (j=1,…….,n)

где a ₀₀ и c_j — целые, а_i0 о и а_ij могут быть произвольными действи­тельными числами. Таблица 14.1 содержит в первых n + 1 строках только целые числа.

Выпишем произвольную производящую строку (опуская обо­значение строки)

Вне зависимости от того, являются ли a₀ и a_j целыми ли действительными, коэффициенты отсечения сегда целые, а ведущий элемент равен —1. В результате итера­ции с таким ведущим элементом первые n+1 строк таблицы останутся целочисленными. Заметим, что переменная s — неотри­цательная целая. В силу приведенных рассуждений доказатель­ство конечности в данном случае мало чем отличается от описан­ного выше. Когда в нулевом столбце a_{i 0} == 1, . . ., n)становятся неотрицательными целыми, а остальные элементы нулевого столб­ца — неотрицательными, то получается оптимальное решение.

В последних главах были обсуждены два алгоритма целочис­ленного программирования, первый из которых называется цик­лическим алгоритмом (λ = 1), а второй — полностью целочис­ленным (λ > 1).

Задача о рюкзаке

Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.

Модель задачи примет вид:

при ограничениях на вместимости отсеков

условии неотрицательности

условии целочисленности

- целые .

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

.

Задача о назначении

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

Математическая модель задачи примет вид:

Каждый исполнитель назначается только на одну работу:

На каждую работу назначается только один исполнитель:

Условия неотрицательности и целочисленности

, .

Задача коммивояжера

Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

Математическая модель задачи:

Условия неотрицательности и целочисленности

, .

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

Заключение .

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

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

Список использованной литературы:

1. А.Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.

2. Т.Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.

3. А.В.Кузнецов, В.А.Сакович, Н.И.Холод. Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.

4. В.Г.Карманов. Математическое программирование: Учебное пособие – 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.

5. Е.Г.Белоусов. Введение в выпуклый анализ и целочисленное программирование. М.:Издательство МГУ, 1977г.

6. В.В. Федосеев, А.Н.Гармаш, Д.М.Дайитбегов.: Экономико-математические методы и прикладные модели: Учеб.пособие для вузов/ЮНИТИ, 1999г.-391с.

7. Н.Ш. Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; под ред. Проф.Н.Ш.Кремера. : Исследование операций в экономике; учеб. Пособие для вузов.

[1] Символ (≡) означает «сравнимость».

[2]