WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:   || 2 |

«1 СОДЕРЖАНИЕ 2. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В MICROSOFT EXCEL. 2 Формализация моделей ЛП (Пример 1) Представление модели ЛП в электронных таблицах Решение ...»

-- [ Страница 1 ] --

1

СОДЕРЖАНИЕ

2. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В MICROSOFT EXCEL. 2

Формализация моделей ЛП (Пример 1)

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

Решение задач ЛП средствами надстройки Поиск решения

3. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

Анализ чувствительности модели ЛП

Изменения коэффициентов целевой функции

Изменение правых частей ограничений

Анализ чувствительности модели ЦЛП

4. ТРАНСПОРТНАЯ МОДЕЛЬ

Пример 2. Выбор оптимального варианта создания мини-завода и прикрепления металлопроката к поставщикам

Формулировка и решение задачи ЛП

Варианты транспортной модели

Максимизация транспортных моделей

Несбалансированные модели

Модель с недопустимыми путями

Целочисленные решения

Альтернативные оптимумы для нескольких целей

2. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В

MICROSOFT EXCEL*

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

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

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

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

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

Модель условной оптимизации призвана так распределить ограниченные ресурсы, чтобы оптимизировать целевую функцию (под «ограниченными» подразумеваются ресурсы, на которые распространяются ограничения).




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

* Разделы 2, 3, 4 даны на основе Мур Дж., Уэдерфорд Ларри, и др. Экономическое моделирование в Microsoft Excel, 6-е изд.: Пер. с англ. М.: Издательский дом «Вильямс», 2004. 1024 с.

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

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

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

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

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

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

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

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

На данном этапе следует проверить модель на соответствие единиц измерения.

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

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





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

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

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

Примером нелинейной функции может служить функция 14x1 + 12x1x2, поскольку слагаемое 12x1x2 содержит произведение переменных. Функция 9x12 + 8x2 также является нелинейной, так как переменная x1 возводится во вторую степень. Другой пример нелинейной функции:

19Logx1 + 12x12x2. Примерами функций Excel, которые часто делают модели нелинейными, являются функции «ЕСЛИ», «MAX», «MIN», «LN» и «ABS».

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

Существуют эффективные методы решения задач ЛП. Прежде чем перейти непосредственно к процессу решению задачи ЛП с помощью электронных таблиц, уделим внимание представлению моделей ЛП в электронных таблицах. Рассмотрим: 1) методику формализации моделей ЛП; 2) правила представления моделей ЛП в электронных таблицах, которые упростят применение средства Excel «Поиск решения»; 3) использование средства «Поиск решения» для решения задачи ЛП.

Формализация моделей ЛП (Пример 1) Первым этапом формализации модели линейного программирования должно стать выявление ограничений на переменные решения, вторым – задание целевой функции.

Рассмотрим формализацию на основе конкретного примера.

Пример 1. Определить оптимальную совокупность (набор) технологических схем и объемы производства по ним изделий двух типов (см. Рис. 2.1), обеспечивающую максимум прибыли, если известно что:

a) производство изделий типа 1 должно быть не менее 1000 тонн;

b) производство изделий типа 2 должно быть равным 2000 тонн (недопроизводство приведет к срыву поставок, к штрафам, а перепроизводство к затовариванию продукции);

c) производство продукции типа 1 возможна по двум технологическим схемам (1 и 2), а производство продукции типа 2 также по двум другим схемам (3 и 4).

d) в технологической цепочке каждой из схем занято два типа оборудования, фонд рабочего времени типа 1 – 7000 станко-часов в год, а типа 2 – 6000 станко-часов в год.

e) нормы расхода станко-часов на 1 т готовых изделий на различных типах оборудования и по различным технологическим схемам, а также прибыль на 1 т изделий представлена в табл. 2.1.

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

Нормы расхода рабочего времени на 1 т продукции и прибыль на 1 т продукции оборудования Схема 1, ст-час/т Схема 2, ст-час/т Схема 3, ст-час/т Схема 4, ст-час/т производства Определение ограничений. Введем обозначения: пусть х1, х2, х3, х4 – интенсивности использования каждой технологической схемы.

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

Начнем с условий a) и c), задающих требование к минимальному объему производства Продукции 1 по технологическим схемам 1 и 2: для любого плана выпуска справедливо следующее неравенство:

(объем пр-ва Продукции 1 по Схеме 1) + (объем пр-ва Продукции 1 по Схеме 2) Тогда, исходя из принятых обозначений, выражение для суммарной потребности в Продукции 1 примет следующий вид:

Условие (2.1) называется ограничением в виде неравенства. Число 1000 называется правой частью неравенства. Левая часть неравенства, которая зависит от неизвестных х1 и х2, называется функцией ограничения. Неравенство (2.1) – символический способ представления ограничения, требующего, чтобы суммарное производство Продукции 1 по технологической схеме 1 и 2 было не менее 1000 тонн.

Теперь рассмотрим условия b) и c), которые задают требования к объему производства Продукции 2 по технологическим схемам 3 и 4:

Отметим, что условие (2.2), в отличие от условия (2.1), задается «жестким»

равенством (перепроизводство для нас также невыгодно, как и недопроизводство).

Неравенства (2.1) и (2.2) – два ограничения по плану производства. Есть ли другие ограничения? В перечне пунктов, которые необходимо учесть, говорится об ограниченности фонда рабочего времени оборудования – условие d). Это ограничивает объемы производства Продукции 1 и Продукции 2. Принимая во внимание условие e) (таблица 2.1), условие d) записывается в виде двух ограничений:

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

Условие вида (2.5), которое требует, чтобы переменные принимали неотрицательные значения, называется условием неотрицательности. Следует помнить, что неотрицательность не то же самое, что положительность. Неотрицательность допускает значение 0, в то время как положительность не допускает нулевого значения.

неотрицательности.

Оценивание решений. Набор конкретных значений переменных (х1, х2, х3, х4) называется решением; сами переменные х1, х2, х3 и х4 называются основными переменными. В данной задаче решение – это оптимальные объемы производства изделий двух типов по четырем технологическим схемам.

Среди бесконечного множества неотрицательных наборов чисел (х1, х2, х3, х4), включая дробные значения, некоторые пары будут нарушать по крайней мере одно ограничение, а некоторые будут соответствовать всем ограничениям. В нашей модели приемлемы только неотрицательные решения, соответствующие всем ограничениям. Такие решения называются допустимыми.

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

1. Прибыль от продажи Продукции 1, изготовленной по Схеме 1.

2. Прибыль от продажи Продукции 1, изготовленной по Схеме 2.

3. Прибыль от продажи Продукции 2, изготовленной по Схеме 3.

4. Прибыль от продажи Продукции 2, изготовленной по Схеме 4.

При перечислении основных производственных факторов отмечалось, что удельная прибыль на тонну Продукции 1, изготовленной по Схеме 1, составляет 260 руб., на тонну Продукции 1, изготовленной по Схеме 2, – 200 руб., на тонну Продукции 2, изготовленной по технологической Схеме 3, – 180 руб., и на тонну Продукции 2, изготовленной по технологической Схеме 4, – 120 руб. Тогда:

260х1 – прибыль от продажи х1 тонн Продукции 1, изготовленной по Схеме 1;

200х2 – прибыль от продажи х2 тонн Продукции 1, изготовленной по Схеме 2;

180х3 – прибыль от продажи х3 тонн Продукции 2, изготовленной по Схеме 3;

120х4 – прибыль от продажи х4 тонн Продукции 2, изготовленной по Схеме 4.

Таким образом, решение произвести х1 тонн Продукции 1 по Схеме 1, х2 тонн Продукции 1 по Схеме 2, х3 тонн Продукции 2 по Схеме 3 и х4 тонн Продукции 2 по Схеме приведет к получению суммарной прибыли, вычисляемой по формуле Заметим, что если известны только данные о доходах, единственное, что можно сделать – это максимизировать доход при соблюдении ограничений. Если же доступны только данные о затратах (себестоимости), то нужно минимизировать затраты, связанные с производством определенного ассортимента изделий. Однако когда известны и данные о доходах, и данные о затратах, предпочтительней максимизировать прибыль, а не просто доход.

удовлетворяющих всем ограничениям (т.е. среди допустимых решений), существует такое, которое обеспечивает наибольшую суммарную валовую прибыль. Это решение будем называть решением задачи, или оптимальным решением. Таким образом, среди всех возможных допустимых решений мы ищем решение, которое максимизирует годовую прибыль. Суммарная прибыль является функцией переменных х1, х2, х3 и х4, поэтому выражение 260х1 + 200х2 + 180х3 + 120х4 называется целевой функцией. Итак, надо найти допустимые значения х1, х2, х3 и х4, которые оптимизируют (в нашем случае максимизируют) целевую функцию. В символической форме это можно записать следующим образом:

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

максимизировать 260х1 + 200х2 + 180х3 + 120х4 (целевая функция) при ограничениях х1 + х2 1000 (минимальный объем производства Продукции 1);

х3 + х4 = 2000 (необходимый объем производства Продукции 2);

2х1 + 5х2 + 3х3 + 2х4 7000 (фонд рабочего времени Оборудования 1);

1,5х1 + 1х2 + 1х3 + 2х4 6000 (фонд рабочего времени Оборудования 2);

х1 0, х2 0, х3 0 и х4 0 (условия неотрицательности).

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

Обратите внимание на то, что ограничения были сгруппированы нами так, чтобы однотипные неравенства находились рядом. Причина такой группировки станет понятна при описании работы средства «Поиск решения». Табличная версия модели Примера 1, созданная в рабочей книге Excel «Lab1.хls», представлена на рис. 2.2. Здесь показан случай, когда по Схеме 1 производится 1428,57 т Продукции 1, по Схеме 2 – 10 т Продукции 1, по Схеме 3 – 142,86 т Продукции 2 и по Схеме 4 – 1857,14 т Продукции 2.

Заметим, что при таком ассортименте нарушается ограничения по фонду рабочего времени – рабочего времени требуется больше, чем имеется.

Наиболее простой способ ввода символов неравенств, таких как «» в ячейках E6, состоит в том, чтобы ввести в ячейку символ «», а затем щелкнуть мышью на кнопке «Подчеркнутый» на панели инструментов форматирования Excel.

Хотя содержимое показанного рабочего листа в особых пояснениях не нуждается, следует сверить формулы на листе (см. рис. 2.2) с формулами математической модели производства. Обратим ваше внимание на некоторые «неочевидные» аспекты данного рабочего листа.

Коэффициенты и переменные решения. Многие ячейки рабочего листа содержат числа. Эти числа представляют а) числовые значения коэффициентов и правых частей неравенств, они называются параметрами данной модели ЛП;

б) числовые значения основных переменных. Они называются решением.

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

Вычисление резерва. За исключением ячеек «I7» и «I8», все элементы таблицы имеют очевидный смысл. Осталось объяснить, что представляет собой элементы в ячейках «I7» и «I8».

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

Часто предпочтительней использовать более содержательные названия (чем «резерв»), например, «Остаток фонда времени, ст-час» (т.е. запас некоторого ресурса на конец планового периода, как в ячейке «I5»). Более того, вычисления в столбце «I»

однотипны. Их назначение – показать, насколько близко значение функции ограничения к значению правой части неравенства, при этом нулевой резерв свидетельствует о том, что в ограничении достигнуто равенство. Например, формула «=H10–F10» в ячейке I 2x1 + 5x2 + 3x3 + 2x4 7000. Здесь из правой части данного ограничения вычитается левая Для этой разности также часто используется название остаток или значение дополнительной переменной.

часть. Таким образом, значение запаса на конец периода (или «резерв» для данного ограничения) – это количество неиспользованных станко-часов фонда времени оборудования типа 1. Однако в ячейке «I7», соответствующей ограничению x1 + x2 1000, записана формула «левая часть ограничения минус правая часть»; такой порядок вычитания обусловлен тем, что резерв должен быть неотрицательной величиной для допустимых решений. Итак, сформулируем следующее правило.

Для ограничений типа «» при вычислении резерва из правой части неравенства вычитается левая часть.

Для ограничений типа «» при вычислении резерва из левой части неравенства вычитается правая часть.

В этих неравенствах экономический смысл «резерва» – это превышение нижней границы неравенства (например, превышение плана).

Хотя вычисление резерва и не является обязательным, оно очень полезно. Например, сразу становится очевидным, что производственный план на рис. 2.2 недопустим, поскольку запас на конец периода в ячейках «I10» и «I11» получился отрицательным.

Один из очевидных способов использования полученной модели производства – проведение анализа «Что-если» для различных решений (т.е. различных значений производства продукции по четырем технологическим схемам). Для этого следует ввести соответствующие значения в ячейки «В5», «C5», «D5» и «E5» и просмотреть значения в ячейке «F5», представляющие годовую валовую прибыль. При этом нужно следить, чтобы значения резерва в ячейках «I7:I8» и «I10:I11» были неотрицательными.

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

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

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

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

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

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

3. Попытка оптимизации модели с помощью надстройки «Поиск решения».

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

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

Ответим на второй вопрос («Почему табличная модель Примера 1 выглядит именно так, а не иначе?»). Модель Примера 1 в Excel построена в соответствии с рекомендациями о представлении моделей в Excel, которые мы приводили ранее. Именно из-за неправильного построения моделей в Excel студентам часто не удается получить нужные результаты на этапе оптимизации. Наши рекомендации позволяют выявить скрытые ошибки в задании связей между ячейками в формулах и избежать определенных проблем интерпретации результатов, получаемых с помощью средства «Поиск решения». Накопив опыт формирования моделей линейного программирования в Excel, можно пропускать этап написания математической модели. Для тех, кто такого опыта пока не имеет, предлагаем следующие рекомендации по созданию табличной модели ЛП в Excel.

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

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

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

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

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

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

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

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

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

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

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

Решение задач ЛП средствами надстройки «Поиск решения»

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

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

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

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

Использование надстройки «Поиск решения»

Используя рабочую книгу «Lab1.xls», можно попробовать получить максимальную прибыль, подставляя различные значения переменных x1, x2, x3 и x4. Скоро становится ясно, что найти наибольшую прибыль, не нарушая ограничений, непростая задача даже для модели небольшой размерности (четыре переменные и четыре ограничения).

Поиск оптимального решения. Средство «Поиск решения» позволяет найти оптимальное решение в любой модели линейного программирования с помощью нескольких щелчков кнопкой мыши. На рис. 2.3 показано оптимальное решение для модели производства из Примера 1.

Рис. 2.3. Значения производства по технологическим схемам, приносящие Надстройка «Поиск решения» состоит из двух программных компонентов. Первая – это встроенная в Excel программа, написанная на языке Visual Basic, которая транслирует представленную на рабочем листе информацию во внутреннее представление, используемое второй программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля; именно она выполняет оптимизацию и возвращает найденное решение первой программе, которая, в свою очередь, обновляет данные на рабочем листе.

Эти две программы взаимодействуют при помощи внутреннего интерфейса прикладных программ, подробности организации которого нас не интересуют. Когда выбирается команда «Поиск решения» в меню Excel «Сервис», происходит обращение к первой программе надстройки «Поиск решения», которая подготавливает таблицу к оптимизации и вызывает вторую программу-оптимизатор.

Надстройка «Поиск решения», хотя и входит в поставку Excel, не подключается автоматически к этой программе. Поэтому, если в меню «Сервис» вы не находите команды «Поиск решения», значит, надстройка не подключена. Для ее подключения выполните команду «Сервис», «Надстройки» и в открывшемся диалоговом окне «Надстройки» установите флажок перед опцией «Поиск решения».

Таким образом, использование надстройки «Поиск решения» состоит из следующих действий.

1. Откройте Excel и выполните обычные операции по созданию табличной модели.

2. После отладки модели переходите к этапу оптимизации, выбрав команду «Поиск решения» в меню «Сервис».

необходимые для процесса оптимизации.

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

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

6. Если в табличной модели нет ошибок, «Поиск решения» выведет на экран диалоговое окно «Результаты поиска решения», где можно указать, обновить ли исходную модель (т.е. занести ли в ячейки значения оптимального решения) и создавать ли отчет (который впоследствии можно распечатать).

Последовательность работы с надстройкой «Поиск решения» схематично показана на рис. 2.4.

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

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

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

Терминология, используемая в надстройке «Поиск решения»

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

Изменение Рис. 2.4. Этапы работы с надстройкой «Поиск решения»

Решение оптимизационной задачи Научиться работать с надстройкой «Поиск решения» лучше всего непосредственно за компьютером. Как показано на рис. 2.4, первым делом нужно загрузить Excel и открыть рабочую книгу «Lab1.xls», табличную модель для Примера 1. После этого с помощью команды «Сервис», «Поиск решения» вызывается средство «Поиск решения», как показано на рис. 2.5.

После того как надстройка «Поиск решения» загрузится в память, на экране должно появиться диалоговое окно, показанное на рис. 2.6. Заметьте, что по умолчанию средство «Поиск решения» настроено на модель максимизации, а курсор в этом диалоговом окне находится в поле «Установить целевую ячейку».

С помощью мыши можно передвигать по экрану диалоговое окно «Поиск решения»

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

В поле «Установить целевую ячейку» диалогового окна «Поиск решения» вводится адрес ячейки, содержащей значение целевой функции. Для модели Примера 1 в это поле следует ввести «F5», но лучше щелкнуть указателем мыши на этой ячейке, чтобы ввести ее адрес автоматически, как показано на рис. 2.7. Если адрес ячейки вводится с помощью щелчка на ячейке, Excel добавляет символы $, которые указывают на абсолютную адресацию. Можно использовать как абсолютные адреса, так и относительные (если вводить адрес ячейки вручную). В любом случае результаты будут одинаковыми.

Если щелкнуть мышью на расположенной справа в поле ввода кнопке, диалоговое окно свернется так, что будет отображаться только текущее поле (рис. 2.8). Это позволяет видеть большую часть рабочего листа и удобно производить выбор ячеек. Чтобы вновь развернуть диалоговое окно, нужно нажать клавишу «Enter» или еще раз щелкнуть на кнопке, расположенной справа в поле ввода.

Опции области «Равной» диалогового окна «Поиск решения» позволяют задать тип оптимизации. В данном случае необходимо максимизировать значение показателя эффективности, т.е. прибыль предприятия. Для этого нужно щелкнуть на переключателе «максимальному значению». Щелчок на кнопке «минимальному значению» укажет, что надо минимизировать целевую функцию (например, если показателем эффективности модели являются суммарные затраты). Можно также сделать значение целевой функции равным заданному числу, установив переключатель «значению» и введя это число. (Последний выбор позволяет с помощью средства «Поиск решения» проводить подбор параметров в моделях, содержащих много переменных и ограничений.) Следующее поле «Изменяя ячейки» позволяет указать основные переменные модели, в данном случае это диапазон «В5:E5». Чтобы ввести их в данное поле, нужно щелкнуть на этом поле, а затем выделить на рабочем листе ячейки «В5:E5» (рис. 2.9).

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

Теперь необходимо задать для средства «Поиск решения» ограничения. Щелчок на кнопке «Добавить» открывает диалоговое окно «Добавление ограничения», которое позволяет вводить ограничения, как показано на рис. 2.10. По умолчанию предполагается, что ограничение имеет вид неравенства со знаком «».

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

Рассмотрим подробно, как задаются ограничения путем указания диапазона ячеек.

Сначала в диалоговом окне «Добавление ограничения» курсор находится слева в поле «Ссылка на ячейку». Нужно выделить ячейки рабочего листа, содержащие суммы левых частей двух ограничений вида «», т.е. диапазон «F10:F11», как показано на рис. 2.10.

Заметим, что в поле «Ссылка на ячейку» нельзя вводить формулы – это должны быть ссылки на ячейки, которые, в свою очередь, могут содержать формулы.

Затем курсор переходит в правое поле ввода диалогового окна «Добавление ограничения», и в это поле помещаются адреса двух ячеек, содержащих соответствующие правые части ограничений, т.е. диапазон «H10:H11», как показано на рис. 2.11. Выполнив одно действие, мы в действительности задали два ограничения. Нужно следить, чтобы адресов ячеек левых частей было ровно столько, сколько и адресов правых частей. После этого щелкните на кнопке «Добавить» диалогового окна «Добавление ограничения», чтобы ввести эти ограничения в спецификацию «Ограничения» диалогового окна «Поиск решения»

и очистить поля диалогового окна «Добавление ограничения» для ввода следующих ограничений.

Теперь введем ограничения вида «». Процедура их ввода такая же, как и для ограничений вида «». Курсор находится слева в поле «Ссылка на ячейку», щелкаем на ячейке, содержащей левую часть ограничения, т.е. на ячейке «F7». В списке поля ввода диалогового окна «Добавление ограничения» выбираем знак «=» («больше или равно»), как показано на рис. 2.12. Обратите внимание на то, что в этом списке можно выбрать любой знак неравенства («=», «=», «=»). (Пока мы не рассматриваем опции «цел» и «двоич» из этого списка; они понадобятся при изучении моделей, в которых требуется, чтобы некоторые ячейки переменных решения принимали целочисленные значения.) После этого помещаем курсор в правое поле ввода диалогового окна «Добавление ограничения» и щелкаем на ячейке «H7». Введенное ограничение должно выглядеть так, как показано на рис. 2.13.

Теперь по аналогичной процедуре введем ограничение вида «=». Введенное ограничение должно выглядеть так, как показано на рис. 2.14.

Далее надо не забывать об условиях неотрицательности для содержимого ячеек «В5:E5». Чтобы ввести эти ограничения, сначала следует вернуться в диалоговое окно «Поиск решения» из диалогового окна «Добавление ограничения», щелкнув на кнопке «OK»

в этом окне. (Если вы случайно щелкнули на кнопке «Добавить», щелкните на кнопке «Отмена» и вы вернетесь в диалоговое окно «Поиск решения».) На данном этапе диалоговое окно «Поиск решения» для модели из Примера 1 должно выглядеть так, как показано на рис. 2.15.

Рис. 2.15. Параметры «Поиска решения» для модели Примера Чтобы определить условия неотрицательности для переменных решения, необходимо щелкнуть на кнопке «Параметры» диалогового окна «Поиск решения».

Появится диалоговое окно «Параметры поиска решения» (рис. 2.16).

Рис. 2.16. Диалоговое окно «Параметры поиска решения»

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

будет обсуждаться ниже. Остальные опции этого окна мы пока рассматривать не будем – они в основном относятся к оптимизации целочисленных и нелинейных моделей. Щелкните на кнопке «OK», чтобы вернуться в диалоговое окно «Поиск решения».

Итак, полностью завершена спецификация оптимизационной модели. Мы ввели следующую информацию:

• адрес ячейки, содержащей целевую функцию, которую необходимо оптимизировать (в данном случае максимизировать);

• диапазон ячеек, которые программа должна изменять (переменные решения);

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

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

Диалоговое окно «Результаты поиска решения» сообщает о завершении поиска (рис. 2.17). То, что программа «Поиск решения» завершила работу, не означает, что она нашла оптимальное решение. Поэтому всегда читайте сообщение, отображаемое в верхней части данного окна! Если поспешить щелкнуть на кнопке «OK», чтобы убрать диалоговое окно «Результаты поиска решения», не прочитав данное сообщение, можно пропустить важную информацию о решении. Если оптимальное решение найдено, в диалоговом окне «Результаты поиска решения» должно присутствовать два ключевых предложения.

• Решение найдено.

• Все ограничения и условия оптимальности выполнены.

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

Рис. 2.17. Диалоговое окно «Результаты поиска решения»

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

Каждый отчет выводится на новый лист рабочей книги.

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

Лист с отчетом о результатах – это просто рабочий лист Excel, у которого отключено отображение сетки. Чтобы вернуть сетку, установите флажок опции «Сетка» в диалоговом окне «Параметры» (команда «Сервис», «Параметры»). Если вы забыли выбрать отчет и закрыли окно «Результаты поиска решения», нет другого способа воссоздать отчет, кроме как повторно оптимизировать модель, чтобы окно «Результаты поиска решения» открылось вновь.

После выполнения всех указанных выше действий исходная таблица модели будет выглядеть так, как показано на рис. 2.19. Средство «Поиск решения» записало в таблицу оптимальные значения основных переменных, определяющих объемы производства по соответствующим технологическим схемам. После этого таблица пересчитывается в последний раз, чтобы вычислить максимальное значение прибыли – 620 000.

Заметим, что значения ячеек в столбце «I» также были изменены. Они показывают объемы перепроизводства и остатки фонда рабочего времени после принятия оптимального решения. Если в ячейке резерва для некоторого ограничения стоит 0 и тип ограничения отличен от «=», то такое ограничение называется лимитирующим или связывающим.

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

Если сравнить рабочий лист на рис. 2.19 с отчетом о результатах, показанным на рис. 2.18, можно заметить, что в таблице представлена вся информация, содержащаяся в отчете о результатах. Таким образом, за исключением различий в форматировании, информация отчета о результатах полностью повторяется в исходной табличной модели.

Поэтому отчет о результатах в некоторой мере избыточен.

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

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

3. АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

х1, х2, х3, х4 – интенсивности использования соответствующих технологических схем;

необходимо максимизировать 260х1 + 200х2 + 180х3 + 120х4 (целевая функция) при ограничениях х1 + х2 1000 (план производства Продукции 1);

х3 + х4 = 2000 (план производства Продукции 2);

2х1 + 5х2 + 3х3 + 2х4 7000 (фонд рабочего времени Оборудования 1);

1,5х1 + 1х2 + 1х3 + 2х4 6000 (фонд рабочего времени Оборудования 2);

х1 0, х2 0, х3 0 и х4 0 (условия неотрицательности).

Средство «Поиск решения» позволяет найти оптимальное решение для любой модели линейного программирования. На рис. 3.1 показано оптимальное решение для данной модели ЛП.

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

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

Анализ чувствительности модели ЛП Предположим, что нас интересует вопрос, насколько чувствительно оптимальное решение к небольшим изменениям исходных данных. Допустим, мы оценили среднее значение некоторого параметра модели и нашли решение, используя данную оценку. Что произойдет с оптимальным решением, если оценка изменится на 5%, 10%, 15% или больше?

Решение и оптимальное значение целевой функции будут меняться в широком диапазоне или останутся более-менее постоянными? Ответ на эти вопросы определяет достоверность рекомендаций, сформулированных на основе модели. Если оптимальное значение целевой функции изменяется незначительно при достаточно больших изменениях значения определенного параметра, можно не беспокоиться из-за неопределенности (или неточности) данного параметра. Если же оптимальное значение целевой функции меняется заметно даже при незначительных изменениях параметра, нельзя допускать высокого уровня неопределенности его значения. В таком случае, возможно, стоит затратить больше усилий на определение более точного значения этого параметра.

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

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

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

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

Естественно, желательно использовать в модели значения параметров, которые соответствовали бы прогнозируемым. Однако, в реальных ситуациях эти данные на момент моделирования зачастую невозможно знать с абсолютной точностью. Например, значения удельного дохода в расчете на единицу продукции (260 руб./т для Продукции 1, изготовленной по Схеме 1, 200 руб./т для Продукции 1, изготовленной по Схеме 2, 180 руб./т для Продукции 2, изготовленной по Схеме 3 и 120 руб./т для Продукции 2, изготовленной по Схеме 4) являются только оценками, основанными на ценах продажи и предполагаемых переменных затратах, которые могут измениться в будущем. Поэтому мы вынуждены использовать текущие оценки параметров модели, отдавая себе отчет, что будущие реальные значения этих параметров наверняка будут отличаться от используемых в модели. Но у нас могут быть достаточно веские соображения относительно возможных диапазонов, в которых будут находиться истинные значения этих параметров. Например, 260, 200, 180 и 120 – наилучшие оценки середин этих диапазонов для значений удельной прибыли.

Еще один источник неопределенности содержится в ограничениях – чаще всего недостаточно точно определены правые части ограничений. Например, правая часть ограничения (начальный запас или ресурс) для фонда времени по Оборудованию 2 равен 6000 станко-часов. В реальных приложениях это число может оказаться не соответствующим действительности, поскольку действительный фонд времени по Оборудованию 2 может быть иным по многим причинам. Таким образом, значение 6000 – всего лишь наилучшая оценка для правой части ограничения. Поэтому необходимо учитывать неопределенность в таких данных.

Последний источник неопределенности – коэффициенты функций ограничений, т.е.

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

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

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

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

Изменение коэффициентов целевой функции приводит к изменению угла наклона прямой целевой функции. Это может отразиться (а может и не отразиться) на оптимальном решении.

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

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

Рассмотрим теперь результаты применения средства «Поиск решения» для пяти различных целевых функций, чтобы разобраться, как интерпретировать информацию, содержащуюся в отчете по устойчивости, генерируемом этим средством. На рис. 3.2 представлена таблица модели лекционного примера, в которой показано оптимальное решение задачи ЛП, только вместо отчета о результатах был выбран отчет по устойчивости. Отчет по устойчивости располагается на отдельном рабочем листе, на котором убраны линии сетки (см. рис. 3.2). Вторая строка верхней части отчета, озаглавленной «Изменяемые ячейки», содержит значение 200 в столбце «Целевой коэффициент» (для Продукции 1, произведенной по Схеме 2), а «Допустимое увеличение»

для данного коэффициента равно 340. Это означает, что если остальные данные модели останутся неизменными, то, увеличив коэффициент целевой функции для Продукции 1, произведенной по Схеме 2 (т.е. удельный доход в расчете на единицу продукции) не более чем на 340, мы получим то же самое оптимальное решение задачи ЛП, что и в исходном случае; если же прирост составит более 340, текущее решение, полученное с помощью «Поиск решения», уже не будет оптимальным.

Рис. 3.2. Модель для лекционного примера и отчет по устойчивости Если прирост коэффициента целевой функции при переменной x2 (интенсивность использования технологической Схемы 2 для производства Продукции 1):

...меньше 340; такого изменения целевой функции недостаточно, чтобы решение сместилось из текущей угловой точки (Рис. 3.3);

...больше 340; такое изменение целевой функции приведет к смещению решения из текущей угловой точки в другую угловую точку (Рис. 3.4);

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

Рис. 3.3. Оптимальное решение и отчет устойчивости для значения удельной прибыли от реализации Продукции 1, произведенной по Схеме 2, равного 539 руб./т Рис. 3.4. Оптимальное решение и отчет устойчивости для значения удельной прибыли от реализации Продукции 1, произведенной по Схеме 2, равного 541 руб./т Рис. 3.5. Оптимальное решение и отчет устойчивости для значения удельной прибыли от реализации Продукции 1, произведенной по Схеме 2, равного 540 руб./т Аналогично, если остальные данные модели остаются неизменными, «Допустимое уменьшение» целевого коэффициента для Продукции 1, произведенной по Схеме 1, равного 260, составляет 140. Это значит, что уменьшение прибыли от реализации данного продукта вплоть до 120 руб., не приведет к изменению плана производства, предложенного средством «Поиск решения», но приведет к уменьшению общей прибыли (например, 421 428,57 руб.

вместо 620 000 руб., для случая x1 = 121, см. Рис.3.6). При значении прибыли, равном 120, имеем случай альтернативных оптимальных планов (Рис. 3.7).

Рис. 3.6. Оптимальное решение и отчет устойчивости для значения удельной прибыли от реализации Продукции 1, произведенной по Схеме 1, равного 121 руб./т Итак, значения «Допустимое увеличение» и «Допустимое уменьшение» в таблице «Изменяемые ячейки» отчета по устойчивости показывают, на сколько можно изменить «Целевой неизменными остальные данные модели, чтобы при изменении прибыли план производства не изменился. Иными словами, диапазоны целевого коэффициента задают пределы изменений данного коэффициента (остальные данные остаются постоянными), которые не вызовут изменений оптимального решения. В отчете по устойчивости средства «Поиск решения» не содержится никакой информации о том, каким будет новое угловое решение.

При этом оптимальное значение целевой функции может меняться.

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

1. Значения в столбцах «Допустимое увеличение» и «Допустимое уменьшение»

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

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

3. Если коэффициент при переменной в целевой функции увеличить или уменьшить в точности на допустимую величину, будет получено альтернативное оптимальное решение.

На основании отчета по устойчивости можно сделать еще один интересный вывод о решении: если для некоторой переменной из таблицы «Изменяемые ячейки» в столбце Решение задачи ЛП может оказаться вырожденным, в таком случае перечисленные далее пункты нужно рассматривать как некое упрощение.

Более точно – о невырожденном решении.

«Допустимое увеличение» или «Допустимое уменьшение» содержится нулевое значение, значит, для данной модели существует по крайней мере одна альтернативная угловая точка оптимального решения. Более того, если альтернативное оптимальное решение существует обязательно появится такое нулевое значение. Это правило проиллюстрировано на рис. 3.8, где изображена гипотетическая линейная модель максимизации с двумя переменными и тремя ограничениями-неравенствами. Прямая целевой функции параллельна прямой второго ограничения (помеченного цифрой 2). Видно, что угловые точки I и II являются альтернативными оптимумами данной модели. Поскольку «Поиск решения»

использует для оптимизации моделей ЛП метод, который просматривает угловые решения по очереди, программа укажет в качестве оптимального решения только одно из них, и отчет по устойчивости будет составлен только для этого углового решения. Предположим, что с помощью средства «Поиск решения» найдено угловое решение I. Из представленной на рис. 3.3 геометрической интерпретации модели следует, что любое увеличение коэффициента при х1, изменит угол наклона прямой целевой функции, например, она приблизится к линии, нарисованной пунктиром, и единственным оптимальным решением станет угловая точка II. Отчет по устойчивости укажет на это, проставив нулевое значение для х1 в столбце «Допустимое увеличение».

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

При наличии в модели ЛП альтернативных оптимумов незначительные отличия в точности выполнения арифметических вычислений часто приводят к тому, что на одном компьютере Поиск решения находит одно оптимальное решение, а на другом – альтернативное угловое решение.

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

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

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

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

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

Логично и обратное: процесс уменьшения правой части ограничения вида «», напротив, называется ослаблением ограничения. Данное ограничение становится проще удовлетворить. Аналогично при увеличении правой части ограничения вида «» его становится проще удовлетворить, следовательно, происходит ослабление данного ограничения.

Усиление (ослабление) ограничения-неравенства означает, что такое ограничение становится сложнее (легче) удовлетворить. Для ограничения вида «» это происходит при увеличении (уменьшении) правой части, а для ограничения вида «» – при ее уменьшении (увеличении).

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

(расширению) допустимой области или оставляет ее неизменной.

Данные выводы справедливы для всех ограничений-неравенств и не зависят ни от размерности модели (числа переменных решения), ни от вида ограничений («» или «»).

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

Посмотрим теперь, как эти выводы отражаются в отчете по устойчивости в таблице «Ограничения».

Устойчивость к изменениям правых частей ограничений и теневые цены* Рассмотрим сначала ситуацию, при которой все числа в модели лекционного примера остаются фиксированными, за исключением фонда времени Оборудования 2. Что если вместо 6 000 станко-часов их запас составит 6 001? Как это отразится на оптимальном значении целевой функции? Поскольку данное ограничение имеет вид «», можно заключить, что увеличение правой части приведет к ослаблению ограничения, т.е. его будет проще удовлетворить. Следовательно, данное изменение определенно не уменьшит значения целевой функции. Однако произойдет ли его увеличение, и если да, то насколько?

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

Введён советским учёным Л.В.Канторовичем в 1959 и в основном используется при решении экономических задач методами математического программирования. О. о. оценки в экономических задачах показывают, к каким экономическим результатам приведёт появление в хозяйственном процессе дополнительной единицы того или иного производственного компонента. Размерность О. о. оценок соответствует размерности критерия оптимальности (натуральные или натурально-условные единицы измерения, денежные и т.д.). О. о. оценки объективно вытекают из условий постановки и решения экономической задачи и целиком обусловлены совокупностью тех конкретных хозяйственных факторов, которые учтены при математической формализации производственно-экономической деятельности. Поэтому они являются эффективным средством анализа текущей хозяйственной деятельности, позволяют выявить и количественно оценить «узкие места», а при предположении некоторой устойчивости О. о. оценки дают возможность наметить направления улучшения показателей работы хозяйственного объекта.

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

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

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

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

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

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

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

При фонде времени Оборудования 2, равном 6 250 станко-часов, значение правой части ограничения для фонда времени Оборудования 2 увеличилось на 250 единиц по сравнению с исходным значением 6 000. В соответствии с определенной ранее теневой ценой (которая равна 40) значение целевой стало равным 630 000, т.е. увеличилось на 630 000 – 620 000 = 10 000 = 40 250.

Если значение фонда времени Оборудования 2 превышает 6 250 (и, например, равно 6 270), то, как показано на рис. 3.10, ограничение по фонду времени Оборудования перестает быть лимитирующим. Более того, оно становится избыточным, поскольку теперь его увеличение никак не отражается на решении. Оптимальное решение остается точно таким же, как на рис. 3.9. Решение, предложенное средством «Поиск решения», и отчет по устойчивости для значения фонда времени по Оборудованию 2, равного 6 270, представлены на рис. 3.10.

Заметим, что теперь лимитирующим является ограничение для фонда времени Оборудования 1 (см. также рис. 3.10). Кроме того, теневая цена для ограничения по фонду времени Оборудования 2 снизилась с 40 до 0. Это изменение теневой цены показывает, что предыдущая ее интерпретация верна только для определенного диапазона значений правой части ограничения. Диапазон значений правой части ограничения, для которого теневая цена остается постоянной, называется допустимым. Соответствующий диапазон указан в таблице «Ограничения» отчета по устойчивости в столбцах «Допустимое увеличение» и «Допустимое уменьшение».

Следует отметить, что теневая цена ресурса, который не полностью расходуется (т.е.

имеется его остаток) всегда равна нулю. Это видно при сравнении Рис. 3.2 и 3.9 с Рис. 3.10:

на Рис. 3.2 и 3.9 остаток фонда времени по Оборудованию 2 равен нулю, а на Рис. 3.10 равен 20. При увеличении ресурса с ненулевой ценой, изменяется также и выпуск продукции. Так, в рассматриваемом примере выпуск Продукции 1 по Схемам 1 и 2 вырос с 1 428,57 т до 1 500,00 т.

Рис. 3.9. Оптимальное решение и отчет устойчивости для фонда времени по Оборудованию 2, равного 6 250 станко-часов Рис. 3.10. Оптимальное решение и отчет устойчивости для фонда времени по Таким образом, из отчетов по устойчивости, приведенных на рис. 3.2, 3.9 и 3.10, можно извлечь следующую информацию.

a) При фонде времени Оборудования 2, равном 6 000 станко-часов (см. рис. 3.2), теневая цена равна 40, допустимое увеличение величины фонда времени Оборудования составляет 250 станко-часов, а допустимое уменьшение – 1 500 станко-часов. Можно убедиться, что для значений фонда времени Оборудования 2, находящихся в диапазоне 4 5006 250, при каждом увеличении значения запаса (правой части ограничения) на единицу (при условии, что остальные данные остаются неизменными) прирост оптимального значения целевой функции составит 40.

b) При фонде времени Оборудования 2, равном 6 250 станко-часов (см. рис. 3.9), теневая цена остается равной 40, но допустимое увеличение становится равным 0, а это означает, что для данных правой части ограничения, превышающих 6 250, значение 40 уже не будет верным. При фонде времени Оборудования 2, большем 6 250, данное ограничение становится нелимитирующим и, более того, избыточным. Незначительные изменения правой части нелимитирующего ограничения не могут повлиять на оптимальное значение целевой функции, следовательно, для нелимитирующего ограничения теневая цена всегда равна 0.

c) При фонде времени Оборудования 2, равном 6 270 станко-часов (см. рис. 3.10), данное ограничение является нелимитирующим, теневая цена равна нулю, а допустимое увеличение – бесконечности. Таким образом, при дальнейшем увеличении Фонда времени по Оборуд. №1» данное ограничение останется нелимитирующим, а теневая цена – равной 0.

Допустимое уменьшение имеет значение 20, при этом правая часть ограничения вновь примет значение 6 250. Для значений фонда времени Оборудования 2, меньше 6 250, как показано на рис. 3.10, теневая цена составляет 40, а не 0.

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

Наибольшее число, которое можно представить в Excel, равно 1Е+30, т.е. 1 и 30 нулей. Это число можно считать бесконечно большим по сравнению с другими числами, фигурирующими в модели.

2. Теневая цена нелимитирующего ограничения всегда равна 0. («Нелимитирующее»

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

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

Нормированная стоимость. К настоящему моменту мы объяснили смысл всех элементов отчета по устойчивости за исключением данных в столбце «Нормированная стоимость». Эти данные можно интерпретировать следующим образом.

1. Нормированная стоимость определенной переменной решения определяется как величина, на которую нужно изменить коэффициент при данной переменной в целевой функции, чтобы оптимальное значение этой переменной стало положительным. Таким образом, если переменная решения в точке оптимальности положительна, нормированная стоимость для нее равна нулю (см. переменные решения лекционной задачи на рис. 3.2, 3.9 и 3.10). Если же оптимальное значение некой переменной решения равно 0, то нормированная стоимость в строке, соответствующей данной переменной, равна значению в столбцах «Допустимое увеличение» или «Допустимое уменьшение» (одно из этих значений будет бесконечным, а второе равно нормированной стоимости). Например, переменная решения x в модели на рис. 3.10 в точке оптимальности имеет нулевое значение. «Нормированной стоимостью» переменной x2 является величина, на которую необходимо увеличить соответствующую ей удельные прибыль (коэффициент при x2 в целевой функции), чтобы получить Это еще один пример, когда для корректной интерпретации результатов отчета необходимо удостовериться, что данное оптимальное решение является невырожденным.

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

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

2. Альтернативный способ интерпретации нормированной стоимости переменной решения, текущее оптимальное значение которой равно 0, – использовать коэффициент (удельной величины) увеличения значения целевой функции при введении данной переменной в изначально оптимальное решение. Следовательно, нужно отказаться от предложенного средством «Поиск решения» нулевого значения и заставить данную переменную принимать положительные значения. Если в оптимальном решении x2 = 0, то удельная прибыль от реализации продукции, выпущенной по данной технологической схеме, должна возрасти, если искать оптимальное решение для модели с дополнительным ограничением, скажем, x2 = 0,1. Этот коэффициент возрастания оптимальной стоимости при условии, что x2 должна принимать положительные значения (т.е. стать базисной), и будет нормированной стоимостью x2.

Напомним, что теневая цена ограничения – это коэффициент изменения оптимального значения целевой функции при увеличении значений правой части данного ограничения. Поскольку в рассматриваемой модели x2 = 0, ограничение неотрицательности для x2 является лимитирующим. Если мы заставляем x2 принимать положительные значения, это то же самое, что увеличивать правую часть ограничения неотрицательности. Отсюда следует еще одна эквивалентная интерпретация: для модели, содержащей условия неотрицательности, нормированная стоимость является теневой ценой ограничения неотрицательности для рассматриваемой переменной решения.

Анализ чувствительности модели ЦЛП Используемый средством «Поиск решения» для решения задач ЦЛП метод ветвей и границ в общем случае требует гораздо больше времени для оптимизации модели ЦЛП, чем для оптимизации модели ЛП. К сожалению, решение ЦЛП, полученное с помощью «Поиск решения» также содержит меньше информации, чем решение задачи ЛП. Хотя диалоговое окно «Результаты поиска решения», которое появилось после успешной оптимизации модели ЦЛП (рис. 3.11), содержит опцию, вроде бы позволяющую вывести отчет по устойчивости, но после выбора этой опции появляется окно, сообщающее о том, что отчет по устойчивости не применим для задач с целочисленными переменными (рис. 3.11)! Это происходит вследствие того, что в процессе решения средство «Поиск решения» не собирает информацию о чувствительности оптимального значения целевой функции к изменениям правых частей ограничений или к изменениям коэффициентов целевой функции. Это не означает, что изменения правых частей ограничений или коэффициентов целевой функции не влияют на решение задачи ЦЛП. Безусловно, влияют! В действительности решения задач ЦЛП могут быть чрезвычайно чувствительны к изменениям значений параметров модели.

Рис. 3.11. Отчеты «Устойчивость» и «Пределы» для задач с целочисленными

4. ТРАНСПОРТНАЯ МОДЕЛЬ

Данный раздел посвящен реализации в Excel одной из наиболее популярных моделей линейной оптимизации – транспортной модели. В данной модели ставится задача потребителям, чтобы удовлетворить существующие требования с наименьшими затратами.

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

Таблица 4.1. Затраты (оценки в условных единицах) на транспортировку 1 тонны продукции, а также мощность металлургических заводов и потребность в прокате машиностроительных предприятий (тонн в год).

Обратите внимание на то, что данная модель является сбалансированной, т.е. суммарное предложение проката (450 т) равно его общему спросу (450 т). На рис. 4. представлена иллюстрация к данной модели. Число рядом с номером металлургического машиностроительного предприятия – требуемое количество проката. Линии показывают возможные пути доставки.

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

Формулировка и решение задачи ЛП Наша цель – минимизировать суммарные затраты на транспортировку проката.

Поскольку расходы на транспортировку для каждой комбинации поставщик-потребитель (например, «Завод 1-Предприятие B») прямо пропорциональны количеству проката, отправленного данным заводом на указанное предприятие (для комбинации «Завод 1Предприятие B» коэффициент пропорциональности равен 9), данную задачу можно сформулировать в виде модели линейного программирования. Обозначим через хij количество проката, отправленного Заводом i на Предприятие j (i = 1, 2, 3, 4, 5, 6, 7; j = А, В, С, D, E, F, G). Тогда х2A – количество проката, отправленного Заводом 2 на Предприятие A.

Используя данные обозначения, целевую функцию – общие транспортные расходы – можно записать как 8х1А + 9х1B +... + 9x4G.

Модель содержит ограничения двух видов.

1. Количество проката, отправленного любым поставщиком, не может превышать количества проката, имеющегося у него в наличии. Например, общее количество проката, предложение проката Заводом 1 равно 110, соответствующее ограничение имеет вид x1A + x1B + x1C + x1D + x1E + x1F + x1G 110.

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

x1A + x2A + x3A + x4A + x5A + x6A + x7A – предприятие A. Поскольку этому предприятию требуется 50 т проката, соответствующее ограничение будет иметь вид x1A + x2A + x3A + x4A + x5A + x6A + x7A 50.

Аналогичные ограничения записываются для каждого предприятия-потребителя.

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

Сформированная модель в Excel и ее оптимальное решение представлены на рис.4. и 4.3. Заметим, что основные модули модели расположены в виде трех блоков ячеек:

стоимостные параметры, переменные решения и общие затраты. Как показано на рис.4.3, используется 10 из 35 возможных маршрутов, и минимальная стоимость транспортировки составляет 3 020 у.е. Более того, из отчета по устойчивости программы «Поиск решения»

(рис. 4.4) следует, что при снижении требований на поставку проката Заводу B общие затраты снизились бы на 3 у.е. за 1 т проката; увеличение запаса проката Завода 5 также привело бы к снижению общих затрат на 10 у.е. в расчете на 1 т проката.

В соответствии с данными в главе 2 рекомендациями, табличные представления моделей строятся с соблюдением следующих правил: 1) параметры удельных затрат/прибыли, переменные решения и суммарные затраты/прибыль располагаются в отдельных диапазонах ячеек;

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

Рис.4.2. Параметры «Поиска решения» для транспортной задачи Примера Рис.4.3. Оптимальное решение транспортной задачи Примера Варианты транспортной модели В общем случае транспортная модель – это модель ЛП, позволяющая найти самый дешевый способ удовлетворить спрос в n пунктах назначения, осуществляя поставки из m исходных (отправных) пунктов.

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

Несбалансированные модели Предположим, что в нашем примере модели предложение проката Заводом составляет 130 т вместо 120 т. Тогда после удовлетворения спроса суммарное количество проката, оставшегося в пяти отправных пунктах, будет равно 10. Поскольку в формулировке задачи применялись неравенства, особых проблем при использовании средства «Поиск решения» не возникнет. Невостребованный прокат в каждом отправном пункте будет представлен в виде резерва предложения.

Если же спрос превышает предложение, модель ЛП не имеет допустимых решений.

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

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

Модель с недопустимыми путями Предположим, что некоторые пути в транспортной модели являются недопустимыми. Иногда в силу организационных условий, таких как региональные ограничения или время доставки, некоторые отправные пункты не могут обслуживать определенные пункты назначения. Предположим, что путь «Завода 1-Завод B» нельзя использовать. Для того чтобы ввести это ограничение в формулировку транспортной задачи, следует присвоить произвольно большое значение M удельным затратам для данного маршрута. Значение M должно быть значительно больше всех остальных удельных затрат модели. Это заставит «Поиск решения» отказаться от данного пути, поскольку при его использовании затраты будут гораздо больше, чем для всех других допустимых альтернатив.

В нашем случае, присвоив коэффициенту удельных затрат на транспортировку в ячейке «C6»

(см. рис. 4.3) значение 10 000, можно не сомневаться, что «Поиск решения» не будет использовать данный путь.

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

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



Pages:   || 2 |
 
Похожие работы:

«ВЫСШЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ ТРАНСПОРТ ЛЕСА УЧЕБНИК В двух томах Том 2 М. М. ОВЧИННИКОВ, В. П. ПОЛИЩУК, Г. В. ГРИГОРЬЕВ ЛЕСОСПЛАВ И СУДОВЫЕ ПЕРЕВОЗКИ Допущено Учебно-методическим объединением по образованию в области лесного дела в качестве учебника для студентов высших учебных заведений, обучающихся по специальностям Лесоинженерное дело и Лесное хозяйство УДК 630*31(075.8) ББК 43.904я73 Т654 Р е ц е н з е н т ы: зав. кафедрой Промышленный транспорт и геодезия Петрозаводского...»

«НЕДВИЖИМОСТЬ. БЛАГОУСТРОЙСТВО СРЕДСТВА ТРАНСПОРТА РАБОТА. ТОВАРЫ. УСЛУГИ Екатеринбург ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ ПОНЕДЕЛЬНИК - СРЕДА Информационное издание ООО НПП Сафлор № 69 (2035) 3-5 сентября 2012 г. Выходит с 1996 г. 2 раза в неделю по понедельникам и четвергам Газета №2035 от 03.09. СОДЕРЖАНИЕ ГАЗЕТЫ 222 Мобильная связь. 413 Средние и тяжелые грузовики.27 Аренда и прокат автомобилей. НЕДВИЖИМОСТЬ Телефоны и контракты 415 Спецтехника 225 Аксессуары для мобильных 567 Аренда спецтехники и...»

«ЧЕТВЕРГ В ГАЗЕТУ ЧЕРЕЗ ИНТЕРНЕТ — БЫСТРО И УДОБНО стр. 43 26 декабря 2013 3 13 23 31 33 40 ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ № 100 (1379) Рекламно информационное издание ООО Пронто НН Распространение: Владимирская область Издается с 1994 г. Выходит 2 раза в неделю: по понедельникам и четвергам 4207639_302 4205615_ 4210713_305 4209242_ 4210609_ КАК ПОДАТЬ ОБЪЯВЛЕНИЕ? 2 Правила публикации, приема объявлений и тарифы на стр. 42- КУРСЫ, УРОКИ, КОНСУЛЬТАЦИИ ТРАНСПОРТНЫЕ УСЛУГИ И АРЕНДА Иностранные языки 380...»

«№ 8/20515 06.04.2009 -147ПОСТАНОВЛЕНИЕ МИНИСТЕРСТВА ТРАНСПОРТА И КОММУНИКАЦИЙ РЕСПУБЛИКИ БЕЛАРУСЬ 21 января 2009 г. № 9 8/20515 Об утверждении Авиационных правил Процедуры сертификации 8/20515 планеров, дельтапланов, парапланов, легких и сверхлегких летательных аппаратов, аэростатических аппаратов и воздушных судов любительской конструкции В соответствии со статьей 28 Воздушного кодекса Республики Беларусь, на основании Положения о Министерстве транспорта и коммуникаций Республики Беларусь,...»

«Зарегистрировано в Минюсте РФ 23 марта 2010 г. N 16699 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПРИКАЗ от 15 февраля 2010 г. N 125 ОБ УТВЕРЖДЕНИИ И ВВЕДЕНИИ В ДЕЙСТВИЕ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 190600 ЭКСПЛУАТАЦИЯ ТРАНСПОРТНО-ТЕХНОЛОГИЧЕСКИХ МАШИН И КОМПЛЕКСОВ (КВАЛИФИКАЦИЯ (СТЕПЕНЬ) МАГИСТР) (в ред. Приказов Минобрнауки РФ от 18.05.2011 N 1657, от 31.05.2011 N 1975) КонсультантПлюс:...»

«База нормативной документации: www.complexdoc.ru МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ПИСЬМО от 10 марта 1995 г. № 431-ВК О СОГЛАСОВАНИИ ПРАВИЛ ПО ОХРАНЕ ТРУДА Правила по охране труда на автомобильном транспорте считать согласованными с Министерством труда Российской Федерации в редакции, изложенной в приложении к письму Департамента автомобильного транспорта Минтранса России от 08.02.95 № ДАТ-16/42. В.Ф. КОЛОСОВ Утверждены Приказом Министерства транспорта Российской Федерации от 13...»

«СОДЕРЖАНИЕ СОДЕРЖАНИЕ ОСНОВНЫЕ ЭКОНОМИЧЕСКИЕ И СОЦИАЛЬНЫЕ ПОКАЗАТЕЛИ ПРОИЗВОДСТВО ТОВАРОВ И УСЛУГ ОБОРОТ ОРГАНИЗАЦИЙ ПРОМЫШЛЕННОЕ ПРОИЗВОДСТВО Добыча полезных ископаемых Обрабатывающие производства Производство и распределение электроэнергии, газа и воды СЕЛЬСКОЕ ХОЗЯЙСТВО ЛЕСОЗАГОТОВКИ РЫБОЛОВСТВО И РЫБОВОДСТВО СТРОИТЕЛЬСТВО ТРАНСПОРТ РЫНКИ ТОВАРОВ И УСЛУГ Оптовая торговля и товарные рынки Розничная торговля Рестораны, кафе и бары Рынок платных услуг населению Туризм ВНЕШНЕЭКОНОМИЧЕСКИЕ СВЯЗИ...»

«МИНИСТЕРСТВО ТРАНСПОРТА РОССИИ ДЕПАРТАМЕНТ ВОЗДУШНОГО ТРАНСПОРТА S • 2/6' • • РУКОВОДСТВО ~ •' по летной эксплуатации самолетов Ту-134 (А, Б) Книга вторая АСЦ ГосНШ ный экземапяр РЛЭ самолета _ Директор ВОЗДУШНЫЙ ТРАНСПОРТ МОСКВА 199G АСЦ ГосНИИ ГА экземпляр РЛЭ самолета. Эталонному экземпляру АС ] • -гвет. _—^2——-/— Директор С. 1С : гра, - омский 1?~~~МИНИСТЕРСТВО ТРАНСПОРТА РОССИИ ДЕПАРТАМЕНТ ВОЗДУШНОГО ТРАНСПОРТА АСЦ ГосНИИ ГА Данный экземпляр РЛЭ самолета / *г. /*/?/-? т Эталонному...»

«Зарегистрировано в Минюсте РФ 18 декабря 2009 г. N 15734 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПРИКАЗ от 9 ноября 2009 г. N 546 ОБ УТВЕРЖДЕНИИ И ВВЕДЕНИИ В ДЕЙСТВИЕ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 190100 НАЗЕМНЫЕ ТРАНСПОРТНО-ТЕХНОЛОГИЧЕСКИЕ КОМПЛЕКСЫ (КВАЛИФИКАЦИЯ (СТЕПЕНЬ) БАКАЛАВР) (в ред. Приказов Минобрнауки РФ от 18.05.2011 N 1657, от 31.05.2011 N 1975) КонсультантПлюс: примечание....»

«1 Министерство Защиты Окружающей Среды Израиля Центр Экологических Систем и Технологий (ЭКОСТ) АВТОТРАНСПОРТ И ЭКОЛОГИЯ ГОРОДОВ ИЗРАИЛЯ Пособие для русскоязычных репатриантов При финансовой поддержке Министерства Защиты окружающей среды При поддержке: * Министерства Абсорбции Израиля * Муниципалитета Иерусалима * Управления Абсорбции Муниципалитета Иерусалима * Иерусалимского Общинного Дома Иерусалим, 2012 2 Авторский коллектив: Д-р. Валерий Анфимов- Введение, главы 1-7, 8,10,12-15. M.Sc. Елена...»

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ 24/28/3 Одобрено кафедрой Утверждено деканом Здания и сооружения факультета Транспортные на транспорте сооружения и здания СОДЕРЖАНИЕ И РЕКОНСТРУКЦИЯ ТОННЕЛЕЙ Рабочая программа и задание на курсовой проект с методическими указаниями для студентов VI курса специальности 270201(291100) МОСТЫ И ТРАНСПОРТНЫЕ ТОННЕЛИ (МТ) специализации (291102) ТОННЕЛИ И МЕТРОПОЛИТЕНЫ (МТ.2) Москва – 2006 Программа составлена в соответствии...»

«СВОДНЫЙ ДОКЛАД о результатах мониторинга эффективности деятельности органов местного самоуправления городских округов и муниципальных районов Московской области за 2009 год СОДЕРЖАНИЕ ВВЕДЕНИЕ...................................................................................... 3 РЕЗУЛЬТАТЫ ОЦЕНКИ ЭФФЕКТИВНОСТИ ДЕЯТЕЛЬНОСТИ ОРГАНОВ МЕСТНОГО САМОУПРАВЛЕНИЯ................................»

«База нормативной документации: www.complexdoc.ru ФЕДЕРАЛЬНОЕ ДОРОЖНОЕ АГЕНТСТВО МИНИСТЕРСТВА ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное унитарное предприятие Информационный центр по автомобильным дорогам Нежесткие дорожные покрытия на металлических мостах ОБЗОРНАЯ ИНФОРМАЦИЯ Автомобильные мосты и дороги 4 - 2004 СОДЕРЖАНИЕ 1. ВВЕДЕНИЕ 2. НЕЖЕСТКИЕ ДОРОЖНЫЕ ПОКРЫТИЯ НА МЕТАЛЛИЧЕСКИХ МОСТАХ 2.1. Основные системы металлических мостов 2.2. Проезжая часть мостов 2.3. Дорожные...»

«НЕДВИЖИМОСТЬ. БЛАГОУСТРОЙСТВО СРЕДСТВА ТРАНСПОРТА РАБОТА. ТОВАРЫ. УСЛУГИ Екатеринбург ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ ЧЕТВЕРГ - ВОСКРЕСЕНЬЕ 16+ Информационное издание ООО НПП Сафлор № 46 (2113) 13-16 июня 2013 г. Выходит с 1996 г. 2 раза в неделю по понедельникам и четвергам Газета №2113 от 13.06. СОДЕРЖАНИЕ ГАЗЕТЫ 222 Мобильная связь. 413 Средние и тяжелые грузовики.27 Аренда и прокат автомобилей. НЕДВИЖИМОСТЬ Телефоны и контракты 415 Спецтехника 225 Аксессуары для мобильных 567 Аренда спецтехники...»

«ПОНЕДЕЛЬНИК-ВОСКРЕСЕНЬЕ ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ 16+ Рекламное издание ООО НПП Сафлор № 40 (143) 14-20 октября 2013 г. Выходит с 2010 г. 1 раз в неделю по понедельникам 2563 В э ТО м НОмЕРЕ ОБЪЯВЛЕНИЙ НЕДВИЖИМОСТЬ СРЕДСТВА ТРАНСПОРТА БЛАГОУСТРОЙСТВО Верхнекамье: Березники, Соликамск РАБОТА. УСЛУГИ Газета №143 от 14.10. СОДЕРжАНИЕ ГАЗЕТЫ 248 Ремонт и сервис НЕДВИжИмОСТЬ Аренда и прокат автомобилей 249 Спрос Грузоперевозки, переезды, грузчики. 429 Спрос МЕБЕЛЬ, ИНТЕРЬЕР, КВАРТИРЫ. ПРОДАЖА...»

«НЕДВИЖИМОСТЬ. БЛАГОУСТРОЙСТВО СРЕДСТВА ТРАНСПОРТА РАБОТА. ТОВАРЫ. УСЛУГИ Екатеринбург ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ ЧЕТВЕРГ - ВОСКРЕСЕНЬЕ 16+ Информационное издание ООО НПП Сафлор № 96 (2062) 6-9 декабря 2012 г. Выходит с 1996 г. 2 раза в неделю по понедельникам и четвергам Газета №2062 от 06.12. СОДЕРЖАНИЕ ГАЗЕТЫ 222 Мобильная связь. 413 Средние и тяжелые грузовики.28 Аренда и прокат автомобилей. НЕДВИЖИМОСТЬ Телефоны и контракты 415 Спецтехника 225 Аксессуары для мобильных 567 Аренда...»

«Logistics Processes and Motorways of the Sea II ENPI 2011 / 264 459 Логистические процессы и морские магистрали II Проект мастер-плана LOGMOS – Приложение 9.1 Обзор страны АЗЕРБАЙДЖАН Октябрь 2013 г. Проект осуществляется Проект финансируется Европейским Союзом Egis International / Dornier Consulting Page 1 of XX Inception Report Логистические процессы и морские магистрали II СОДЕРЖАНИЕ ВВЕДЕНИЕ 1 НАЦИОНАЛЬНАЯ ТРАНСПОРТНАЯ ПОЛИТИКА ЗАКОНОДАТЕЛЬНАЯ БАЗА В ОБЛАСТИ ТРАНСПОРТА НАЦИОНАЛЬНАЯ ПОЛИТИКА...»

«РЕДАКЦИОННЫЙ СОВЕТ 1 Ефимов Александр Васильевич — главный редактор, ректор УрГУПС. 2 Сай Василий Михайлович — зам. главного редактора, проОБЩИЕ ВОПРОСЫ ТРАНСПОРТА. ректор по научной работе (УрГУПС). 3 Асадченко Виталий Романович — зам. главного редактора, С.А. Румянцев, Е.Б. Азаров / МАТЕМАТИЧЕСКАЯ д.т.н., профессор (УрГУПС). МОДЕЛЬ НЕСТАЦИОНАРНОЙ ДИНАМИКИ СИСТЕМЫ 4 Силуков Юрий Дмитриевич — д.т.н., профессор (УГЛТУ). ВИБРОМАШИНА — ЭЛЕКТРОПРИВОД В СЛУЧАЕ ПРИВОДА 5 Багин Юрий Иванович — д.т.н.,...»

«Глава IV ТРАНСПОРТ И ПУТИ СООБЩЕНИЯ 1 1. Ж Е Л Е З Н О Д О Р О Ж Н Ы Й Т Р А Н С П О Р Т Как указано было ранее (гл. II, разд. 4), железные дороги не страховали своего имущества от огня. Правда, статистика акционерного страхования имеет в разделе экстерриториального имущества (т. е. не приуроченного к определенной губернии) рубрику железнодорожные, но ничтожный размер общей суммы (всего 288 млн. руб. на 1/1 1914 г. по всем видам имущества) и соотношение ее структурных частей убеждают нас в том,...»

«НЕДВИЖИМОСТЬ. БЛАГОУСТРОЙСТВО СРЕДСТВА ТРАНСПОРТА РАБОТА. ТОВАРЫ. УСЛУГИ Екатеринбург ГАЗЕТА ЧАСТНЫХ ОБЪЯВЛЕНИЙ ПОНЕДЕЛЬНИК - СРЕДА 16+ Информационное издание ООО НПП Сафлор № 45 (2112) 10-12 июня 2013 г. Выходит с 1996 г. 2 раза в неделю по понедельникам и четвергам Газета №2112 от 10.06. СОДЕРЖАНИЕ ГАЗЕТЫ 222 Мобильная связь. 413 Средние и тяжелые грузовики.26 Аренда и прокат автомобилей. НЕДВИЖИМОСТЬ Телефоны и контракты 415 Спецтехника 225 Аксессуары для мобильных 567 Аренда спецтехники и...»





Загрузка...



 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.