книги / Оптимизация в LINDO

М инистерство образования РФ

Пермский государственный технический университет

А.Л. Гольдштейн

Оптимизация в LINDO

Утверждено Редакционно-издательским советом университета в качестве учебного пособия

Пермь 2000

УДК 519.8:681.3.069 Г 635

Рецензенты:

канд. техн. наук В.А. Краснобаев (ГосНИИУМС);

доц. AM. Ноткин (Пермский государственный технический университет)

Гольдштейн А.Л.

Г 635 Оптимизация в UNDO: Учеб, пособие / Перм. гос. техн. ун-т. Пермь, 2000. 88 с.

ISBN 5-88151-263-4

Дано описание пакета прикладных программ UNDO, предназначенного для решения задач математического программирования: линейных, целочисленных и квадратичных. Подробно рассмотрены команды пакета под Windows, способы представления моделей, их решения и анализа.

В пособии использована документация фирмы - разработчика пакета: LINDO Systems, Inc.

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

Табл. 7. Ил. 27.

УДК 519.8:681.3.069

ISBN 5-88151-263-4

© Пермский государственный технический университет, 2000

О Г Л А В Л Е Н И Е

з

4

Введение

UNDO (Линейный Интерактивный Дискретный Оптимизатор) - это удобное и. мощное средство для решения задач линейного, целочисленного и квадратичного программирования. Такие задачи возникают в бизнесе, промышленности,' сельском хозяйстве, исследовательской деятельности и во многих других областях. UNDO находит большое применение в задачах распределения ресурсов, определения состава смеси, составления производственного и персонального расписания, управления запасами и др. Алгоритм решения задач основан на переработанном модифицированном симплекс-методе. Для персональных компьютеров имеется 5 версий LINDО, позволяющих решать задачи от малой до очень большой размерности: Student/Regular, Super, Hyper, Industrial и Extended. В частности, максимальная размерность задач для Super PC 6.1 составляет 2000 переменных (непрерывных), 1000 ограничений, 200 целочисленных переменных и 2000000 ненулевых коэффициентов. При этом достаточно компьютера с 16 М RAM Для больших задач необходим математический сопроцессор.

Внастоящем пособии, основанном на технической документации фирмы UNDO Systems, Inc., описана работа с LINDO только под Windows 95/98, хотя возможна работа и под другими ОС.

Существуют 3 основных стиля применения программного обеспечения LINDO. Для представления задач малого и среднего размера в UNDO можно использовать клавиатуру. Ввести модель небольшого размера не составляет труда. Также возможна работа LINDO с файлами, созданными вне UNDO, которые содержат коды команд и входные данные, а файлы, полученные в LINDO, могут быть использованы при составлении отчетов. Наконец, пользовательские подпрограммы могут быть объединены непосредственно с LINDO в форму интегрированной программы, содержащей вместе код подпрограмм и библиотеки оптимизации UNDO. В последнем случае используется динамическая библиотека - LINDO Windows DLL (в данном пособии не рассматривается).

1.Синтаксис модели

Вэтом разделе подробно описывается синтаксис модели LINDO. Список синтаксических правил невелик, и они легко осваиваются.

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

способов:

SUBJECT ТО

SUCH THAT S.T.

ST

Конец записи условий обозначается словом END без точки.

Длина имени переменной в LINDO не должна превышать 8 символов. Имена должны начинаться с буквы (от А до Z), за которой может следовать до 7 дополнительных символов. В качестве дополнительных могут использоваться любые

5

символы за исключением следующих:!) + - = <->. Так, например, правильными будут имена:

Имена можно присваивать и условиям модели. Имена условий облегчают восприятие отчетов LINDО. Эти имена должны удовлетворять тем же соглашениям, что и имена переменных. Чтобы присвоить имя условию, следует начать условие с его

интерпретировать его как нестрогий, т.е. больше или равно (>=), или меньше или равно (<=) соответственно, что позволяет обходиться одним оператором в неравенствах. В системах, где имеется нестрогий оператор, LINDO не поймет его.. Однако допустимо вводить. (>=) вместо (>) и {<=) вместо (<).

LINDO не будет воспринимать скобки как индикатор изменения порядка действий в выражении. Все операции в LINDO исполняются слева направо.

Комментарии могут быть расположены в любом месте модели. Комментарий выделяются восклицательным знаком (!). Все, что следует за восклицательным знаком на этой строке, будет трактоваться как комментарий. Например, возможное начало модели:

МАХ 25X1 + 5X2 ! максимальная прибыль SUBJECT ТО

! Здесь отражены возможности фирмы '! по рабочей силе

Примечание. Комментарии сохраняются в LINDO только в текстовом файле. Сохранение в сжатом формате (*ХРК) или в MPS формате (*.MPS) удаляет из модели как комментарий, так и любое специальное форматирование.

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

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

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

• :г

Max z sT

Z < 3

END

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

5X1 -20> Х 2

будет отклонена LINDO. Эта строка должна быть записана так:

5X1 -Y2>20

б

Факультативные операторы модели

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

Таблица 1

Ниже на небольших примерах показано использование каждого из этих операторов.

Оператор FREE

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

применить этот оператор.

Следующий небольшой пример иллюстрирует использование FREE:

MIN5X + Y

ST

X + Y >5

X - Y> 7

END

FREE Y

Здесь Y определена как свободная переменная, и UNDO находит оптимальное решение Х=6 и Y=-l. Без оператора FREE нижняя граница Y равнялась бы 0 и UNDO возвратил бы решение Х=7 и Y=0,

7

Оператор GIN

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

МАХ 11 XI + 10 Х2 ST

2X1 + Х2 < 12 XI - 3X2 > 1

END GIN XI GINX2

Для этой модели LINDO найдет оптимальное решение Х1=б и Х2=0. Без операторов GIN UNDO трактовал бы X и Y как непрерывные и возвратил бы решение Х1=5.29 н Х2=1.43.

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

Оператор INT

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

Операторы SUB и SLB

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

Второй способ предпочтительнее по следующим причинам. Во-первых, SUB и SLB ограничения воспринимаются решателем косвенно и поэтому более эффективны с точки зрения производительности, чем прямые условия. Во-вторых, SUB и SLB не входят в число условий-ограничений UNDO, что позволяет решать модели больших размеров, чем допустимо используемой версией UNDO (по числу ограничений).

8

Оператор QCP

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

Оператор TITLE

Этот оператор используется для записи заголовка модели. Заголовок может быть любой буквенно-цифровой строкой длиной до 74 символов. Заголовок текущей модели может быть показан с помощью команды Title в меню File^B отличие от всех других операторов, которые могут появляться только после слова END, оператор TITLE может быть записан перед целевой функцией или после END. Например:

TITLE Заголовок моей модели MAX 17X + 22Y

ST

14Х + 2Y < 98 END

При запуске команды Title из меню FILE заголовок модели будет послан в окно отчетов в следующем виде:

TITLE Заголовок моей модели

2. Windows-команды UNDO

Здесь рассмотрены все команды, доступные пользователю LINDO под Windows. Команды разделены на шесть категорий, образующих главное меню LENDO:

1.File-Ф айл

2.Edit-Правка

3.Solve - Решение

4.Reports - Отчеты

5.Window-Окно

6.Help - Помощь

Большинство команд имеют.также клавиши быстрого вызова (без обращения к меню). Ниже они приводятся вместе с именем команды.

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

9

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

Меню FILE

Это меню содержит команды, которые обычно имеют отношение к перемещению файлов и данных в LINDО. Одни из них являются стандартными для Windows, другие имеют небольшие отличия от стандартных, третьи - собственные команды LINDO.

New______________F2

Команда NEW создает новое пустое окно модели. Можно ввести модель прямо в окно или вставить в текст из буфера обмена.

Open____________ F3

Команда OPEN читает сохраненную в файле модель и помещает ее в окно редактирования. Все стандартные средства редактирования (такие как вставка, копирование, удаление) доступны в окне редактирования. Следует учитывать, что окна редактирования работают с файлами размером до 64000 символов. Если попытаться открыть файл большего размера, то появится предложение поместить его в окно просмотра (см. команду View).

В диалоговом окне команды выводятся имена файлов определенного типа. Нужный тип указывается в списке типов «List files of type», расположенном в нижней части окна. В списке четыре типа: текстовый LINDO (*.ltx), упакованный UNDO (Mpk), MPS (* mps) и все файлы (*.*). Первые три соответствуют трем различным форматам файлов, которые поддерживаются LINDO для хранения файлов. В большинстве случаев целесообразно использовать текстовый (*.ltx) формат LINDO. Тогда модель сохраняется в текстовой форме точно в том же виде, как она видна на экране. Другие форматы поясняются в команде SAVE ниже.

После выбора файла для открытия, LINDO проверяет файл, определяя его формат. Если модель в текстовом формате или в некотором неизвестном формате, она читается прямо в LINDO без модификации. Файлы MPS формата и упаковаштого LINDO формата перед выводом в окно преобразовываются в их текстовый эквивалент. Например, если MPS файл содержит следующую модель:

10