Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 63

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 63)

Рассмотрим, например, формулу (х<+х»+х»).(х,+х,) (х,+х,) (х,+х,) (х,+х»+х»). (13.5) Для того чтобы формула (13.5) приняла значение истина, все подформулы в скобках (называемые дизьюнктами), содержащие литералы (т. е. переменные или отрицания), должны принимать значение истина. Первый дизъюнкт утверждает, что по крайней мере одна из переменных должна принять значение истина. Следующие три дизъюнкта требуют, чтобы все переменные были одинаковы. Чтобы понять это, предположим, что х, принимаез значение ложь. Так как значением второго дизъюнкта должна быть истина, то х, должно принимать значение ложь; тогда третий дизъюнкт показывает, что х, также должно принимать значение ложь. Какое бы значение ни принимала некоторая переменная, второй, третий и четвертый дизъюнкты будут требовать, чтобы остальные переменные принимали то же самое значение, Поэтому все переменные должны принимать одно и то же значение, и, поскольку мы знаем, что по крайней мере одна из иих должна принимать значение истина, все они должны принимать значение истина.

Однако последний дизъюнкт требует, чтобы не все переменные принимали значение истина и, следовательно, формула (13.5) содержит противоречие. Она невыполнима. Задача о выполнимости (ВЫПОЛНИМОСТЬ) состоит в следующем: 11» 3224 Гл. 18. Целочисленное линейное программирование хе+х,+ х, ~ )1, х;+(1 — х,) ) 1, х,+(1 — х,)) 1, Хе+(! Хе) (1 — х;)+(1 — х;)-1-(1 — х,) = 1, х;, х„хе<1, х;, х;, х, )О, целые.

(1 3,6) Легко понять, как выполнимость формулы (13.5) выражается ограничениями (13,6). В общем случае. формула, сосзоящая из нескольких дизъюнктов, соединенных связками или (мы будем гово. рить, что это формула в конъюннтивной нармильнай форме), выпал.

пима тогда и только тогда, когда в соответствующей задаче ЦЛП имеется допустимая точка. Таким образом, формулировка (13.6) не задает задачу ЦЛП, поскольку мы не ищем минимума некоторого линейного функционала. Однако ее легко преобразовать в эквива. лен1 ную обычную задачу ЦЛП. Например, в (13.6) первое неравенство можно заменить на х,+х,+хе)у и максимизировать у. Тогда формула выполнима в том и только в том случае, если оптимальное значение у существует и удовлетворяет неравенству у) 1. Задача ЦЛП (13.6) принадлежи~ важному классу задач Цй!П, в которых переменные могут принимать только два значения: О или 1.

Такие задачи ЦЛП называются задачами двоичного линейного прогримми. рования, или зидачами 0-1 линейного программирования (НОЛП). Последние две строки задачи ЦЛП (13.6) обычно записывают в виде Для данных т дизъюнктов С„..., С, содержащих переменные х, ..., х„, определить, выполнима ли формула С; С, ... Сеи ВЫПОЛНИМОСТЬ являешься центральной задачей в матема. тической логике, и построение эффективных алгоритмов для ее ре. щения вызывает большой ингерес Естественно, одно из решений состоит в том, чтобы испытать всевозможные наборы значений истинности и посмотреть, если ли среди них набор, выполняющий данную формулу. Однако этот алгоритм неэффективен, так как потребуется испытать 2ч наборов значений истинности (для каждой переменной возможны два варианта).

К настоящему моменту не известно эффективного алгоритма, который бы решал задачу ВЫПОЛНИМОСТЬ. Поэтому интересно, что ВЫПОЛНИМОСТЬ можно сфор. мулировать как задачу ЦЛП. Соответствующая формулировка по. лучается моментально, если отождествить значение исспина с 1 и значение ложь с нулем. Тогда или превращается в обычное сложение, х выражается как 1 — х и требуется, чтобы каждый дизъюнкт С содержал по крайней мере один литерал, принимающий значение истина. Другими словами, ч~~~„есх+~,— ес(! — х))1 Например, полная задача ЦЛП для.формулы (13.5) будет иметь вид 18.3.

Вполна унимодулярносвь 325 хам (О, 1), 1=1, ..., и. Более причудливым способом выражения этого же условия является равенство х',=хл Представление задачи о выполнимости в виде задачи ЦЛП (13.6) иллюстрируез сказанное вами ранее: в общем случае нельзя правильно решить задачу ЦЛП, просто округляя решение соответствук щей задачи ЛП.

Ограничения, соответствующие задаче о выполнимости для произвольной формулы в конъюнктивной нормальной форме, каждый дизъюнкт которой содержит по меньшей мере два литерала,— условие, которого легко добиться (см, задачу 5),— выполняются, если всем переменным х, придать дробные значения х =1~2. Следовазельно, допустимое решение соответсгвующей задачи ЛП всегда тривиально находизся; но округлить это решение допустимым образом (на самом деле всего лишь определить, можно ли его округлить) настолько же трудно, как решить саму задачу о выполнимости, которая в действительности очень трудна (см. гл.

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

15 мы введем понятие ЫР-полноты для характеризации тех задач, которые, подобно задаче ЦЛП, по-видимому, трудны, по существу, именно из-за их общности. ~за Вполне унммодулярность Напомним, что, например, в задачах о максимальном потоке и взвешенном двудольном паросочетании решения соответствующих задач линейного программирования без специальных ограничений на целочисленность были тем не менее всегда целочисленными. Естественно поставить вопрос, в чем причина такой благоприятной ситуации в этих случаях, с тем, чтобы можно было в полной мере использовать достоинства такого механизма. Для ответа на этот вопрос нам потребуется вначале определить следующее центральное понятие.

Определение 13.1. Квадратная целочисленная матрица В называется унимодулярной (УМ), если ее определитель де((В)=~1, Целочисленная матрица А называется вполне унимодулярной (БУМ), если каждая квадратная невырожденная подматрица матрицы 4 унимодулярна. Гл. И. целочисленное линейное программирование 326 Если матрица В составлена из т линейно независимых столбцов матрицы А, то она определяет базисное решение в "аl ь х=В гЬ-= —, ле! !й! ' где В'ю — присоединенная матрица для матрицы В.

Поэтому если матрица В унимодулярна и Ь вЂ” целочисленный вектор (что мы всегда предполагаем), то х целочисленно, Если определить многогранник И,(А) = (х; Ах=Ь, х- 0), представляющий обычное допустимое множество для задачи ЛП в стандартной форме, то получаем следующую теорему. Теорема 13.1. Если митрици А вполне унимодулярна, то для любого целочисленного вектори Ь все вершины многогранники Я,(А) цел очислен ны.

Таким образом, решение задачи г!П в стандартной форме с ВУМ матрицей с помощью симплекс-алгоритма всегда приводит к целочисленному оптимуму. Тот же результа"г имеет место и в том случае, когда в формулировке задачи ЛП используются ограничения в виде неравенств. Пусть соответствующий многогранник имеет вид В,(А)==(х: Ах<Ь, х)0). Тогда справедлива Теорема '13.2.

Если матрици А вполне унимодулярни, то для любого целочисленного вектора Ь все вершины многогранника гс,(А) целочисленны. Доказательство. Для доказательства достаточно показать, что если матрица А вполне унимодулярна, то матрица (А!Т) также вполне унимодулярна, ибо тогда можно будет добавить переменные недостатка и применить теорему !3.!. Пусть С вЂ” квадратная певырожденная подматрица матрицы (4!!).

Переставляя строки матрицы С, можно привести ее к виду где )и — единичная матрица размера й и  — квадратная подматрица матрицы А, возможно, с переставлеипыми строками. Отсюда де! (С)=-де! (В)=~1, поскольку матрица А вполне унимодулярна и С вЂ” невырожденная подматрипа. Е) Покажем теперь, что в тех случаях, рассмотренных в предыдущих главах, где решения автоматически получались целочисленными, матрица ограничений была в действительности вполне уиимодуляр- 327 13.2.

Вполне упомодулпрноогпь ной. Удобное достаточное (но не являющееся необходимым) условие дает Теорема 13.3. Целочисленная мшприца А с элементами а>1= =О, ~! вполне унимодулярни, если в киждом сгполбце содержится не более двух ненулевых элеменгггов и строки митрицы А можно разбить на тикие дви множества г'г и йм что 1) если в некотором столбце стоят дви .элемента с одиниковьгм зником, то соответствующие илг строки лежат в ризных множествах; 2) если в некотором столбце стоягп элеменгпьг с разными знакими, то соопгвепюпгв!!ющие им строки лежат в одном и том же множеспиге.

Доказательство. Доказательство можно провести индукцией по размеру подматриц. Для получения базиса индукции достаточно заметить, что любая подматрица из одного элемента вполне унимодулярна. Пусть С вЂ” произвольная подматрица размера я. Если матрица С содержит полностью нулевой столбец, то она вырожденна. Если в матрице С имеется столГ>ец с одним ненулевым элементом, то ее определитель можно разложить по этому столбцу, и нужный результат будет следовать из предположения индукции. Остается последний случай, когда в каждом столбце матрицы С имеются два ненулевых элемента. Тогда из условий 1 и 2 теоРемы вытекает, что '>г,г, аг =~я,'го>,а„длЯ каждого 1, т.

Характеристики

Список файлов книги