книги / Моделирование и оптимизация в LINGO

BNP установкой Off. В последнем случае для смешанных целочисленных задач будет использоваться стандартный решатель MIP. По умолчанию установлено Blocks= Off. Решатель BNP может использовать также эвристики, если их выбор определен параметром Heuristic.

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

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

Применительно к смешанным линейным целочисленным моделям в каждом узле дерева решений решатель ветвей и границ решает непрерывную линейную задачу, используя прямой симплексметод либо двойственный симплекс-метод, либо барьерный решатель (см. выше). При этом, если имеется предыдущее решение, оно принимается за начальное решение для текущей задачи (опция Warm Start – теплый старт), что уменьшает время решения. В противном случае начальное решение находит решатель (Cold Start – холодный старт). Параметр Node Selection позволяет управлять порядком выбора узлов дерева решений. С помощью функции @PRIORITY можно влиять на выбор переменной для ветвления.

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

11

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

Global Solver и Multistart Solver – специализированные реша-

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

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

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

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

внекоторых случаях оно может оказаться глобальным.

Впоследних версиях LINGO появился SP Solver, использование которого требует приобретения опции SP как части лицензии.

12

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

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

Следует иметь в виду, что количество сценариев возрастает экспоненциально с увеличением числа этапов. Например, при одной случайной переменной с двумя возможными результатами в каждом из N этапов, количество сценариев будет равно 2N. Таким образом, модели SP могут быть очень большими.

13

Для решения задач SP LINGO предлагает 2 метода:

1.Deterministic Equivalent (DE), когда генерируется и сразу решается детерминированный эквивалент модели SP.

2.Nested Benders (NBD), который, используя строго блочноугловую структуру DE (из-за дублирования основной модели по сценариям), выполняет декомпозицию большой модели, применяя для этого подход Nested Benders.

В опциях решателей на вкладке Solver SP можно выбрать один из этих методов или предоставить выбор LINGO.

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

2.ОСОБЕННОСТИ ПРЕДСТАВЛЕНИЯ МОДЕЛИ В LINGO

Математическое программирование как совокупность методов поиска оптимальных решений находит практическое применение в различных сферах человеческой деятельности для решения задач, возникающих в науке и бизнесе, в экономике и финансах, в строительстве и сельском хозяйстве, в военном деле и сфере услуг и т.д. [1–3]. Это задачи прогнозирования, проектирования и конструирования, планирования, размещения, организации и производства продукции, логистики и безопасности и др. [4–9, 11, 15].

Математические модели таких задач оптимизации содержат от десятков до многих тысяч переменных и условий (ограничений), т.е. относятся к задачам средней и большой размерности [10]. Поэтому при использовании компьютерных программ возникает проблема представления в них математической модели решаемой задачи. Например, в простейшей транспортной задаче, включающей 50 пунктов отправления и 1000 пунктов назначения, модель будет содержать 50 тыс. переменных и 1050 функциональных ограничений.

14

В известной задаче коммивояжера с n городами, которая сегодня находит практическое применение, число переменных равно n2+n – 1, число равенств – 2n и число неравенств, исключающих подциклы, – [(n – 1)2 – (n – 1)] [12]. Еще бóльшая размерность моделей присуща многоиндексным транспортным и производственным системам [10, 11]. Поэтому традиционная запись моделей таких задач, при которой целевая функция и каждое условие должны быть представлены в развернутом виде со всеми коэффициентами, оказывается неприемлемой.

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

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

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

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

вобычном математическом виде со всеми числовыми коэффициентами, как например, в пакете LINDO (предшественник LINGO) [13].

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

15

ются разделы множеств SETS, данных DATA и математической модели (ММ). В первом разделе описываются структуры данных через задание множеств и, возможно, их атрибутов. Каждое множество – это совокупность подобных объектов, фигурирующих в задаче. Например, такими объектами могут быть поставщики, клиенты, заводы, товары, маршруты и т.д. В разделе DATA приводятся данные задачи и/или указывается их источник (текстовый файл, электронная таблица, база данных или приложение) и направление вывода результатов решения. Раздел ММ не имеет собственного обозначения и служебных слов для его выделения. Он содержит целевую функцию и ограничения задачи. Каждый из этих разделов может быть представлен и более одного раза в разных частях модели, но при этом обязательно предшествование описания объектов и данных ссылкам на них. При необходимости модель задачи дополняется вспомогательными разделами INIT и CALC. В первом из них, как правило, задаются начальные значения (например, стартовые точки), во втором – выражения, обеспечивающие первоначальную обработку исходных данных (например, вычисление средних значений, дисперсий и т.п.). В CALC также записывают последовательность команд (скрипт или сценарий) решения задачи. Все разделы за исключением ММ выделяются в модели задачи ключевыми словами начала и конца раздела, содержащими имя раздела.

3. ВИДЫ МНОЖЕСТВ

LINGO воспринимает два вида множеств: первичные, или примитивные (primitive), и вторичные, или производные (derived). Первичные множества являются исходными, их объекты неделимы. Производные множества derived образуются из одного или нескольких других множеств (первичных и/или вторичных), выступающих в роли родителей.

Определение множества primitive задает все элементы такого множества и, возможно, его атрибуты:

setname [/ member_list /] [: attribute_list];

16

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

Рассмотрим пример раздела SETS с возможными вариантами задания множеств primitive:

SETS:

SUPPLIERS /1..N/: A;

CONSUMERS /1..9/: B;

PRODUCT /Pr1, Pr2, Pr3/: price, Q; QUALITY: level;

FIRMS; ENDSETS

Здесь SETS: и ENDSETS – ключевые слова начала и окончания раздела SETS. В нем определены 5 множеств: SUPPLIERS задает N поставщиков, обозначенных целыми числами от 1 до N, с атрибутом А – количество товара; CONSUMERS – 9 потребителей с атрибутом В – величина потребности; PRODUCT включает 3 продукта (явное перечисление) с двумя атрибутами: ценой и количеством. Задание числа поставщиков N отнесено к предшествующей секции данных, что целесообразно, если N может варьироваться. Элементы последних двух множеств не заданы, но тогда они должны быть перечислены в секции DATA, например,

FIRMS=F1 F2 F3 F4;

Таким образом, все элементы первичного множества могут задаваться диапазоном (через двоеточие) или явным перечислением. Диапазон может быть определен не только целыми числами, но и отрезком очевидной последовательности (дней недели, месяцев, годов и т.п.). Например, элементы множества FIRMS можно задать так: FIRMS/F1..F4/.

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

TOP_PRODUCT (PRODUCT) | price ( &1) #GE# 2000:;

17

В этом определении символ &1, как индекс родительского множества, указывает на принадлежность атрибута первому, здесь единственному, множеству PRODUCT, #GE# – логический оператор (>=). Производное множество TOP_PRODUCT образовано элементами первичного множества PRODUCT, цена которых не меньше 2000. В условиях могут использоваться также операторы #EQ# (=), #NE# ( ), #GT# (>), LT (<), #LE# (<=) и общепринятые логические операции (#AND# и т.д.). В приложении 1 приведены приоритеты логических и арифметических операций.

В общем случае производное множество вводится следующим образом:

set_name (parent_set_list) [filter] [: attribute_list];

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

SETS:

SUPPLIERS;

CONSUMERS;

NET (SUPPLIERS, CONSUMERS): cost, X; ENDSETS

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

Различают плотные производные множества (dense) и разреженные (sparse). Плотное множество содержит все сочетания элементов родительских множеств, т.е. определяется их декартовым произведением. Таким является множество NET из вышеприведенного примера.

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

18

4. РАЗДЕЛ ДАННЫХ (DATA)

Этот раздел выделяется в модели служебными словами DATA: и ENDDATA. В нем даются значения атрибутов множеств и элементы тех множеств, которые не раскрыты в разделе SETS. При явном представлении данных используются выражения:

attribute_list = value_list; set_name = member_list;

Оба варианта показаны в следующем примере:

SETS:

SET1 / M1, M2, M3/: X, Y, Q; SET2: Z, Var;

ENDSETS

DATA:

X = 8 12 3;

Y = 74 45 66; SET2=A, B, C, D;

Z=91 47 23 82;

ENDDATA

Здесь в разделе DATA приведены значения атрибутов множества SET1, а его элементы в разделе SETS, в то время как для SET2 и элементы, и атрибуты определены в секции DATA. Возможен другой вариант записи данных в секции DATA:

SETS:

SET1 / M1, M2, M3/: X, Y, Q; SET2: Z, Var;

ENDSETS

DATA:

X = 8 12 3;

Y = 74 45 66; SET2 Z=

A91

B47

C23

D82;

ENDDATA

Атрибуты, значения которых не даны в секции DATA, являются искомыми переменными задачи. В примере таковыми будут Q

и Var.

19

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

ASSIGNATION:

SETS:

DRIVER ; BUS ; ROUTE ;

ASSIGNATION( DRIVER, BUS, ROUTE): EFFICIENCY, APPOINTMENT;

ENDSETS

DATA:

DRIVER = A B C;

BUS = K L M N;

ROUTE = 1..4; ASSIGNATION, EFFICIENCY = A M 1 45

A N 2 70

B K 1 65

B N 3 90

B L 3 80

C L 2 100

C M 4 50

C K 4 95; ENDDATA

Значения части атрибутов могут отсутствовать в разделе DATA, например, значение атрибута APPOINTMENT в приведенном примере. Как и в предыдущем примере, такие атрибуты являются искомыми переменными задачи.

В секции DATA помимо элементов множеств и значений их атрибутов можно определять скалярные величины (константы, параметры). Так, в первом примере описания множеств (см. с. 17) число элементов множества SUPPLIERS задано неявно, поэтому секции SETS должна предшествовать секция DATA, в которой дается это значение:

DATA:

N = 12; ENDDATA

В одном выражении можно инициализировать более одного параметра:

20