«Е. В. Алексеева ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ПРИМЕРЫ И ЗАДАЧИ Учебное пособие Новосибирск 2012 УДК 519.8(075.8) ББК В183я73-1 A 471 Алексеева Е. В. Построение ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет информационных технологий

Е. В. Алексеева

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ

МОДЕЛЕЙ ЦЕЛОЧИСЛЕННОГО

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

ПРИМЕРЫ И ЗАДАЧИ

Учебное пособие

Новосибирск 2012 УДК 519.8(075.8) ББК В183я73-1 A 471 Алексеева Е. В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т.

Новосибирск, 2012. 131 с.

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

Рецензент д-р физ.-мат. наук, проф. Ю. А. Кочетов ISBN c Новосибирский государственный университет, c Алексеева Е. В., Оглавление 1. Введение 2. Моделирование с помощью булевых переменных 2.1. Примеры математических моделей.................. 2.2. Правила моделирования логических импликаций.......... 2.3. Моделирование свойств логических отношений........... 2.4. Моделирование выбора минимального элемента.......... 2.5. Моделирование взаимоисключающих событий........... 2.6. Линеаризация в математических моделях.............. 2.6.1. Линеаризация произведения переменных.......... 2.6.2. Линеаризация заменой переменных............. 2.6.3. Линеаризация кусочно-линейной функции......... 2.7. Симметрия в математических моделях................ 3. Примеры математических моделей целочисленного линейного программирования 3.1. Задача о потоке минимальной стоимости.............. 3.2. Задача коммивояжера......................... 3.3. Задача о покрытии........................... 3.4. Задача о двухстадийном гильотинном раскрое........... 3.5. Задача о разрезе балок......................... 3.6. Задача о башнях............................. 4. Анализ качества моделей целочисленного линейного программирования 4.1. Классификация моделей........................ 4.2. Разрыв целочисленности........................ 4.3. Число ограничений и переменных в модели............. 4.4. Многогранники. Правильные неравенства.............. 4.5. Целочисленные решения задачи линейного программирования.. 4.6. Уточнение значения границ переменных............... 4.7. Удаление избыточных ограничений.................. 5. Упражнения 5.1. Теоретические задания......................... 5.2. Практические задания......................... 6. Решение оптимизационных задач в GAMS 7. Список литературы 1. Введение Ежедневно люди принимают тысячи решений, отвечая на различные вопросы, начиная от простых «Где пообедать?» до сложных «В каких городах разместить филиалы компании?» Часто процесс принятия решения можно описать аналитически. Предположим, Вы хотите оценить время, затрачиваемое на дорогу от работы до дома, для этого нужно узнать расстояние и разделить его на среднюю скорость передвижения. Получаем количественную модель:

где S — расстояние, v — средняя скорость, t — время в пути. Эта модель полезна, но, как и любая модель, обладает существенным недостатком: упрощает и идеализирует реальность. Например, в модели не учитывается, что, возвращаясь с работы домой, Вы делаете остановки, чтобы зайти в магазины. Это можно учесть, добавив слагаемое:

где n — планируемое число остановок, R — среднее время на остановку. В данной модели имеются постоянные величины: расстояние между домом и офисом;

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

Рассмотрим следующий пример. Фирма производит шесть типов стульев:

капитан, помощник, маркиза, испанский, венский и офисный. Для производства стульев необходимы универсальные детали: длинные и короткие болты, тяжелые и легкие сиденья, длинные и короткие ножки, перекладины, гайки, роллеры, каркас и крепления. В табл. 1 приводятся данные о стоимости стульев, потребности в деталях для каждого типа стульев и их наличие на складе.

Благодаря универсальности деталей производитель может быстро реагировать на изменения в спросе. Поступил заказ изготовить 40 стульев каждого типа из имеющихся на складе деталей.

Суммарный доход от продажи стульев определяется выражением:

где i — тип стула, ci — стоимость одного стула i-го типа. Результаты расчетов для склада приводятся в табл. 2. Согласно этому плану доход составляет 8760 y.e., причем длинные болты израсходованы полностью. Можно ли увеличить доход фирмы, если количество стульев в заказе будет другим? Чтобы ответить на этот вопрос, проанализируем решение. Заметим, что для стула «капитан» длинных болтов требуется больше, чем для других стульев.

Сократим производство стульев «капитан» на 2 единицы, а на вырученные длинных болта произведем 3 «офисных» стула. При этом фирма потеряет от непроизводства «капитана» 90 y.e., но заработает 108 y.e., если продаст дополнительно три «офисных» стула. Таким образом, суммарный доход увеличится на 18 = (43 · 36 + 40 · 40 + 38 · 45 + 40 · 38 + 40 · 35 + 40 · 25 8760) y.e.

Можно ли еще увеличить доход? Проведем те же рассуждения. Для производства «испанского» стула необходимо 8 длинных болтов, а для «венского» в 2 раза меньше. Значит, если вместо одного «испанского» стула будем производить два «венских» стула, то доход составит не 35 y.e., а 50 y.e. Следовательно, если фирма будет производить вместо 40 «испанских» стульев 80 «венских»

стульев, то ее суммарный доход увеличится на 600 = (40 · 36 + 40 · 40 + 40 · 45 + 40 · 38 + 0 · 35 + 120 · 25 8760) y.e. Результаты расчетов по этому плану приводятся в табл. 3. Однако этот план не может быть реализован из-за недостатка деталей на складе, о чем свидетельствуют отрицательные значения в столбце остаток.

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

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

Оптимизационные модели активно стали использоваться в годы Второй мировой войны при решении военных задач. Со временем сложились научные дисциплины исследование операций (от англ. operations research) и теория принятия решений (от англ. management science), которые занимаются оптимизационными задачами, возникающими в экономике, производстве, политике и других областях человеческой деятельности. Под исследованием операций понимают применение математических и количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности [2]. Под теорией принятия решений понимают особый вид человеческой деятельности, направленный на выбор наилучшего варианта действий [11]. Четкое разделение между этими дисциплинами трудно провести, но можно сказать, что дисциплина «Теория принятия решений» оказывается шире, чем «Исследование операций», и использует ее как инструмент, когда реальную задачу удается формализовать в виде математической модели и найти наилучший вариант решения путем математических расчетов. Однако такая формализация часто оказывается труднореализуемой из-за нескольких критериев оптимизации, слабой структурированности задачи, наличия многих лиц, принимающих решения или других причин. В таких ситуациях методы исследования операций носят вспомогательный характер и выступают как инструмент теории принятия решений.

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

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

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

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

Л. В. Канторович получил Нобелевскую премию за достижения в этой области [3]. В 1947 г. американский ученый Д. Данциг разработал алгоритм решения этой задачи. С этого момента линейное программирование стало важным инструментом в исследовании операций.

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

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

Построение математической модели и решение задачи лучше доверить специалистам по исследованию операций.

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

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

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

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

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

Следующий важный этап состоит в построении математической модели.

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

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

Полезность модели зависит еще и от того, кто с ней работает. ЛПР должно обладать долей интуиции и понимать степень реалистичности получаемого решения. Не всегда цель моделирования состоит исключительно в том, чтобы найти оптимальное решение задачи, т. е. наилучшее решение для конкретной модели, но также может быть интересным исследование различных альтернативных решений, с помощью которых можно прогнозировать сложные ситуации. Не всегда оптимальное решение является подходящим для практического внедрения. Может оказаться, что поиск оптимума требует больших вычислительных ресурсов, в то время как приближенное решение не сильно отличается от оптимального или оно устраивает того, кто принимает решение. Кроме того, при моделировании часто возникают труднореализуемые аспекты. Имеется много критериев оптимизации, и понятие оптимального решения является условным. Многовариантные расчеты по сценарию «А что, если...?» позволяют проверить чувствительность решений к изменениям исходных данных, исследовать различные предположения и оценить последствия принимаемых решений.

В большинстве задач выбора имеется много критериев оценки вариантов решения. Критерии могут быть зависимыми или независимыми. Зависимыми называют те критерии, при которых оценка альтернативы по одному из них определяет оценку по другому критерию. Количество критериев влияет на сложность задачи принятия решений. При небольшом числе критериев (дватри) задача сравнения по ним может быть выполнена непосредственно. При большом числе критериев задача становится малообозримой, и тогда необходимо использовать специальные методы решения многокритериальных задач оптимизации [7, 27].

В пособии будут рассмотрены задачи, в которых поиск решения проводится по одному критерию оптимизации. Материал, содержащийся в пособии, является частью лекционных курсов и семинарских занятий по дисциплине «Теория принятия решений» [1], читаемой студентам 3 и 5-го курсов на факультете информационных технологий Новосибирского государственного университета.

Программа этой дисциплины составлена в соответствии с требованиями ФГОС ВПО к структуре и результатам освоения основных образовательных программ магистратуры по циклу «Общие математические и естественно-научные дисциплины» по направлению подготовки «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.

2. Моделирование с помощью булевых переменных В общем виде оптимизационная модель состоит из целевой функции и ограничений. Целевая функция устанавливает зависимость критерия оптимизации от управляемых и неуправляемых параметров x и k соответственно в виде функции f (x, k). Функция может быть задана аналитически или с помощью алгоритма. Для f (x, k) указывается, по какому критерию будет проводиться оптимизация, минимизация или максимизация:

Все ограничения модели записываются с помощью некоторых функций, также зависящих от управляемых и неуправляемых параметров x и k в виде неравенств:

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

Итак, получаем общий вид математической модели (2.1)—(2.3).

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

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

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

Прежде чем переходить к моделированию с помощью булевых переменных, заметим, что любую переменную, которая принимает целое неотрицательное значение, ограниченное сверху, можно представить как сумму булевых переменных с соответствующими коэффициентами. Например, пусть переменная x принимает целые значения из отрезка [0, U ]. Тогда x можно представить, используя двоичное разложение следующим образом:

где xj {0, 1} для всех j = 0,..., log2 U.

Кроме построения модели, может возникнуть обратная задача, в которой по математической модели необходимо понять содержательный смысл ограничений и взаимосвязей между переменными. Например, пусть имеются булевы переменные x1, x2, x3, непрерывная переменная y, принимающая значения из отрезка [0, 1], и неравенство Возникает вопрос, какие взаимосвязи между переменными реализованы в этом неравенстве? После недолгих размышлений нетрудно заметить, что это неравенство моделирует следующую зависимость: если x1 = 1, x2 = 0, x3 = 1, то y 0, учитывая, что y [0, 1], следует, что y = 0. Моделирует ли это неравенство еще какие-либо зависимости между этими переменными? Ответ «нет», а почему это так, будет объясняться ниже.

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

Задача о 0–1 рюкзаке Имеется n предметов и рюкзак грузоподъемностью V. Известна полезность cj и вес vj каждого предмета, j = 1,..., n. Требуется определить, какие предметы положить в рюкзак, чтобы суммарная полезность выбранных предметов была наибольшей, а общий вес не превышал грузоподъемность рюкзака [29].

Для моделирования событий «предмет положили в рюкзак» или «не положили» введем n булевых переменных:

Целевая функция задачи — максимальная суммарная полезность выбранных предметов:

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

Ограничения на значения переменных:

Итак, получили математическую модель (2.4)–(2.6) для задачи о 0–1 рюкзаке с n булевыми переменными и одним ограничением.

Задача о назначениях Имеется n рабочих и m работ, n m. Известны (cij ) затраты при выполнении работы j рабочим i. Требуется составить план назначений рабочих на работы так, чтобы все работы были выполнены с минимальными суммарными затратами.

Введем nm булевых переменных:

Целевая функция — минимальные суммарные затраты:

При условиях, что каждая работа должна быть выполнена каждый рабочий может выполнять не более одной работы и при ограничениях на значения переменных В литературе можно встретить разные интерпретации этой задачи. Она полиномиально разрешима, в [1, 13] для случая с n = m описывается алгоритм, трудоемкость которого составляет O(n3 ).

Задача о размещении студентов в общежитии Рассмотрим задачу, близкую к задаче о назначениях. Имеется 2n студентов, которых нужно расселить по n двухместным комнатам, т. е. каждому студенту назначить ровно одного соседа. Величина (cij ) задает расстояние между городами, в которых жили студенты i и j до поступления в университет. Требуется разместить студентов по комнатам таким образом, чтобы перезнакомить как можно больше студентов из наиболее удаленных друг от друга городов.

Введем булевы переменные:

Целевая функция — максимальное расстояние между познакомившимися студентами при ограничениях, что у каждого студента ровно один сосед k m, рассмотренная выше, эквивалентна задаче о поиске паросочетания минимального веса на двудольном графе (рис. 3).

2.2. Правила моделирования логических импликаций Рассмотрим некоторые правила, следуя которым можно моделировать логические импликации с помощью линейных ограничений и булевых переменных [26].

Рис. 2. Cовершенное паросочетание для задачи о размещении студентов Рис. 3. Паросочетание минимального веса для задачи о назначениях Напомним, что под импликацией понимается логическая связка некоторого условия и следствия из него и выражается союзами «если..., то...».

Первое правило. Пусть I — конечное множество индексов, xi — булева переменная, i I и y — непрерывная переменная, такая, что 0 y 1. Тогда импликация Нетрудно проверить, что неравенство (2.14) действительно реализует нужную логическую связку. Если xi = 0 для всех i I, то iI xi = 0 и неравенство (2.14) превращается в неравенство y 0. Поскольку y — неотрицательная величина, то y = 0.

Более того, неравенство (2.14) не порождает никаких лишних ограничений, т. е. если xi = 1 для некоторого i, то 1 iI xi, и так как y 1, то неравенство (2.14) всегда выполнено.

Следствие 1.1. Пусть значение переменной y ограниченно сверху величиной c, 0 y c. Тогда импликация Пример. Задача размещения производства [9] Задано конечное множество возможных мест производства I некоторой однородной продукции и конечное множество клиентов J. Известны затраты ci на организацию производства в пункте i. Продукция доставляется клиентам, стоимость доставки клиенту j из пункта i равна dij. Каждый клиент может обслуживаться только из одного пункта. Необходимо определить, в каких пунктах следует разместить производство, чтобы обслужить всех клиентов с наименьшими суммарными затратами.

Введем булевы переменные:

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

Вторая группа ограничений гарантирует, что если в пункте i производство не размещено, то клиент j из него не обслуживается. В виде импликации это условие записывается так:

Следуя первому правилу, получаем:

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

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

Задача размещения с ограничениями на мощности производства [9] Пусть производственная мощность предприятия i составляет ui единиц, а величина bj задает спрос клиента j. Величины dij задают удельные затраты на доставку продукции от клиента j до пункта i. Изменим смысл переменных yij.

Теперь они будут обозначать количество продукции, поставляемое клиенту j из пункта i. Тогда задача размещения с ограничениями на мощности производства может быть записана в следующем виде:

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

и 0 jJ yij ui. Модифицируя первое правило, эти условия моделируются неравенствами: Добавив ограничения на значения переменных:

получаем математическую модель (2.19)–(2.23) смешанного целочисленного линейного программирования.

Пример. Задача о покрытии Задано конечное множество клиентов J и конечное множество пунктов размещения магазинов I. Известны кратчайшие расстояния dij между элементами i, j из множеств I и J соответственно. Величина sj задает максимальное расстояние, которое клиент j согласен преодолеть до магазина. Учитывая это, для каждого клиента j можно определить множество магазинов Nj, которые он мог бы посещать: Nj := {i I|dij sj }.

Требуется определить минимальное количество магазинов, которое нужно открыть, чтобы обслужить всех клиентов. Другими словами, требуется выбрать минимальное по числу элементов подмножество множества I, покрывающее все множество J.

Введем булевы переменные:

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

Ограничения на значения переменных:

Получаем математическую модель (2.24)–(2.26) для одной из задач о покрытии.

Существуют и другие постановки задач о покрытии, которые образуют целый класс этих задач [21, 30].

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

Пусть wi — затраты, связанные с открытием магазина в пункте i, B — общий бюджет на открытие магазинов. Требуется обслужить как можно больше клиентов при ограниченном бюджете на открытие магазинов.

Введем новые булевы переменные:

Целевая функция — максимальное число обслуживаемых клиентов:

Переменные yj и xi логически связаны между собой следующим образом:

yj = 1, тогда и только тогда, когда xi = 1 для некоторого i Nj.

Это условие содержит две импликации. Смоделируем отдельно каждую из них.

Первая импликация:

или Следуя первому правилу, получаем:

Вторая импликация:

или Применяя первое правило, получаем формулировку этой импликации в виде следующего неравенства:

Суммарные затраты на открытие магазинов ограничены:

Ограничения на значения переменных:

Второе правило. Пусть xi — булева переменная, i I, где I — конечное множество индексов; I0 и I1 — непересекающиеся подмножества множества I и y — целочисленная, или непрерывная, переменная, удовлетворяющая неравенству 0 y 1. Тогда логическая импликация моделируется неравенством Логическая импликация моделируется неравенством Эквивалентность импликаций и неравенств нетрудно проверить самостоятельно, пользуясь первым правилом.

После приведения подобных неравенства (2.32) и (2.33) можно переписать Этот вид более компактный, но по нему сложнее восстановить логические взаимосвязи между переменными.

Итак, если импликация содержит xi = 1 для некоторого i, то в неравенство вместо переменной xi будет входить (1 xi ).

Пример Смоделируем импликацию:

Следуя второму правилу, получаем:

или Это неравенство рассматривалось в разд. 2, и теперь должно быть понятно, какие взаимосвязи оно реализует.

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

Для моделирования введем следующие булевы переменные:

Обозначим через Cis множество всех предприятий, которые находятся к клиенту i ближе, чем предприятие s. Тогда Применяя второе правило, получаем:

или 2.3. Моделирование свойств логических отношений Моделирование отношения транзитивности. Часто в задачах между объектами заданного множества I определено некоторое отношение R. Например, i < j, в данном случае под R понимается отношение сравнения «строго меньше». Как правило, R должно обладать свойством транзитивности, т. е. если iRj и jRk, то iRk для любых i, j, k I.

Рассмотрим граф с множеством вершин V и множеством ребер E. Требуется смоделировать транзитивность отношения связности вершин. Пусть булева переменная:

Тогда для любой тройки вершин (i, j, k) V V V Следуя второму правилу, получаем линейное неравенство:

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

Введем булевы переменные:

Запишем условие антисимметричности. Для любой пары работ i и j всегда одна работа должна выполняться раньше другой, т. е. только одна из переменных xij или xji может быть равна единице:

и xii = 0. Следовательно, можно ограничиться рассмотрением только переменных xij с i < j и xii = 0.

Для каждой тройки работ i, j и k должно выполняться отношение транзитивности:

С учетом антисимметричности, при переходе к переменным xij с i < j из шести групп неравенств останутся только следующие неравенства:

Неравенство (2.38) гарантирует транзитивность в очередности выполнения работ i, j и k, если работа i предшествует работе j (xij = 1). Если это не так, то неравенство (2.38) верно при любых значениях xjk и xik, а с помощью неравенства (2.39) сохраняется транзитивность при xij = 0.

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

В силу симметричности принадлежности двух объектов одному подмножеству число переменных можно сократить и рассматривать только xij с i < j, добавив условия, что xji = xij, и условие рефлексивности xii = 1. Кроме того, для любой тройки должно выполняться отношение транзитивности. Но, в отличие от предыдущего примера из теории расписаний, в задачах разбиения между объектами, попавшими в одно подмножество, должна соблюдаться симметричность. Поэтому кроме одного неравенства типа (2.37) нужно сформулировать еще два неравенства. Итак, первое неравенство гарантирует, что если i и j в одном подмножестве, j и k в одном подмножестве, то i и k также в одном подмножестве, т. е.

Второе неравенство гарантирует, что если i и j в одном подмножестве, i и k в одном подмножестве, то j и k также в одном подмножестве, т. е.

Третье неравенство гарантирует, что если i и k в одном подмножестве, j и k в одном подмножестве, то i и j также в одном подмножестве, т. е.

2.4. Моделирование выбора минимального элемента Часто в задачах нужно, чтобы переменная из нескольких значений принимала минимальное значение. Например, необходимо, чтобы переменная y принимала значение, равное min(u1, u2 ), где u1, u2 0. Значит, одновременно должны выполняться неравенства и одно из неравенств Сложность возникает в моделировании выполнения одного из двух последних неравенств. Введем две вспомогательные булевы переменные:

через W обозначим некоторое большое положительное число. Тогда выбор минимального из двух чисел u1 и u2 эквивалентен совместности следующей системы ограничений:

Ограничение (2.47) говорит о том, что ровно одна из переменных, x1 или x2, будет равна 1. Предположим, что u1 < u2. Тогда случай, когда x1 = 0, x2 = 1, не возможен потому, что ограничение (2.48) будет выполнено при любом значении y, но из ограничения (2.49) получается y u2, следовательно, система (2.45)– (2.49) несовместна. Остается вариант, когда x1 = 1, x2 = 0, в этом случае условие (2.49) будет выполнено при любом значении y, а согласно неравенствам (2.45) и (2.48) получаем y = u1.

2.5. Моделирование взаимоисключающих событий Рассмотрим ситуацию, в которой возникает необходимость выполнения некоторой подгруппы ограничений. Предположим, что допустимая область формируется из нескольких групп неравенств. Например, пусть допустимая область соответствует заштрихованной части, как показано на рис. 4, и образована объединением двух многоугольников P1 и P2.

Каждый многоугольник задается группой неравенств.

Решение является допустимым, если оно удовлетворяет хотя бы одной группе неравенств P1 или P2. Другими словами, из двух групп ограничений нужно, чтобы выполнялась, по крайней мере, одна группа. Рассмотрим два способа моделирования этой ситуации.

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

Введем булевы переменные:

Введем вспомогательный вектор (w1, w2, w3, w4 ) с числом компонент, равным максимальному числу неравенств в P1 и P2, а значения компонент — большие положительные числа, такие, что при добавлении компоненты к правой части соответствующего неравенства это неравенство выполняется при любых значениях y1 и y2. Выпишем следующую систему ограничений I:

Условие (2.52) означает, что, по крайней мере, одна группа ограничений для P1 или для P2 выполняется. Если x1 = 0, то в силу (2.52) получается x2 = 1, и группа ограничений для P1 становится избыточной из-за наличия компонент вспомогательного вектора, а выполняться должна другая группа ограничений для P2. Аналогично если x2 = 0, то x1 = 1, и решение должно удовлетворять условиям для P2. Если x1 = 1, x2 = 1, то обе группы ограничений должны быть выполнены.

Второй способ Увеличим число переменных следующим образом. Будем разделять переменные y1 и y2 на два типа. В системе неравенств, определяющей область P1, будем использовать переменные y1, y2. В системе неравенств, задающих область P2, будем использовать переменные y1, y2. Причем y1 + y1 = y1, y2 + y2 = y2.

Кроме того, введем булевы переменные x1, x2, смысл которых, как и в первом способе. Запишем систему ограничений II :

Утверждается, что P1 P2 = тогда и только тогда, когда система II разрешима. Проверим это.

Пусть y1, y2 (P1 P2 ), можно считать, что y1, y2 P1. Тогда полагаем x1 = 1, x2 = 0, y1 = y1, y2 = y2, y1 = y2 = 0 — решение системы.

Пусть, без ограничений общности, x1 = 1, x2 = 0, y1 = y1, y2 = y2, y1 = y2 = 0 — решение системы II. Тогда y1, y2 P1, следовательно, P1 P2 =.

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

Задача составления расписания Имеется n работ и m машин. Для каждой работы задан порядок выполнения на машинах, т. е. работа j сначала выполняется на машине с номером j(1), затем на машине с номером j(2) и т. д. В каждый момент времени машина может выполнять не более одной работы, каждая работа выполняется не более, чем на одной машине. Работы не прерываются. Известна длительность pij выполнения работы j на машине i. Требуется выполнить все работы и минимизировать сумму времен завершения всех работ.

Введем целочисленные переменные tij, означающие время начала выполнения работы j на машине i. Введем mnn булевых переменных, чтобы задать условия непересечения работ при выполнении на одной машине:

Возникают взаимоисключающие друг друга условия. Если работа j предшествует работе k на машине i, то время начала работы k должно наступить не раньше времени завершения работы j:

Используя рассуждения изложенные в этом разделе, эти условия можно реализовать с помощью следующих неравенств:

где W — большое положительное число.

Каждая работа состоит из операций, выполняемых на разных машинах, и (r + 1)-я операция работы j не может начаться, пока не будет завершена предыдущая r-я операция, значит, Итак, математическая модель выглядит следующим образом. Целевая функция — минимальная сумма времен завершения всех работ:

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

Заметим, что в целевой функции (2.54) величина j=1 pj(m)j является постоянной и не зависит от порядка выполнения работ. Следовательно, оптимальное реn шение не изменится, если целевую функцию (2.54) заменить на min j=1 tj(m)j.

2.6. Линеаризация в математических моделях 2.6.1. Линеаризация произведения переменных Если в задаче встречается квадратичное выражение вида xi xj, где xi, xj {0, 1}, то для него можно предложить эквивалентную линейную переформулировку. Для этого введем новую булеву переменную yij, такую, что yij = xi xj, т. е.

другими словами, Применяя первое и второе правила к трем импликациям, получаем три следующих неравенства:

Или в более упрощенной форме:

Интересное и полезное наблюдение с точки зрения линейного программирования заключается в том, что даже если отказаться от булевости переменных yij и перейти к непрерывным значениям из отрезка [0, 1], то неравенства (2.55)– (2.58) будут выполняться, только когда переменные yij равны 0 или 1.

Пример. Задача о клике Задан неориентированный граф G с множеством вершин V и множеством ребер E. Задача заключается в том, чтобы найти максимальный (по количеству вершин) полный подграф, т. е. клику. Напомним, что простой граф без петель и кратных ребер называется полным, если любая пара вершин соединена ребром.

Введем следующие булевы переменные:

Тогда целевая функция найти клику максимальной мощности:

Подграф является кликой тогда и только тогда, когда он не содержит пару вершин, между которыми нет ребра в исходном графе, т. е.

С учетом описанных выше правил, эта импликация моделируется неравенством:

Добавив ограничения на значения переменных:

получаем постановку задачи о клике в виде математической модели (2.59)– (2.61) целочисленного линейного программирования.

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

Ребро (v, w) из множества E входит в подграф тогда и только тогда, когда обе вершины v и w входят в подграф. Следовательно, yvw = xv xw. Произведение можно линеаризовать, переписав в виде линейной системы неравенств. Из импликации yvw = 1 тогда и только тогда, когда xv = 1 и xw = 1 для (v, w) E, пользуясь правилами, получаем:

Итак, неравенства (2.60)–(2.64) гарантируют, что выбранный подграф будет кликой.

Заметим, что можно предложить другой вариант моделирования полноты подграфа. Рассмотрим произвольные четыре вершины. Если одна пара вершин в графе соединена ребром и другая пара вершин соединена ребром, а между какими-либо вершинами из этих пар ребра в графе нет, то в подграф должна входить только одна пара из этих вершин. Формально для любых s, t, u, v V, таких, что (s, t) E, (s, u) E и (t, v) E, в аналитической форме Эту формулировку можно получить из неравенств (2.60)–(2.64). Просуммировав пару неравенств типа (2.63) для (s, u) E и (t, v) E, получим ysu + ytv xs + xt. Поскольку (s, t) E, то из (2.60) получаем xs + xt 1, следовательно, неравенство (2.65) выполняется.

Последний вариант модели содержит меньше переменных, их столько, сколько ребер в исходном графе, но существенно больше ограничений по сравнению с (2.60)–(2.64).

2.6.2. Линеаризация заменой переменных Пример. Задача размещения с распределенными закупками Предпринимателю известно конечное множество I возможных мест для открытия p торговых центров и конечное множество потребителей J. Под потребителями можно понимать не индивидуальное лицо, а «типичного» представителя, который характеризует поведение некоторой группы людей. Потребители выбирают открытый торговый центр и расходуют деньги пропорционально своим предпочтениям. Предпочтение торгового центра i потребителем j измеряется величиной uij, uij 1 для всех i I, j J. Бюджет каждого потребителя ограничен величиной Bj. Предприниматель оценивает свою прибыль от каждой потраченной потребителем j денежной единицы в магазине i величиной cij.

Задача предпринимателя — открыть p торговых центров так, чтобы получить максимальную прибыль.

Введем булевые переменные:

и неотрицательные вещественные переменные yij, которые означают сумму, потраченную клиентом j в торговом центре i.

Целевая функция — максимальная суммарная прибыль:

при ограничениях на число открываемых предприятий:

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

Недостатком этой модели является нелинейная связь между переменными xi и yij в ограничениях (2.68).

Линеаризация модели Сделаем замену переменных. Введем новые неотрицательные вещественные переменные zj, j J, такие, что Тогда целевая функция и ограничение на число открываемых предприятий остаются без изменений. Условия, что клиенты могут посещать торговый центр, только если он открыт, записывается следующим образом:

Потребители тратят весь свой бюджет:

Следующая группа ограничений устанавливает связь между переменными yij и zj и определяет значения переменных zj в соответствии с равенством (2.70):

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

Группы ограничений (2.73), (2.74) означают, что если i-й торговый центр открыт, т. е. xi = 1, то значение yij будет совпадать со значением uij zj. Если же i-й торговый центр закрыт, xi = 0, то благодаря наличию в ограничении (2.74) достаточно большого числа Bj неравенство остается верным.

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

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

Обозначим через I множество филиалов, через J множество потребителей;

bj — бюджет j-го потребителя; cij — транспортные затраты от i-го филиала до j-го потребителя.

Введем неотрицательные переменные pi — стоимость продукции в i-м филиале и булевые переменные:

Целевая функция задачи — максимальный суммарный доход фирмы:

Каждый потребитель выбирает не более одного филиала:

Затраты каждого потребителя не должны превышать его бюджет:

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

Ограничения на принимаемые значения переменных:

Недостатком этой модели является нелинейность целевой функции (2.76) и ограничений (2.78), (2.79).

Линеаризация модели для задачи о ценообразовании Обозначим через pi максимально возможную цену в i-м филиале: pi = maxjJ (bj cij ). Введем неотрицательные вещественные переменные zij, отвечающие за доход, который получает производитель от i-го филиала и j-го потребителя в нем: zij = pi xij. Используя данные обозначения, получим следующую модель: при ограничениях:

Ограничения (2.84)–(2.86) гарантируют, что доход фирмы zij от обслуживания j-го потребителя в i-м филиале равен pi, если j-й потребитель выбрал i-й филиал, т. е. xij = 1, и равен нулю из условий (2.86) при xij = 0. По сути, ограничения (2.84)–(2.86) заменяют равенство zij = pi xij, что и приводит к линейной модели.

2.6.3. Линеаризация кусочно-линейной функции Пусть на отрезке [a0, ak ] задана кусочно-линейная функция (рис. 5):

Коэффициенты bi, ci, i = 0,..., (k 1) — действительные числа. Требуется смоделировать поиск минимума функции f (x), при a0 x ak.

Введем булевые переменные:

и неотрицательные переменные zi — столько от числа x лежит в интервале [ai, ai+1 ], т. е. zi = x ai.

MIP для поиска минимума f (x) выглядит следующим образом:

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

Проверим, что если (y, z, x) — допустимое решение, удовлетворяющее ограниk чениям в этой модели, то f (x) = i=0 (bi y i + ci z i ).

Рассмотрим y. Предположим, что y r1 = 1, y r = 0, 1 r (k 1). Т.к.

т.к. y r1 = 1, то Следовательно, i=0 (bi y i + ci z i )= i=0 bi + i=1 ci1 (ai ai1 ) +cr1 z r1 = i=1 ci1 (ai ai1 )+cr1 (x ar1 ). Последнее равенство следует из того, что по построению x = ar1 + z r1 при 0 z r1 (ar ar1 ), следоваk тельно f (x) = i=0 (bi y i + ci z i ).

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

2.7. Симметрия в математических моделях Один из недостатков, которым могут обладать математические модели, является симметрия в допустимых решениях. Этот недостаток приводит к тому, что точные методы, типа ветвей и границ, будут тратить время на просмотр и проверку эквивалентных решений. Рассмотрим один из вариантов симметрии и как от нее избавиться на примере задачи кластеризации [26].

Пусть требуется разбить конечное множество объектов I на p групп. Каждый объект может попасть только в одну группу. В разд. 2.3 уже рассматривались задачи кластеризации, но переменные, которые использовались там, в данном случае будут неудобными, поскольку сейчас необходимо отслеживать количество групп. Введем другие булевы переменные:

где i I, k = 1,..., p. Каждый объект должен попасть только в одну группу, значит, Сложность возникает в том, что группы можно пронумеровать по-разному, и в результате будут получаться формально разные решения, но по содержащимся в группах объектам это будет одно и то же решение. Например, для I = {a, b, c, d}, p = 3 и разбиения {a}, {b, d}, {c} следующие решения эквивалентны:

Таким образом, каждому разбиению множества объектов соответствует (p!) эквивалентных решений, отличающихся друг от друга нумерацией групп. Возникает необходимость избавиться от перестановочной симметрии и лишних, по сути, решений, оставив только одно из них. Одним из способов может быть установление лексикографического порядка на множестве решений. Для этого упорядочим объекты множества I от 1 до |I|.

Среди множества эквивалентных решений выберем одно следующим образом. В каждой группе найдем объект с наименьшим номером. Упорядочим группы по возрастанию этих номеров и пронумеруем группы от 1 до p согласно полученному порядку. Построенное таким образом решение будем называть лексикографически минимальным решением среди эквивалентных ему решений.

Например, разобьем множество {1,..., 10} на группы {4, 6, 8, 9}, {1, 2, 7}, {3, 5, 10}. Согласно установленному выше лексикографическому порядку группа {1, 2, 7} будет первой, {3, 5, 10} — второй, {4, 6, 8, 9} — третьей.

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

Назначения в группу 1. Объект 1 должен лежать в группе 1, т. е. x11 = 1.

Заметим, что остальные переменные x1k, при k > 1, равны нулю.

Назначения в группу 2. Если объект 2 не лежит в группе 1, то он должен лежать в группе 2, т. е.

Получаем неравенство:

Если объект 2 лежит в группе 1 и объект 3 не лежит в группе 1, то он должен лежать в группе 2, т. е.

Получаем неравенство:

Далее если объекты 2,..., (j 1) лежат в группе 1 и объект j не лежит в группе 1, тогда объект j должен быть в группе 2, т. е.

Получаем неравенство:

Назначения в группы c 3 по (p 1). В каждую группу k (k = 3,..., p 1) должен попасть объект с наименьшими номером, который еще не попал в предыдущую группу с номерами от 1 до (k 1). Значит, для любого объекта с номером j, если все предыдущие объекты с номерами от 2 до (j 1) лежат в группе l, l < k, а j не лежит в l, то j должен быть в группе k.

Вспомним, что каждый объект принадлежит только одной группе, значит i может лежать в группе с меньшим номером l (меньшим, чем k) тогда и только тогда, когда l=1 xil = 1.

Таким образом, чтобы еще не размещенный ни в одной группе объект j определял следующий номер группы c 3 по (p 1), должно быть выполнено условие: если l=1 xil = 1 и xjk = 1.

Следуя правилам 1 и 2, смоделируем эту импликацию в виде следующих неравенств:

или после приведения подобных:

Заметим, что переменные xik с индексами i < k не нужны, так как согласно лексикографическому порядку никакой объект не может быть размещен в группе с большим, чем у самого объекта, номером.

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

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

3.1. Задача о потоке минимальной стоимости В общем виде задача формулируется следующим образом. Задана сеть — ориентированный граф с множеством вершин V, в которых могут размещаться предприятия (поставщики, производители и пр.) некоторой продукции, множеством дуг A и двумя специальными вершинами: источником и стоком. Дуга (i, j) означает, что из вершины i в вершину j может осуществляться поставка некоторой продукции. Каждая дуга имеет неотрицательный вес uij, соответствующий пропускной способности этой дуги. Известны cij — удельные стоимости перевозки продукции вдоль дуги (i, j). Каждая вершина i имеет вес bi.

В зависимости от знака величины bi вес вершины может означать:

– спрос на продукцию в этой вершине (или сколько продукции должно быть доставлено в вершину i), если bi < 0;

– предложение продукции в этой вершине (или сколько продукции можно вывести из вершины i), если bi > 0;

– транзитная вершина (продукция не остается и не забирается из вершины Предполагается, что iV bi = 0.

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

Введем неотрицательные переменные xij — величина потока, пропускаемого по дуге (i, j).

Целевая функция — минимальные суммарные затраты на перевозки внутри сети:

при ограничениях на пропускные способности для каждой дуги:

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

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

Полученная модель линейного программирования (3.1)–(3.4) соответствует задаче о потоке минимальной стоимости.

В некоторых задачах за осуществление перевозок, кроме удельных затрат, взимаются затраты, которые не зависят от объемов перевозок. Пусть hij — плата за использование дуги (i, j). В этом случае нужны дополнительные булевы переменные:

Целевая функция изменится, в ней появятся дополнительные слагаемые:

Переменные xij и yij связаны следующим образом:

Согласно следствию из первого правила (разд. 2.2) эта зависимость моделируется следующим образом:

Модель (3.3)–(3.6) с yij {0, 1}, для всех (i, j) A, является моделью смешанного целочисленного программирования и соответствует задаче о потоке с фиксированными затратами [30].

Подобные задачи о потоках возникают при моделировании систем подачи воды, отопления. Этот класс задач обладает важным свойством: если все веса bi и пропускные способности uij являются целыми числами, то оптимальное решение будет целочисленным. Это свойство задачи будет важным при обсуждении вопроса о разрыве целочисленности в разд. 4.

3.2. Задача коммивояжера Дано n городов. Известно cij — время перемещения из города i в город j.

Коммивояжер выезжает из какого-то города, объезжает все города и возвращается в исходный. Необходимо найти такую последовательность посещения городов, при которой суммарное время перемещения было бы минимальным.

Введем n2 булевых переменных xij, i = 1,..., n, j = 1,..., n:

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

Например, при n = 4 решение со значениями переменных x12 = x21 = x34 = x43 = 1 удовлетворяет ограничениям (3.7), (3.8), но не является решением задачи, так как образует два цикла, как показано на рис. 6.

В 1954 г. Данциг предложил следующий способ исключения такой ситуации.

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

Обозначим через I множество всех городов. Пусть J — некоторое подмножество множества I, тогда условия, запрещающие всевозможные подциклы, выглядят следующим образом:

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

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

Предположим, что оптимальное решение задачи о назначениях состоит из двух подциклов. Пусть элементы cij, участвующие в подциклах, равны p, а остальные элементы равны q, q > p (рис. 7).

Рис. 7. Ликвидация подциклов в задаче коммивояжера Чтобы получить оптимальное решение задачи о коммивояжере, т. е. один цикл, необходимо «разорвать» первый и второй подциклы, как показано на рис. 7, т. е. удалить два ребра длиной 2p и добавить два ребра длиной 2q. Если в первом подцикле k ребер, а во втором — s, то значение целевой функции в задаче о назначениях на оптимальном решении равно (k + s)p. Для оптимального решения задачи о коммивояжере получаем значение целевой функции, равное (n 2)p + 2q. Тогда разница между оптимальными значениями составляет 2(q p). Следовательно, при фиксированном значении p величина q может быть выбрана так, что разность 2(q p) может быть сколько угодно большой.

Недостатком приведенной модели является то, что число ограничений экспоненциально, их (n + n + (2n1 n 1)). В работе Таккера в 1960 г. была предложена постановка с полиномиальным числом ограничений.

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

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

Сложив эти неравенства, получим kn (n 1)k, что невозможно при k = 0.

Проверим, что цикл, проходящий через все города, удовлетворяет условиям (3.14), т. е. можно подобрать соответствующие значения переменных ui. Пусть ui = k, если город i посетили на шаге k, тогда неравенство ui uj n 1 верно при xij = 0. Если xij = 1, то ui = k, а uj = (k + 1), тогда k (k + 1) + n n 1, Итак, (3.9)—(3.11), (3.13), (3.14), ui 0, i I — математическая модель задачи коммивояжера с полиномиальным числом ограничений.

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

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

Оставим прежние булевы переменные xij и введем полиномиальное количество новых переменных: yij — поток некоторой продукции между городами i и j, тогда ограничения (3.10), (3.11) и следующий набор ограничений представляют все гамильтоновы циклы в задаче о коммивояжере:

Ограничения (3.15) гарантируют перевозку продукции между городами i и j, только если xij = 1. Ограничение (3.16) говорит о том, что из первого города нужно развести (n 1) единиц товара по остальным городам, оставляя, согласно (3.17), в каждом городе ровно одну единицу товара. Чтобы развести всю продукцию, сеть должна быть связанной, таким образом, подциклов в обходе возникать не будет. Итак, в этой модели (n2 + 3n) ограничений и 2n2 переменных.

3.3. Задача о покрытии Задано n возможных мест расположения пожарных станций. Величины cj, j = 1,..., n задают стоимость размещения пожарной станции в месте j. Известно m объектов, на которые должны выезжать пожарные бригады. Причем пожарной бригаде имеет смысл выезжать на объект, если он находится на расстоянии не более D км, поэтому все объекты разбиты на группы объектов Mj, которые можно достичь из пожарной станции j.

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

Построим вспомогательную матрицу (aij )mn, чтобы задать разбиение объектов на группы:

Введем n булевых переменных xj, j = 1,..., n:

Целевая функция задачи — минимальные суммарные затраты на открытие станций:

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

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

Модели вида (3.20)–(3.22) соответствуют задачам о покрытии множества.

В рассмотренной задаче допускалось, что один объект может обслуживаться несколькими пожарными станциями, неравенство (3.21) гарантировало выполнение этого условия. Заменим в (3.21) знаки неравенства на равенства:

Получим более жесткое требование, которое означает, что нужно построить разбиение множества объектов на непересекающиеся подмножества. Модели вида (3.20), (3.22), (3.23) соответствуют задачам о разбиении множества на непересекающиеся подмножества. Заметим, что решение задачи о разбиении является также решением задачи о покрытии, но обратное неверно. Задача о разбиении может не иметь решения при разрешимой задачи о покрытии.

Например, пусть n = 3, m = 3, M1 = {1, 2}, M2 = {1, 3}, M3 = {2, 3}. Тогда задача о покрытии имеет несколько решений: x1 = (1, 0, 1), x2 = (0, 1, 1), а задача о разбиении не разрешима. Если же M3 = {3}, то задача о разбиении имеет решение: x = (1, 0, 1).

Рис. 8. Расположение предметов без поворотов 3.4. Задача о двухстадийном гильотинном раскрое Задачи о раскрое имеют широкое применение в различных отраслях промышленности: машиностроении, деревообработке, стеклопроизводстве [29]. Их суть в том, чтобы разместить и вырезать заготовки из материала с учетом различных технологических требований. Задачи классифицируются по форме заготовок, их размерности, способу разрезов. Часто по технологии можно выполнять только гильотинные разрезы, когда каждый разрез листа выполняется перпендикулярно одной из сторон листа и параллельно другой стороне от одного края до другого. В зависимости от узора на поверхности определяется ориентация вырезаемых кусков. Например, если на кусках задан рисунок, то повороты могут быть запрещены (рис. 8).

В двухстадийной задаче разрезы выполняются постадийно. На первой стадии лист разрезается по вертикали на несколько параллельных полос, на второй стадии каждая полоса разрезается по горизонтали на прямоугольные куски (рис. 9).

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

Рис. 10. Двухстадийный раскрой с подрезкой остатков материала Рис. 11. Линейные размеры для задачи о раскрое С точки зрения оптимизации можно сформулировать различные задачи.

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

Задача о двухстадийном гильотинном раскрое Имеется один лист материала шириной W, длиной L и n типов прямоугольных заготовок шириной wj и длиной lj каждая, j = 1,..., n (рис. 11). Каждую заготовку можно вырезать в любом количестве. Известен доход pj от продажи заготовки j. Требуется определить, какие заготовки и в каком количестве нужно вырезать, чтобы получить максимальный доход. Повороты прямоугольников при выкраивании запрещены, раскрой листа — гильотинный.

Поскольку раскрой гильотинный, значит на первой стадии лист разрезается по вертикали. Пусть k — максимальное число вертикальных полос, тогда k можно оценить сверху величиной lmin, где lmin — длина самого короткого прямоугольника, lmin = minj{1,...,n} {lj }. Пусть mj — максимальное количество прямоугольников j-го типа, которое можно выкроить из данного листа, mj можно оценить сверху величиной lLWj.

Введем следующие целочисленные переменные:

yi — длина i-й полосы, i = 1,..., k, xij — количество прямоугольников j-го типа, выкраиваемых из i-й полосы.

Чтобы выписать условие на вместимость прямоугольника j-го типа в i-ю полосу, нужно ввести вспомогательные булевы переменные:

Используя введенные переменные, выпишем математическую модель.

Целевая функция задачи — максимальный суммарный доход:

ограничения задачи:

– общая ширина всех заготовок, выкраиваемых из i-й полосы, не превышает ширины листа – суммарная длина всех полос не превышает длины листа:

– длина i-й полосы позволяет выкроить j-ю заготовку:

Необходима еще группа ограничений, чтобы связать булевы переменные x ij с целочисленными переменными xij и гарантировать, что если j-я заготовка выкраивается из i-й полосы, то можно выкроить ограниченное число заготовок, и наоборот, нельзя выкраивать j-ю заготовку из i-й полосы, если она не помещается по размерам, т. е. нужно смоделировать два взаимоисключающих условия:

Это можно реализовать с помощью следующих неравенств:

Последняя группа ограничений на значения переменных:

3.5. Задача о разрезе балок В деревообрабатывающий цех поступил заказ вырезать короткие бруски прямоугольной формы из длинных прямоугольных балок. Высота балок и брусков одинаковая. Заказ состоит из b разных типов брусков, в количестве ni штук каждого, i = 1,..., b. На складе имеется l разных типов балок длиной Lj каждая в количестве Qj, j = 1,..., l. Бруски можно вырезать из имеющихся балок, в этом случае стоимость выполнения одного разреза составляет c y. e., можно купить готовые по цене pi y. e. за один брусок i-го типа. Задача заключается в том, чтобы выполнить заказ на бруски с минимальными суммарными затратами.

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

Пусть sj — количество возможных вариантов раскроя j-й балки, kis — колиj чество брусков i-го типа, выкраиваемых из j-го типа балки по s-му варианту, fs — столько разрезов выполняется на j-й балке по s-му варианту, где j = 1,..., l i = 1,..., b s = 1,..., sj. Обрезание остатков балки до нужной длины бруска тоже считается разрезом.

Введем неотрицательные целочисленные переменные ys — столько раз исl пользуется s-я карта раскроя, s = 1,..., ( j=1 sj ), неотрицательные целочисленные переменные xi — количество купленных готовых брусков, i = 1,..., b.

Целевая функция — минимальные суммарные затраты, которые складываются из затрат на разрезание и закупку:

Общее число балок разной длины не превосходит имеющегося количества на складе:

Необходимо выполнить заказ на бруски разной длины:

Допустимые значения переменных:

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

Пример Заказ состоит из 60 брусков длиной 8 м, 40 брусков длиной 5 м и 75 брусков длиной 3 м. Длина балок составляет 12 и 10 м, в наличии имеется 20 и 25 штук соответственно. Стоимость выполнения одного разреза составляет 0,5 y.e., готовые бруски покупаются по цене 2 y.e., 1,5 y.e., 1,1 y.e. за восьми-, пяти- и трехметровый брусок соответственно. Выполнить заказ на бруски с минимальными суммарными затратами.

В данном случае получается 8 карт раскроя (рис. 12). Математическая модель выглядит следующим образом:

min y1 + y2 + 1.5y3 + 1.5y4 + 0.5y5 + 0.5y6 + y7 + 1.5y8 + 2v1 + 1.5v2 + 1.1v 3.6. Задача о башнях Имеется конечное множество клиентов {1,..., n} и конечное множество возможных мест, где можно размещать башни сотовой связи {1,..., m}. Известны расстояния между клиентами и башнями. Каждый клиент прикрепляется к ближайшей башне, если ближайших башен несколько, то к любой из них.

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

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

Сформулируем эту задачу в виде задачи целочисленного линейного программирования. Введем булевы переменные:

1, если i-й клиент обслуживается башней в j-м пункте, и неотрицательные целочисленные переменные:

u — максимальное число клиентов, обслуживаемых одной башней, l — минимальное число клиентов, обслуживаемых одной башней.

Тогда в целевой функции минимизируется разница:

при условиях:

и ограничениях на допустимые значения переменных:

где Mi = maxj{1,...,m} cij, i {1,..., n}.

Группа ограничений (3.25) уже встречалась в моделях размещения, она гарантирует, что обслуживание клиентов будет только из «активных» башен. Ограничение (3.26) насчитывает число размещенных башен. Ограничения (3.27) гарантируют, что каждый клиент обслуживается одной башней. Ограничения (3.28) и (3.29) определяют максимальное и минимальное число клиентов по всем башням. Для того, чтобы переменная l не обращалась в нуль, в правой части ограничений (3.29) добавлено слагаемое n(1 yj ), которое позволяет при yj = 0 не ограничивать значение переменной l сверху, а при yj = 1 насчитать минимальное число клиентов и выбрать башню с наименьшей загруженностью.

Ограничения (3.30) гарантируют, что каждому клиенту соответствует ближайшая башня.

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

Математическая модель следующего вида называется моделью смешанного целочисленного линейного программирования, записанная в стандартной форме (сокращенно M IP, от англ. mixed integer programming):

где c = (c1,..., cn ), f = (f1,..., fp ) — вектор-строки с вещественными компонентами, задающие коэффициенты целевой функции;

x = (x1,..., xn )T — вектор-столбец переменных задачи, принимающих неотрицательные вещественные значения;

y = (y1,..., yp )T — вектор-столбец переменных задачи, принимающих неотрицательные целочисленные значения;

A, B – матрицы размерности (mn) и (mp) соответственно, с рациональными значениями компонент, определяющие коэффициенты в системе из m ограничений;

b = (b1,..., bm )T — вектор-столбец с вещественными компонентами правых частей ограничений.

Обозначим через XM IP множество значений переменных, удовлетворяющих ограничениям (4.2)–(4.4). Множество XM IP называют множеством допустимых решений задачи. Обозначим через z (XM IP ) оптимальное значение целевой функции (4.1) на множестве XM IP.

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

Существуют каноническая и общая формы записи M IP. Каждую из этих форм можно преобразовать в стандартную, пользуясь следующими простыми соображениями:

— ограничения равенства Ax + By = b эквивалентны паре неравенств Ax + — задача на максимум с целевой функцией (cx+f y) эквивалентна задаче на минимум с целевой функцией (cx + f y). Аналогичные преобразования, т. е.

умножение на (1), нужно сделать в неравенствах со знаком ;

— каждое вхождение свободной переменной x, т. е. переменной без ограничения на знак, нужно заменить разностью двух новых неотрицательных переменных, x = (u v). Таким образом, все переменные в модели будут неотрицательными.

Любое оптимальное решение, полученное для модели в стандартной форме, нетрудно преобразовать в оптимальное решение исходной задачи, и наоборот.

Задача M IP, в которой все переменные принимают значения только 0 или 1, называют задачей булева, или 0–1, программирования.

Задача M IP, в которой все целочисленные переменные принимают значения 0 или 1, называют задачей смешанного 0–1 программирования.

Задача M IP, в которой все переменные принимают вещественные значения, называют задачей линейного программирования (сокращенно LP, от англ.

linear programming).

Задача M IP, в которой все переменные принимают только целые значения, называют задачей полностью целочисленного программирования (сокращенно IP, от англ. integer programming).

Известно, что задача IP является NP-трудной в общем случае [5], но полиномиально разрешима при фиксированном числе переменных [22]. Задача IP имеет широкие рамки, внутри которых формулируются задачи M IP смешанного 0–1 программирования. Слабое место этих задач в том, что в общем виде не известно алгоритма, практически применимого для решения задач большой размерности.

Решать задачу LP в общем случае проще, чем соответствующую задачу M IP, потому что для LP существуют точные полиномиальные алгоритмы [13].

Поэтому иногда в задачах M IP отказываются от условий целочисленности и решают соответствующую задачу LP. Некоторые задачи обладают тем свойством, что оптимальное решение задачи LP является целочисленным, однако это не всегда так. Отказ от условий целочисленности в задаче M IP и переход к соответствующей задаче LP называют линейной релаксацией. Под линейной релаксацией задачи (4.1)–(4.4) понимается следующая задача:

Будем обозначать задачу (4.5)–(4.8) через LR (от англ. relaxation — ослабление), а множество допустимых решений (4.6)–(4.8) через XLR. Нетрудно заметить, что множество XLR шире допустимого множества XM IP : XM IP XLR.

Значит, оптимальное значение целевой функции задачи линейной релаксации дает нижнюю оценку на оптимум соответствующей задачи M IP : z (XLR ) z (XM IP ), если исходная задача на минимум, и дает верхнюю оценку, если исходная задача M IP на максимум.

4.2. Разрыв целочисленности Величина отклонения оптимального значения линейной релаксации от оптимального значения целевой функции для задачи смешанного целочисленного программирования называется разрывом целочисленности. Рассматривают абсолютный разрыв целочисленности и относительный разрыв целочисленности Для вычисления разрыва нужно точно решить обе задачи. Часто вместо оптимальных значений рассматривают хорошие приближенные значения для z (XLR ) и z (XM IP ) и тогда вместо разрыва целочисленности вычисляют следующую величину:

где U B, LB — верхняя и нижняя оценка оптимального решения соответственно. Оптимальное значение должно лежать в промежутке [LB, U B]. Иногда в решателях разрыв вычисляется по отношению к нижней оценке, т. е. в знаменателе стоит LB вместо U B.

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

Пример [28] Рассмотрим следующую задачу P1 :

Заменим в задаче P1 условие (4.12) на условие x1 0, целые и обозначим новую задачу P2. Заменим в задаче P1 условие (4.13) на условие x2 0, целые и обозначим новую задачу P3. Заменим в задаче P1 оба условия (4.12), (4.13) на x1 0, целые и x2 0, целые, полученную задачу IP обозначим P4.

На рис. 14 изображено графическое представление допустимой области для каждой из задач P1, P2, P3 и P4.

Задача P1 является задачей линейного программирования, и ее допустимая область XP1 — это заштрихованная часть, в том числе и границы. Для задачи смешанного целочисленного программирования P2 допустимая область XP2 — это вертикальные отрезки, проходящие через точки с целочисленными значениями x1, удовлетворяющие ограничениям задачи. Аналогично для задачи P допустимая область XP3 — это горизонтальные отрезки. Допустимая область XP4 для задачи полностью целочисленного программирования P4 состоит из восьми точек с целочисленными координатами, удовлетворяющих ограничениям задачи. Таким образом, после добавления требования целочисленности область XP4 стала существенно меньше по сравнению с XP1, XP2, XP3. Рассмотрим оптимальные решения этих задач:

Нетрудно заметить, что, переходя от решения задачи P1 с наименее жесткими требованиями к задаче P4 с более жесткими требованиями, оптимальное значение целевой функции уменьшается: z (XP4 ) < z (XP1 ).

Пример В рассмотренных выше примерах оптимальное решение задачи P4 может быть получено округлением решения задачи P1 вниз. Однако округление не всегда приводит к оптимальному решению соответствующей задачи M IP. Рассмотрим следующую задачу:

Оптимальным решением соответствующей задачи линейного программирования будет x = (6.5455, 0.7955) со значением целевой функции zLP = 13.8864. Оптимальным решением исходной задачи является вектор xIP = (5, 1) со значением целевой функции zIP = 11. Из рис. 15 видно, что x нельзя получить простым округлением решения x. LP Вычислим разрыв целочисленности. Абсолютный разрыв составляет 13.8864 11 = 2.8864, относительный равен 13.8864 · 100 % = 20.79 %. Величина относительного разрыва дает информацию о том, насколько сложной в вычислительном плане окажется задача для точных методов, которые используют решение линейной релаксации при доказательстве оптимальности целочисленного решения. Обычно задачи с относительным разрывом 10 % считаются простыми, а задачи с разрывом 50 % — сложными. В связи с этим среди разных возможных математических моделей M IP лучше выбирать ту, у которой разрыв целочисленности меньше.

Рис. 15. Оптимальные целочисленное и дробное решения Более того, может оказаться, что задача LP имеет решение, а соответствующая задача IP не разрешима. Например, заменим ограничение (4.16) на тогда область допустимых решений в задаче (4.14), (4.15), (4.17)–(4.19) — это треугольник ABC (рис. 16). Оптимальное решение соответствующей задачи LP находится в точке C. Заметим, что ни одна целочисленная точка не входит в область ABC, следовательно, множество допустимых решений в задаче IP (4.14), (4.15), (4.17)–(4.19) является пустым.

Пусть допустимая область образована неравенствами:

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

Рис. 16. Допустимая область — треугольник ABC Рис. 17. Допустимая область — многогранник ABCDEF Пример. Задача планирования производства Завод занимается производством некоторой однотипной продукции. Продукция производится в начале месяца и либо отправляется потребителям сразу, либо хранится на складе. Продукцию можно производить и хранить на складе на протяжении всего горизонта планирования. Производственные затраты складываются из единовременных расходов на запуск производства, удельных производственных затрат и удельных затрат на хранение продукции. Задан промежуток времени T месяцев, в течение которого необходимо спланировать производство и хранение продукции так, чтобы выполнить заказ с минимальными затратами.

Обозначим через dt — заказ на продукцию в месяц t, ct — затраты на запуск производства в месяц t, pt — удельные затраты на производство в месяц t, ht — удельные затраты на хранение продукции в течение месяца t. Выпишем две модели с разными переменными.

Первая модель использует следующие переменные:

yt — количество продукции, произведенной в месяц t;

количество продукции, оставленной на складе к концу месяца t;

1, если в месяц t было запущено производство, Тогда получаем следующую математическую модель:

Целевая функция (4.25) — минимальные общие затраты, которые складываются из затрат на запуск, производство и хранение. Ограничения (4.26) и (4.27) отвечают за удовлетворение спроса и выполнение «закона сохранения» продукции в каждом месяце. Поскольку в начальный момент времени на складе отсутствует продукция, то для первого месяца выписано отдельное условие.

Ограничения (4.28) устанавливают связь между переменными xt и yt и ограничивают сверху максимальный ежемесячный объем партии. Только если производство запущено в месяц t, на нем может производится продукция, но не более, чем величина суммарного спроса на него. Ограничение (4.29) задает уровень запасов на складе в конце горизонта планирования.

Вторая модель использует следующие переменные: qit — столько продукции производится в месяц i, чтобы выполнить заказ в месяц t, t i, переменные xt остались теми же, что и в предыдущей модели. Используя введенные переменные, получаем следующую математическую модель:

Вторая модель обладает тем свойством, что если требование целочисленности переменных xt заменить на условие непрерывности переменных 0 xt 1, то в оптимальном решении соответствующей задачи линейной релаксации переменные xt будут принимать значение 0 или 1, т. е. разрыв целочисленности для LR (4.31)–(4.34) равен нулю. Первая модель — это M IP, поскольку в ограничениях (4.28) имеются большие константы, то разрыв целочисленности не равен нулю.

Следующая теорема дает оценку близости решений IP и соответствующей LR.

Теорема [22]. Пусть A — целочисленная (m n)-матрица, каждый минор которой по абсолютной величине не превосходит, и пусть даны векторы b и c. Предположим, что оба максимума конечны. Тогда:

1. Для любого оптимального решения y задачи (4.35) существует оптимальное решение z задачи (4.36), для которого y z n.

2. Для любого оптимального решения z задачи (4.36) существует оптимальное решение y задачи (4.35), для которого y z n.

(y обозначает максимум абсолютных величин компонент вектора y.) Эта теорема обобщает результат о том, что для любой рациональной матрицы A существует такой конечный набор векторов x1,..., xN, что для любой вектор-строки c и любого целочисленного вектор-столбца b из того, что x является оптимальным базисным решением (вершиной) релаксированной задачи целочисленного линейного программирования max{cx|x 0, Ax = b}, следует, что оптимум IP max{cx|x 0, Ax = b, x Z} достигается на одном из векторов Пример Следующий пример показывает, что указанная в теореме граница n не улучшаема.

для любого, 0 < 1 следующие векторы являются единственными решениями задач max{cx|Ax b} и max{cx|Ax b, x Z}:

4.3. Число ограничений и переменных в модели Качество построенной математической модели можно оценивать по разным показателям. Для задач булевого программирования одним из показателей является количество булевых переменных. Число переменных особенно важно при решении задач точными методами, одним из которых является метод ветвей и границ [13]. В процессе решения этим методом строится так называемое дерево ветвления. Число вершин в дереве зависит от количества булевых переменных. Таким образом, если в модели n булевых переменных, то в дереве ветвления может быть 2n вершин в худшем случае. Следовательно, с ростом n время решения задачи может расти экспоненциально.

Рассмотрим на примерах несколько идей для сокращения количества переменных.

Пример Имеется парк из трех грузовиков и два маршрута, по которым нужно отправить грузовики. Предполагается, что все грузовики одинаковые. Требуется назначить грузовики на маршруты. Это можно сделать несколькими способами.

Первый способ. Пусть где i {1, 2, 3}, j {1, 2}. Этот способ может привести к тому, что в дереве ветвления в худшем случае будет 26 вершин.

Второй способ. Пусть 1, если грузовик i отправляется по первому маршруту, 0, если грузовик i отправляется по второму маршруту, где i {1, 2, 3}. Этот способ может привести к тому, что в дереве ветвления в худшем случае будет 23 вершин.

Второй способ приводит к меньшему количеству переменных для ветвления.

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

Третий способ. Пусть nj — количество грузовиков, отправленных по маршруту j. Тогда решение и решения (4.37), (4.38), (4.39) и (4.40), по сути, подразумевают одно и то же назначение грузовиков на маршруты, но теперь в модели, в три раза меньше переменных.

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

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

Поясним это на следующем примере.

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

Введем булевы переменные:

Ограничение-равенство гарантирует, что будет реализован только один вариант работы фабрики.

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

Тогда вместо ограничения (4.41) будет пара ограничений:

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

Пример [31] Пусть в задаче имеется ограничение вида где все переменные xj, коэффициенты aj и правые части ограничений b — целые числа.

В процессе решения программными средствами это ограничение приводится к канонической форме. Для этого добавляется так называемая переменная недостатка u, u 0, такая, что Однако это можно сделать вручную на этапе построения модели. Нетрудно заметить, что если все коэффициенты и переменные в ограничении целые числа, то u может принимать только целые значения. Наличие этой переменной позволяет организовать процесс ветвления по ней, а само ограничение (4.42) будет выступать в качестве отсекающей плоскости в соответствующей задаче LR [22].

4.4. Многогранники. Правильные неравенства Рассмотрим следующую задачу IP :

Пусть X — множество допустимых решений этой задачи. Множество точек P = {x Rn |Ax b}, удовлетворяющих конечному числу линейных неравенств, называют многогранником.

Многогранник P называют представлением множества допустимых решений X, если X совпадает с целочисленными точками из многогранника, т. е.

X = P Zn. На рис. 18 приводится два представления.

Пусть P 1 и P 2 — два представления для X. Как уже неоднократно наблюдалось в предыдущих разделах, для одной и той же задачи можно предложить несколько математических моделей. Возникает вопрос: «Существует ли наилучшее представление и как его найти?»