1. Постановка и особенности задач дискретного
 Скачать 177.02 Kb.
|
|
Оглавление. Постановка и особенности задач дискретного программировании 4 2. Методы отсечения 7 3. Задача о ранце 15 Метод ветвей и границ Список использованной литературы 31 Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце х годов. Основная задача дискретного программирования – выбор наилучшего варианта из конечного, возможно, очень большого их числа. Возникающие при этом экстремальные задачи имеют ряд особенностей, которые не встречаются в таких стандартных задачах математического программирования, как линейные, выпуклые или многокритериальные задачи. 1. Постановка и особенности задач дискретного программирования Под задачей дискретного программирования дискретной оптимизации) понимается задача математического программирования ) ( ) , , min 0 G x x f x f ∈ = (множество допустимых решений которой конечно, те. ∞ < = ≤ N G 0 , где G - число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать вычислить ( ) N i x f i ,..., 2 , 1 , = , и найти наименьшее значение. Однако такой метод полного перебора при решении задачи реализовать невозможно, так как N может оказаться настолько большим, что этот перебор невыполним на ЭВМ любой мощности. Во многих задачах условия дискретности отделены от других условий, те. если ( ) n x x x x ,..., , 2 1 = , то ( ) j kj j j j j x x x G x ,..., , 2 1 = ∈ , 2 ≥ j k . Поэтому n n j j n j k G N 2 1 1 ≥ = = ∏ ∏ = = , отсюда видно, что с ростом числа переменных объем вычислительной работы резко возрастает. 4 В качестве примера задачи дискретного программирования рассмотрим задачу частично целочисленного линейного программирования – одну из наиболее часто встречающихся в приложении и наиболее изученных задач. Задача формулируется следующим образом, (1.2) i j n j ij b x a ≤ ∑ = 1 , n i ,..., 2 , 1 = , (1.3) 0 ≥ j x , n j ,..., 2 , 1 = (целые, n n j ≤ = 1 ,... 2 , 1 . (Если n n < 1 , то задача называется частично целочисленной, если n n = 1 - полностью целочисленной. Среди задач рассматриваемого класса выделяются задачи с булевыми переменными } n n j x j ≤ = ∈ 1 ,..., 2 , 1 , 1 , 0 Особенности задач Нерегулярность. Дискретные задачи математического программирования входят в класс нерегулярных задач. Регулярные задачи математического программирования характеризуются следующими условиями- для каждой точки G x ∈ можно определить некоторым образом понятие непустой окрестности G G x ⊂ ; - можно указать достаточно эффективно проверяемые необходимые и достаточные условия локальной оптимальности на основании этих условий локальный оптимум целевой функции на G может быть найден при помощи конечного (или бесконечного) сходящегося процесса- локальный оптимум целевой функции совпадает с глобальным К регулярным относятся задачи линейного и выпуклого программирования. К нерегулярным, наряду с дискретными, относятся многоэкстремальные задачи, в которых локальный экстремум может не совпадать с глобальным. Дискретные задачи характеризуются тем, что область допустимых решений невыпукла и несвязна, а это делает невозможным решение их с помощью стандартных методов, применяемых для решения регулярных задач математического программирования. Трудности при определении окрестности В задачах регулярного математического программирования значительная часть методов основана наследующем исходном положении если точки G x ∈ 1 и G x ∈ 2 близки, то значения ( ) 1 x f и ( ) 2 x f также близки. В задачах дискретной оптимизации это положение не имеет места. Поэтому близость двух точек может быть оценена лишь по значениям функции в них. Например, под окрестностью булевого вектора ( ) n x x x x ,..., , 2 будем понимать все векторы, получаемые из x заменой любой единицы нулем или любого нуля единицей. Рассмотрим задачу стремя переменными 3 2 2 1 → + + x C x C x , 2 3 2 1 ≤ + + x x x , 3 2 1 C C < < , { Оптимальное решение очевидно ( ) ( ) 3 2 0 , 1 ; 1 ; 0 C C x f x + = = . Вектор ( ) 0 ; 1 ; 0 1 = x находится в окрестности вектора ( ) 2 1 0 , C x f x = . Ясно, что разность ( ) ( ) 3 1 0 C x f x f = − может быть сделана сколь угодно большой при помощи выбора величины Трудности нахождения допустимого целочисленного плана в задаче (1.2)-(1.5). Предположим, что рассматривается задача частично целочисленного линейного программирования общего вида. Вопрос о существовании допустимого решения сводится к выяснению, разрешима 6 ли система линейных равенств и неравенств в целых неотрицательных числах. Известно, что это трудоемкая вычислительная задача. Поэтому в общей задаче рассматриваемого класса поиск допустимого решения может оказаться столь же трудоемким, как и поиск оптимального решения. Невозможность выполнения большого перебора на ЭВМ Многие из методов решения задач дискретной оптимизации основаны на идее перебора вариантов, качество алгоритмов оценивается числом точек x , для которых вычислялись значения ( ) x f или значения некоторых других функций. Объем вычислительной работы резко возрастает с ростом числа переменных. Поэтому перебор большого числа вариантов принципиально невозможен ни при каком быстродействии ЭВМ. Методы отсечения Выделим следующие (основные) методы решения задач дискретного программирования- метод отсечения для задач (частично) целочисленного линейного программирования- комбинаторные методы- приближенные методы. Первые попытки решения задач целочисленного линейного программирования сводились к отбрасыванию условия целочисленности, решению линейной задачи и округлению полученного решения. Можно привести простой пример, который показывает неприемлемость такого подхода 3 3 2 1 → + − x x x , 4 2 3 2 1 ≤ − + x x x , 2 3 4 2 1 ≤ − x x , 3 2 3 3 2 1 ≤ + + − x x x , 0 , , 3 целые Игнорируя условие целочисленности, получим оптимальное решение линейной задачи 2 1 4 , 0 , 2 1 3 2 1 = = = x x x . Никакие округления компонент этого решения не дают даже целочисленного плана. Оптимальное решение целочисленной задачи имеет вид 5 , 2 , 2 3 2 Описанный подход основан на идее сведения решения нерегулярной задачи к решению конечной последовательности регулярных задач, неудача связана с прямолинейным применением идеи сведения. Применительно к задаче целочисленного линейного программирования идея регуляризации позволяет свести решение этой задачи к решению последовательности специальным образом построенных линейных задач. Она состоит в следующем. Если полученное решение удовлетворяет условию целочисленности, то процесс окончен. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами- полученный нецелочисленный план ему не удовлетворяет- любой целочисленный план ему удовлетворяет. Решается задача с дополнительно введенным ограничением, процесс повторяется дополучения целочисленного решения. Идея отсечения приводит к трем проблемам- нахождение универсального правила формирования отсечений; - доказательство конечности процесса отсечения- борьба с чрезмерным разрастанием размерности задач при добавлении ограничений. Только решение этих проблем может привести к универсальному и реализуемому в вычислительном отношении алгоритму. Р. Гомори удалось решить эти проблемы В дальнейшем выявилась большая непредсказуемость в поведении различных алгоритмов отсечения. Для некоторых вариантов алгоритма Гомори существуют задачи, в которых число отсечений быстро растет с ростом размерности задачи и ростом коэффициентов, а в текущих симплекс-таблицах появляются весьма большие числа. Методы отсечения не нашли широкого применения при решении прикладных задач последующим причинам- определение того, какое отсечение (из большого их числа) есть сильнейшее, есть сложная в вычислительном отношении задача- методы отсечения приспособлены в основном для решения чисто целочисленных задач, которые составляют лишь малую часть задач, встречающихся в приложениях- методы отсечения не приспособлены для решения задач со слабо заполненными матрицами. Алгоритм Гомори Приведем в качестве примера один из алгоритмов Гомори для решения полностью целочисленной задачи линейного программирования. Рассмотрим полностью целочисленную задачу линейного программирования j n j j x c Z ∑ = = 1 max(min) ; (2.1) m i b x a i j n j ij ,..., 1 , 1 = = ∑ = , (2.2) n j x j ,..., 1 , 0 = ≥ , (целые. (Алгоритм Гомори состоит из следующих этапов Решается задача (2.1) – (2.3) с отброшенным условием целочисленности. 2. Полученное оптимальное решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение задачи (2.1) – (2.4) совпадает с оптимальным решением задачи (2.1) – (2.3). Если это условие не выполняется хотя бы для одной переменной, то переходят к третьему этапу. Если задача (2.1) – (2.3) оказывается неразрешимой, то задача (2.1) – (2.4) тоже не имеет решения. 3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение задачи (2.1) – (2.3) и не содержится ни одного допустимого решения задачи (2.1) – (Последний этап предусматривает возвращение к ЗЛП с отброшенным условием целочисленности, нос расширенной системой ограничений, в которую включено дополнительное ограничение, полученное на третьем шаге. К расширенной системе ограничений вновь применяется симплексная процедура. Если найденное таким образом решение будет опять нецелым, то формируется новое дополнительное ограничение и процесс вычислений повторяется. Алгоритм Гомори позволяет за конечное число шагов прийти к оптимальному целочисленному решению, если оно существует. С геометрической точки зрения каждому дополнительному линейному ограничению в мерном пространстве соответствует определенная гиперплоскость, отсекающая от многогранника решений некоторую его часть, включая и оптимальную на данном этапе нецелочисленную вершину. При этом все точки с целочисленными координатами, в том числе и искомая оптимальная, остаются в усеченном многограннике. Так как множество целых точек усеченного многогранника совпадает с множеством целых точек исходного многогранника, то понятно, что если оптимальное решение ЗЛП на усеченном многограннике 10 удовлетворяет условию целочисленности, то оно является оптимальным целочисленным решением и исходной задачи. Через несколько операций отсечения искомая целочисленная точка оказывается сначала на границе, а затем становится оптимальной вершиной неоднократно усеченного многогранника решений. Может оказаться, что многогранник решений не содержит ни одной целочисленной точки. В этом случае, сколько бы ни вводили дополнительных ограничений, целочисленного допустимого решения получить нельзя. Основное в алгоритме – составление дополнительного ограничения, те. отсекающей гиперплоскости, которая называется правильным отсечением Правильное отсечение должно удовлетворять следующим условиям 1) быть линейным 2) отсекать найденное оптимальное нецелочисленное решение задачи (2.1) – (2.3); 3) не отсекать ни одной из целочисленных точек задачи (2.1) – (Рассмотрим, как можно сформировать правильное отсечение. После каждой итерации система ограничений имеет вид } { } БП x x b x i j СП x ij i i j ∈ − = ∑ ∈ , α , (где { } БП - множество базисных переменных. Если выполняется условие оптимальности задачи, то находим оптимальное решение. Если все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые 0 β - нецелые. Пусть компонента 0 i - нецелая. Рассмотрим 0 i - равенство системы (2.1.5), для которой выполняется условие оптимальности, те } ∑ ∈ − = СП x j j i i i j x x 0 0 0 α β . (Найдем целую и дробную часть коэффициентов 0 i β и j i 0 α : [ ] { } 0 0 0 i i i β β β + = , (2.7) [ ] { } { } СП x j j i j i j i ∈ + = , 0 0 0 α α α 11 Так как, по предположению, 0 i β нецелое, то { } 0 0 > i β . Кроме того, { } 0 0 ≥ j i α . Подставив выражение (2.7) в равенство (2.6), получим ] [ ] { } { } { } { } ) ( ) ( 0 0 0 0 0 j СП x j i i j СП x j i i i x x x j j ∑ ∑ ∈ ∈ − + − = α β α β . (Так как первое слагаемое равенства (2.8) есть целое число, то, для того чтобы 0 i x было целым, необходимо, чтобы второе слагаемое также было целым числом, те. величина } { } { } j x j i i i x L СП j ∑ ∈ − = 0 должна быть целым числом. Так как 0 i x - координата допустимого целочисленного решения задачи (2.1) – (2.4), то 0 i L - всегда целое число. Легко показать, что 0 0 ≤ i L . Таким образом, любое допустимое решение задачи (2.1) – (2.4) должно удовлетворять неравенству } { } { } 0 0 ≤ − ∑ ∈ j СП x j i i x j α β . (Справедлива теорема. Неравенство (2.9) определяет правильное отсечение Гомори, те 1) является линейным 2) отсекает найденное оптимальное нецелочисленное решение задачи (2.1)–(2.3); 3) не отсекает ни одного целочисленного плана задачи (2.1) – (Если после очередной итерации окажется, что в оптимальном плане задачи (2.1) – (2.3) имеется несколько нецелых координат, то для построения отсекающей гиперплоскости целесообразно выбрать строку, содержащую свободный член с наибольшей дробной частью. Признаком отсутствия целочисленности решения служит появление в симплексной таблице хотя бы одной строки с дробным свободным 12 членом и целыми остальными коэффициентами, так как в этом случае соответствующее уравнение не имеет решения в целых числах. Пример 2.1. Решить задачу 1 max x x Z + = ; 3 3 2 1 ≤ + − x x , 3 3 2 1 ≤ − x x , 0 , 2 1 целые x x − ≥ Р е ш е ни е. В результате решения задачи без учета условия целочисленности переменных получаем оптимальный план ( ) ( ) 0 ; 0 ; 2 / 3 ; 2 / 3 1 = ∗ нц x , содержащийся в таблице Таблица 2.1 БП Б с 0 А 1 x 2 x 3 x 4 x 1 1 0 0 2 x 1 3/2 0 1 3/8 1/8 1 x 1 3/2 1 0 1/8 3/8 j j c z − 3 0 0 1/2 Таблица 2.2 БП Б с 0 А 1 х 2 х 3 х 4 х 5 х 1 1 0 0 0 2 x 1 3/2 0 1 3/8 1/8 0 1 x 1 3/2 1 0 1/8 3/8 0 - - 4 0 0 1 3 -1 j j c z − 3 0 0 1/2 1/2 0 2 x 1 4/3 0 1 1/3 0 1/24 1 x 1 1 1 0 0 0 1/8 4 x 0 4/3 0 0 1/3 1 -1/3 j j c z − 7/3 0 0 1/3 В полученном плане две компоненты нецелые. Поскольку они равны по величине, сформируем правильное отсечение (2.9), например, по 13 строке { } { } { } 4 8 / 3 8 / 1 2 / 3 4 3 ≥ − − x x . Эквивалентное уравнение имеет вид 4 3 5 4 3 = − + x x x . Дополняя табл. 2.1 строкой для этого уравнения и столбцом для новой переменной 5 x , получаем расширенную задачу, записанную в табл. 2.2. В этой же таблице в результате симплексного преобразования найден оптимальный нецелочисленный план ) ( ) 0 ; 3 / 4 ; 0 ; 3 / 4 ; 1 2 = ∗ нц x расширенной задачи. Продолжаем процедуру отсечения. Новое правильное отсечение (2.9) сформируем, например, по 2 x - строке { } { } { } 0 24 / 1 3 / 1 3 / 4 5 3 ≤ − − x x или 8 8 5 3 ≥ + x x . Эквивалентное этому неравенству уравнение принимает вид 8 8 6 Вновь расширяем задачу, добавляя строку для нового уравнения и столбец для переменной 6 x . В результате табл. 2.2 преобразуется в табл. Таблица 2.3 БП Б с 0 А 1 x 2 x 3 x 4 x 5 x 6 x 1 1 0 0 0 0 2 x 1 4/3 0 1 1/3 0 1/24 0 1 x 1 1 1 0 0 0 1/8 0 4 x 0 4/3 0 0 1/3 1 -1/3 0 - - 8 0 0 [ ] 8 0 1 -1 j j c z − 7/3 0 0 1/3 0 1/6 0 2 x 1 1 1 x 1 1 4 x 0 1 3 x 0 1 j j c z − 2 0 0 0 0 1/8 После очередной итерации получен оптимальный план ( ) ( ) 0 ; 0 ; 1 ; 1 ; 1 ; 1 ц новой расширенной задачи. Все компоненты этого плана – целые числа. Максимальное значение целевой функции выражается целым числом ц, а поэтому решение задачи закончено. Итак, для исходной задачи получили ( ) 1 , 1 = ∗ x , 2 = ∗ Z 14 Упражнения для самостоятельной работы. Дать геометрическую интерпретацию приведенного решения задачи. Решить задачи методом отсечения: а) (max) 3 2 3 2 1 x x x f + + = ; б) (min) 2 3 2 1 x x x f + + = ; 25 3 4 6 3 2 1 ≤ + + x x x , 3 2 3 2 1 ≥ + + x x x , 15 2 3 5 3 2 1 ≤ + + x x x , 1 2 2 целые целые 0 |