Здавалка
Главная | Обратная связь

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



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


 

(1) Условия (1) могут быть записаны как (2) Предположим, что для t = 0 (т. е. для исходной таблицы) все аij — целые и столбцы j (j = 1, . . ., n) — лексикографиче­ски положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными. Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосхо­дящее х. Для любого числа у (положительного или отрицатель­ного) и положительного можно записать (3) где 0ry < (ry — неотрицательный остаток от деления нацело у на ). В частности, 1 = [1/ ] + г. Поэтому если > 1, то [1/] = 0 и г = 1. Если = 1, то [1/,] = 1 и г == 0. Так же как и ранее, вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (1). Рас­смотрим некоторое уравнение в t-таблице (опуская индекс строки) с a0 < 0: (4) где х — соответствующая компонента вектора х, a xtj — текущие небазисные переменные. Можно выразить x, a0 и аj, используя введенное выше представление (З): (5) и (6) (j=0,1..,n) Подставив выражения (5) и (6) в (4), и переставив члены, получим (7) Поскольку rj 0, r0 и на переменные х и xt j наложено требование неотрицательности, левая часть уравнения (7) всегда неотрицательна. Рассмотрим выражение в правой части, заклю­ченное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требо­ванию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т. е. (8) Целочисленная слабая переменная s является неотрицатель­ной. Действительно, если бы s было отрицательным, т. е. прини­мало значения —1, —2, . . ., то умножение на ( > r0) сделало бы всю правую часть уравнения (7) отрицательной, в то время как левая часть неотрицательна. Рассмотрим два случая =1 и >1. Подставляя в уравнение (8) выражение для x из (4), получим: S=[a0]+[aj] (-xtj)-{a0 +aj(-xtj)}=-f0-fj (-xtj). (9) Полученное уравнение есть не что иное, как отсечение Гомори. Для >1 имеем [1/]=0[2] и уравнение (8) приобретает вид (10) Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если а0 < О,. то [a0/] < 0 в уравнении (10). Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном сим­плекс-методе. В частности, всегда можно выбрать достаточно большим, так чтобы ведущий элемент [aj /] в строке (10) стал: равным —1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве началь­ного необходимо взять двойственно допустимое решение, которое-можно получить добавлением ограничения xn +m+1 = М — x1 — ... ... —xn, где М — достаточно большая константа, и про­ведением одной итерации с добавленной строкой и с лексикогра­фически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов. Ш а г 0. Начать с двойственно допустимой матрицы А° в урав­нении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А° может содержать и нецелые элементы). Шаг 1. Среди строк с аi0 < 0 (i = 1, . . ., n+m) выбрать строку с наименьшим значением i; эта строка станет производя­щей. (Если аi0 0 (i= 1, . . ., n + m), то задача решена.) Ш а г 2. Выбрать > 0 (правило выбора будет описано даль­ше) и написать внизу таблицы дополнительную строку Эта строка выбирается в качестве ведущей. Ш а г 3. Провести шаг двойственного симплекс-метода, вычерк­нуть дополнительную строку и вернуться к шагу 1. Доказательство конечности. Доказательство конечности про­водится в предположении, что существует нижняя граница целевой функции x0. Использование двойственного метода гарантирует выполнение условия Если a00 уменьшается, то уменьшается на целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов a00 станет меньше x0. Если алгоритм бесконечен, то a00 должно оставаться Неизменным для всех t > to. Рассмотрим тогда компоненту a10 , столбца 0. Если a10 уменьшается, то на целое число. Когда a10 становится отрицательным, первая строка должна быть выбрана в качестве производящей. Если а1j< О для всех j, то задача неразрешима. Теперь опишем правило выбора в шаге 2 полностью цело­численного алгоритма. Пусть производящая строка имеет вид и дополнительная строка Для любого аj<0 всегда можно выбрать достаточно большим, чтобы [aj/]|==—1. Согласно лексикографическому двойственному симплекс-методу, ведущий столбец s выбирается по правилу Поскольку [as/]=-1 и [aj/] – отрицательные числа, т.е. -1, -2,...., -j, имеем (11)

Таким образом, s должен быть лексикографически минималь­ным столбцом. Последнее означает, что среди всевозможных столбцов (с avj < 0) ведущий столбец должен быть лексикографи­чески минимальным вне зависимости от того, какоезначение выбирается. Теперь рассмотрим два значения К, при каждом из которых выполняется условие [a s/1]=—l и [as/2]=—l. Столбец 0 изменяется следующим образом: Следовательно, чем меньше , тем сильнее лексикографически уменьшится нулевой столбец. Значение следует выбирать так, чтобы, во-первых, ведущий элемент стал равным —1 и, во-вторых, чтобы давало максимальное уменьшение столбцу 0. Правило формулируется следующим образом. Шаг 0. Пусть строка с номером v является производящей. Шаг 1. Пусть s, — лексикографически минимальный стол­бец среди столбцов с vj< 0. Шаг 2. Для каждого с vj< 0 , пусть i —наибольшее целое, такое ,что s<j/ j Шаг 3. Пусть [j=-avj/j]. Тогда Шаг 4. Положить = max j для аvj < 0. Правило выбора , описанное выше, позволяет сделать веду­щий элемент равным —1, при этом будет сохраняться двойствен­ная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться. Следует заметить, что отсечение Гомори не является самым «сильным» возможным неравенством. Оно также может быть «сильнее» или «слабее» самого производящего неравенства. Например, пусть производя­щей строкой будет X= -4-3 (-x1) – 5 (-x2) (12) Если использовать =2, то получим отсечение S= -2-2 (-x1) – 3 (-x2)0 (13) Для =3 имеем S= -2-1 (-x1) – 2 (-x2)0 (14) Для =4 S=-1-1 (-x1)-2 (-x2)0 (15) Как видно, неравенство (14) сильнее, чем (12), (12) сильнее, чем (13), а (13) сильнее, чем (15). Другое замечание касается того, что если величина , полу­чаемая указанным выше способом, может быть увеличена так, чтобы [a0/] и [a j/] (аj > 0) оставались без изменения, то отсече­ние Гомори можно усилить, несмотря на то, что нулевой столбец -уменьшится на ту же величину. Выпишем производящую строку Чем больше величина , тем меньше абсолютная величина коэффи­циентов отсечения. Естественно, что мы хотели бы иметь абсо­лютную величину [a0 /] большой, а абсолютные величины [aj/] — малыми. Если значение (полученное по приведенному выше правилу) может быть увеличено так, чтобы значения [aj/ [] и [a0/] не изменялись, то используется большее значение для . Тем самым по возможности уменьшится абсолютная величина [aj/] для некоторых j, и отсечение станет сильнее. Например, пусть целевая функция имеет вид X0= - 20 – x1- 2x2 – 3x2 – x4 , И производящая строка X= -20+ (-7) (-x1)+ (-8) (-x2)+ (-15) (-x3)+18 (-x4).

Используя описанную выше процедуру выбора , получим = 7. Соответствующее отсечение s = -3 + x1 + 2x2 + Зx3 — 2x4 0. Если использовать = 9 вместо = 7, получим отсечение s* = -3 + x1 + x2 + 2x3 — 2x4 О, являющееся более сильным . Интересная особенность полностью целочисленного алгоритма состоит в том, что для его использования не обязательно требовать целочисленности всех аij. Пусть задача целочисленного програм­мирования имеет вид максимизировать при условиях xn+i= ai0 - aijxj 0 (i=1,...,m) xj0 (j=1,...,n) где a 00 и cj — целые, аi0 о и аij могут быть произвольными действи­тельными числами. Таблица 14.1 содержит в первых n + 1 строках только целые числа. Выпишем произвольную производящую строку (опуская обо­значение строки) Вне зависимости от того, являются ли a0 и aj целыми ли действительными, коэффициенты отсечения сегда целые, а ведущий элемент равен —1. В результате итера­ции с таким ведущим элементом первые n+1 строк таблицы останутся целочисленными. Заметим, что переменная s — неотри­цательная целая. В силу приведенных рассуждений доказатель­ство конечности в данном случае мало чем отличается от описан­ного выше. Когда в нулевом столбце ai0 == 1, . . ., n)становятся неотрицательными целыми, а остальные элементы нулевого столб­ца — неотрицательными, то получается оптимальное решение. В последних главах были обсуждены два алгоритма целочис­ленного программирования, первый из которых называется цик­лическим алгоритмом ( = 1), а второй — полностью целочис­ленным ( > 1). Задача о рюкзаке Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.

Модель задачи примет вид: при ограничениях на вместимости отсеков условии неотрицательности условии целочисленности - целые . Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид: . Задача о назначении Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель. Математическая модель задачи примет вид: Каждый исполнитель назначается только на одну работу: На каждую работу назначается только один исполнитель: Условия неотрицательности и целочисленности , . Задача коммивояжера Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути. Математическая модель задачи: Условия неотрицательности и целочисленности , . Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.

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

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

Модель задачи примет вид: при ограничениях на вместимости отсеков условии неотрицательности

условии целочисленности - целые .

 

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

.

 

Можно решать с помощью алгоритмов:

1.1 Точные алгоритмы

1.1.1 Полный перебор

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

1.1.3 Применение метода ветвей и границ

1.2 Приближённые алгоритмы

1.2.1 Жадный алгоритм

1.3 Метаалгоритмы

1.3.1 Генетический алгоритм

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.