Примеры целочисленных линейных моделей

Примеры целочисленных линейных моделей

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

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

максимизировать (суммарный эффект)

при условиях

(на каждую линию назначается не более одного самолета),

(каждый самолет назначается не долее чем на одну линию),

, .

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

Исторически первой задачей целочисленного линейного программирования считается опубликованная венгерским математиком Е.Эгервари в 1932 году задача о назначении персонала, которая ставится аналогично только что рассмотренной задаче.

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

2. Задача о ранце. В простейшей постановке эта задача может быть сформулирована так. Имеется п предметов, которые желательно уложить в ранец, вес j -го предмета (в килограммах) равен , а ценность его равна (условных единиц), . Общий вес уложенных в ранец предметов не может превышать b кг. Требуется максимизировать суммарную ценность выбранных для укладки в ранец предметов без превышения предела для веса. Математическая формулировка поставленной задачи выглядит так:

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

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

1) неделимостью (выбираемое для транспортировки количество груза должно выражаться целым числом единиц);

2) полезностью (условных единиц) единицы груза j -го вида, ;

3) расходом i -го ресурса для перевозки единицы груза j -ого вида, , .

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

Обозначим – количество выбранных для перевозки предметов j -ого вида и составим математическую модель поставленной задачи. Очевидно, требованию неделимости груза соответствует условие:

, – целое, . (1)

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

. (2)

Общую полезность рейса определяет значение функции

. (3)

Таким образом, задача сводится к максимизации целевой функции (3) при ограничениях (1)-(2).

Встает вопрос: не является ли наилучшим общим методом решения целочисленных задач простой перебор всех допустимых решений с последующим выбором наилучшего из них. Если имеется всего несколько допустимых решений, то такой метод действительно легче реализовать, чем любой из имеющихся в настоящее время алгоритмов решения целочисленных задач. В ряде случаев, встречающихся на практике, именно такой метод и применяется (часто многие допустимые решения сразу исключаются из рассмотрения как «явно» не оптимальные). Однако, как правило, метод полного перебора оказывается неработоспособным. Это объясняется тем, что число допустимых решений не всегда конечно, но даже тогда, когда условие конечности не нарушается, это число обычно огромно. Рассмотрим, например, случай отыскания оптимального решения задачи целочисленного программирования, содержащей 100 переменных, каждая из которых может принимать всего два значения – 0 и 1. Время перебора всех 2¹⁰⁰ (более 10³⁰) возможных решений на самом быстродействующем компьютере довольно велико.

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

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

Дата добавления: 2015-09-29