Целочисленные задачи линейного программирования

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

Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые пере­менные могут принимать только два значения: 0 или 1. Такие пе­ременные носят название булевых.

Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. Они разработаны в на­чале 60-х годов XX века и затем неоднократно усовершенствова­лись и модифицировались. Решения примеров и задач, приводи­мых в этой главе, получены с помощью метода ветвей и границ и являются точными.

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

• неделимость;

• целочисленная задача;

• целочисленная и булева переменные;

• взаимоисключение и взаимообусловленность.

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

Первоначальным стимулом к изучению целочисленных и дис­кретных задач явилось рассмотрение задач линейного программи­рования, в которых переменные представляли физически недели­мые величины (скажем, количество единиц продукции разных видов). Для характеристики этого класса моделей используется термин «задачи с неделимостями».

Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремаль­ным комбинаторным задачам, для решения которых приходится вводить булевы переменные, носящие логический характер (х = 1 или х = 0).

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

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

1) транспортная задача (см. главу 5) и ее варианты;

2) задачи с неделимостями;

3) экстремальные комбинаторные задачи;

4) задачи с неоднородной разрывной целевой функцией (см. транспортную задачу с фиксированными доплатами в главе 5);

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

Целочисленная задача линейного программирования (задача с неделимостями). К данному классу принадлежат задачи распре­деления капиталовложении и задачи планирования производства.

Целочисленная задача линейного программирования заключа­ется в максимизации функции:

(1)

при условиях

(2)

где J — некоторое подмножество множества индексов N = ={1,2,...,n}.

Если J = N (T.e. требование целочисленности наложено на все переменные), то задачу называют полностью целочисленной; если же J ¹ N, она называется частично целочисленной.

Модель (1)—(4) естественно интерпретировать, например, в следующих терминах. Пусть через i = 1,..., т обозначены произ­водственные факторы, через j = 1, ..., п — виды конечной про­дукции.

Обозначим далее:

a_ij — количество факторов i, необходимое для производства единицы продукта j;

b_i — наличные ресурсы фактора i;

с_i — прибыль, получаемая от единицы продукта j.

Пусть продукты j для jÎJ являются неделимыми, т.е. физи­ческий смысл имеет лишь их целое неотрицательное количество («штуки»). Предположим, что требуется составить производствен­ную программу, обеспечивающую максимум суммарной прибы­ли и не выводящую за пределы данных ресурсов. Обозначая через x_j искомые объемы выпуска продукции, мы сводим эту задачу к мо­дели (1)-(4).

Задача с булевыми переменными. Логическая взаимосвязь:

1) взаимоисключение. Пусть x_j = 1, если реализуется проект А_j, и х_j = 0 в противном случае. Запись A_jÚA_k означает, что в план может быть включен либо проект А_j, либо проект А_k. Вместе они включены быть не могут. С помощью этой записи выражается от­ношение взаимоисключения между проектами.

В этих обозначениях взаимоисключение A_j Ú А_k выражается неравенством х_j + х_k £ 1;

2) взаимообусловленность. Запись А_k ® A_j («проект А_k влечет за собой проект А_j») означает, что проект А_k может быть включен в план только в том случае, если в план включен и проект A_j. С по­мощью этой записи выражается отношение между обусловлива­ющими друг друга проектами, например когда проект A_k — резуль­тат тиражирования проекта A_j на другом объекте или когда А_k ба­зируется на результатах реализации проекта A_j.

В принятых обозначениях взаимообусловленность А_k ® А_j вы­ражается неравенством х_k £ х_j.

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

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

Пусть х_ij = 1, если коммивояжер переезжает из города i непо­средственно в город j, и x_ij = 0 в противном случае. Обозначим через с_ij расстояние между городами i и j (чтобы избежать бессмыс­ленных значений х_ij = 1, предполагается, что с_ii равны достаточно большому числу).

Тогда формальная модель имеет вид

К приведенным ограничениям необходимо добавить условия на недопустимость подциклов, т.е. повторного посещения горо­дов (за исключением исходного). Это ограничения вида

где на переменные z_i и z_j не требуется накладывать никаких огра­ничений.

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

Один из представителей задач данного типа — так называемая задача о ранце. Имеется п предметов. Предмет j (j = 1, ..., п) об­ладает весом w_j и полезностью с_j. Пусть b — общий максимально допустимый вес предметов, которые можно положить в ранец. Требуется выбрать предметы таким образом, чтобы их общий вес не превышал максимально допустимый и при этом суммарная по­лезность (ценность) содержимого ранца была максимальной. Пусть х_j = 1, если предмет положен в ранец, и х_j = 0 в противном случае. Математическая формулировка задачи имеет вид

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

Большинство целочисленных и комбинаторных типов задач, таких, как задача с неделимостями, задача коммивояжера, задача календарного планирования, принадлежит к разряду так называ­емых трудно решаемых. Это означает, что вычислительная слож­ность алгоритма их точного решения — зависимость числа элемен­тарных операций (операций сложения или сравнения), необходи­мых для получения точного решения, от размерности задачи я — является экспоненциальной (порядка 2ⁿ), т.е. сравнимой по тру­доемкости с полным перебором вариантов. В качестве п, например, для задачи с неделимостями служит число целочисленных перемен­ных и число ограничений, для задачи коммивояжера — число горо­дов (или узлов графа маршрутов), для задачи календарного плани­рования — число деталей и число станков. Такие задачи называют еще NP-трудными или NP-полными. Получение их точного ре­шения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Примером таких задач служит задача о ранце с булевыми пере­менными.

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

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

1) симплекс-метод (для транспортных задач, задач о назначениях);

2) метод отсечения (метод Гомори);

3) метод ветвей и границ (в общем случае не обеспечивает получения точного решения);

4) эвристические методы (не обеспечивают получения точно­го решения).

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

Примеры. Пример 1. Оптимизация капиталовложений.

Имеется 10 работ (А₁ ¸ А₂), каждая из которых характеризуется тремя технико-экономическими показателями:

а_j — трудозатраты;

b_j — размер, необходимых капиталовложений;

с_j — ожидаемый экономический эффект.

Исходные данные приведены в следующей таблице:

Общие трудозатраты не должны превышать 20. Общий объем капиталовложений не должен превышать 20. Определите, какие из 10 работ следует выполнить, чтобы максимизировать ожида­емый экономический эффект, учитывая следующие условия вза­имообусловленности и взаимоисключения:

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

В результате расчетов получаемх* = (0101110010).

Пример 2. Оптимизация производственной программы.

Автомобилестроительный завод выпускает три модели автомо­билей, которые изготавливаются последовательно в трех цехах. Мощность цехов составляет 300, 250 и 200 человекодней в дека­ду. В первом цехе для сборки одного автомобиля первой модели требуется б человекодней, второй модели — 4 и третьей модели — 2 человекодня в декаду соответственно. Во втором цехе трудоем­кость равна 3,4 и 5 человекодней соответственно, в третьем — по 3 человекодня на каждую модель. Прибыль, получаемая заводом от продажи одного автомобиля каждой модели, составляет соот­ветственно 15, 13 и 10 тыс. долл.

Постройте модель для определения оптимального плана.

Решение. Пусть х_i — количество выпускаемых автомобилей i-й модели в течение декады (i = 1,..., n). В принятых обозначе­ниях модель имеет вид

Пример 3. Двумерная задача раскроя.

Из минимального количества листов стекла размером 8 х 6 м² требуется вырезать 10 оконных стекол размером 4 х 4 м², 20 окон­ных стекол размером 4 х 5 м² и 30 оконных стекол размером 3х3 м². Множество вариантов раскроя (см. главу 3) показано в следующей таблице:

Построите модель для определения плана раскроя, требующе­го минимального количества материала.

Решение. Пусть х_i — количество листов стекла размером 8 х 6 м², которые следует раскроить по варианту i.

Тогда модель имеет вид

Пример 4. Задача о ранце.

Некая торговая компания имеет свои универсамы в Москве, Санкт-Петербурге, Нижнем Новгороде, Екатеринбурге, Самаре, Воронеже и Казани. В результате ошибок менеджмента экономи­ческое положение компании стало ухудшаться, ей пришлось взять кредит в размере 13 млн руб. и в конечном счете, чтобы вовремя его погасить, срочно продавать некоторые из своих универсамов. Средства, которые компания могла бы получить от продажи уни­версамов в Москве, Санкт-Петербурге, Нижнем Новгороде, Ека­теринбурге, Самаре, Воронеже или Казани, составляют соответ­ственно 5,2; 4,9; 4,5; 3,6; 3,4; 3,2 и 3,1 млн руб. Однако продажа универсамов сопряжена с необходимостью увольнения персона­ла. Его численность составляет соответственно 200,190,180,170, 150,130 и 110 человек. По требованию объединенного профсоюза работников торговли компания должна минимизировать числен­ность увольняемого персонала.

Постройте модель для нахождения оптимального решения.

Решение. Пронумеруем города в соответствии с порядком их перечисления. Пусть х_i = 1, если универсам, расположенный в го­роде, продается, и х_i = 0 в противном случае. Тогда оптимизаци­онная модель имеет вид