2) Искусство создания моделей лп

Чтобы описать управленческую ситуацию в виде символической (математической) мо­дели, полезно сначала составить "словесную модель". Это делается следующим образом.

1. Описать словами цель и целевую функцию, т е показатель эффективности

2. Дать словесное описание каждого ограничения, обращая особое внимание на то, является данное ограничение требованием в форме неравенств или равенством

3. Шаги 1 и 2 приведут к словесному описанию переменных решения

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

После выполнения пп 1-3 следует присвоить обозначения (или имена) переменным решения Затем необходимо выполнить такие действия.

4. Выразить все ограничения через обозначенные переменные решения

5. Выразить с помощью обозначенных переменных целевую функцию

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

Рассмотрим еще один аспект формирования модели ЛП. Как уже отмечалось, ограни­чения могут иметь форму неравенств типа "<" или ">". Студенты часто задают вопрос, бы­вают ли в модели линейного программирования ограничения в виде строгих неравенств ти­па "<" или ">". Ответ — нет. Причина этого имеет математическую природу: так делается для того, чтобы надлежащим образом сформулированная задача имела решение. Матема­тическое доказательство данного утверждения не входит в нашу задачу. Однако не будет преувеличением сказать, что практически в любой реальной жизненной ситуации, в которой встречаются ограничения, неравенств типа "<" или ">" вполне достаточно, что­бы передать реальный смысл. Например, если переменная Х должна быть < 15, то в модели вполне можно использовать ограничение Х< 14,9999999999.

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

Невозвратные и переменные издержки

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

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

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

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

Модель ЛП и ее представление в электронных таблицах

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

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

1. Написание и проверка символической модели ЛП. Модель записывается на бумаге в математическом виде; это не займет много времени и поможет при отладке окончательного варианта табличной модели в Excel. Затем анализируются формулировки математической задачи с целью выявления возможных логических оши­бок.

2. Создание и отладка табличной модели ЛП На основе символической модели ЛП создается ее представление в Excel. Затем производится проверка полученной табличной модели путем задания различных значений переменных решения с целью выявить возможные очевидные ошибки (например, для заведомо допустимых ре­шений нарушаются ограничения, значения в ячейках левых частей или критерий эффективности оказываются лишенными смысла и т.д.).

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

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

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

• Каждая переменная решения располагается в отдельной ячейке, ячейки груп­пируются по строкам или столбцам; каждому ограничению отводится отдельная строка или столбец таблицы. (Чаще всего переменные решения расположены в столбцах, а ограничения — в строках.)

• Переменные решения группируются в отдельный блок столбцов/строк; аналогично ограничения группируются в свой блок строк/столбцов.

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

• Коэффициенты целевой функции хранятся в отдельной строке, располагаясь непосредственно под или над соответствующими переменными решения; фор­мула для вычисления целевой функции находится в соседней ячейке.

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

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

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

• Ячейки, содержащие правые части ограничений, должны включать константы или формулы, в которые не входят переменные решения, — все формулы в пра­вой части, прямо или косвенно связанные с переменными решения, должны быть перенесены в левую часть с помощью алгебраических преобразований данного неравенства.

• Не следует использовать в формулах модели ЛП функции Excel ЕСЛИ, ABS, MAX, MIN и другие нелинейные функции. Такие функции могут использоваться в формулах рабочего листа, но только в том случае, если они не влияют (прямо или косвенно) на вычисление целевой функции.

• Условия неотрицательности переменных решения не обязательно включать в табличную модель. Как правило, они опускаются и указываются непосредст­венно в диалоговом окне средства Поиск решения.

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