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

Автор: Пользователь скрыл имя, 02 Декабря 2012 в 18:56, курсовая работа

Краткое описание

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

Оглавление

Введение.
1.Целочисленное программирование. Общие понятия.
2.Метод Гомори.
3.Метод ветвей и границ.
4.Циклический алгоритм целочисленного программирования.
5.Полностью целочисленный алгоритм.
6.Задача о рюкзаке.
7.Задача о назначении.
8.Задача коммивояжера.
Заключение.
Список используемой литературы.

Файлы: 1 файл

курс.doc

— 258.50 Кб (Скачать)

Введение. 
 
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, а также при дополнительном условии  

 
(7.4)

 
х— целые числа.  
 
В некоторых случаях условие (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] и [arj] - целые части, a qt, qr] - дробные части чисел аrи arj. 
 
Например, 37/=12 +1/3, так как [37/3] = 12, a -s/, = -3 + 1/3„ так как [-8/3] = -3. 
 
Из уравнения (7.5) найдем хr 
 
xrr0-  
 
Теперь числа аю и аrj заменим суммами целых и дробных частей: 
 
 
x=  
 
 
Предположим, что все x- целые числа. Тогда разность 
 
 
является целым числом. 
 
Чтобы оказалось целым числом и хr, необходима целочисленность разности 
 
 
Но О<qг<1, 0<g< i="">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) = х1 
- Зх2 + 5х3 + 2х4 -max 
 
при условия 
 
x1+x2+x3 
=15 
 
2x1+ 3x3+x4=8, 
 
хj, > 0, хj 
— целые числа, j = 1, 2, 3, 4. 
 
Решение. Пошаговое решение задачи приведено в табл. 7.1 
 
Таблица 7.1 
 
 
 
 
 
 
 
 
 
 
Оптимальный план задачи без условия целочисленности 
 
X = (0, 37/3, 8/3, 0)- для дальнейшего решения задачи к таблице оптимального плана добавлено условие 
 
-2/3x1-1/3x4≤-2/3. 
 
 
Номер индекса г выбран из условия большей дробной части компоненты аi0. Имеем г = 2; j = 0: [8/3] = 2, 2 – 8/3 = -
2/3; j=1: [2/31 = О, О - 2/3 -2/3; j = 2: [0] = 0, 0 - 0 = 0; j = 3: [0]= 0, 0 - 0 = 0; j 4: [1/3] = 0, 0 — 1/3 = -1/3. Сделав один шаг (в общем случае для получения целочисленного решения одной итерации, конечно, недостаточно) метода последовательного уточнения оценок, получили оптимальный план целочисленной задачи Х*= (О, 13, 2, 2) 
 
Трудоемкость решения целочисленной задачи обусловлена вводом новых добавочных ограничений и новых переменных. В связи с этим необходимо придерживаться следующего правила, позволяющего при определенных условиях сокращать текущие таблицы. Дополнительная переменная хп+1 
вводится в процессе решения с добавочным ограничением как базисная переменная очередного псевдоплана и сразу, на этой же итерации, переводится в число небазисных компонент. Если на дальнейших итерациях, согласно правилу преобразования таблицы, переменная хп+1 снова окажется базисной, ее значение станет несущественным для основных переменных задачи, так что строка и столбец текущей таблицы, отвечающие хп+] вычеркиваются. Правило сокращения таблиц ограничивает их размеры: не более n строк и не более (2n -m) столбцов. 
 
Рассматриваемый алгоритм целочисленного программирования сводится к методу последовательного уточнения оценок с дополнительными правилами расширения и сокращения текущей таблицы решения задачи. 
 
Пример 2. Получить целочисленный оптимальный план задачи 
 
Z(X) = x1— 4х2 
— 2х3 + Зх4 —> max при условиях 
 
3x1+x2+8x3+x4=35 
 
x1 
+x3+x4≤6 
 
xj≥ 0, хj 
— целые числа, j = 1, 2, 3, 4. 
 
 
Решение. Пошаговое решение задачи приведено в табл. 7.2. 
 
 
Таблица 7.2 
 
 
На шаге 2 решения задачи без ограничения целочисленности получаем оптимальный нецелочисленный план 
 
 
X = (0, 0, 29/7, 13/7). 
 
Поскольку обе базисные координаты X нецелочисленны, выбираем любую — первую или вторую — строку таблицы на шаге 2, а именно вторую, и строим добавочное ограничение 
 
-5/7x1-6/7x2-1/7x5+x6=-6/7. 
 
Вводя ограничение добавочной строкой на шаге 2, находим направляющий элемент в этой строке: 
 
 
Осуществляя преобразование табл. 7.2 с направляющим элементом (-5/7), получаем на шаге 3 оптимальный план новой задачи, снова нецелочисленный. На шаге 3 добавляем очередное условие, получаем четыре строки ограничений. Поскольку на шаге 3 достигается 
 
в столбце А6, то х6 
становится базисной переменной на шаге 4. В соответствии с правилом сокращения таблицы на шаге 4 вычеркиваем строку и столбец, соответствующие х6, добавляем новую строку, а на шаге 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
0) = £(D), то Х° = Xявляется решением задачи. Если указанное условие не выполняется, то возможно разбиение (ветвление) множества D на конечное число непересекающихся подмножеств D1i: ỤD1i. = D, ∩D1= Ө, и вычисление оценки £(D1i) (границ), 1≤i≤m (рис 7.1) 
 
 
 
Рис. 7.1 
 
Если для некоторого плана X
1е Di1, 1 ≤ / ≤ m выполняется условие f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m то Xk1=Xявляется оптимальным планом (решением) задачи (7.9)-(7.10).  
 
Если такого плана нет, то выбирается подмножество Dk
с наибольшей оценкой £(D1i): 
 
 
и разбивается на конечное число непересекающихся подмножеств 
 
D
2kj: UD2kj=D1k, ∩D2kj=Ө. Для каждого подмножества находится оценка £(D2kj), 1≤j≤n (рис 7.2) 
 
 
(рис. 7.2). 
 
 
 
Если при этом найдется план X
2е D2kJ, 1 ≤j ≤n, такой, что f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, то X2r= X* является решением задачи (7.9)-(7.10). Если такого плана нет, то процедуру ветвления осуществляют для множества D2kj с наибольшей оценкой £(D2kj) , 1≤j≤n . Способ ветвления определяется спецификой конкретной задачи. 
 
Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования. 
 
Пример. 
 
 
Контейнер объемом 5 м
помещен на контейнеровоз грузоподъемностью 12 т. Контейнер требуется заполнить грузом двух наименований. Масса единицы груза mj (в тоннах), объем единицы груза Vj (в м3), стоимости Cj (в условных денежных единицах) приведены в табл. 7.3. 
 
Таблица 7.3 

 
Вид груза у 

 
m

 
V

 
С

 

 

 

 
10 

 

 

 

 
12 


 
Требуется загрузить  контейнер таким  образом, чтобы стоимость  перевозимого груза была максимальной. 
 
Решение. Математическая модель задачи имеет вид 
 
Z(X) = 10x1+12x2→max, (7.11) 
 
3x1+x2≤12, 
 
x1+2x2≤5 
 
x1≥0 (7.12) 
 
 
x2≥0 
 
x1, x2- целые числа (7.13) 
 
 
где x1, x2 
- число единиц соответственно первого и второго груза. 
 
Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (рис. 7.3). 
 
 
 
Рис. 7.3 
 
Сначала решаем задачу (7.11)—(7.13) без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптимальном плане Х° = (
19/5, 3/5): 
 
ТочкаXнеявляется оптимальным планом задачи (7.1 1)— (7.13). Поэтому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x1=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D
1и D22. Линии x1=3 (L3) и x4= (L3) являются линиями разбиения.

 

 

 
L\

 
 
 
Рис. 7.4 
 
 
Найдем оценки £(D
11) и £(D12), для чего решим задачи линейного программирования 
 
Z(X)=10x1+12x2→max, 
 
 
 
3x1+x2≤12 
 
x1+2x2≤5 
 
x1≤3 
 
x1≥0, x2 
– целые числа 
 
 
Z(X)=10x1+12x2→max, 
 
 
3x1+ x2≤12 
 
x1+2x2≤5 
 
x1≥4 
 
x1≥0, x2 
– целые числа 
 
 
Например, графическим методом: 
 
X
11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40. 
 
Результат ветвления приведен на рис. 7.5

 

 

 
Рис. 7.5

 
 
 
 
План 
X0удовлетворяет условиям задачи (7.11)-(7.13), и для него выполняется условие: Z(X11)= £(D11)=42 > 
 
 
£(/)/) = 42 >£(D
12) = 40. Следовательно, план X°1= (3, 1) является решением задачи (7.11)-(7.13),  
 
т.е. надо взять три единицы первого груза и одну единицу второго груза. 
 
 
Алгоритм метода ветвей и границ

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

 
 
ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ 
 
 
Рассмотрим следующую задачу линейного программирования: 
 
Максимизировать 
 
X0=a00-a01x1-a02x2-……..-a0nxn, 
 
при условии 
 
xn+1=an+1,0-an+1,1x1-an+1,2x2-…….-an+1,nxn, 
 

 

 
 
xn+m=an+m,0- an+m,1x1-an+m,2x2-…….-an+m,nxn, 
 
xj≥0 (j=1,…….,n+1,…….,n+m). 
 
 
Заметим, что xn+1, 
. ., хn+m — слабые переменные, a x1 ... ., х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=—(—Xj) (j'=1, ...,n), а задача в матричной форме принимает вид 
 
х = А (-хn), (2) 
 
где х — вектор-столбец с компонентами 
Х0, x1, . . ., xn, xn+1, . . .,xn+m А — соответствующая матрица размера (п т + 1) * (n + 1) и (—хn) — вектор с компонентами (1, —x1,—x2, . . ., —xn), представляющими собой небазисные переменные исходной таблицы. Задачу целочисленного программирования также можно записать в виде таблицы.  
 
Причины представления переменных в виде (—x1), (—x2, . . . 
. . ., (—xn)) — чисто исторические, но это стало обычной практикой в целочисленном программировании. Будем использовать αj(j 0, 1, . . ., п) для обозначения j-го столбца текущей таблицы и aij (i = 0, 1, . . ., п т; j = 0, 1, . . ., n) для обозначения элемента 1-й строки и 7-го столбца таблицы. Предполагается, что все a,ij в исходной таблице целые. Следовательно, все слабые переменные xn+1, . . ., Хn+mдолжны быть также неотрицательными целыми числами. 
 
При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочисленного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма аij≥0 
(i = 1, ... . . ., п т) и a0j≥ 0 (j' = 1, . . ., n). (Для получения исходного двойственного допустимого решения введем дополнительное ограничение xn+m+1 == М — X1 —x2 — . . . — xn≥ 0, где M — достаточно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если аi0≥ 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если аi0≥ 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е. аi0<О для == п т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi0≥ 0. Если аi0 получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi0 (i = 1, . . ., n, . . ., n + m) не станут все целыми и неотрицательными. 
 
Если после введения дополнительного ограничения текущая таблица перестает быть прямо допустимой, то текущее решение, представляющее собой вершину многогранника решений, не удовлетворяет этому дополнительному ограничению. Другими словами, дополнительное ограничение отсекает часть пространства решений. Если дополнительные ограничения не отсекают ни одной целочисленной точки пространства решений исходной задачи, то, вполне вероятно, после введения достаточного числа дополнительных ограничений вершины суженного множества решений будут целочисленными. Тогда, используя симплекс-метод, можно получить оптимальное целочисленное решение. Трудность состоит в систематическом получении дополнительных ограничений и доказательстве конечности алгоритма. 
 
Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таблица также меняется. Будем использовать 
для обозначения t-й. таблицы. Матричное уравнение (2) запишется как 
 
Х
= А(-хtn), (3) 
 
где х° — вектор-столбец с n + 
т + 1 компонентами, А° — матрица размера (п + т + 1)*(n + 1) и (—х0n) — вектор с компонентами (1, —x1, . . ., —xn), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а0i≥0 (j = 1, . . ., n), а00 ≡ 0 (mod 1) 1и аi0 ≥ 0 (i=1, . . ., п+т) — целые неотрицательные числа, то получено оптимальное решение целочисленной задачи. Если аi0 не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (3), в котором аi0m нецелое. Опуская индексы строки, имеем 
 
(4) x=a0+∑aj(-xj) 
 
 
где xj 
в правой части — текущие небазисные переменные и a0 — нецелое. Поскольку требуется, чтобы х было целым, или х 10 (mod1), правая часть уравнения (4) также должна удовлетворять условию 
 
0≡a0+∑aj(-xj) (mod1). (5) 
 
Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы xj 
,были целыми, можно алгебраически складывать с (5) отношения 0≡f0+∑jfi(-xi) (mod1) (0<f0<1, 0≤fj<1). (6) 
 
Условие (6) эквивалентно следующему: 
 
∑fjxj≡f0 
(mod1). (7) 
 
В соотношении (7) f0 
– константа, меньшая единицы ,и поскольку fj≥0 и xj≥, левая часть всегда положительна. Т.к. (7) – отношение сравнения по модулю 1, левая часть может принрмать только значения вида f0, f0+1,……, т.е. 
 
∑fjxj≥f0 
(8) 
 
Неравенство (8) можно представить в виде уравнения с помощью введения неотрицательной целочисленности слабой переменной 
 
S=-f0+∑fjxj≥0. (9) 
 
Это уравнение можно приписать внизу таблицы и использовать в качестве ведущей строки. Таким образом, переменная s войдет в базис с отрицательным значением (—fо)- После итерации слабая переменная s станет небазисной с нулевым значением. Ведущая строка превратится в тождество s ≡ (—1) (—s) и может быть исключена. Будем называть переменную s в уравнении (9) слабой переменной Гомори. Ниже будет обсуждено, что произойдет, если сохранять все дополнительные строки, соответствующие слабым переменным Гомори. 
 
Дадим доказательство конечности алгоритма. Доказательство будет проведено в предположении, что известна некоторая нижняя граница значения Х0, т. е. если существует целочисленное решение, то оно больше, чем наперед заданная величина М (М может быть достаточно большой по абсолютной величине отрицательной константой). Такое предположение не слишком обременительно и всегда выполняется, если выпуклое множество, определяемое условиями (2), ограничено. Сначала изложим сам алгоритм. 
 
Шаг 1. Решить задачу целочисленного программирования так, как если бы это была линейная программа, т. е. с помощью прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то ai0≥0 (i=1, . . ., m + n) и a0i≥0(j = 1, . . ., n). Требуется также, чтобы а
t> 0 (j = 1, . . ., n). 
 
 
Шаг 2. Если аi0 
— все целые, то задача решена, и решение получено без использования дополнительных ограничений. В противном случае пусть аti0 — первая нецелочисленная компонента в αt0. Тогда i-я строка называется производящей строкой. Записать внизу таблицы уравнение 
 
 
s=-f
ti0-∑ftij(-xtj). (10) 
 
 
Уравнение (10) называется отсечением Гомори. Проделать шаг двойственного симплекс-метода, используя в качестве ведущей строки отсечение Гомори (10). При этом таблица останется двойственно допустимой. Повторять до тех пор, пока все аi0 
(i = 1, . . ., m+n) не станут целыми неотрицательными. Если аi0 на некотором шаге остается отрицательным, следующий шаг двойственного метода производится без введения отсечения Гомори. (Если аi0становится отрицательным, нулевая строка не выбирается в качестве производящей. Если a00 становится нецелым, следует выбрать нулевую строку в качестве производящей.) 
 
Изменение элементов аij 
(i = 0, 1, . . ., n+m; j = 0, . . . . . ., n) в таблице за одну итерацию называется циклом. Для обозначения циклов используется буква t. Для доказательства конечности не достаточно условий αt>α0 t+1 >М, поскольку a00 может изменяться каждый раз на ε(t), а ∑ ε (t) = с. 
 
Примером этого может служить ε (t) =1/2t. Другой возможностью является то, что а00 
остается равным фиксированному значению, большему нижней границы, в то время как некоторое аi0 неограниченно уменьшается. Чтобы увидеть, как преодолеваются эти трудности, необходимо в деталях рассмотреть шаги итерации. 
 
При доказательстве будет показано, что либо после конечного числа шагов все компоненты 0-го столбца становятся неотрицательными целыми, либо не существует целого решения. Если a00 
остается постоянным для всех t ≥ t0, то at00 должно быть целым. 
 
Предположим, что а
t00—нецелое. Пусть аt00 =nt00+ft00,где nt00— целое и 0 < ft00 < 1. Тогда 0-я строка становится производящей и требуется ввести дополнительное ограничение 
 
 
S=-f
t00-∑ft0(-xtj). 
 
Если s-й столбец является ведущим, то 
 
 
a
t+100=at00-at0s* ft00/ftos 
 
или 
 
 
 
Другими словами, a00 
уменьшится по крайней мере до ближайшего целого. Следовательно, a00 не может уменьшаться на ε(t) при 
 
∑ε (t)<c 
 
 
Если a00 
каждый раз уменьшается до ближайшего целого или на целую величину, то после конечного числа шагов оно станет меньше любого наперед заданного М (М — предполагаемая нижняя граница). Если алгоритм бесконечен, то a00 должно оставаться некоторым фиксированным целым числом для t> t0. Предположим, что это произошло. 
 
Тогда рассмотрим а10 
. Так же как и a00, a10 не может оставаться нецелым значением. Если бы это было так, то, поскольку a00 — целое, первая строка стала бы производящей и после введения отсечения Гомори и итерации симплекс-метода мы получили бы 
 
 
A
t+110=at10-at1s*ft10/ft1s, 
 
 
где 0<f
t1s<ft1s<1. Здесь at1s —неотрицательное число, большее ft1s. (Если at1s—отрицательно и αts—лексикографически положителен, то аt0s положительно и, следовательно, аt00 не может 
 
не измениться.) Отсюда 
 
 
at+1
10≤at10-ft10=[at10], 
 
 
т. е. а
10 уменьшается по крайней мере до ближайшего целого. Поэтому а10 либо будет оставаться некоторым фиксированным целым числом, либо после конечного числа шагов станет отрицательным. Если а10 станет отрицательным, то первая строка будет ведущей и 
 
 
α
0t+1=αt0-a10/a1s*αts
 
 
Из того, что αt
> 0 и a1s <. О, следует, что a0s > 0, т. е. значение a00 строго уменьшится, что противоречит допущению о неизменности значения a00. Если a1j≥ 0 для всех j = 1, . . ., s, ... . . ., n, то задача не имеет допустимых решений. (Заметьте, что ведущий элемент должен быть отрицательным.) 
 
Таким образом, остается единственная возможность—а
10 через конечное число шагов должно стать некоторым неотрицательным целым числом и больше не меняться. 
 
Аналогичные рассуждения можно провести и для остальных компонент вплоть до (n+m)-й, что завершит доказательство конечности. Заметим, что нам надо, чтобы только первые n + 1 компонент вектора α
были целыми неотрицательными числами, a00 <> 0 и aij (i = n+1,…..,n+m) — неотрицательные. 
 
Причем, если неравенства выразить через исходные небазисные переменные, они будут иметь целые коэффициенты. 
 
Если сохранять все строки, соответствующие слабым переменным Гомори, то эти слабые переменные могут становиться базисными, после того как они были небазисными. Если слабая переменная Гомори вошла в базис с неотрицательным значением, то соответствующая строка представляет собой неравенство, справедливое при текущем решении, и эта строка может быть вычеркнута. Если слабая переменная Гомори становится базисной с отрицательным значением, соответствующую строку следует использовать в качестве ведущей. Если сохранять все строки, соответствующие всем отсечениям Гомори, то, вообще говоря, потребуется меньшее число дополнительных ограничений, однако увеличение таблицы много более неприятно, чем введение лишних дополнительных ограничений. 
 


 

 

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

  1.  
    А.Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.
  2.  
    Т.Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.
  3.  
    А.В.Кузнецов, В.А.Сакович, Н.И.Холод. Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.
  4.  
    В.Г.Карманов. Математическое программирование: Учебное пособие – 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.
  5.  
    Е.Г.Белоусов. Введение в выпуклый анализ и целочисленное программирование. М.:Издательство МГУ, 1977г.
  6.  
    В.В. Федосеев, А.Н.Гармаш, Д.М.Дайитбегов.: Экономико-математические методы и прикладные модели: Учеб.пособие для вузов/ЮНИТИ, 1999г.-391с.
  7.  
    Н.Ш. Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; под ред. Проф.Н.Ш.Кремера. : Исследование операций в экономике; учеб. Пособие для вузов. 

5. Специальные задачи линейного программирования 
 
План: 
 
А) Целочисленное программирование 
 
В данном пункте плана рассмотреть следующие вопросы: 
 
- формулирование в Древней Греции Диофантом (II-III вв.) уравнения, в котором искомые переменные целые; 
 
- какие задачи называют задачами целочисленного программирования; 
 
- какую задачу называют целочисленной задачей линейного программирования, а какую – целочисленной задачей нелинейного программирования; 
 
- привести примеры задач целочисленного или дискретного программирования; 
 
- в каком случае задачу называют полностью целочисленной, а в каком – частично целочисленной; 
 
- методы отсечений и методы возврата, метод ветвей и границ; 
 
Б) ^ Метод ветвей и границ 
 
В данном пункте плана рассмотреть следующие вопросы: 
 
- какая задача называется непрерывной; 
 
- методом ветвей и границ решить задачу:  
 
 
 
После получения нецелочисленного решения составить две новые задачи с различными граничными условиями. 
 
В) ^ Задача выбора вариантов 
 
В данном пункте плана рассмотреть следующие вопросы: 
 
- какие переменные называют булевыми, в честь кого они получили такое название; 
 
- составить математическую модель и решить задачу выбора вариантов: 
 
Для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл.) 
 
Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трёх ( ).

 
Показатели

 
Варианты

 
Наличие

 
1

 
2

 
3

 
4

 
Прибыль, д. е./ед.

 
65

 
80

 
90

 
210

 
-

 
Материальные ресурсы

 
200

 
180

 
240

 
250

 
800

 
Трудовые ресурсы

 
10

 
15

 
22

 
28

 
50


 


Информация о работе Целочисленное программирование