Output Options

Эти опции позволяют управлять количеством и характером вывода информации, которую вы получаете из LINDO.

Status Window

Как только LINDO начинает решать задачу, он выводит на экран окно состояний решателя (Solver Status Window), которое позволяет управлять процессом решения. Если вы хотите отказаться от вывода этого окна на экран при каждом решении модели, удалите отметку в поле Status Window в диалоговом окне Options, как показано ниже:

После того, как вы сделаете это, LINDO больше не будет автоматически выводить на экран окно состояний решателя. Однако, вы по-прежнему можете открыть его сами в любой момент в процессе выполнения оптимизации, использую команду Open Status Window из меню Window (см. ниже раздел «меню Window»).

По умолчанию LINDO выводит на экран это окно, как только вызывается решатель.

Terse Output

Если не оговорено иное в диалоге Options, LINDO автоматически направляет отчет после решения модели в окно отчета (Reports Window). Вы можете подавить это, поставив отметку в поле Terse Output диалогового окна Options, как показано ниже:

Заметим, что вы можете запросить отчет о решении в любой момент, воспользовавшись командой Reports|Solution (см. ниже раздел «меню Reports»).

Переключение в режим Terse Output (компактный вывод) также подавит многое из детальной информации, посылаемой в окно отчета (Reports Window) при решении целочисленной модели.

По умолчанию в LINDO опция Terse Output выключена. То есть он находится в режиме Verbose Output (подробный отчет).

Page Length Limit

Вы можете ввести параметр Page Length Limit (предельная длина страницы), чтобы LINDO останавливал вывод в окно отчета после каждых нескольких строк и ждал вашей реакции. Это удобно, если вы хотите изучить решение по мере его вывода, прежде чем текст прокрутится в окне. Например, если вы введете предельную длину страницы, равной 25, как показано ниже:

… то LINDO каждый раз, послав в окно отчета 25 строк, будет останавливаться и выводить на экран следующий диалог:

LINDO не возобновит вывод, пока вы не нажмете кнопку “More” в этом диалоговом окне.

По умолчанию Page Length Limit установлено в значение “None”, то есть эта опция выключена.

Terminal Width

При выполнении последовательности операторов ввода/вывода LINDO учитывает Terminal Width (ширину экрана), то есть максимальное количество символов в строке. Поэтому в соответствии с этой величиной выводимая строка в окне отчета заканчивается и вывод обрезается. Вы можете изменить параметр Terminal Width в диалоговом окне Options в следующем поле редактирования:

Допустимые минимальное и максимальное значения для этого параметра равны соответственно 40 и 132. Когда LINDO читает входной файл, символы вне этого диапазона не распознаются, что может сказаться при решении модели. Ограничения и целевая функция могут быть разбиты на несколько строк, чтобы удержать длину строки в заданных пределах. Вы можете разбивать строку в любом месте, кроме как в середине имени переменной или посреди коэффициента. Позаботьтесь о том, чтобы использовать клавишу перевода строки, когда длина строки превосходит установленный предел. По умолчанию длина строки принимается равной 80 символам.

Go to Line Ctrl+T

Команда Go To Line позволяет осуществить переход к заданной строке в текущем окне. Можно также указать переход к началу или концу окна.

При выполнении этой команды появится диалоговое окно в следующем виде:

Если вы хотите перейти к конкретной строке, введите ее номер в поле редактирования “Line number to go to” и щелкните по кнопке OK. LINDO передвинет курсор к началу этой строки, прокрутив, если требуется, содержимое окна.

Чтобы перейти к верхней или нижней части окна нажмите соответственно кнопку “Go to Top” или “Go to End”.

Paste Symbol Ctrl+P

Команда Paste Symbol выводит на экран диалоговое окно, которое помогает в построении модели. Этот диалог содержит все зарезервированные синтаксисом LINDO символы, а также все определенные вами к этому моменту имена переменных и строк модели. Диалог выглядит следующим образом:

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

Предположим в качестве примера, что вы хотите использовать указанный диалог для добавления в модель строки XSAT + XSUN >= 4. Для этого следует дважды щелкнуть мышью по элементам:

1. XSAT в окне списка переменных Variables

2. The plus sign в списке зарезервированных слов Reserved

3. XSUN в окне списка переменных Variables

4. The >= sign в списке зарезервированных слов Reserved

В заключение непосредственно в окне редактирования введите 4 в правой части буфера вставки. В этот момент диалоговое окно будет выглядеть следующим образом:

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

Одно важное заключительное замечание, которое следует иметь в виду. Когда вы используете команду Paste Symbol, LINDO должен уже откомпилировать модель (см. команду Compile), чтобы построить список переменных и имен строк. Иначе команда не будет вставки выполнена.

Select All Ctrl+A

Команда Select All выделяет весь текст в текущем окне. То есть весь текст в текущем окне будет подсвечен. Это полезно, если вы хотите скопировать целиком весь текст окна и поместить его в новое окно или в другое приложение.

Clear All

Команда Clear All стирает все содержимое текущего окна. Она может быть полезной, если вы хотите удалить старый вывод из окна отчета и начать «с пустого места». Если вы ошибочно выполните команду Clear All, ее можно отменить командой Undo.

Choose New Font

Используйте команду Choose New Font, чтобы выбрать новый шрифт, которым будет заполняться или печататься активное окно. Возможно, вы сочтете решения или отчеты более удобными для чтения, если вы берите моноширинный шрифт типа Courier.

Меню Solve

Меню Solve показано слева и содержит все команды, которые вызывают ядро решателя LINDO. Эти команды подробно рассмотрены ниже.

Solve Ctrl+S

Команда Solve является основной командой, которую вы будете использовать из меню Solve. Она заставляет LINDO начать решение вашей модели. Если это сравнительно небольшая модель, команда Solve отработает почти мгновенно. В случае очень большой модели команда может потенциально работать часами.

Когда вы вызываете команду Solve, LINDO проверяет модель, была ли она модифицированы и не нуждается ли в компиляции. Предполагая, что в процессе компиляции не встретилось ошибок, LINDO выводит окно состояний решателя (LINDO Solver Status). Это окно позволяет управлять решателем в процессе решения. Пример этого окна показан ниже:

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

Поля/управляющие элементы	Описание
Status	Показывает состояние текущего решения. Возможными значениями являются: Optimal (оптимальное), Feasible (допустимое), Infeasible (недопустимое), Unbounded (неограниченное).
Iterations	Количество выполненных решателем итераций.
Infeasibility	Количество, на которое нарушены ограничения.
Best IP	Значение целевой функции наилучшего целого решения. Только для моделей целочисленного программирования.
IP bound	Теоретические границы для целевой функции в задачах целочисленного программирования.
Branches	Количество «ветвлений» для целых переменных, выполненных целочисленным решателем.
Elapsed Time	Время, прошедшее с начала работы LINDO.
Update Interval	Частота (в секунда), с которой обновляется окно состояний решателя. Установка этого значения в нуль может привести к увеличению времени решения.
Interrupt Solver	Нажмите эту кнопку, чтобы прервать процесс решения и вернуть текущее значение найденного наилучшего решения
Close	Нажмите эту кнопку, чтобы закрыть окно состояний решателя.

Когда команда Solve закончит работу, решение будет отправлено в окно отчета (Reports Window), в котором его можно просмотреть, отредактировать и отпечатать. Если модель сформулирована корректно, окно состояний покажет оптимальное решение. Если окно состояний сообщает, что модель недопустима или неограниченна, значит имеются проблемы в самой постановке задачи, и вы не должны пытаться получит решение в LINDO. Если модель не содержит целых переменных и не является задачей квадратичного программирования, то команда Debug может помочь вам обнаружить ошибки в случае, если модель неограниченна или недопустима.

Если вы хотите подавить автоматическую генерацию отчета о решении в конце выполнения команды Solve, отметьте поле “Terse output” (компактный вывод) в диалоговом окне команды Edit|Options.

Окно отчета может содержать только до 64000 символов информации. Если потребуется, LINDO сотрет часть текста в верхней части окна, освободив место для нового вывода в нижней его части. Если отчет о решении слишком велик, и вам необходимо изучить его полностью, можете записать всю информацию, направляемую в окно отчета, в дисковый файл с помощью команды Log Output меню File. Этот файл затем может быть изучен с помощью внешнего текстового редактора или команды View из меню File.

Если модель линейная, то после записи отчета о решении LINDO пригласит вас определить, хотите ли вы получить анализ чувствительности и интервалов. Если вы затребуете для просмотра эти данные, они также будут направлены в окно отчета. Вы можете также запросить этот отчет в любой момент, используя команду Reports|Range. Более подробную информацию об этом виде анализа можно найти в описании команды Range.

Compile Model Ctrl+E

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

В процессе компиляции модели LINDO удерживает на экране следующее окно, позволяющее следить за процессом компиляции:

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

Если LINDO обнаруживает ошибку в процессе компиляции, он информирует вас о номере строки, в которой встретилась ошибка, и перемещает курсор к этой строке.

Вызов компилятора может оказаться полезным в некоторых ситуациях. Прежде всего, вы можете использовать его, чтобы проконтролировать ошибки в процессе разработки модели. Во-вторых, компиляция модели строит таблицу переменных и имен строк, необходимую для команды Paste Symbol. И, наконец, компиляция удаляет ранее сохраненные базисы модели. Если вы сохранили модель в течение сеанса работы, LINDO удерживает в памяти базис (т.е. решение) для использования в качестве стартовой точки на случай, если вы модифицируете модель и повторно запустите ее решение. Выполнение команды Compile приведет к стиранию базиса модели. Так что все последующие команды будут начинаться «с нуля».

Debug Ctrl+D

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

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

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

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

Обычно отладчик помогает существенно сократить усилия по поиску ошибок. Первая версия отладчика была разработана по просьбе пользователя, имеющего дело с недопустимой моделью. Пользователь тратил целые сутки на поиск ошибки в модели из 400 строк. Отладчик быстро сформировал «необходимое множество» из 55 ограничений, равно как и «достаточное множество» строк. Пользователь очень быстро заметил, что RHS (правая часть) в «достаточном множестве» ограничений была неправильной.

Следующий пример носит иллюстративный характер. Коэффициент 0.55 в 4-й строке должен быть 5.5.

При попытке решить модель в этой формулировке, получим следующее сообщение об ошибке:

Если теперь запустить команду Debug, то получим следующий анализ в окне отчета:

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

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

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

Получившаяся модель является неограниченной, и при выполнении команды Solve мы получим следующее сообщение об ошибке:

Получив такой сигнал и выполнив команду Debug из меню Solve, мы получим следующий анализ:

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

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

Pivot Ctrl+N

Основной операцией в алгоритме симплекс-метода, который использует LINDO, является ввод в решение переменной, имеющей ранее нулевое значение, одновременно полгая нулю другую переменную. Эта операция обычно называется «выбором ведущего (pivot) элемента». Команда Pivot позволяет выполнить индивидуальную настройку выбора нового базиса, оптимальным образом выбирая переменную и строку для изменения базиса.

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

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

Мы будем дважды использовать команду Pivot для того, чтобы ввести X и Y в решение, и, выполнив это, получить оптимальное решение.

При первом обращении к команде Pivot будет выведен на экран следующий диалог:

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

Возвращаясь к нашему примеру, выберем в качестве ведущей переменную Y, поскольку она имеет наибольший коэффициент в целевой функции. Поскольку мы хотим сами выбрать ведущую переменную, то должны мышкой выбрать радио-кнопку “Use Mine” в группе “Variable Selection”. Затем, наберем имя переменной, Y, в поле редактирования “My variable Selection”. Поскольку мы решили выбирать также и ведущую строку, щелкнем мышкой по радио-кнопке “Use Mine” в группе “Row Selection”. И наконец, наберем ведущую строку в поле редактирования “My Row Selection”. Анализируя нашу модель, найдем, что строка 4 является строкой с наиболее сильным ограничением на Y, поэтому ее и выберем в качестве ведущей. После всего этого диалоговое окно команды Pivot будет иметь вид:

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

LINDO констатирует, что в качестве ведущей была выбрана переменная Y в строке 4, и что теперь переменная Y имеет значение 60, а целевая функция — значение 1600.

В образовательных целях полезно посмотреть симплекс-таблицу, прежде чем выполнять следующее изменение базиса. Чтобы вывести ее на экран, выберите команду Reports|Tableau. LINDO выведет на экран следующее:

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

Нажав OK, чтобы выполнить преобразование, получим результат в виде:

После ввода X в решение значение целевой функции поднялось до 2050 — оптимального решения. Если вам требуется полный отчет о решении, выберите команду Reports|Solution. Вы получите следующий отчет:

Preemptive Goal Ctrl+G

Команда Preemptive Goal (Приоритетная цель) выполняет лексическую оптимизацию модели. Она позволяет пользователю указать упорядоченный список целей. LINDO начнет с оптимизации первой цели. Имея оптимальное значение для нее, он затем оптимизирует вторую цель при условии, что первая сохраняет оптимальное значение. Имея оптимальные значения для первой и второй целей, LINDO затем оптимизирует третью цель и.д.

Типичной ситуацией является такая, в которой прежде всего следует минимизировать затраты или максимизировать прибыль, а второй целью является «сглаживание» (в некотором смысле) решения. Примерами могут служить задача о запасах или планирование штатного расписания, в которых требуется удовлетворить ряду требований. Традиционные формулировки таких проблем часто приводят к решению со множеством оптимумов, некоторые из которых чрезмерно перекрывают одно или несколько требований, а остальные просто удовлетворяются. Пользователь обычно заинтересован в том, чтобы решения, в которых имеет место чрезмерное удовлетворение требованиям, были распределены более равномерно. В целевом программирования в качестве первой цели будет выбрана минимизация затрат при выполнении всех требований, и, возможно, в качестве второй цели — минимизировать максимум чрезмерно выполненных требований. Лексический подход позволяет пользователю не беспокоиться о точном выборе соотношения между затратами на решение и значениями чрезмерно выполненных требований.

В следующем примере, мы рассмотри применение команды Preemptive Goal к небольшой модели планирования расписания. Мы имеем ограничения в расписании для каждого из семи дней недели. Нанятые сотрудники работают по пять дней в неделю с двумя выходными. Переменная M представляет количество рабочих, начинающих работу в понедельник, T — начинающих работу во вторник, и т.д. Формулировка модели следующая:

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

Как утверждает решение, все излишки рабочей силы встречаются только в понедельник (Monday) и во вторник (Tuesday), на что указывают ненулевые коэффициенты в столбце SLACK OR SURPLUS для этих двух дней. Таким образом, в понедельник и вторник мы имеем по два лишних рабочих, в то время как в остальные дни таковых нет.

Мы согласны иметь лишних рабочих, но, по возможности, нежелательно иметь более одного лишнего рабочего в день. Обозначим количество лишних рабочих переменными с первой буквой X, превышающего одного рабочего, в каждый из дней. Тогда, используя (вместо стандартной команды Solve) команду Preemptive Goal, мы сможем сначала минимизировать затраты, зафиксировать их при оптимальных значениях, и затем максимизировать сумму X-переменных. Модифицированная модель примет вид:

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

Отметим, что поскольку мы максимизируем EXTRA она имеет отрицательный знак в целевой функции.

После применения команды Preemptive Goal получим новое решение:

Отметим, что теперь мы имеем только по одному лишнему рабочему в каждый из четырех дней — понедельник (Monday), среду(Tuesday), субботу(Saturday) и воскресенье(Sunday), что соответствует переменным XM, XT, XS И XN. Таким образом мы распределили излишек рабочих дополнительно на два рабочих дня, не увеличивая затрат по найму рабочих.

Команда Preemptive Goal применима как линейным, так и целочисленным программам. Она может использоваться и в моделях квадратичного программирования.

Меню Report

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

Solution Alt+O

Команда Solution посылает стандартный отчет о решении в окно отчета (Reports Window). Обычно такой отчет генерируется автоматически как часть команды Solve. Это автоматическое создание отчета будет подавлено, если вы переводите LINDO в режим Terse (краткий) в настройках команды Options. Если LINDO находится именно в режиме Terse, необходимо использовать команду Solution, чтобы получить отчет о решении.

Когда команда начинает работать, на экран выводится следующий диалог:

По существу, LINDO приглашает вас определиться, хотите ли включить в отчет все значения (All Values) или только не нулевые (Nonzerous). Если затребуете только не нулевые, то LINDO включит в отчет только переменные, значения которых отличны нуля, а также только связанные с ними строки. Такой ответ может значительно уменьшить размер отчета.

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

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

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

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

Далее, в разделе строк отчета находится по одной сроке на каждое ограничение, определяемой его именем (если таковое имеется), его значение «избытка или недостатка» (slack or surplus) и его двойственной цены. Столбец SLACK OR SURPLUS говорит о том, насколько точно выполняется каждое из ограничений. Эта величина для ограничений типа «меньше или равно» обычно называется недостатком (slack), а для неравенств типа «больше или равно» — иэбытком (surplus). Если ограничение выполняется точно в виде равенства, то величина SLACK OR SURPLUS будет равна нулю. Если ограничение нарушается, как в случае недопустимого решения, то значение SLACK OR SURPLUS будет отрицательным. Знание этого обстоятельства поможет вам находить ограничения с нарушениями для недопустимых моделей.

Отчет о решении также содержит столбец DUAL PRICE (двойственной цены) для каждого ограничения. Можно интерпретировать двойственную цену как количество, на которое может быть улучшено значение целевой функции при увеличении на единицу правой части ограничения. Эту величину иногда называют теневой ценой, поскольку она говорит о том, как много вы готовы заплатить за единицу дополнительного ресурса. Значение двойственной цены имеет смысл в линейных и квадратичных моделях, но, в целом, может быть проигнорировано при решении моделей целочисленного программирования.

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

Заключительная строка в отчете решения дает количество итераций, или ведущих преобразований симплекс-метода, потребовавшихся для решения задачи. Для задач целочисленного программирования LINDO также выдает количество ветвей, являющееся количеством переменных, на которых решатель метода «ветвей и границ» вынужден произвести ветвление при поиске решения.

Range Alt+1

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

Отчет о диапазонах включает в себя:

· Имена переменных вместе с их коэффициентами в целевой функции и допустимые увеличение и уменьшение этих коэффициентов

· Номера (или имена) строк с их значениями правых частей и допустимых увеличения и уменьшения значения правой части.

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

Чтобы проиллюстрировать команду Range, рассмотрим небольшую линейную задачу:

Решив ее, получим решение в виде:

… и команда Range сформирует следующий отчет:

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

Внесем некоторые изменения в приведенный пример, чтобы проиллюстрировать эти принципы. Отметим, что допустимое уменьшение переменной для COMP1 равно 5. Следовательно, изменение коэффициента целевой функции у переменной COMP1 до 15.1 (20–4.9) не должно приводить к изменению значения переменной в решении. Однако, уменьшение этого коэффициента еще на одну десятую до 15 уже окажет влияние на решение. Внеся изменения в целевую функцию, получим:

… и, решив заново задачу, получим:

Как и предсказывалось отчетом о диапазонах, оптимальное значение не изменилось.

Теперь изменим коэффициент при COMP1 сверх допустимого изменения до значения 14.9, так что измененная модель будет:

Решив заново модель, получим новое решение:

Отметим, что теперь значения переменных изменились до того, что COM1 выведена из решения.

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

Parametric Alt+2

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

Чтобы дать LINDO возможность параметрически изменять значение в правой части модели, решите ее и затем выберите команду Parametrics. Для иллюстрации предположим, что мы уже решили следующую модель планирования найма рабочих:

Далее, мы вызываем команду Parametrics, после чего на экране появится диалоговое окно:

Прежде всего, мы должны выбрать строку и ввести ее в поле с меткой “Parametric Row”. Предположим, что хотим посмотреть, как изменяются затраты по найму рабочих с возрастанием требования штатного расписания в субботу (Saturday). В этом случае параметризуемой строкой будет строка “SAT”. Можно набрать слово SAT в поле редактирования или просто дважды щелкнуть мышкой по строке SAT в расположенном ниже списке. После этого наше диалоговое окно примет вид:

После того, как выбрана строка, LINDO выведет в левом нижнем углу диалогового окна тип строки (<=, =, или >=) и текущее значение правой части. Предположим, что мы хотим проследить влияние роста требований на количество рабочих в субботу вплоть до четырехсот рабочих. В соответствии с этим следует изменить текущее значение правой части с 120 на 400 в поле “New RHS Value”. Затем перейдем группе “Report Type” в нижней правой части диалогового окна, где мы должны выбрать тип отчета — текстовый (text) и/или графический (Graphics). В случае выбора графического отчета следует также определиться, какой тип графика вы выбираете — двумерный (2D) или трехмерный (3D).

Далее, нажмем кнопку OK, чтобы сгенерировать параметрический отчет. Текстовый отчет будет послан в окно отчета (Reports Window) и появится в следующем виде:

Начиная с начального требования в 129 рабочих для субботы, показанного в первой строке значения RHS VAL, мы имеем двойственную цену 120. Это означает, что затраты возрастут на $20 при увеличении требований на одного рабочего в субботу. Возрастание требований до 170 рабочих (показано во второй строке) приведет к увеличению целевой функции на $1000 (50*$20). Однако, когда требования возрастут до 185 человек, двойственная цена изменится до 33.33. То есть теперь затратs на одного рабочего в субботу составят $33.33 (на $13.33 больше, чем в предыдущем случае). Увеличение числа рабочих до 260 (показано в строке 4) увеличит целевую функцию на $2500 ($33.33*75) по сравнению с увеличением до 185 человек. Двойственная увеличится до 100, когда требования в рабочей силе в субботу возрастут до 340 человек в 5-й строке. Это приведет к увеличению целевой функции на $8000 (80*$100) по сравнению с требованием в 260 человек. С этого момента и далее возрастание требований на одного рабочего потребует дополнительных затрат в $100 на человека.

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

Значения правой части представлены по горизонтально оси, а целевой функции — по вертикальной.

На первый взгляд, команда Parametrics позволяет исследовать за один раз изменения правой части только одного ограничения. Представьте, однако, что простой прием позволяет вас сделать это линейным образом для нескольких правых частей одновременно. Введем изменяемый столбец с именем D. Его коэффициенты могут присутствовать в некоторых или всех строках. Добавим ограничение D=0, а затем выполним параметрический анализ для правых частей (RHS) этого ограничения.

Команда Parametrics применима к линейным и квадратичным моделям, но не применима к задачам целочисленного программирования.

Statistics Alt+3

Команда Statistics посылает небольшой отчет в Reports Window (окно отчета). Этот отчет содержит некоторое суммарные сведения статистического характера о модели активного окна.

В качестве иллюстрации рассмотрим следующую модель:

Выполнение команды Statistics для этой модели выведет следующий отчет:

Первая строка содержит:

· Количество строк,

· Количество переменных,

· Количество целых переменных, вместе с количеством (в скобках) бинарных переменных типа 0/1,

· QCP, являющегося индексом первого реального квадратичного ограничения (в задачах квадратичного программирования).

Вторая строка содержит:

· Число ненулевых коэффициентов во всей модели,

· Количество ненулевых коэффициентов в ограничениях, с количеством (в скобках) тех из них, которые имеют значения +1
или –1,

· Плотность модели, определяемую как (количество ненулевых элементов)/[(число строк)*(число столбцов + 1)]

Третья строка содержит:

· Абсолютные значения наименьшего и наибольшего из ненулевых элементов соответственно.

Четвертая строка содержит:

· Тип целевой функции (MIN или MAX),

· Количество ограничений типа «меньше или равно», «равно» и «больше или равно»,

· Верхнюю границу, вычисляемую из суммы обобщенных верхних ограничений (GUBS) — ограничений, которые не имеют общих переменных,

· Нижнюю границу, вычисляемую из верхних границ переменных (VUBS). Например, ограничение X1 + X2 – X3 = 0 содержит следствия:

из X3 = 0 следует X1 = 0

из X3 = 0 следует X2 = 0

Последняя строка содержит:

· Количество столбцов с единственным ненулевым коэффициентом,

· Количество избыточных столбцов, то есть идентичных какому-то другому, за исключением, может быть, границ.

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

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

Peruse Alt+4

Команда Peruse может быть использована для просмотра или детального анализа выделенной части решения модели и/или структуры. (Для пользователей предыдущих версий LINDO эта команда является расширенной версией старых команд CPRI и RPRI). Отчет о части решения генерируется в текстовом и/или графическом формате. Возможность сосредоточить внимание на какой-то отдельной части модели и его решения с помощью команды Peruse особенно полезна в больших моделях, в которых попытка отсеять что-либо из всего текста может оказаться непреодолимой проблемой.

Чтобы использовать все возможности команды Peruse, следует сначала для модели выполнить команду Solve (хотя это и не обязательно). Затем запустите на исполнение команду Peruse, и LINDO откроет диалоговое окно:

Команда Peruse создает отчет либо по строкам, либо по столбцам. Поэтому, в зависимости от желаемого вида отчета, вы должны вы брать либо радио-кнопку Columns (колонки), либо кнопку Rows (строки) в группе “Orientations”.

Далее, необходимо в группе “View Items” отметить элементы, которые вы хотите включить в отчет. Список элементов-кандидатов и их определение приведен ниже (Заметим, что определение элемента зависит от того, как будет ориентирован отчет — по строкам или по столбцам):

Элемент отчета	Определение в столбцах	Определение в колонках
Name	Имя столбца	Имя строки
Primal	Имя столбца	Имя строки
Dual	Приведенные затраты	Двойственная цена
Rim	Коэффициент в целевой функции	Правая часть
Upper bound	Верхняя граница	N/A
Lower bound	Нижняя граница	N/A
Type	“C” для непрерывного, “F” для свободного, “I” для целого	“<” для «меньше или равно», “=” для «равно,» “>” для «больше или равно»
Nonzeros	Количество ненулевых столбцов	Количество ненулевых строк

Затем вы можете (в необязательном порядке) ввести в поле редактирования “Condition (optional)” условие, которое вы можете использовать для отфильтровки из отчета нежелательных строк или столбцов. Мы обсудим эту возможность подробнее ниже.

Остальные опции касаются формата отчета. Первой рассматриваемой в этом отношении опцией является тип отчета в группе “Report Type”. Вы можете выбрать либо текстовый отчет, либо графический, либо оба. Текстовый отчет направляется в окно отчета. Графический отчет помещается в отдельное окно. Если вы выберите текстовый отчет, то вам будут доступны также опции в группе “Text Report Format” — включать ли (Include Header) заголовок столбцов или использовать в качестве разделителя запятую (Comma Delimited). Если вы выбрали графическую форму отчета, то можете дополнительно указать в группе “Graph Type” характер графика — area (в виде площади), bar (столбчатый), line (линиями), pie (секторный), point (точками). Вы можете также в группе “Graph Style” указать стиль графика — двумерный (2D) или трехмерный (3D). И наконец, для графического отчета вы можете указать (по желанию) заголовок графика, введя его в поле редактирования “Graph Title”.

После того, как определитесь со всеми этими опциями, нажмите кнопку OK для генерации отчета.

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

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

Создадим теперь текстовый и графический отчеты, в которых выводятся значения столбцов. Для графического отчета используем столбчатую (bar) трехмерную (3D) диаграмму. Диалоговое окно команды Peruse при таком выборе опций будет выглядеть следующим образом:

Текстовый отчет посылается в окно отчета и будет иметь вид:

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

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

Элемент отчета	Символ
Name	N
Primal	P
Dual	D
Rim	R
Upper bound	U
Lower bound	L
Type	T
Nonzeros	Z
Name

В дополнение к этим символам, в следующей таблице перечислены операторы, которые можно применять к символам при конструировании выражения:

Оператор	Функциональное описание
%	Универсальный символо-заменитель, используемый при формировании шаблона имени переменной
+	Сложение
-	Вычитание
/	Деление
*	Умножение
LOG(x)	Натуральный логарифм числа x
EXP(x)	Степень числа x с основанием e
ABS(x)	Абсолютная величина x
.AND.	Логическое И
.OR.	Логическое ИЛИ
.NOT	Логическое НЕ
>	Больше
<	Меньше
=	Равно
#	Не равно
()	Скобки для указания порядка действий

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

Введем это выражение в поле редактирования “Condition”, как показано на следующем рисунке:

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

Picture Alt+5

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

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

Чтобы создать изображение модели, сначала выберите мышью окно модели. Затем запустите команду Picture. На экране появится диалоговое окно:

Во-первых, вы должны определиться, хотите ли вы, чтобы LINDO переставил строки и столбцы, так чтобы ненулевые элементы располагались ниже главной диагонали. Модель, в которой возможно такое преобразование, решается относительно проще. Если вы хотите, чтобы LINDO выполнил такую перестановку, отметьте опцию “ Lower Triangular” в группе “Row/Var Permutation”, иначе выберите радио-кнопку “None”.

Следующая опция, которую следует выбрать в группе Picture Type — это тип изображения (Picture Type). Вы можете выбрать текстовый (Text) тип, графический (Graph) или оба вместе (Graph and Text). Текстовое изображение направляется в окно отчета. Графическое изображение модели выводится в отдельное окно.

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

Установим опцию, чтобы LINDO не выполнял перестановок строк и столбцов к нижне-диагональному, виду введем установку для генерации как текстового, так и графического отчета. Так что диалоговое окно установок команды Picture будет выглядеть следующим образом:

После нажатия кнопки OK появятся текстовый и графический отчеты в следующем виде:

Дата добавления: 2015-11-16