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

Сыктывкарский Государственный Университет

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

По теме: «Некоторые экономические задачи целочисленного программирования»

Сыктывкар 2010г.

План

Введение

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

1.1 Постановка задачи целочисленного программирования

2. Методы решения задач целочисленного программирования

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

2.2 Метод Гомори

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

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

Заключение

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

Ведение

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

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

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

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

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

Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочисленными переменными, общая задача формулируется следующим образом: найти тах{сх|Ах ? b; х - целочисленный}. ЦЛП может рассматриваться так же, как поиск точки решетки, принадлежащей многограннику или как решение системы линейных уравнений с целыми неотрицательными переменными. Иными словами, в ЦЛП рассматриваются совместные ограничения - не отрицательность и целочисленность.

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

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

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

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

1.1 Постановка задачи целочисленного программирования

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

Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x₁,x₂,...,x_n), при котором линейная функция

(1)

принимает максимальное или минимальное значение при ограничениях

=b_i, i=1, 2…, m. (2)

х_j 0, j=1, 2,..., п. (3)

x_j - целые числа (4)

2. Методы решения задач целочисленного программирования

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

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

Несостоятельность метода округления как общего метода решения задач целочисленного программирования обусловлена не только возможностью получения неоптимального решения. Дело заключается в том, что многие задачи математического программирования, не имеющие на первый взгляд никакого отношения к полностью или частично целочисленным задачам, могут быть сформулированы как задачи целочисленного программирования, в которых переменные модели принимают значения из множества {0, 1}. В этой ситуации процедура округления является логически неприемлемой.

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

а) оно содержит все точки множества G, координаты которых удовлетворяют требованию целочисленности;

б) оно является выпуклым множеством;

в) координаты всех его крайних точек удовлетворяют требованию целочисленности.

Рис. 1

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

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

Наиболее известным комбинаторным методом является метод ветвей и границ, использующий процедуру решения задачи линейного программирования с ослабленными ограничениями, соответствующей исходной задаче целочисленного программирования. Если оптимальное решение X* задачи линейного программирования с ослабленными ограничениями не удовлетворяет требованию целочисленности (на рисунке 2 этому решению соответствует точка В), то из множества G допустимых решений выделяют два непересекающихся выпуклых подмножества К₁ и К₂, содержащих все допустимые решения из G, удовлетворяющих требованию целочисленности и не содержащих X* (см. рис. 2). Это позволяет заменить рассматриваемую задачу целочисленного программирования совокупностью двух эквивалентных ей задач с множествами допустимых решений К₁ и К₂ соответственно, так как или .

Рис. 2

Комбинаторные методы широко используют для решения задач булева программирования, т.е. для решения полностью целочисленных задач, переменные которых принимают значения из множества {0, 1}. Эти переменные называют булевыми переменными. Свойства булевых переменных позволяют существенно упростить процедуры поиска оптимального решения.

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

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

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

Элемент 3. В результате анализа решения ослабленной задачи в зависимости от специфики метода, как правило, принимается решение, относящееся к задаче-истоку:

а) исключить ее из рассмотрения;

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

в) заменить системой порожденных задач.

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

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

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

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

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

Алгоритм решения:

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X₀. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и F_max = F(X_o).

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

Предполагая, что найденный оптимальный план X₀ не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X₀ дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу + 1. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:

Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:

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

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).

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

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

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

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х₀ задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

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

1. Находят решение задачи линейного программирования (1)-(3).

2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.

3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.

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

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

Проиллюстрируем метод ветвей и границ на примере.

Решить задачу

Z = Зх₁ + х₂ max

при ограничениях:

4x_l + Зх₂ < 18,

x₁ + 2x₂ 6,

0 x₁ 5,

0 x₂ 4,

х₁, x₂ - целые числа.

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z₀ = Z (0; 0) = 0.

I этап. Решая задачу симплексным методом, получим Z_max = 13 при Х₁^*= = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х₁^* дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х₁^*, т.е. 4 < х₁ < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:

Задача 2 Задача 3

Z=3x₁+x₂>max Z=3x₁+x₂>max

при ограничениях: при ограничениях:

4x_l + Зх₂ < 18 4x₁+3x₂<18

x₁ + 2x₂ 6 x₁ + 2x₂ 6

0 x₁ 4 5 x₁ 5

0 x₂ 4 0 x₂ 4

х₁, x₂ - целые числа. х₁, x₂ - целые числа.

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z₀=0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплексным методом. Получим Z_max =14/3 при X₃^*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X₃^*) = 14/3 > Z₀ = 0, по-прежнему сохраняется Z₀ = 0, ибо план нецелочисленный. Так как х₂^* - дробное число, из области решений исключаем полосу 0 < x₂ < 1 и задачу 2 разбиваем на две задачи 4 и 5.

Задача 4 Задача 5

Z=3x₁+x₂>max Z=3x₁+x₂>max

при ограничениях: при ограничениях:

4x_l + Зх₂ < 18 4x_l + Зх₂ < 18

x₁ + 2x₂ 6 x₁ + 2x₂ 6

0 x₁ 4 0 x₁ 4

0 x₂ 0 1 x₂ 4

х₁, x₂ - целые числа. х₁, x₂ - целые числа.

Список задач: 4 и 5. Значение Z₀ = 0.

IV этап. Решаем задачу 4 симплексным методом.

Получим Z_max = 12 при X₄^* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z₀; Z₀ = Z(X₄^*) = 12, ибо план Х₄^* целочисленный.

V этап. Решаем задачу 5 симплексным методом.

Получим Z_max = 12,25 при X₅^* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z ₀ не меняется, т.е. Z₀ = 12, ибо план X₅^* нецелочисленный. Так как х₁^* - дробное, из области решений исключаем полосу 3<x₁<4, и задача 5 разбивается на две задачи: 6 и 7.

Задача 6 Задача 7

Z=3x₁+x₂>max Z=3x₁+x₂>max

при ограничениях: при ограничениях:

4x_l + Зх₂ < 18 4x_l + Зх₂ < 18

x₁ + 2x₂ 6 x₁ + 2x₂ 6

0 x₁ 3 4 x₁ 4

1 x₂ 4 1 x₂ 4

х₁, x₂ - целые числа. х₁, x₂ - целые числа.

Список задач: 6 и 7. Значение Z₀ = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.

Получим, что условия задачи 7 противоречивы (рис. 3).

VII этап. Решаем задачу 6 симплексным методом.

Получим Z_max = 10,5,при X₆^* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как Z(X₆^*) = =10,5 < Z₀ = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X^* = Х₄^* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Z_max = 12.



Рис. 3

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

2.2 Метод Гомори

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

Далее описывается метод отсечений Гомори, дающий алгоритм решения задач целочисленного линейного программирования. Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейного программирования) в канонической форме. Описываемая ниже версия алгоритма предназначена для решения полностью целочисленных задач, т.е. таких, у которых все параметры a_ij, c_j, b_i - целые.

Описание алгоритма.

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

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

2. В оптимальном плане (симплекс-таблице) выбирают строку, в которой целая часть дробного(!) свободного члена (P0) принимает наибольшее значение.

3. Построение для найденной компоненты условия отсечения. Исходя из уравнения по данной строке x_r=P0_r - a_r,1*x₁ - … - a_r,n*x_n в систему ограничений добавляем неравенство, в котором коэффициенты будут дробными частями коэффициентов данного уравнения: {P0_r}-{ a_r,1}*x₁ -… -{ a_r,n}*x_n ?0. Переводим к каноническому виду добавляя новую переменную x_n+1, получим: {P0_r}-{ a_r,1}*x₁ -… -{a_r,n}*x_n+x_n+1 =0 И соответственно добавляем в симплекс-таблицу новый базисный вектор по новой переменной x_n+1.

4. Переход на начало следующей большой итерации.

Замечание:

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

Решить задачу.

Zmin=6*x1 +x2;

при ограничениях:

3*x1 - x2>=92*x1+3*x2=<50- x1+4*x2>=18

x1,x2>=0; x1,x2: целые числа

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

Целевая функция:

S min = 6*x1+1*x2

при ограничениях:3*x1-1*x2>=92*x1+3*x2<=50 -1*x1+4*x2>=18

x1,x2 >=0; - условие не отрицательности переменных.

Решение задачи с использованием метода симплекс-таблиц.

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

Целевая функция: S min = 6*x1+1*x2

при ограничениях: 3*x1-1*x2>=9 2*x1+3*x2<=50 -1*x1+4*x2>=18

x1,x2, >=0; - условие неотрицательности переменных.

Система неравенств приведена к каноническому виду:

Целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Система ограничений: -3*x1+x2+x3=-9 2*x1+3*x2+x4=50 x1-4*x2+x5=-18

Векторный анализ системы ограничений:

Расширенная целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)
-9	-3	1	1	0	0
50	2	3	0	1	0
-18	1	-4	0	0	1

Базис: Базисный вектор №1: P3(x3)

Базисный вектор №2: P4(x4)

Базисный вектор №3: P5(x5)

Расширенная целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Заполним первую таблицу:

№	Base	CBase	P0	6	1	0	0	0
				P1	P2	P3	P4	P5
1	P3	0	-9	-3	1	1	0	0
2	P4	0	50	2	3	0	1	0
3	P5	0	-18	1	-4	0	0	1
S min =	0	-6	-1	0	0	0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P3 (1-я строка) Новый базисный вектор: P1 (1-й столбец) Заменяем базисный вектор P3 на P1.

№	Base	CBase	P0	6	1	0	0	0
				P1	P2	P3	P4	P5
1	P1	6	3	1	-0,3333	-0,3333	0	0
2	P4	0	44	0	3,6667	0,6667	1	0
3	P5	0	-21	0	-3,6667	0,3333	0	1
S min =	18	0	-3	-2	0	0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P5 (3-я строка) Новый базисный вектор: P2 (2-й столбец) Заменяем базисный вектор P5 на P2. 

№	Base	CBase	P0	6	1	0	0	0
				P1	P2	P3	P4	P5
1	P1	6	4,9091	1	0	-0,3636	0	-0,0909
2	P4	0	23	0	0	1	1	1
3	P2	1	5,7273	0	1	-0,0909	0	-0,2727
S min =	35,1818	0	0	-2,2727	0	-0,8182

Решение не целочисленное. Применим метод Гомори: выберем в таблице строку, в которой целая часть дробного свободного члена (P0) принимает наибольшее значение. Макс. целая часть дробного свободного члена при базисном векторе P2 (3-я строка). Составим уравнение ограничения и добавим в таблицу новый базисный вектор по новому уравнению и новой переменной. Добавляем базисный вектор: P6 (6-й столбец).

№	Base	CBase	P0	6	1	0	0	0	0
				P1	P2	P3	P4	P5	P6
1	P1	6	4,9091	1	0	-0,3636	0	-0,0909	0
2	P4	0	23	0	0	1	1	1	0
3	P2	1	5,7273	0	1	-0,0909	0	-0,2727	0
4	P6	0	-0,7273	0	0	-0,9091	0	-0,7273	1
S min =	35,1818	0	0	-2,2727	0	-0,8182	0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P6 (4-я строка) Новый базисный вектор: P5 (5-й столбец) Заменяем базисный вектор P6 на P5.

№	Base	CBase	P0	6	1	0	0	0	0
				P1	P2	P3	P4	P5	P6
1	P1	6	5	1	0	-0,25	0	0	-0,125
2	P4	0	22	0	0	-0,25	1	0	1,375
3	P2	1	6	0	1	0,25	0	0	-0,375
4	P5	0	1	0	0	1,25	0	1	-1,375
S min =	36	0	0	-1,25	0	0	-1,125

Невозможно выбрать столбец замещения, так как нет положительных dj! Получено оптимальное решение! 

Из таблицы получим значения переменных целевой функции:

x1	x2	x3	x4	x5	p6
5	6	0	22	1	0

Целевая функция: S min = 6*5+1*6 И в результате: S min = 36; Задача решена.

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

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

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

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

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

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



Рис. 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), (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), в котором а_i0m нецелое. Опуская индексы строки, имеем

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

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

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

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

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

?f_jx_j?f₀ (mod1). (7)

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

?f_jx_j?f₀ (8)

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

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

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

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

Шаг 1. Решить задачу целочисленного программирования так, как если бы это была линейная программа, т. е. с помощью прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то a_i0?0 (i=1,..., m + n) и a_0i?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_1s -неотрицательное число, большее f^t_1s. (Если a^t_1s-отрицательно и б^t_s-лексикографически положителен, то а^t_0s положительно и, следовательно, а^t₀₀ не может не измениться.) Отсюда

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

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

б₀^t+1=б^t₀-a₁₀/a_1s*б^t_s,

Из того, что б^t_s > 0 и a_1s <. О, следует, что a_0s > 0, т. е. значение a₀₀ строго уменьшится, что противоречит допущению о неизменности значения a₀₀. Если a_1j? 0 для всех j = 1,..., s,......, n, то задача не имеет допустимых решений. (Заметьте, что ведущий элемент должен быть отрицательным.)

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

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

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

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

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

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

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