Full Text

Математическое программирование как совокупность методов поиска оптимальных решений находит практическое применение в различных сферах человеческой деятельности: в науке и бизнесе, в экономике и финансах, в строительстве и сельском хозяйстве, в военном деле и сфере услуг, и т.д. [1-3]. С его помощью решаются задачи прогнозирования, исследований, проектирования и конструирования, планирования, размещения, организации и производства продукции, логистики и безопасности, и др. [4-9, 11, 15]. Математические модели таких задач оптимизации содержат от десятков до многих тысяч переменных и условий (ограничений), т.е. относятся к задачам средней и большой размерности [10]. Поэтому при использовании компьютерных программ возникает проблема представления в них математической модели решаемой задачи. Например, в простейшей транспортной задаче, включающей 50 пунктов отправления и 1000 пунктов назначения, модель будет содержать 50 тыс. переменных и 1050 функциональных ограничений. В известной задаче коммивояжера с n городами, которая сегодня находит практическое применение, число переменных равно n2 + n - 1, число равенств - 2n и число неравенств, исключающее подциклы, - (n - 1)2 - (n - 1) [13]. Еще бóльшая размерность моделей присуща многоиндексным транспортным и производственным системам [10, 11] . На наш взгляд, указанная проблема (наряду с другими подобными) довольно успешно и элегантно решена в пакете математического программирования LINGO. Этот пакет имеет встроенный мощный и гибкий язык математического описания задач оптимизации, позволяющий представлять модель задачи в компактной форме с последующим решением встроенным решателем или решателями. При этом собственно математическая модель не зависит от размера задачи: так, модель вышеприведенной транспортной задачи на языке LINGO будет содержать выражения целевой функции в виде короткой строки и двух ограничений, по одному для пунктов отправления и пунктов назначения. При изменении числа пунктов в любую сторону эти выражения не изменятся. Поэтому масштабирование задачи в LINGO не вызывает затруднений (как правило, оно касается только данных). Далее рассмотрим основные конструкции языка моделирования LINGO. Сразу заметим, что для решения небольших задач можно обойтись без использования специального языка, представив модель в обычном математическом виде со всеми числовыми коэффициентами, как, например, в пакете LINDO (предшественник LINGO) [12]. Первый принцип, обеспечивающий компактность модели, - работа с наборами или множествами (sets) объектов, которые могут иметь атрибуты. Второй принцип - отделение данных от математического описания. Эти принципы реализуются через структурированность модели задачи. Модель большой системы (задачи) обычно имеет три секции или раздела (sections): SETS, DATA и математическая модель (ММ). В первом разделе описываются структуры данных через задание множеств и, возможно, их атрибутов. Каждое множество - это совокупность подобных объектов. В разделе DATA приводятся данные задачи или указываются их источник (текстовый файл, электронная таблица, база данных или приложение) и направление вывода результатов решения. Раздел ММ содержит целевую функцию и ограничения задачи. Каждый из этих разделов может быть представлен и более одного раза в разных частях модели, но при этом обязательно предшествование описания объектов и данных ссылкам на них. При необходимости модель задачи дополняется вспомогательными разделами INIT и CALC, в которых приводятся соответственно начальные значения (например, стартовые точки) и выражения, обеспечивающие обработку исходных данных (например, вычисление средних, дисперсий и т.п.). Все разделы, за исключением ММ, выделяются в модели задачи ключевыми словами начала и конца раздела, содержащими имя раздела. LINGO воспринимает два вида множеств: первичные или примитивные (primitive) и вторичные или производные (derived). Множества derived образуются из одного или нескольких других множеств, выступающих в роли родителей. Примеры задания множеств primitive: SETS: SUPPLIERS /1..N/: A; CONSUMERS /1..9/: B; PRODUCT /Pr1, Pr2, Pr3/: price, Q; QUALITY: level; FIRMS; ENDSETS Здесь определены 5 множеств, которые задают N поставщиков с атрибутом А - количество товара, 9 потребителей с атрибутом В - величина потребности, 3 продукта с ценой и количеством; элементы последних двух множеств должны быть перечислены в секции DATA. Явное задание числа поставщиков N отнесено к предшествующей секции данных. Производное множество может быть образовано из одного примитивного, как его подмножество, с помощью задания условий (фильтра) на его атрибуты, которые записываются после вертикальной черты, например: TOP_PRODUCT (PRODUCT) | price (&1) #GE# 2000; В этом определении символ &1 как индекс родительского множества указывает на принадлежность атрибута первому, здесь единственному множеству PRODUCT, #GE# - логический оператор (>=). В условиях могут использоваться также операторы #EQ# (=), #NE# (¹), #GT# (>), LT (<), #LE# (<=) и общепринятые логические операции (#AND# и т.д.). В общем случае производное множество вводится следующим образом: set_name (parent_set_list) [filter] [: attribute_list]; где обязательным является только список родительских множеств. Пример: SETS: SUPPLIERS; CONSUMERS; NET (SUPPLIERS, CONSUMERS): cost, X; ENDSETS Здесь производное множество NET имеет общие атрибуты: стоимость перевозки и количество груза, перевозимое от поставщиков к потребителям. Различают плотные производные множества (dense) и разреженные (sparse). Плотное множество содержит все сочетания элементов родительских множеств, т.е. определяется их декартовым произведением. Для образования разреженного множества применяется фильтр (условия) или явное перечисление всех входящих в него элементов. Раздел DATA содержит значения атрибутов множеств и элементы тех множеств, которые не раскрыты в разделе SETS. При явном представлении данных используются выражения: attribute_list = value_list; set_name = member_list; Оба варианта показаны в следующем примере: SETS: SET1 / M1, M2, M3/: X, Y; SET2: Z; ENDSETS DATA: X = 8 12 3; Y = 74 45 66; SET2=A, B, C, D; Z=91 47 23 82; ENDDATA Если все данные или их часть берутся из внешних источников, то в секции DATA они описываются с помощью функций @TEXT, @OLE, @ODBC или @POINTER для обмена соответственно с файлами, электронными таблицами, БД или приложениями. Эффективность языка моделирования в LINGO определяется возможностью применять операцию и/или соотношения последовательно ко всем элементам множества с помощью одного операторного выражения. Для реализации этой возможности LINGO имеет специальные функции, называемые set looping functions (SLF). К ним относятся функции @FOR, @SUM, @MIN, @MAX и @PROD. Первая используется для генерации ограничений для всех членов множества, последняя - для вычисления произведения, остальные функции пояснений не требуют. Допускается любая вложенность SLF-функций за исключением @FOR, которая может быть вложенной только в другую функцию @FOR. Синтаксис SLF-функций: @loop_function ( setname [ ( set_index_list)[ | conditional_qualifier]] : expression_list); Как видно, обязательными аргументами функции являются множество и выражения, применяемые ко всем элементам этого множества. При наличии условий действие функции будет распространяться только на те члены множества, которые им удовлетворяют. Для описания прямых ограничений на переменные применяются следующие функции: @GIN - задает целочисленный тип переменных; @BIN - задает бинарный тип переменных; @FREE - придает вещественной переменной неограниченность по знаку; @BND - накладывает двухсторонние ограничения; @SOS1 - из всех бинарных переменных, описанных этой функцией, самое большее - это одна может быть равна 1; @SOS2 - не более двух бинарных переменных могут равняться 1, и если ровно 2 переменные ненулевые, то они будут смежными; @SOS3 - точно только одна бинарная переменная равна 1; @CARD - из всех переменных, описанных этой функцией, не более N переменных могут быть больше нуля; @SEMIC - переменная может либо равняться нулю, либо быть больше некоторой константы. Функция @SOS2 применяется, например, при описании кусочно-линейных зависимостей, а функция @SEMIC - для зависимостей с разрывом в нуле, например, при учете в модели фиксированных затрат на производство или перевозки. Функции @SOS и @CARD имеют общий синтаксис: @function( 'set_name', variable), где set_name - уникальное имя списка переменных, к которым относится действие этой функции (таких записей столько, сколько переменных в списке). При использовании функции @CARD записи по переменным дополняются особой записью (одной на список), в которой вместо переменной указывается целое число N. При моделировании некоторых ситуаций возникает необходимость преобразовывать текущий индекс так, чтобы его значение принадлежало заданному диапазону. Такое преобразование выполняет функция @WRAP, имеющая 2 аргумента: INDEX и LIMIT (фактический индекс и верхняя граница диапазона). Функция возвращает значение из интервала [1, LIMIT]. Так, при планировании на 3 года текущий индекс может представлять порядковый номер месяца в плановом периоде. Если он равен, например, 27, функция @WRAP(27, 12) вернет значение 3, т.е. месяц март. Еще одна сильная сторона языка моделирования LINGO - это возможность реализации в одной модели вариантных решений (например, по разным наборам целевых функций и ограничений), декомпозиции большой задачи и т.п. Для этого в разделе ММ выделяются модели подзадач (подмодели) следующим образом: submodel name_sabmodel: подмодель; endsubmodel. Подмодель может включать только целевую функцию, только ограничения или то и другое. Комбинации подмоделей указываются в функции @SOLVE, которая записывается в разделе CALC. Она объединяет подмодели в единую модель и запускает ее решение. Рассмотрим пример построения модели типичной производственной задачи на языке моделирования LINGO. Пусть некоторая фирма имеет n типов универсального оборудования, на котором может производить определенный ассортимент изделий (m видов). Типы оборудования отличаются временем tij, необходимым на изготовление одного i-го изделия на j-м оборудовании. При получении заказа на изделия его необходимо распределить по оборудованию так, чтобы выполнить за минимальное время. Следует учесть, что заказ может включать не весь ассортимент изделий, и по технологическим причинам число видов изделий, производимых на одном типе оборудовании за время выполнения заказа, ограничено величиной kj. Исходная математическая модель этой задачи имеет вид: где xij - количество изделий i-го типа, производимых на j-м оборудовании, bi - заказанное количество изделий i-го типа; yij = 1, если на j-м оборудовании производятся i-е изделия, иначе yij = 0; M - большое положительное число. Эта модель содержит 2nm + n переменных, n + m равенств и n + nm неравенств, что свидетельствует о большой размерности задачи. На языке моделирования, рассмотренном выше, модель этой же задачи записывается в виде: MODEL: sets: PRODUCT: order; EQUIPMENT /1..3/: TWORK, K; PR_EQ (PRODUCT, EQUIPMENT): T, X; endsets data: PRODUCT=pr1 .. pr4; order= 75 123 0 62; T = 7 11 9 14 8 10 12 7 13 10 9 11; K = 2 1 3; enddata MIN = TIME; @FOR(PRODUCT(I)|order #NE# 0: @SUM(EQUIPMENT(J): X(I,J))=order); @FOR(EQUIPMENT(J): @SUM(PRODUCT(I)|order #NE# 0: T(I,J)*X(I,J))- TWORK(J)=0); TIME = @MAX(EQUIPMENT: TWORK); @FOR(PR_EQ(I,J)|order(I) #NE# 0: @GIN(X)); @FOR( EQUIPMENT(J): @CARD( 'name'+ EQUIPMENT(J), K); @FOR( PRODUCT(I)|order #NE# 0: @CARD('name'+ EQUIPMENT(J), X(I,J)))); END Здесь введены два первичных множества и одно производное, атрибутом PRODUCT является величина заказа, а атрибутами множества EQUIPMENT - время работы оборудования и число видов изделий. Заметим, что ограничения по числу видов изделий на одном типе оборудования kj описаны не неравенствами, а функцией @CARD. Условие order #NE# 0 исключает из модели ограничения и переменные, соответствующие отсутствующим в заказе видам изделий. Очевидно, что выражения целевой функции и ограничений в этой модели не зависят от значений n и m, и при их изменении потребуется изменить только данные. Для примера мы взяли n = 3 и m = 4, в этом случае LINGO сгенерирует для решателя развернутую математическую модель, соответствующую введенным данным, в следующем виде: MODEL: [_1] MIN= TIME; [_2] X_PR1_1 + X_PR1_2 + X_PR1_3 = 75; [_3] X_PR2_1 + X_PR2_2 + X_PR2_3 = 123; [_4] X_PR4_1 + X_PR4_2 + X_PR4_3 = 62; [_5] 7 * X_PR1_1 + 14 * X_PR2_1 + 10 * X_PR4_1 - TWORK_1 = 0; [_6] 11 * X_PR1_2 + 8 * X_PR2_2 + 9 * X_PR4_2 - TWORK_2 = 0; [_7] 9 * X_PR1_3 + 10 * X_PR2_3 + 11 * X_PR4_3 - TWORK_3 = 0; [_8] TIME = @SMAX( TWORK_1, TWORK_2, TWORK_3); @CARD( 'NAME1', X_PR1_1); @CARD( 'NAME1', X_PR2_1); @CARD( 'NAME1', X_PR4_1); @CARD( 'NAME1', 2); @CARD( 'NAME2', X_PR1_2); @CARD( 'NAME2', X_PR2_2); @CARD( 'NAME2', X_PR4_2); @CARD( 'NAME2', 1); @CARD( 'NAME3', X_PR1_3); @CARD( 'NAME3', X_PR2_3); @CARD( 'NAME3', X_PR4_3); @CARD( 'NAME3', 3); @GIN( X_PR1_1); @GIN( X_PR1_2); @GIN( X_PR1_3); @GIN( X_PR2_1); @GIN( X_PR2_2); @GIN( X_PR2_3); @GIN( X_PR4_1); @GIN( X_PR4_2); @GIN( X_PR4_3); END Как и следовало ожидать, в этой модели присутствуют только те ограничения и переменные, которые соответствуют реальному заказу. Нетрудно видеть, что построенная модель задачи является нелинейной. Простым преобразованием ее можно привести к линейному виду: достаточно исключить из целевой функции взятие максимума, заменив его неравенствами TIME ³ Tj, j = 1..n. Интересно сравнить решения задачи, полученные по линейной и нелинейной модели. С этой целью, не затрагивая разделы SETS и DATA, изменим раздел ММ, заменив его подмоделями, и добавим раздел CALC, где сформируем оба варианта модели и решим их. В результате разделы ММ и CALC принимают вид: . . . enddata submodel OBJ_1: MIN = TIME1; TIME1 = @MAX(EQUIPMENT: TWORK); endsubmodel submodel OBJ_2: MIN = TIME2; @FOR(EQUIPMENT: TIME2>=TWORK); endsubmodel submodel CONSTR: @FOR(PRODUCT(I)|order #NE# 0: @SUM(EQUIPMENT(J): X(I,J))=order); @FOR(EQUIPMENT(J): @SUM(PRODUCT(I)|order #NE# 0: T(I,J)*X(I,J))- TWORK(J)=0); @FOR(PR_EQ(I,J)|order(I) #NE# 0: @GIN(X)); @FOR( EQUIPMENT(J): @CARD( 'name'+ EQUIPMENT(J), K); @FOR( PRODUCT(I)|order #NE# 0: @CARD('name'+ EQUIPMENT(J), X(I,J)))); endsubmodel calc: @SOLVE(OBJ_2, CONSTR); @SOLVE(OBJ_1, CONSTR); Endcalc Как видно из раздела CALC, первой решается линейная модель, а затем нелинейная. Оба решения выводятся в одном отчете: Global optimal solution found. Objective value: 745.0000 Objective bound: 745.0000 Infeasibilities: 0.000000 Extended solver steps: 7 Total solver iterations: 141 Model Class: MILP Variable Value Reduced Cost TIME1 0.000000 0.000000 TIME2 745.0000 0.000000 TWORK(1) 745.0000 0.000000 TWORK(2) 744.0000 0.000000 TWORK(3) 740.0000 0.000000 X(PR1, 1) 75.00000 7.000000 X(PR1, 2) 0.000000 0.000000 X(PR1, 3) 0.000000 0.000000 X(PR2, 1) 0.000000 14.00000 X(PR2, 2) 93.00000 0.000000 X(PR2, 3) 30.00000 0.000000 X(PR3, 1) 0.000000 0.000000 X(PR3, 2) 0.000000 0.000000 X(PR3, 3) 0.000000 0.000000 X(PR4, 1) 22.00000 10.00000 X(PR4, 2) 0.000000 0.000000 X(PR4, 3) 40.00000 0.000000 Local optimal solution found. Objective value: 767.0000 Objective bound: 767.0000 Infeasibilities: 0.000000 Extended solver steps: 29 Total solver iterations: 2885 Model Class: PINLP Variable Value TIME1 767.0000 TIME2 745.0000 TWORK(1) 767.0000 TWORK(2) 760.0000 TWORK(3) 766.0000 X(PR1, 1) 21.00000 X(PR1, 2) 0.000000 X(PR2, 1) 0.000000 X(PR2, 2) 95.00000 X(PR2, 3) 28.00000 X(PR3, 1) 0.000000 X(PR3, 2) 0.000000 X(PR3, 3) 0.000000 X(PR4, 1) 62.00000 X(PR4, 2) 0.000000 X(PR4, 3) 0.000000 Отчет показывает, что LINGO воспринял первую модель как модель смешанного (непрерывно-целочисленного) линейного программирования (MILP), а вторую - как модель полностью целочисленного нелинейного программирования (PINLP). Соответственно в первом случае найден глобальный минимум, а во втором только локальный. При этом для решения нелинейной модели потребовалось 2885 итераций вместо 141 для линейной. Приведенный пример продемонстрировал, с одной стороны, возможности языка моделирования LINGO, с другой - важность преобразования модели к более простому классу. Рамки статьи не позволяют раскрыть весь спектр возможностей языка моделирования LINGO: помимо рассмотренных конструкций язык включает множество математических и финансовых функций, функции программирования хода решения и оформления отчетов, линейку функций для моделирования непрерывных и дискретных случайных величин и их вероятностных распределений, функции моделирования задач стохастического программирования и др. [14]. Несмотря на это, приведенный в статье материал наглядно показывает особенности и существенные преимущества этого языка при моделировании и решении задач оптимизации как средней, так и большой размерности.

About the authors

A. L Goldshtein

Perm National Research Polytechnic University

Email: gal@pstu.ru

References

Statistics

Views

Abstract - 136

PDF (Russian) - 42

Refbacks

• There are currently no refbacks.