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

более двух ненулевых элементов с противоположными знаками; или каждый столбец имеет более двух ненулевых элементов, но в последовательных строках и с одинаковыми знаками.

Для других моделей предугадать хорошее свойство решения LP иногда удается исходя из специфики конкретной структуры условий. Например, в IP-задаче составления графика производства полезным может быть предположение, что потребности одинаковы для всех продуктов и что потребности и цены постоянны из периода в период. В этом случае можно оценить оптимальное решение LP и его целочисленность без численного решения.

Установка допуска оптимальности

В сложных IP-задачах для сокращения поиска может быть использован Допуск Оптимальности Целочисленного Программирования (Integer Programming Optimality Tolerance - IPTOL). Использование IPTOL нередко приводит к сокращению времени решения. Установка значения IPTOL возможна в меню Edit|Options. Это значение может быть любым дробным числом/от 0 до 1. Когда допустимое IP решение найдено, ветвь дерева будет продолжена, ’если только она может улучшить текущее наилучшее решение по крайней мере на долю / Конечный результат значение критерия последнего решения, возвращенного UNDO, будет в пределах 100/* процентов от истинного оптимального значения критерия. Предположим, для примера, что IPTOL равен 0.02 и в задаче на максимум процедурой ветвей и границ только что найдено решение со значением 100. Ветвь поискового дерева не будет продолжена, если она не приведет к решению лучше чем 102. Конечный результат - значение критерия последнего решения, возвращенного LINDO в этом случае, будет не более чем на 2% меньше истинного оптимального решения.

Использование известного хорошего решения для ГР

Если известно хорошее решение (но не обязательно оптимальное) для IP, то его можно использовать для сокращения поиска оптимального решения. В начале стадии поиска методом ветвей и границ ветви с явно неоптимальными значениями критерия (по информации об известном решении) будут отброшены. Значение IP Objective Hurdle (барьера - начального значения рекорда цели) позволяет использовать такую возможность. Установить значение барьера можно, используя команду Edit|Options. Например, пусть известно, что оптимальное значение критерия для решаемой на максимум IP-задачи заведомо больше 1492. Тогда при установке IP Objective Hurdle в 1492 LINDO не будет тратить время для проверки решений со значением критерия меньше или равно 1492.

Декомпозиция Вендерса

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

51

NEWIP (ACTUAL, BOUND), которая находится в динамической библиотеке UNDO. По умолчанию NEWTP.DLL не выполняет каких-либо действий кроме оператора выхода. Для использования декомпозиции Вендерса пользователь должен переписать эту подпрограмму так, чтобы она решала соответствующую подзадачу. Результатом ее выполнения должно быть новое допустимое решение всей задачи. При этом аргумент ACTUAL заменяется значением критерия в этом решении.

Преобразование модели IP-задачи

Так как IP-задачи более сложны для решения, чем LP, важно, чтобы IPформулировки были по возможности «сжатыми». Это значит, что когда задача решается как LP, решение должно выглядеть подобно решению IP, т.е. многие целочисленные переменные действительно целые и значение критерия LP приблизительно равно значению критерия IP. UNDO имеет команду TITAN, которая делает подобное “сжатие”. Она делает две вещи: 1) сужает верхние и нижние границы для непрерывных переменных и далее использует эту информацию; 2) уменьшает коэффициенты целочисленных переменных, где возможно. Второй прием дает эффект, когда задача, решенная как LP, имеет ненулевые целочисленные переменные со значениями, более близкими к 1, чем было бы в ином случае. Например, если имеется" ограничение 7 х + 4 у + 2 z >= 5, где все переменные имеют нижнюю границу 0 и X определена как целочисленная переменная, то TITAN трансформирует это ограничение в 5x:+4y + 2z>=5.'

4. Квадратичное программирование

LINDО предоставляет возможность решать модели с квадратичной целевой | функцией. Это значит, что в критерии имеются произведения двух переменных. В' матричном представлении квадратичная задача может быть записана так:

Minimize x’Qx + сх

Subject То

Ax<=b

Итак, задача оптимизации считается квадратичной, когда:

1)все ограничения линейные,

2)критерий содержит, по крайней мере, один квадратичный (второй степени)

элемент.

Так, например, модель 1 - это квадратичная задача, а модель’2 не соответствует! квадратичной задаче из-за кубического элемента в критерии и квадратичного элемента в первом ограничении.

Модель I

MAX X2-X*Y + 3*X+10*Y

ST

X+Y < 10

X<7

Y<6 END

52

Модель 2

MAX X3 • X*Y + 3 X + 10 Y

X2+Y2<10

X<7

Y<6 END

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

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

В записи модели для UNDO оператор QCP распознает конец ограничений первого порядка и начало реальных ограничений. В Windows версиях UNDO оператор QCP появляется как часть текста модели после оператора END. За командой QCP вводится целое число, указывающее индекс первого действительного ограничения, которое непосредственно следует за условными ограничениями первого порядка. Допустимое значение аргумента для команды QCP может быть от 2 до значения, равного общему числу ограничений плюс 1. В случае, когда этот аргумент превышает последний номер строки в модели, реальных ограничений в задаче нет, т.е. имеет место задача на безусловный экстремум.

Приведем небольшой пример. Предположим, что необходимо оптимизировать портфель ценных бумаг при ограниченном бюджете. Существует 3 вида ценных бумаг, в которые могут быть сделаны вложения (соответственно X, Y, Z). Необходимо определить долю вложения в каждый вид бумаг так, чтобы рассчитанная прибыль составила по крайней мере 12% (эквивалентно росту в 1.12). Ожидаемая прибыль для X, Y, Z равна 30, 20 и 8% соответственно. Кроме того, любой отдельный вклад не может превышать 75% от портфеля. Наконец, известна ковариационная матрица для

Так как X, Y, Z представляют доли портфеля по вложениям в ценные бумаги, то дисперсия портфеля в целом будет иметь вид

3 Xz+ 2 Y2+ ZJ + 2 X Y - X Z - 0.8 Y Z

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

53

Minimize 3X2+ 2 Y 2+Z2 + 2 X Y - X Z - 0.8 Y Z Subject To

X + Y + Z = 1

! Желание получить в итоге не менее 12% прироста: 1.3 Х + 1.2 Y + 1.08 Z> 1.12

! Вложения не могут составлять более чем 75% от портфеля: Х<0.75

Y<0.75

Z<0.75

Процедура ввода для UNDO требует, чтобы эта модель была преобразована к полностью линейной форме с помощью записи условий первого порядка. Чтобы выполнить преобразование, построим функцию Лагранжа для нашей модели. Каждое ограничение входит в эту функцию со своим множителем Лагранжа. Обозначим их соответственно как: Ul, U2, U3, U4 и U5.

Тогда функция Лагранжа запишется в виде

F(X,Y,Z) = ЗХ2+ 2Y2+Z 2 + 2 X Y - X Z - 0.8Y Z

+ ( X + Y + Z -1) U1+ + (1.12-I.3X- 1.2Y - 1.08Z)U2

+(X - 0.75) U3 + (Y - 0.75) U4 + (Z - 0.75) U5 => MIN

•\Следующий шаг - получение условий первого порядка.

Согласно необходимым условиям оптимальности (Куна - Таккера) условия первого порядка находятся взятием частных производных функции F(X,Y,Z) по каждой переменной и заданием их неотрицательности. Например, для переменной X условие первого порядка будет:

6 X + 2 Y - Z + U1 - 1.3 U2 + U3 >=0.

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

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

Так, для приведенного выше условия первого порядка условия дополнительной нежесткости требуют, чтобы при строго положительном X ограничение (6 X + 2 Y - Z + UI - 1.3 U2 + U3 >=0) выполнялось как равенство. Таким образом, LINDO должен знать это соответствие между переменными и ограничениями, чтобы добиться выполнения условий нежесткости. Наконец, при вводе квадратичных моделей существует еще одно требование: действительные ограничения должны записываться последними. В нашем примере это следующие ограничения:

Х+ Y + Z = 1

Х+ 1.2 Y + 1.08 Z >«1.12 Х<=0.75 Y<=0.75 Z<=0.75

54

Команда QCP используется для указания первого действительного ограничения. В рассматриваемом примере имеем цель (первая строка) и по одному условию первого порядка для каждой из трех переменных. Следовательно, действительные 01раничения начинаются с 5 строки, и последним в модели для LINDO будет оператор «QCP 5». Окончательно модель для ввода примет вид

MINX + Y + Z + U 1+U 2 + U3 + U4 + U5

ST

j условие первого порядка для X 6X + 2 Y - Z + U1 - 1.3U2 + U 3 > 0 Jусловие первого порядка для Y

2X + 4Y - 0 . 8 Z + U1 -1. 2U2 + U 4 X ) I условие первого порядка для Z

-X-0.8Y + 2 Z + U1 -1.08 U2 + U5 > 0

| ----------------------- начало действительных ограничений-------------

!Ограничения сметы, множитель — U1 Х + Y + Z = 1

!Ограничение роста, множитель — U2

1.3 Х+ 1.2 Y + 1.08 Z > 1.12

!Максимальная доля X, множитель — U3 Х<0.75

!Максимальная доля Y, множитель — U4 Y<0.75

!Максимальная доля Z, множитель— U5 Z<0.75

END QCP 5

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

OBJECTIVE FUNCTION VALUE

1)0.4173749

55

Таким образом, дисперсия портфеля (т.е. риск вложений) минимизирована до

.417 путем инвестирования 15.5% в первый вид бумаг (X), 25% - во второй (Y) и 59.5% - в третий (Z).

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

Отладка квадратичных моделей

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

В матричной форме квадратичная задача может быть представлена так:

MIN x’Qx + сх Subject То Ах <= Ь.

Часть целевой функции x’Qx - это квадратичная форма. Матрица Q - положительно определена тогда и только тогда, когда x’Qx > 0 для всех ненулевых х. Если Q положительно определена, тогда целевая функция строго выпукла, и найденное решение гарантированно будет единственным оптимальным. Список всех возможных условий для матрицы Q таков:

1)положительно определена, если x’Qx > 0 для всех ненулевых х,

2)положителЬйЬ полуопределена, если x’Qx >= 0 для всех ненулевых х,

3)отрицательно полуопределена, если x’Qx <= 0 для всех ненулевых х,

4)отрицательно определена, если x’Qx < 0 для всех ненулевых х,

5)не определена, если x’Qx > 0 для некоторых х и x’Qx < 0 для других х.

Бели задала не удовлетворяет условию 1 или условию 2, тогда результаты решения LIND0 будут непредсказуемы и не будут надежными.

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

56

UNDO имеет команду для установления свойства матрицы, соответствующей квадратичной части критерия. Это команда Positive Definite или POSD в меню Reports. При запуске она сначала проверяет, симметрична ли матрица Q. Если она несимметрична, то LINDO определит элементы, нарушающие симметричность. Таким образом, команда Positive Definite используется и для отладки квадратичных моделей. После проверки симметричности матрицы команда Positive Definite определяет свойство матрицы, ее ранг и сообщает о результатах.

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

В качестве примера ниже приведены результаты запуска команды Positive Definite для модели о портфеле трех ценных бумаг:

(SUB)MATRIX IS

POSITIVE DEFINITE; RANK=3 OUT OF 3

Из этого сообщения следует, что (под)матрица положительно определена и ее ранг равен 3.

Параметрический анализ квадратичных задач

UNDO позволяет выполнить параметрический анализ коэффициентов правых частей (RHS) квадратичной модели так же, как и для линейной модели. Однако существуют некоторые тонкие различия, которые пользователь должен иметь в виду.

Поясним это с помощью примера о портфеле ценных бумаг из предыдущего раздела. Предположим, что требуется выявить влияние на критерий увеличения-fUlS ограничения роста: 1.3 X + 1.2 Y + 1.08 Z > 1.12. Самое высокое значение, которое может быть достигнуто, - это 1.3, когда все вкладывается в ценные бумаги X,;Чтобы выполнить параметрический анализ этого ограничения, следует запустить команду Reports|Parametrics. Результатом будет следующий отчет:

Каждая строка отчета соответствует значению RHS, при котором некоторая переменная достигает границы. Параметрический анализ показывает, что изменение RHS до 1.1441 не влияет на критерий. Выше этого значения исследуемое ограничение становится существенным. При значении 1.26947 существенным становится ограничение Х<0.75 и значение 1фитерия увеличивается до 2.03651, а двойственная цена ограничения роста составляет -25.8299. Это означает, что при малом уменьшении RHS, значение критерия будет уменьшаться со скоростью 25,8299 (т.е. двойственная цена - это производная критерия по правой части ограничения в оптимальном

57

решении). Однако, в отличие от линейных, в квадратичных задачах двойственная цена не остается постоянной между точками смены базиса.

Интерполяция значения 1фитерия в параметрическом анализе

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

Vi - значение критерия в точке /, Rj - значение RHS в точке i ,

D2 . двойственная цена точно перед точкой 2, г - некоторое Значение между Я/ й

w ^(R i-r)/(R 7-Ri).

Значешю критерия с RHS,равным ^вычисляется по формуле:

V2 + D2R2- r + ( V , - V 2- D 2(R2- R I ) ) W }.

1.3X + 1.2 Y +1.08 Z > 1.2

иполучаем оптимальное значение критерия 0.739300400. При этом двойственная цена становится равной -11.51752.

Таким образом, значение критерия подтвердилось. Кроме того, двойственная цена приняла промежуточное значение между ценами в двух точках, между которыми находится г =1.2, т. е. двойственная цена действительно не остается постоянной между точками излома зависимости критерия от RHS.

5.Анализ и отладка модели

Анализ модели становится более трудным с возрастанием ее размера. Далее будем считать модель большой, если ни ее запись в синтаксисе LINDO, ни ее отчет о решениц не помещаются на одну печатную страницу. При этом нас может интересовать только часть модели или часть отчета о решении. Сложность будет очевидна, если эти часта’ разбросаны по нёсколыснм страницам.

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

58

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

Основные команды для анализа модели в LINDO - это Reports|Statistics, RepoTts|Peru$e и Solve|Debug. Эти команды уже рассматривались ранее. Ниже мы еще раз обсудим их применение.

Статистика модели

Команда Reports|Statistics выдает краткую статистику по текущей модели. Проиллюстрируем работу команды на частично целочисленной модели:.

MAX2x + 3y+2z

ST 4x + 3z<8

2х + Зу - z - 1 4x + 3y - 2 z> 2 . .

* END INT2

Статистический отчет; выданный командой Statistics, имеет вид:

ROWS=4 VARSrr3 INTEGER VARS = 2(2=0/l) QCP=0 NONZEROS=l4 CONSTRAINT NONZ=8 (1=+-1) DENSHY=0.875

SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE=1.0 8.0. OBJ=MAX. NO. <=,>: 1 1 1, GUBS <=1 VUBS>=0

SINGLE COLS= 0 REDUNDANT COLS- 0

Большая часть статистики в отчете понятна без пояснений, как, например, число строк и столбцов. Если имя переменной написано неправильно, оно должно обнаружить себя через число столбцов, которых будет больше, чем ожидается. Это произойдет потому, что нормальные переменные появляются в нескольких местах в модели, а неправильно написанная переменная появится только в одном месте. Статистика QCP показывает номер строки, с которой начинается первое действительное ограничение, (в противоположность условиям первого порядка) в квадратичной задаче. Число ненулевых значений (NONZ) дает другую меру размера модели. CONSTRAINT NONZ - это число ненулевых коэффициентов в левой части ограничений. Если эти ненулевые значения равны +1 или -1, решение модели облегчается. Число таких значений дается в скобках. Плотность (DENSITY) - это доля ненулевых элементов в модели. Если десятичная точка в коэффициенте по ошибке поставлена не на то место, она должна обнаружить себя как либо крайне маленькое число, либо очень большое число. С этой цепью в отчете приводятся самые большие и самые маленькие по ^абсолютному значению коэффициенты (SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE). Если одно из них будет:за пределами реального, то обратит на себя внимание.

В четвертой строке отчета приводится число строк условий каждого типа. Величина GUBS, General ..Upper Bounds statistic (общие верхние границы), характеризует простоту модели. Это верхняя граница по числу непересекающихся ограничений в модели. Если бы все ограничения были непересекаюгцимися, модель

59

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

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

Детальный анализ модели на наличие ошибок

Для более - подробного анализа используется команда Reports|Peruse. Она позволяет выбрать подмножество строк или столбцов, которые удовлетворяют указываемым условиям, и получить по ним различные атрибуты.

Например, предположим, есть подозрение, что имя некоторой переменной написано неправильно в одном из условий. Такую ошибку можно обнаружить путем выявления переменной, имеющей только один ненулевой коэффициент. С этой целью выберем команду Reports|Peruse и заполним появившееся диалоговое окно (рис. 26).

Рис. 26

Вокне отмечаем Columns (столбец), вводим условие "Ъ=Л" в поле Condition и выбираем текстовый отчет. Условие Z=1 означает, что в отчет могут войти только столбцы с одним ненулевым элементом.

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

ROWS=85 VARS=84 NO. INTEGER VARS = О QCP-0

NONZEROS=l 848 CONSTRAINT NONZ=1680 (1680 ARE +-1) DENSITY=256

60