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

Представление P 1 лучше P 2, если P 1 P 2, поскольку допустимые целочисленные решения задачи лежат и в P 1, и в P 2, но с точки зрения линейной релаксации допустимая область представления P 2 больше, поэтому разрыв целочисленности с P 1 будет меньше, чем с P 2, и для задачи на минимум Выпуклой оболочкой множества X называется множество conv(X), состоT T ящее из точек вида x = i=1 i xi, где i=1 i = 1, i 0, i = 1,..., T, где {x1,..., xT } все точки из X, а T — общее число точек в множестве X. В этом случае точка x является выпуклой комбинацией точек {x1,..., xT }. Выпуклая оболочка conv(X) образует многогранник и является лучшим из возможных представлений для X (рис. 19). Суть выпуклой оболочки в том, что все крайние точки допустимого множества X содержатся в ней. Из теории линейного программирования известно, что оптимальное решение задачи LP достигается именно в крайних точках. Кроме того, conv(X) содержится в любом множестве, содержащем X. Таким образом, conv(X) — это минимальное множество, содержащее X и описываемое системой линейных неравенств, а значит модель задачи с представлением, в котором оно совпадает с выпуклой оболочкой, является самой лучшей моделью с точки зрения разрыва целочисленности. В этом случае разрыв равен нулю.

С практической точки зрения поиск такой переформулировки задачи сталкивается со следующими трудностями:

1) заранее неизвестно, как задать conv(X), а ее нахождение является не менее сложной задачей, чем решить исходную задачу M IP ;

2) для многих задач M IP описание conv(X) требует экспоненциального чисРис. 19. Наилучшее представление ла переменных и линейных неравенств, а значит для решения полученной таким образом задачи LP потребуется много времени. С другой стороны, добавление «правильных» ограничений улучшает верхнюю оценку LP и может заметно ускорить время работы алгоритма. Неравенства, добавление которых не меняет целочисленную допустимую область, называют правильными неравенствами.

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

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

Рис. 21. Целочисленные допустимые решения Заметим, что множество целочисленных точек Y1 и Y2 совпадает (рис. 21) Следовательно, неравенства (4.50)–(4.52) — правильные.

Добавление правильных неравенств позволяет сузить допустимую область в задаче линейной релаксации, но не меняет допустимой области в задаче целочисленного программирования. На рис. 21 видно, что после добавления неравенств (4.50)–(4.52) к системе (4.43)–(4.49) допустимая область задачи линейной релаксации уменьшилась и совпадает с внутренней частью многогранника ABM N EF.

Пусть f — линейная целевая функция. На рис. 22 показано направление градиента f. Требуется найти max f при ограничениях (4.43)–(4.49). Мы устаРис. 22. Допустимая область и направление градиента новили, что добавление неравенств (4.50)–(4.52) не меняет целочисленную область, следовательно, вместо исходной задачи можно решать задачу линейной релаксации (4.43)–(4.52). Оптимальное решение задачи линейной релаксации лежит в крайней точке N с целочисленными координатами. Таким образом, разрыв целочисленности равен нулю. Это означает, что оптимальное решение задачи M IP с целевой функцией f при ограничениях (4.43)–(4.49) совпадает с оптимальным решением задачи LP с целевой функцией f при ограничениях (4.43)–(4.52). Следовательно, в данном случае вместо задачи M IP можно решать задачу LP. Допустимая область, образованная (4.43)–(4.52), совпадает с conv(Y1 Y2 ).

В рассмотренном выше примере неравенство y1 + y2 6 — правильное, но оно не улучшает представление допустимого множества с точки зрения сокращения разрыва целочисленности. Неравенство y2 2 не только является правильным, но еще и формирует conv(Y1 ). Возникает вопрос: «Как строить правильные неравенства, определяющие выпуклую оболочку?»

Построение правильных неравенств Существует много способов построения правильных неравенств [25, 30], но универсального алгоритма не известно. Рассмотрим один из наиболее простых способов.

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

Вернемся к множеству Y1, которое задается системой неравенств (4.43)– (4.49), и построим правильное неравенство. Мы уже заранее знаем ответ, это неравенство (4.50), которое обсуждалось выше.

Рассмотрим в качестве релаксации множества Y1 множество Y, состоящее из точек, удовлетворяющих следующим неравенствам: (4.43)—(4.45), 0 y2 3, (4.48) и (4.49). Неравенство y2 3 получается, если учесть, что y1 +8y2 26 и y1 0, y1 целые, а следовательно, y2 26 = 3. Теперь, учитывая (4.45), заметим, что неравенство y1 +y2 6 является правильным для Y, следовательно, оно будет правильным и для Y1.

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

Пример. Правильные неравенства для задачи планирования производства Вернемся к задаче (4.25)–(4.30). Рассмотрим правильные неравенства для этой задачи.

Утверждение. Для любых l и C неравенства являются правильными для задачи (4.25)–(4.30).

Доказательство. Проверим, что добавление неравенств (4.55) в модель не приводит к потере допустимых решений задачи. Возьмем допустимое решение (y, s, x) задачи (4.26)–(4.30) и покажем, что неравенства (4.55) выполняются.

Рассмотрим два случая.

Тогда yi = 0 для любого i C и из (4.55) получаем, что sl 0.

требовалось доказать.

Известен и более сильный результат.

Теорема [30]. Выпуклая оболочка множества (4.26)–(4.30) задается следующей системой ограничений:

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

Квадратная матрица D = (dij ) с целочисленными компонентами, i = 1,..., m, j = 1,..., m называется унимодулярной, если ее определить равен ±1.

Матрица A = (aij ) с целочисленными компонентами, i = 1,..., m, j = 1,..., n называется полностью унимодулярной, если определитель любой ее квадратной подматрицы равен 0 или ±1.

Таким образом, полностью унимодулярная матрица состоит из 0, 1 или 1.

Однако, например, матрица не является полностью унимодулярной, поскольку определитель подматрицы, составленной из первых трех столбцов и первых трех строк, равен —2.

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

Теорема [30]. Следующие утверждения эквиваленты.

1. Матрица A является полностью унимодулярной.

2. Матрица, полученная транспонированием матрицы A, является полностью унимодулярной.

3. Матрица, полученная приписыванием к A единичной матрицы E справа, является полностью унимодулярной.

4. Матрица, полученная удалением строки (столбца) из матрицы A, является полностью унимодулярной.

5. Матрица, полученная умножением строки (столбца) матрицы A на (1), является полностью унимодулярной.

6. Матрица, полученная перестановкой двух строк (столбцов) матрицы A, является полностью унимодулярной.

7. Матрица, полученная дублированием строк (столбцов) матрицы A, является полностью унимодулярной.

8. Матрица, полученная после выполнения операции замены базисной переменной, является полностью унимодулярной.

Следующее достаточное условие гарантирует, что матрица A будет полностью унимодулярной.

Утверждение [13]. Матрица A, составленная из 0, 1 или —1, является полностью унимодулярной, если в каждом столбце не более двух ненулевых элементов, и строки матрицы A можно так разбить на два подмножества I1 и I2, что для каждого столбца верно следующее:

1. Если два ненулевых элемента имеют одинаковые знаки, то соответствующие им строки лежат в разных множествах.

2. Если два ненулевых элемента имеют разные знаки, то соответствующие им строки лежат в одном и том же множестве.

Рассмотрим задачу LP в следующем виде:

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

Каким условиям должна удовлетворять матрица A = (aij ) и вектор правых частей b = (b1,..., bm )T, чтобы все вершины многогранника (4.63)–(4.64) были целочисленными? Ответ на этот вопрос дает следующая теорема.

Теорема [30]. Пусть целочисленная матрица A = (aij ), i = 1,..., m, j = 1,..., n, m < n имеет ранг m и вектор правых частей b = (b1,..., bm )T — целочисленный. Для того, чтобы вершины многогранника (4.63)–(4.64) лежали в целочисленных точках, необходимо и достаточно, чтобы матрица A была полностью унимодулярной.

Пример. Транспортная задача Пусть имеется m пунктов производства и n пунктов потребления однородного продукта. Объем производства в пункте i равен ai ; объем потребления в пункте j равен bj, i = 1,..., m, j = 1,..., n. Предполагается, что производство и потребление сбалансированы, т. е.

Задана матрица c = (cij ) транспортных расходов на перевозку единицы продукции из пункта производства i в пункт потребления j. Требуется составить план перевозок, который, не нарушая производственные мощности, удовлетворяет все потребности с минимальными суммарными затратами на перевозки.

Введем переменные xij 0, обозначающие объем перевозок из пункта производства i в пункт потребления j. Тогда получаем следующую задачу линейного программирования:

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

Условие сбалансированности производства и потребления является необходимым и достаточным условием разрешимости транспортной задачи [13]. Число переменных xij в этой задаче равно mn, число ограничений равно m + n.

Из-за условия сбалансированности производства и потребления строки (4.67) и (4.68) являются линейно зависимыми, следовательно, ранг системы ограничений равен (m + n 1), а значит число ненулевых значений xij не превосходит (m + n).

Если объемы производства ai и объемы потребления bj — целые числа, то любая вершина многогранника (4.67)–(4.69) целочисленная, поскольку матрица ограничений является полностью унимодулярной [4].

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

Пусть в модели имеются булевы переменные xi, i = 1,..., n и задача требует, чтобы выполнялось следующее условие:

Тогда неравенство гарантирует выполнение этого условия. Нетрудно заметить, что условие (4.70) можно смоделировать и по-другому, системой из (n 1) неравенств:

Построив для модели с представлением (4.72) двойственную задачу [14], нетрудно заметить, что матрица ограничений соответствующей двойственной задачи будет полностью унимодулярной. Следовательно, решив линейную релаксацию двойственной задачи, можно найти оптимальное целочисленное решение исходной задачи, пользуясь средствами линейного программирования. Таким образом, замена одного ограничения (4.71) системой ограничений (4.72) улучшает модель.

4.6. Уточнение значения границ переменных Рассмотрим распространенное в моделях M IP ограничение вида y ux, где u — некоторое положительное число, x {0, 1}. Насколько важно значение u с точки зрения разрыва целочисленности?

Если переменная x принимает целые значения, то неважно, чему равно u, но если 0 x 1, то значение u оказывается существенным.

Предположим, что максимальное допустимое значение, которое может принимать переменная y, равно u и u < u, а в целевой функции имеются слагаемые вида f x, соответствующие, например, затратам на запуск производства, f > 0. Если в оптимальном решении y = u, то, учитывая ограничение y ux, получаем, что x = u и x < 1. Следовательно, затраты составят f u. С другой стороны, если бы ограничение было записано как y u x, то при y = u получили бы x = 1 и затраты составили бы величину f. Следовательно, чем грубее значение u по сравнению с u, тем больше разрыв целочисленности.

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

Пример В задаче о планировании производства, рассмотренной в разд. 4.2, в ограничениях (4.28) для каждого промежутка времени t вместо грубой оценки k=1 dk лучше использовать уточненную оценку k=t dk.

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

Рис. 23. Сеть для задачи о потоке с фиксированными затратами Известны cij — удельные стоимости перевозки продукции вдоль дуги (i, j), hij — плата за использование дуги (i, j), bi — спрос или предложение в вершине i. Требуется доставить 3 и 7 единиц продукции в 3-ю и 4-ю вершины соответственно с минимальными затратами.

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

Пусть B — некоторое положительное большое число.

Математическая модель выглядит следующим образом:

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

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

Итак, вес первой вершины составляет 10 единиц. Если дуга (1, 2) используется, то по дуге x12 можно отправить не более 10 единиц, следовательно, Вторая вершина — транзитная, и доставить в нее можно не более 10 единиц, следовательно, и вывезти из нее по каждой выходящей дуге можно не более единиц, значит В третьей вершине потребляется 3 единицы продукции, поэтому если доставить максимально возможное количество продукции в размере 10 единиц в третью вершину, то вывезти из нее можно будет не более 7 единиц:

Аналогично получаем следующие уточненные границы на значения переменных:

Добавление новых неравенств вместо ограничений (4.74) позволяет сузить допустимую область и сократить разрыв.

4.7. Удаление избыточных ограничений Рассмотрим еще один способ предварительной обработки математической модели с булевыми переменными. Пусть допустимое множество задается группой линейных неравенств вида Если aj < 0 для некоторого j, тогда заменой переменной xj на (1 x ) можно получить эквивалентное ограничение:

j=1,...,n|aj >0 j=1,...,n|aj b, для некоторого N {1,..., n}, то в модель можно ввести дополнительное неравенство или несколько неравенств для каждого k N, при котором jN \{k} aj b.

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

Пример Рассмотрим следующую систему неравенств:

Выполним замену переменных, получим:

Учитывая (4.78) для (4.83), получаем для (4.85) получаем Объединяя (4.87) и (4.88), получаем x2 = 1 или x = 0, и тогда ограничение (4.79) избыточное, а ограничения (4.84) и (4.85) превращаются в Учитывая (4.78), получаем следовательно, x1 + x3 = 1. Используя это равенство, можно исключить одну из переменных x1 или x3. Таким образом, удается сократить число переменных и ограничений.

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

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

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

Упражнения разделены на две части. В первой части собраны задачи, которые решаются без помощи специальных программных средств. Во второй части приводятся задания, для выполнения которых сначала рекомендуется построить математическую модель, а затем найти решение с помощью программных средств. Существует много коммерческих и бесплатных программных обеспечений для решения оптимизационных задач [16 — 20]. Читатель может выбрать любой из них, например, систему GAMS. Размерность задач в упражнениях подобрана таким образом, что можно построить математическую модель, количество ограничений и целочисленных переменных которой будет не слишком велико. Для тех, кто незнаком с этой системой, в следующем разделе разобран пример решения задачи в GAMS.

5.1. Теоретические задания 1. Пусть xi {0, 1}, i {1,..., n}. Что можно сказать о значениях каждой из переменных, удовлетворяющих следующим неравенствам:

2. Пусть область S задается следующим образом:

где aj > 0. Выпишите необходимые и достаточные условия, чтобы 2) S совпадало со всеми 0–1 векторами размерности |N1 | + |N2 |, 3. Представьте произведение y1 y2 y3 трех (четырех и т.д.) булевых переменных линейными ограничениями.

4. Пусть xj 0, j. Задайте выполнение по крайней мере одного из двух используя только линейные ограничения и одну вспомогательную булеву переменную.

5. Пусть xj 0, j. Задайте выполнение одного из двух неравенств используя только линейные ограничения и одну вспомогательную булеву переменную.

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

7. Пусть кусочно-линейная функция f (x) задана следующим образом:

где c0 = 50, c1 = 207, a0 = 0, a1 = 140, a2 = 220, a3 = 420. Постройте MIP поиска минимума f (x), x [a0, a3 ].

8. Смоделируйте с помощью линейный ограничений, чтобы переменная y принимала значение, равное max(u1, u2 ), где u1, u2 0.

9. Совет директоров должен принять решение о выборе инвестиций. Имеется 7 вариантов вложений. На множестве инвестиций заданы условия вложений (табл. 6).

Известны ri — доход от инвестиции i, ci — расходы при вложении i. Объем инвестиций не должен превышать M y.e. Компания стремится получить максимальную прибыль от вложений. Постройте математическую модель.

10. Компания должна назначить 8 команд на 3 проекта: A, B и C. Доход от каждого проекта зависит от числа команд, назначенных на проект. Ни один проект не должен остаться без команды. Выполнять один проект может не более 5 команд. Каждая команда может быть назначена только на один проект. Доход от соответствующих назначений приводится в Цель компании — назначить команды на проекты так, чтобы максимизировать суммарный доход.

Ответьте на следующие вопросы.

а. Сколько ограничений нужно включить в модель:

3) четыре или пять;

4) по крайней мере шесть?

б. Какое из следующих утверждений неверно:

1) все коэффициенты при переменных во всех ограничениях либо 0, 2) в модели все переменные — булевы;

3) можно записать модель, используя ограничения только в виде равенств;

4) в оптимальном решении на проекты назначены все 8 команд?

в. Предположим, что появляется еще один проект. Сколько потребуется новых переменных:

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

11. Для обслуживания m клиентов могут быть задействованы n грузовиков.

Каждого клиента можно посетить только один раз. Время на дорогу от клиента i до клиента j, которое затрачивает грузовик k, равно cijk, i, j {1,..., m}, k {1,..., n}. Общее время, в течение которого может быть задействован грузовик k, не должно превышать величину lk. Постройте модель целочисленного линейного программирования допустимой схемы объезда всех клиентов.

12. Для обслуживания склада используется два грузовика A и B. Каждый грузовик может выезжать в 13:00, 14:00, 15:00 или в 16:00. Грузовик B не должен выезжать в течение часа после выезда грузовика A. Например, если грузовик A выехал в 13:00, то грузовик B может выезжать в 15: или в 16:00. Каждый грузовик выезжает со склада в течение дня один Используя переменные предложите два разных способа построения множества допустимых выездов грузовиков и сравните их.

13. Компания занимается доставкой посылок. Нужно развести посылки клиентам. Заданы величины dj — количество посылок, которые нужно доставить клиенту j, j = 1,..., 10. В компании имеется 4 грузовика вместимостью qi посылок каждый, i = 1,..., 4. Предполагается, что все посылки не входят в один грузовик, но i=1 qi j=1 dj и dj qi. Партию посылок предназначенную одному клиенту нельзя доставлять разными грузовиками. Затраты при отправке грузовика i равны ci, i = 1,..., 4.

Каждый грузовик может объехать не более пяти клиентов, кроме того, к следующим парам клиентов нельзя доставлять посылки одним и тем же грузовиком: (1,7), (2,6), (2,9). Определите, какие грузовики необходимо задействовать, чтобы доставить все посылки клиентам с минимальными суммарными затратами. Постройте математическую модель.

14. Отдел статистики подсчитал, что в городе имеется n женихов и n невест.

Известна привлекательность (cij ) невесты i женихом j. Постройте математическую модель так, чтобы каждому жениху назначить невесту и каждой невесте назначить жениха с максимальной суммарной привлекательностью между парами. Правда ли, что задача является полиномиально разрешимой?

15. Компания производит два типа продукции на одном заводе, чтобы удовлетворить запросы клиентов в пяти регионах. Поставка продукции осуществляется через два крупных центра. Величина djk определяет запрос клиентов из региона j на продукт k, k = 1, 2, j = 1,..., 5. Компания должна решить, какой тип продукта в какой центр доставить и как его распределить по регионам, чтобы минимизировать суммарные затраты.

Затраты складываются из:

• фиксированных затрат fik, возникающих, если продукт типа k поставляется из центра i;

• фиксированных затрат gijk, возникающих, если продукт типа k поставляется доставляется клиенту в регион j через центр i;

• удельных затрат cijk на транспортировку продукта типа k в регион Постройте математическую модель.

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

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

pj — длительность выполнения работы j, dj — крайний срок завершения каждой работы и wj — важность работы, 1) Требуется найти допустимое расписание, минимизирующее взвешенную сумму времен завершения работ. Постройте математическую модель. Избегайте в модели введения вспомогательных больших чисел, используйте точные оценки на время окончания работ.

2) Постройте модель, используя следующие переменные:

18. Компания имеет две машины для производства пластиковых бутылок.

В течение года нужно проводить техническое обслуживание оборудования. Техническое обслуживание каждой машины длится 2 месяца подряд. Кроме того, в декабре и январе половина рабочих отдыхает, поэтому в производственном процессе может быть задействована только одна машина, а другая машина в это время может проходить техническое обслуживание. Ежемесячный спрос на бутылки составляет dt штук, t = 1,..., 12. Максимальное количество бутылок, которые машина k может произвести в месяц составляет ak штук, k = 1, 2. Для того, чтобы произвести ak бутылок, машина должна проработать lk рабочих дней.

В каждом месяце только Lt рабочих дней, t = 1,..., 12.

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

Как изменится модель, если требуется:

1) минимизировать суммарные ежемесячные скачки в загруженности рабочих дней;

2) минимизировать наибольший скачок в течение года между загруженными рабочими днями.

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

Время работы каждой машины k ограничено величиной Lk, производительность машины k равна ik единиц продукта i в час, i = 1,..., N, После смешивания и расфасовки продукта i машину необходимо промыть в течение i часов. Завод имеет склад, и первоначально на складе имеется S0 единиц упакованного продукта i, а к концу каждой недели t на складе должно оставаться St единиц упакованного продукта i в качестве резерва, Необходимо спланировать производство продуктов на T недель вперед так, чтобы на складе оставалось как можно меньше готовой продукции за весь период планирования, при этом удовлетворить спрос Dt единиц упакованного продукта i на неделю t. Постройте математическую модель.

20. Вспомните два представления допустимого множества решений задачи коммивояжера (разд. 3.2). Какое из этих представлений лучше?

21. Вспомните задачу коммивояжера, предложенную в разд. 3.2, и предложите представление, используя следующие переменные:

22. Вспомните двухстадийную задачу о гильотинном раскрое, рассмотренную в разд. 3. Постройте математическую модель при условии, что прямоугольники можно поворачивать на 900.

23. Вспомните задачу о башнях, рассмотренную в разд. 3. В том примере пять из шести возможных вариантов размещения башен приводят к разбросу клиентов, равному двум, и только один вариант с открытием 2-й и 3-й башен дает равномерное распределение клиентов с перепадом, равным нулю. Придумайте пример, т. е. подберите соответствующие значения n, m и p, и задайте матрицу (cij ), демонстрирующую, что перепад между максимальным и минимальным количеством клиентов может быть большим.

24. Задан взвешенный неориентированный граф G = (V, E) со множеством вершин V и множеством ребер E. Каждому ребру e E приписан неотрицательный вес we. Под весом разреза для произвольного разбиения множества вершин на непересекающиеся подмножества будем понимать сумму весов ребер, каждое из которых имеет вершины в разных подмножествах. Для заданного натурального числа p задача заключается в том, чтобы найти разбиение множества вершин V на подмножества мощности не более p, имеющее минимальный вес разреза.

Представьте задачу в терминах целочисленного линейного программирования. Имеет ли полученная математическая модель симметрии? Если да, то удалите симметрии введением дополнительных ограничений.

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

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

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

Правда ли, что среди оптимальных решений задачи всегда найдется решение с одинаковым порядком скачивания и просмотра фильмов?

26. Заданы матрица (hij ), i = 1,..., n, j = 1,..., m с положительными вещественными элементами и вектор (cj ), j = 1,..., m с положительными вещественными элементами. Пусть F — семейство всех непустых подмножеств множества {1,..., m}. Для каждого F F определим Постройте для задачи максимизации функции z(F ) модель целочисленного линейного программирования, используя только булевы переменные.

27. Докажите, что если все компоненты матрицы A и вектор-столбца b целочисленные и A — унимодулярная матрица, то все базисные решения имеют целочисленные компоненты. Докажите, что утверждение верно, 28. Множество S может быть задано несколькими способами:

Какой из способов наиболее эффективный при решении задачи maxxS cx?

29. Пользуясь результатами из упражнений 1 и 2, решите следующую задачу, не делая перебора:

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

30. Пусть множество S задается следующей системой неравенств:

Найдите систему неравенств, задающую выпуклую оболочку множества 31. Многогранник P задается следующей системой неравенств:

Найдите «наименьшее» представление для многогранника P.

32. Найдите conv(X), если множество X задано следующим образом:

33. Найдите наилучшее представление для множества X, заданного следующим образом:

34. Пусть многогранник задается следующей системой неравенств:

где b = (b1, b2 )T — целочисленный вектор с неотрицательными компонентами.

Ответьте на следующие вопросы.

1. Является ли матрица ограничений полностью унимодулярной?

2. Существует ли вектор правых частей b, такой что все вершины многогранника будут целочисленными точками?

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

Постройте правильные неравенства для (5.1)–(5.3).

36. Рассмотрим множество:

где C, b — целые числа.

1. Найдите conv(X).

2. Найдите conv(X {0, 1}n ).

37. Рассмотрим задачу:

1. Найдите разрыв целочисленности.

2. Постройте правильное неравенство.

5.2. Практические задания 38. Ресторан работает 7 дней в неделю. Повара работают 6 часов в день, дней подряд и затем 2 дня отдыхают. У всех поваров одинаковая зарплата.

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

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

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

39. Авиакомпания «Альфа» составляет расписание вылетов из Чикаго по следующим направлениям: Колумбия, Денвер, Лос-Анджелес и Нью-Йорк.

В каждый город должен состояться ровно один вылет. Вылеты могут быть в 8:00, 10:00 и 12:00. Авиакомпания оплачивает вылет каждого самолета по каждому направлению. Эти затраты составляют 5 тыс. у.е., если вылет совершается до 10:00 включительно, и 3 тыс. у.е. — после 10:00. В каждый момент времени выполняется не более двух рейсов. Кроме того, если в определенное время есть вылет в Нью-Йорк, то в это же время должен быть вылет в Лос-Анджелес. Ожидаемый доход (в тыс. у.е.) от полетов приводится в следующей табл. 9.

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

40. В городе 7 районов (рис. 25). Известна численность населения в каждом районе (табл. 10).

В институте по повышению уровня грамотности работает 2 специалиста.

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

41. Издательство планирует выпустить новую серию книг по исследованию операций. В серию войдут три книги: OR1, OR2, OR3. Авторы сдают в редакцию рукопись книги, а издательство брошюрует и печатает книгу.

В издательстве имеются три машины для печати книг — P1, P2, P3 и две машины для брошюровки — B1, B2. Время работы каждой машины с соответствующей книгой указано в табл. 11.

Машины могут работать только определенное количество часов. Максимальное время работы (в часах) каждой машины указано в табл. 12.

Стоимость аренды одной машины не зависит от числа книг и составляет 10, 8, 9, 20 и 23 тыс. y.e. соответственно. Доход от продажи одной книги составляет 40, 60 и 70 y.e. соответственно. Издательство стремится получить максимальную прибыль. При этом оно должно выпустить не менее 500 штук книг OR3, чтобы поддерживать хороший академический имидж.

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

42. Трое рабочих W1, W2, W3 должны выполнить пять работ J1, J2, J3, J4, J5.

Уровень подготовки и опыт работы у рабочих разный. Время выполнения конкретной работы в часах у каждого работника приводится в табл. 13.

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

43. В лесничестве нужно принять решение, какие участки леса будут вырублены под застройку. Лес разделен на 16 участков прямоугольной формы, как показано в табл. 14.

Соседние участки нельзя выбирать под застройку, чтобы избежать больших вырубленных площадей. Соседними для шестого участка являются, например, участки с номерами 2, 5, 7 и 10. Польза от застройки каждого участка приводится в табл. 15.

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

44. Компания «Гига» владеет тремя складами S1, S2, S3 вместимостью 30, 10 и 50 тыс. тонн соответственно. Фиксированные затраты на подготовку к использованию каждого склада составляют 25, 50 и 45 тыс. y.e. соответственно. Первый склад можно расширить за счет использования подземного хранилища на 20 тыс. тонн с дополнительными затратами 1 тыс. y.e.

за тонну. При необходимости имеется возможность открыть еще два склада S4, S5 вместимостью 20 и 30 тыс. тонн с затратами на подготовку 15 и 25 тыс. y.e. соответственно. В настоящий момент в «Гигу» обратились три компании K1, K2, K3 для хранения 20, 60 и 40 тыс. тонн. Компания «Гига» забирает грузы у клиентов и привозит их на склады, транспортные затраты на доставку приводятся в табл. 16.

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

45. Импресарио готовит выставку старинных автомобилей, среди которых могут быть Buggati, Cadillac, Cobra, Corvette, Pierce Arrow, Studebaker.

Опрос показал, что посмотреть именно Buggati придут 58 специально приглашенных гостей, Cadillac — 37, Cobra — 42, Corvette — 40, Pierce Arrow — 55 и Studebaker — 33. Бюджет организации выставки составляет 15 млн y.e. Стоимость доставки автомобиля на выставку и обеспечение его сохранности составляют 6, 4, 3.8, 4.2, 5.5 и 3.2 млн y.e. соответственно.

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

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

46. Компания распространяет технику по пяти городам: Екатеринбург, Омск, Новосибирск, Томск, Иркутск. В настоящий момент 10 снегоуборочных машин находятся в Екатеринбурге и должны быть доставлены в Новосибирск и Томск. В Новосибирск нужно 3 машины, в Томск — 7 машин.

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

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

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

47. На рис. 27 изображена электроэнергетическая сеть, соединяющая электрогенераторы G1,..., G4 с источниками потребления C1,..., C4. Потоки энергии могут идти в любом направлении по ребрам сети, пропускные способности ребер неограничены, стоимость передачи по одному ребру составляет 11 y.e. за 1000 кВт/час. Мощность каждого электрогенератора и стоимость выработки электроэнергии приводятся в табл. 18.

Стоимость выработки (за 1000 кВт/час) 15 13,5 21 23, Энергопотребление в C1,...,C4 составляет 35, 50, 60 и 40 тыс. кВт соответственно. Какие электрогенераторы из сети использовать, чтобы суммарные затраты были минимальные, а потребность в электроэнергии была удовлетворена? Постройте математическую модель и найдите оптимальное решение задачи.

48. Компания производит два вида полимерных материалов: полипропилен и полистирол. Для этого она нанимает неквалифицированных, квалифицированных и высококвалифицированных рабочих. Почасовая оплата в y.e.

каждого рабочего и количество тонн материалов, производимых каждым рабочим в час, приводятся в табл. 19.

Почасовая оплата и почасовые объемы производства Рабочие могут производить одновременно оба продукта, например, квалифицированный рабочий может производить 3 тонны полипропилена и 3 тонны полистирола каждый час. Поступил заказ произвести за один час 21 тонну полипропилена и 15 тонн полистирола.

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

Компания освоила производство поликарбоната и получила заказ произвести 24 тонны за один час. При этом неквалифицированные рабочие могут произвести 1 тонну поликарбоната в час, квалифицированные рабочие — 3 тонны, а высококвалифицированным рабочим запрещено производить поликарбонат. Как изменится модель при добавлении заказа на новый материал?

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

49. Производитель планирует запуск производства двух новых типов стекла:

A и B. Для этого необходимо приобрести специальные печи. Стоимость печи для производства стекла типа A составляет 500 тыс. у.е., стекла типа B — 600 тыс. у.е.

Для производства стекла необходимы песок, карбонат калия и карбонат кальция в заданных пропорциях (табл. 20).

Тип стекла Песок Карбонат калия Карбонат кальция Согласно контракту поставщики могут доставить не более 1460 тонн песка, 500 тонн карбоната калия и 700 тонн карбоната кальция.

Доход от продажи 1 тонны стекла типа A составляет 6 тыс. y.e., от продажи 1 тонны стекла типа B — 3 тыс. y.e. Производство устроено таким образом, что если оно запущено, то не менее одной тонны стекла любого типа должно быть произведено.

Постройте математическую модель, максимизирующую прибыль, используя только следующие переменные:

xA (xB ) — объем производства стекла типа A (B).

Ответьте на следующие вопросы.

1) Какое из следующих ограничений входит в модель:

1.1) 0.52xA + 0.73xb 1460;

1.2) 0.52xA + 0.73xb 14.60;

1.3) 52xA + 73xb 1460;

1.4) 0.52xA + 0.73xb 1460?

2) Какое из следующих ограничений входит в модель:

2.1) xA 1000yA 0;

2.2) 1000xA yA 0;

2.3) xB 1000yB 0?

3) Какое из следующих ограничений входит в модель:

3.1) xA 1460xA 0;

3.2) 2000yA xA 0;

3.3) 1460xA yA 0;

3.4) xA 1460yA 0?

50. Винодел, смешивая четыре сорта винограда, получает три сорта вина. Количество виноградного сока, имеющегося в наличии (литров), пропорции смешивания и стоимость каждого сорта вина указаны в табл. 21.

— в любом количестве.

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

51. В обязанности завхоза входит закупка продуктов питания, расфасованных в жестяные банки. По данным прошлого года, известно необходимое количество банок на каждый месяц (табл. 22).

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

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

52. Сантехник имеет большой запас 13-метровых медных труб. Ему нужны труб длиной 4 метра, 10 труб длиной 5 метров и 23 трубы длиной 6 метров.

Как он должен разрезать 13-метровые трубы? Постройте математическую модель минимизации числа использованных 13-метровых труб. Найдите оптимальное решение задачи.

53. Предприятие занимается переработкой руды. Процесс переработки схематически изображен на рис. 28. Перерабатываются два вида руды: А и В. Предприятию может быть поставлено до 100 тыс. тонн руды вида А по цене 3.25 y.e. за тонну и до 30 тыс. тонн руды вида В по цене 3.40 y.e. за тонну. Общая мощность основного процесса переработки равна 100 тыс. тонн руды при затратах на переработку 0.35 y.e. за тонну.

Основной процесс обработки позволяет получать • из каждой тонны руды вида А 0.15 тонн продукта I и 0.85 тонн продукта II, • из каждой тонны руды вида В 0.25 тонн продукта I и 0.75 тонн продукта II.

Продукт I более ценный, и агрегат, называемый конвертером, способен из каждой тонны продукта II получить 0.5 тонн продукта I и 0.5 тонн продукта II, который нельзя повторно перерабатывать конвертером. Мощность конвертера — 50 тыс. тонн сырья при затратах на конвертерную обработку 0.25 y.e. за тонну сырья. Затраты на фильтрацию продукта I после основного процесса обработки равны 0.10 y.e. тонн сырья.

Условия реализации продукции следующие. Вся продукция идет на продажу. Продукт II может быть реализован в неограниченном количестве по цене 3.80 y.e. за тонну. Продукт I продается по цене 5.50 y.e. за тонну, и его можно продать по этой цене до 45 тыс. тонн. Кроме того, можно продать до 4 тыс. тонн по цене 5.2 y.e. за тонну и неограниченное количество продукта по заниженной цене 5 y.e. за тонну.

Существует контракт, согласно которому требуется поставлять потребителям не менее 40 тыс. тонн продукта I. Оба продукта можно при необходимости докупить: закупочная цена продукта I равна 5.75 y.e. за тонну, закупочная цена продукта II — 4 y.e. за тонну.

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

1) найдите план выпуска продукции с максимальной прибылью;

2) покажите, как изменится оптимальный план, если мощность фильтра ограничена величиной 15 тыс. тонн;

3) покажите, как изменится оптимальный план производства, если фильтр сломается и не будет задействован в производственном процессе, а продукт I в этом случае будет продаваться только по цене Постройте математическую модель для задачи, в которой требуется найти единую (не зависящую от объемов продаж) минимальную цену на продукт I, при которой прибыль предприятия будет не меньше 50 тыс. y.e.

По-прежнему ли это модель линейного программирования?

54. Выполните упражнение 53 со схемой работы предприятия, изображенной 55. Выполните упражнение 53 со схемой работы предприятия, изображенной на рис. 30. Затраты на упаковку продукта I составляют 0.15 y.e. за тонну 56. На складе имеются прямоугольные листы материала размером см2 в количестве 100 штук (рис. 31) и деловые отходы в форме многоугольника в количестве 70 штук (рис. 32). В цех поступил заказ на изготовление деталей форм, указанных на рис. 33 в следующих количествах: невыпуклых многоугольников — 550 штук; четвертей круга радиусом 30 см — 800 штук; равнобедренных прямоугольных треугольников с Рис. 29. Процесс переработки Рис. 30. Процесс переработки Рис. 31. Заготовки Рис. 32. Деловые отходы Рис. 33. Формы деталей в заказе катетами 50 см — 330 штук; прямоугольников 50 30 см2 — 700 штук. При раскрое материала разрешаются произвольные повороты деталей. Найдите, какое минимальное число листов материала нужно дополнительно закупить, чтобы выполнить заказ? Постройте математическую модель, решите и предъявите использованные карты раскроя.

57. Завод может выпускать насосы 10 типов: V 1, V 2, SV 1, SV 2, SV 3, W 1, W 15, W 2, SW 2, SW 3. Для производства насосов каждого типа известны:

— затраты (в тыс.y.e.) на наладку оборудования (табл. 24), — удельная стоимость (в y.e.) производства (табл. 25).

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

символ «» означает, что замена невозможна.

Например, выделенное жирным шрифтом число 2 в табл. 57 означает, что вместо одного насоса V 2 можно произвести 2 насоса V 1.

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

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

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

1) Как изменится план выпуска насосов, если суммарные затраты на наладку оборудования не должны превышать 3000 y.e.?

2) Изменится ли номенклатура выпускаемых насосов, если на складе имеется запас насосов типа SW 3 в количестве 50 шт.?

3) Известно, что для производства одного насоса требуется определенное количество килограмм резины указанное в табл. 28.

Завод обладает запасом резины в размере 10 кг. Как изменится план выпуска, если завод может закупать резину по цене 20 y.e. за один 4) Постройте математическую модель для случая, когда любой тип насосов можно заменять не более двумя (тремя) другими допустимыми 58. Завод может выпускать насосы 10 типов: V 1, V 2, SV 1, SV 2, SV 3, W 1, W 15, W 2, SW 2, SW 3. Время на наладку оборудования (в тыс. мин.) приводится в табл. 29.

Время, затрачиваемое на производство одного насоса в часах приводится в табл. 30.

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

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

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

1) Как изменится план выпуска насосов, если суммарное время на наладку оборудования не должно превышать 3500 часов?

2) Изменится ли номенклатура выпускаемых насосов, если на складе имеется запас насосов типа SW 3 в количестве 50 шт.?

3) Известно, что наладка оборудования для производства каждого типа насосов требует финансовых затрат (тыс. y.e.), указанных в табл. 32.

Удельная себестоимость (в y.e.) производства насосов каждого типа приводится в табл. 33.

Как изменится план выпуска, если суммарные затраты на выполнение заказа не должны превышать 10000 y.e., а суммарное время на наладку оборудования не должно превышать 5000 часов?

59. Строительный магазин столкнулся со следующей проблемой. Клиентам нужен оргалит размером 120 90 см2, 120 150 см2 и 120 180 см в количестве не менее 20, 50 и 40 листов по цене 700, 900 и 1000 y.e.

за один лист соответствующего размера. Магазин может вырезать листы нужного размера из стандартных листов большего размера 120 240 см2, которых имеется неограниченное количество, оптовая стоимость закупки таких листов составляет 600 y.e. за один лист. Стоимость выполнения одного разреза составляет 150 y.e.

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

60. У раскройщика имеется 30 листов фанеры размера 300 300 см2, из которых необходимо выкроить 20 кругов диаметром 150 см и 15 прямоугольников размером 120 180 см2. Образцы раскроя приводятся на рис. 34.

Стоимость выкраивания одного круга составляет 200 y.e., одного прямоугольника — 150 y.e. В стоимость включено выполнение всех разрезов, и она не зависит от выбранного образца. Круги и прямоугольники можно купить готовые по цене 450 и 300 y.e. соответственно, если не хватит больших листов. Раскройщик стремится минимизировать расходы на выкраивание. При этом он должен получить нужное количество кругов и прямоугольников и использовать больших листов не больше, чем у него есть, а суммарные отходы должны быть не более 30 %. Постройте математическую модель и найдите решение.

61. Менеджер компании «K&Co» должен выбрать, в какие из пяти проектов A, B, C, D или E сделать инвестиции на ближайшие 3 года так, чтобы получить максимальную прибыль. Проекты могут принести доход (млн y.e.), указанный в табл. 34.

Менеджер обратился к аналитикам и получил следующие рекомендации.

1) По крайней мере в один из проектов C, D или E обязательно нужно сделать инвестиции, так как они идеально соответствуют специализации сотрудников компании.

2) Если для инвестиций выбран проект A, то и проект D тоже должен 3) Если выбраны проекты A и B, то в проект C не нужно инвестировать из-за высоких рисков.

4) Если выбраны проекты B и C, то нужно инвестировать и в E, поскольку в этом случае можно получить хорошие скидки от поставщиков.

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

62. В 2015 году Алиса планирует отправиться в кругосветное путешествие.

В начале 2011 года она готова начать делать сбережения для путешествия так, чтобы к началу 2015 года у нее было 21 тыс. евро.

Она может выбирать из трех типов акций A, B или C. Каждая акция стоит 100 y.e. Покупка акций осуществляется в начале каждого года. Через год инвестиций в акции типа A выплачивается 104 y.e., через два года инвестиций в акции типа B — 110 y.e., через четыре года инвестиций в акции типа C — 125 y.e. В начале каждого года — 2011, 2012, 2013 и Алиса планирует инвестировать всего не более 5 тыс. y.e.

Необходимо найти минимальный суммарный объем инвестиций за 2011– 2014 годы. Постройте математическую модель и найдите оптимальный план.

Как изменится модель, если появляется еще один тип инвестиций: акции типа D? Стоимость каждой такой акции составляет 100 y.e., а через три года ее стоимость составит 115 y.e.

63. Завод производит некоторую продукцию. Клиенты сразу забирают её с места производства, так как у завода нет складских помещений. Если же объемы производства превысили спрос, то продукция отправляется на склад магазина. Если же произведенной продукции недостаточно для удовлетворения спроса, то недостающее количество нужно привести со склада магазина. Продукция отправляется на склад или забирается со склада в конце дня, а поступает на склад или к клиентам в начале следующего дня. Удельные транспортные затраты на перевозку продукции с или на склад составляют 0.2 y.e.

Известно, что в первый день на складе лежит 100 единиц продукции, к концу 4-го дня там должно оставаться 100 единиц продукции. Ежедневный спрос и максимальный объем производства в единицах приводятся в табл. 35.

Ежедневный спрос и максимальный объем производства Удельные затраты на производство составляют 5 y.e. в день, удельная стоимость хранения — 0.1 y.e. в день.

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

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

Затраты на наладку производства составляют 5000 y.e., стоимость производства одной единицы составляет 100 у.е. Таким образом, производство партии из 1 велосипеда требует затрат в 5100 у.е., для производства партии из 10 велосипедов затраты составят 5000 + (10 · 100)= 6000 y.e.

В табл. 36 приводится прогноз ежемесячного спроса dt на велосипеды на следующий год.

Известно, что на складе осталось 200 велосипедов с прошлого года. Удельная стоимость хранения в месяц составляет 5 y.e., вместимость склада неограничена. Задача менеджера — составить такой план производства и хранения велосипедов, чтобы удовлетворить спрос с минимальными суммарными затратами на год.

65. Проект состоит из 8 работ. Длительности выполнения каждой работы (дней) приводятся в табл. 37.

Работы можно выполнять на несколько дней быстрее, но не быстрее, чем на максимальное количество дней, приведенное в табл. 38.

Стоимость ускорения выполнения работы на один день (в y.e.) приводится в табл. 39.

У некоторых работ имеются непосредственные работы-предшественники (табл. 40).

Постройте сеть (работы – дуги) и выберите правильные варианты ответов на следующие вопросы.

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

2) 1-3-6-8;

3) 1-4-5-8;

4) 1-3-5-8?

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

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

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

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

68. На склад экспресс-почты прибыло восемь посылок, которые требуется доставить восьми адресатам. За хранение каждой посылки в течение одного часа взимается плата в размере ci y.e., время доставки посылки i до адресата составляет ti часов, i = 1,..., 8, данные приводятся в табл. 42.

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

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

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

Суммарные затраты складываются из затрат на хранение продукции и производственных затрат. Известны ежедневные производственные затраты на каждый тип продукта на любой линии. В начале периода планирования готовой продукции нет.

В день можно произвести не более 342 единиц каждого типа продукта на каждой линии. Ежедневная удельная стоимость хранения (в y.e.) каждого типа продукта приводится в табл. 43.

Ежедневная удельная стоимость хранения Ежедневная удельная стоимость производства (в y.e.) каждого продукта на любой линии приводится в табл. 44.

Ежедневная удельная стоимость производства Количество единиц продукции j-го типа низкого качества при переключении с i-го продукта на k-й линии рассчитывается по формуле cij = k sti + 10(k 1) + 10|j i|, где st = (40, 20, 20, 20, 40, 50) — начальное количество низкокачественного продукта. После переключения линии на новый продукт (пока производится низкокачественый) производственные затраты считаются для нового продукта. В начале горизонта планирования все линии настроены на производство качественного продукта. Данные о спросе на каждый тип продукта на каждый день приводятся в табл. 45.

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

70. Предприятие установило систему производственного планирования в своих отделениях. Задача системы — осуществлять планирование производства и хранения продукта. Производственный процесс состоит из нескольких шагов: переработка сырья, упаковка продукта, хранение и отправка упакованного продукта потребителям. Планирование осуществляется на 3 месяца.

Схема производственного процесса представлена на рис. 35. Процесс производства начинается с переработки сырья, количество которого неограничено. В результате получается 4 типа продукта: A, B, C, D. Ежемесячно каждого продукта можно произвести не более Ci штук, i = A, B, C, D.

Известна потребность Di штук i-го типа продукта в месяц t. После переработки сырья продукт отправляется либо в цех по упаковке, либо на склад.

Вместимость склада неограничена. Цех по упаковке может обрабатывать не более 28000 штук продукции в месяц. Упакованный продукт может отправляться либо на склад, либо к потребителям. На складе имеются Рис. 35. Схема производственного процесса помещения для хранения упакованной и неупакованной продукции. Поскольку для хранения упакованной продукции нужны специальные стеллажи, то затраты на хранение упакованного продукта на 4 y.e. за штуку в месяц больше, чем затраты на хранение неупакованного продукта. Данные приводятся в табл. 46.

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

2) Стоит ли увеличивать мощность цеха по упаковке? Какие данные Вам необходимы, чтобы ответить на этот вопрос?

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

Затраты на очистку упаковочной линии перед упаковкой каждого типа продукта приводятся в табл. 47.

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

71. Промышленное предприятие получило разрешение на разработку месторождения руды на участке размером 200 200 футов2. Вскрытие участка производится наклонными выработками, предельный уклон наклона 450.

С учетом максимального угла наклона и с целью предотвращения засыпания нижних слоев и заполнения всего поперечного сечения выработки выемку руды делают блоками высотой 25 футов, шириной и длиной по 50 футов, размещая их, как показано на рис. 36. Чтобы добраться до внутреннего блока, не лежащего на поверхности, нужно отработать «пирамиду» из четырех блоков, лежащих на один слой выше этого блока.

Проведенные исследования местности позволили оценить возможное соРис. 36. Выработка внутреннего блока держание руды (в процентах) в разных местах участка на разной глубине для каждого блока (табл. 48—51).

Если бы блок состоял на 100 % из руды, то он приносил бы доход в тыс. y.e.

Стоимость выработки одного блока зависит от глубины (табл. 52).

Стоимость выработки одного блока на разной глубине Какие блоки следует вырабатывать, чтобы получить максимальную прибыль? Постройте математическую модель и найдите оптимальное решение. В модели должно быть 56 ограничений и 30 переменных.

Можно ли использовать методы решения задач линейного программирования для поиска оптимального решения?

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

Сначала масла очищаются, а затем смешиваются. В наличии имеется пять типов масел: два из которых растительного происхождения V 1, V 2, три — животного O1, O2, O3. Горизонт планирования производства — с января по июнь. Сырье можно покупать как непосредственно перед использованием в любой месяц горизонта планирования, так и заранее. В табл. приводится стоимость покупки тонны масла в соответствующий месяц.

Конечный продукт продается по цене 150 y.e. за тонну.

Очистка растительных и животных масел выполняется на разных аппаратах. Согласно технологическим требованиям аппараты ежемесячно могут очищать не более 200 тонн растительного масла, и не более 250 тонн масла животного происхождения. В процессе очистки сырье не теряет в весе.

Затратами на очистку можно пренебречь.

На складе можно хранить всего до 1000 тонн неочищенного растительного и столько же животного происхождения масел. Стоимость хранения любого масла 5 y.e. за тонну в месяц. Масло, прошедшее очистку, и готовый продукт не могут храниться на складе. В начале января на складе лежит 500 тонн масла каждого происхождения и столько же должно остаться к концу горизонта планирования, т. е. в конце июня.

Качество готового продукта оценивается его плотностью. Этот показатель зависит прямо пропорционально от массы (и только от нее) и должен принимать значение от 3 до 6. Плотность масел приводится в табл. 54.

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

73. Модифицируйте модель для задачи 72, учитывая следующие требования.

1. При изготовлении продукта в смеси всегда должно присутствовать не более трех различных типов масел.

2. Нельзя использовать меньше 20 тонн масла любого типа в месяц.

3. Если при изготовлении продукта в смеси присутствует масло V 1 или V 2, то обязательно должно быть и масло O3.

74. Крупная компания собирается принять решение о переносе некоторых филиалов из Лондона в другие города. Это позволит сотрудникам компании приобрести недорогое жилье, обеспечить рабочими местами жителей других городов. Новые филиалы могут размещаться в Эдинбурге, в Брайтоне либо остаться в Лондоне. Необходимо разместить пять филиалов. В каждом городе может быть расположено не более трех филиалов.

Выгода (тыс. y.e. в год) от перемещения филиалов в другие города приводится в табл. 55.

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

В табл. 57 приводятся стоимости пересылки единицы продукции в год (y.e.).

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

75. Крупная кинокомпания планирует съемку фильма. Известно, что в съемке фильма будут участвовать n актеров. Фильм состоит из m эпизодов.

Каждый день снимается ровно один эпизод. Для каждого эпизода известны актеры, которые в нем задействованы. Актер может сниматься в нескольких эпизодах. Он приезжает на съемочную площадку в тот день, когда снимается первый эпизод с его участием, и покидает площадку в конце последнего дня съемок всех эпизодов с его участием. За каждый день присутствия на съемочной площадке (независимо от того, занят ли актер в съемке в этот день или нет) кинокомпания выплачивает ему персональный гонорар.

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

Постройте математическую модель и найдите оптимальное решение для съемок фильма «Новосибирск, я тебя люблю!».

Эпизоды фильма:

1. Знакомство с городом. Участвуют: Брюс, Джеки, Брэд, Том и Пенелопа.

2. У фонтана. Участвуют: Брэд, Джулия и Сальма.

3. В парке. Участвуют: Брэд, Том и Джулия.

4. Знакомство с университетом. Участвуют: Брюс, Джеки и Пенелопа.

5. Прогулка. Участвуют: Брэд и Сальма.

6. В театре. Участвуют: Брюс, Брэд, Том, Джулия и Пенелопа.

Персональные гонорары актеров (в тыс. y.e. за один день) приводятся в табл. 58.

6. Решение оптимизационных задач в GAMS В этом разделе на одном из примеров, рассмотренном в начале пособия, будет разобран процесс построения модели в системе GAMS.

GAMS — это аббревиатура английских слов General Algebraic Modeling System, что можно перевести как «система для алгебраического моделирования». Система GAMS представляет собой оболочку для описания моделей. Она не решает задачу, а направляет к одной из решающих программ (solver или решатель) CPLEX, BARON и др.

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

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

I — множество типов стульев, I = {кап., пом., мар., исп., вен., офис.};

J — множество деталей, J = {дл.бол., кор.бол., тяж.сид., лег.сид., длин.нож., кор.нож., перек.,гайк., ролл., кар., креп.};

pi — цена i-го типа стула, i I;

dji — количество деталей j-го типа, необходимое для производства одного стула i-го типа, i I, j J;

qj — запас деталей j-го типа на складе, j J.

Введем переменные:

xi — количество стульев i-го типа, которое производит фирма;

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

Целевая функция — максимизировать суммарный доход (function). Группа ограничений constraints1 гарантирует, что имеющихся деталей на складе достаточно для производства стульев. Группа ограничений constraints2 определяет допустимые значения переменных.

Ниже приводится текст программы для решения этой задачи в GAMS.

1. $ontext 2. Решается задача о работе мебельного комбината.

3. Математическая модель записана 4. в терминах целочисленного линейного программирования.

5. $offtext 6. Sets 7. I множество стульев /1*6/ 8. J множество деталей /1*11/ 9.;

10. Parameters 11. p(i) стоимость i-го типа стула i из I 12. / 18. q(j) кол-во деталей j-го типа на складе j из J 19. / 20. 21. 22. 23. 30. Table 31. d(j,i) кол-во деталей j-го типа для пр-ва стула i-го типа 44. Integer Variables 45. x(i)сколько стульев $i$-го типа производит фирма;

46. x.up(i)=INF;

47. Free Variable 48. z суммарный доход от продажи стульев;

49. Equations 50. function суммарный доход от продажи 51. constraints1(j) ограничения на кол-во деталей на складе;

52. function.. z =e= sum(i,x(i)*p(i));

53. constraints1(j).. sum(i,d(j,i)*x(i)) =l= q(j);

54. Model Chairs /function,constraints1/;

55. *Model Chairs /all/;

56. Chairs.optcr=0.0;

57. Solve Chairs using mip max z;

58. Display x.l, z.l, constraints1.l;

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

Строки 1—5 соответствуют комментариям. Для того, чтобы закомментировать одну строку, нужно поставить знак «» в начале строки. Для того, чтобы закомментировать несколько строк, нужно окружить их командами $ontext и $of f text.

Строки 6—42 соответствуют описанию исходных данных задачи. Для этого используются специальные блоки: Sets — для задания множеств, P arameters — для векторных величин, T ables — для матриц, Scalars — для скалярных величин и констант. Эти блоки могут следовать в произвольном порядке друг за другом, но должны при этом использовать определенные ранее величины.

Для сокращения кода программы типы стульев капитан, помощник, маркиза, испанский, венский и офисный пронумерованы подряд от 1 до 6, а детали пронумеровали подряд от 1 до 11. В строке 7 приводится задание множества стульев I, в строке 8 — задание множества деталей J. Между именем множества и перечислением элементов, входящих в это множество, находится поясняющий текст.

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

Строки 10—29 соответствуют описанию векторов pi и qj. Между двумя наклонными чертами «/... /» заключены пары: координата вектора и значение по этой координате. В конце блока ставится «;».

Строки 30—43 соответствуют описанию матрицы (dji ). Обратите внимание, что каждый столбец в таблице выровнен по левому (допускается выравнивание по правому) краю.

В строках 44—48 декларируются переменные. В задаче имеется шесть целочисленных неотрицательных переменных x(i). На языке GAMS они объявляются Integer Variables. По умолчанию диапазон значений переменных типа Integer от 0 до 100. В данном примере это ограничение может оказаться существенным, поэтому необходимо расширить диапазон Integer. Для этого в строке 46 изменяется максимальное значение переменных x(i) с помощью команды x.up(i) = IN F, где INF — это некоторое большое число в GAMS, аналог бесконечности. Переменная z, которая соответствует значению целевой функции, должна быть свободной. На языке GAMS она объявляется Free Variable («Free»

можно опустить).

Строки 49—53 соответствуют блоку Equations. В нем объявляются имена всех ограничений, чтобы в дальнейшем на них ссылаться, и выписываются ограничения. Символы две точки подряд «..» всегда разделяют название ограничения и начало алгебраического выражения. Символы = e = означают равенство (от англ. equal — равно); = l = означают меньше либо равно (от англ.

less — меньше); = g = означают больше, либо равно (от англ. greater — больше).

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

В строке 54 с помощью оператора M odel присваивается название модели и перечисляются именно те ограничения, которые следует учесть при решении задачи. В данном примере модель называется Chairs. Между двумя наклонными чертами /... / перечислены те ограничения, которые вошли в модель.

Поскольку все описанные ограничения формируют модель, то можно записать это в более компактной форме с помощью ключевого слова all (от англ. all — все), строка 55.

Строки 56, 57 соответствуют подготовке и обращению к решателю. Для того, чтобы вызвать решатель, нужно в операторе Solve указать название решаемой модели, её тип и критерий оптимизации. Модель Chairs относится к целочисленному линейному программированию. Критерий оптимизации — максимизация дохода z.

Для задач минимизации используется ключевое слово min. Кроме задач класса mip, можно решать и другие. Это зависит от возможностей установленного решателя. В меню F ile Options Solvers можно подключить соответствующий решатель.

Перед тем, как вызывать решатель, можно сделать ряд настроек, улучшающих качество получаемого решения. Так, в строке 56 устанавливается относительный разрыв (relativegap), равный 0 %, который по умолчанию составляет 10 %.

В результате выполнения оператора Solve:

— подготовлены данные в соответствующей структуре, чтобы запустить решатель;

— запущен решатель;

— получено решение или установлена неразрешимость задачи.

Результаты расчетов выводятся в отдельный файл с расширением.lst.

Получить оптимальное решение можно с помощью оператора Display, как это сделано в строке 58. В результате выполнения этого оператора будут напечатаны значения переменных x и z в файле с расширением.lst после ключевого слова Execution.

Для запуска программы выберите меню F ile Run. Появится вспомогательное окно, в котором решатель сообщит о результатах компиляции и поиска решений. В случае успешного завершения работы решателя будет создан новый файл с расширением.lst, в котором появится полная информация о модели, процессе вычислений, статистике модели и результатах работы алгоритма.

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

**** REPORT SUMMARY :

Execution 58 VARIABLE x.L сколько стульев $i$-го типа производит фирма 58 VARIABLE z.L = 10294.000 суммарный доход от продажи стульев 58 EQUATION constraints1.L ограничения на кол-во деталей на складе EXECUTION TIME = 0.000 SECONDS Суммарный доход составляет 10294. Оптимальный план производства состоит из 100 стульев типа капитан, 72 стульев типа помощник, 40 стульев типа маркиза и 53 испанских стульев, остальные типы стульев в оптимальном решении отсутствуют. Дополнительно приводится информация о том, сколько деталей было задействовано при реализации оптимального плана. Эта информация может оказаться полезной при анализе решения.

Кроме упомянутых выше возможностей, в GAMS заложены и другие средства для реализации сложных задач и взаимодействия с приложениями [18].

7. Список литературы 1. Алексеева Е. В., Кочетов Ю. А. Курс лекций по теории принятия решений. URL: http://www.math.nsc.ru/LBRT/k5/or.html 2. Вентцель Е. С. Исследование операций. Задачи, принципы, методология. М.: КноРус, 2010.

3. Вершик А. М. Леонид Витальевич Канторович: человек и ученый: В 2 т.

Новосибирск: Изд-во СО РАН. Филиал «Гео», 2002. Т. 1.

4. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Либроком, 2010.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

6. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники графы, оптимизация (комбинаторная теория многогранников). М.: Наука, 1981.

7. Есипов Б. А. Методы исследования операций: Учебное пособие. СПб.: Лань, 8. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2009.

9. Кочетов Ю. А. Методы локального поиска для дискретных задач размещения Модели и алгоритмы. Saarbrucken: Lambert Academic Publishing, 10. Кочетов Ю. А., Плясунов А. В. Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности // Журнал вычислительной математики и математической физики. 2012. Т. 52. № 1.

11. Ларичев О. И. Теория и методы принятия решений, а также Хроника событий в Волшебных Странах: Учебник. М.: Логос, 2000.

12. Лэсдон Л. Оптимизация больших систем. М.: Наука, 1975.

13. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

14. Ларин Р. М., Плясунов А. В., Пяткин А. В. Методы оптимизации. Примеры и задачи: Учеб. пособие, 2-е изд. Новосибирск, 2009.

15. Программное обеспечение для решения оптимизационных задач Advanced Integrated Mathematical Modeling System AIMMS. URL: www.aimms.com 16. Программное обеспечение для решения оптимизационных задач AMPL Optimization. URL: www.ampl.com 17. Программное обеспечение для решения оптимизационных задач IBM ILOG. URL: www.ibm.com/software/websphere/products/optimization 18. Программное обеспечение для решения оптимизационных задач GAMS.

URL: http://gams.com/ 19. Программное обеспечение для решения оптимизационных задач GNU Linear Programming Kit Package. URL: http://www.gnu.org/software/ glpk/glpk.html 20. Программное обеспечение для решения оптимизационных задач Microsoft Oce, надстройка «Поиск решения» в Excel. URL: http://www.solver.

21. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программрование программирование: модели и вычислительные алгоритмы: Учеб.

пособие. М.: ФИЗМАТЛИТ, 2007.

22. Схрайвер A. Теория линейного и целочисленного программирования:

В 2 т. М.: Мир, 1991.

23. Appa G. M., Pitsoulis L. S., Paul W. H. (Eds.) Handbook on Modelling for Discrete Optimization. Springer Series Vol. International Series in Operations Research & Management Science 2006. V. 88, XXII.

24. Eppen G. D., Gould F. J., Schmidt C. P. Introductory management science.

4th Edition. A Simon & Schuster Company. 1993.

25. Pochet Y., Wolsey L. A. Production planning by mixed integer programming.

In: T. V. Mikosh, S. I. Resnick, S. M. Robinson (Eds.) Springer Series in Operations Research & Financial Engineering. 2006.

26. Plastria F. Formulating logical implications in combinatorial optimization // European journal of Operational Research. 2002. № 140.

27. Ehrgott M. Multicriteria Optimization. 2nd Edition. Berlin: Springer, 2005.

28. Eiselt H. A., Sandblom C.–L. Operations Research: A Model-Based Approach.

Berlin, Heidelberg: Springer-Verlag, 2010.

29. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin, Heidelberg:

Springer-Verlag, 2004.

30. Nemhauser G. L., Wolsey L. A. Integer and combinatorial optimization. John Wiley & Sons, Inc., 1999.

31. Williams H. P. Model Building in Mathematical Programming. 4th Edition, University of Southampton, John Wiley & Sons, Inc., 1999.

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

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

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

В оформлении обложки использована иллюстрация из детского анимационного сериала «Фиксики». Все права на объекты, входящие в состав указанного анимационного сериала, такие как персонажи, музыкальные произведения, принадлежат закрытому акционерному обществу «Аэроплан».

Уч.-изд.л. 8. Усл. печ. л. 7,44. Тираж 200 экз.