Модели линейной оптимизации на примерах задач об ассортименте продукции

Любая экономико-математическая модель лишь упрощенно, грубо отображает реальный экономический процесс, и это упрощение существенно сказывается на получаемых результатах. Исследователя вряд ли устроила бы заключительная симплекс-таблица, из которой можно было бы получить только список переменных и их значения. На самом же деле результирующая симплекс-таблица «насыщена» весьма важными данными, лишь небольшую часть которых составляют оптимальные значения переменных. Из симплекс-таблицы можно получить информацию относительно:
оптимального решения;
статуса ресурсов;
ценности каждого ресурса;
чувствительности оптимального решения к изменению запасов ресурсов, вариациям коэффициентов целевой функции и интенсивности потребления ресурсов.
Сведения, относящиеся к первым трем пунктам, можно извлечь непосредственно из итоговой симплекс-таблицы. Получение информации, относящейся к четвертому пункту, требует дополнительных вычислений.
Для иллюстрации возможностей получения указанной выше информации из заключительной симплекс-таблицы воспользуемся опять задачей об ассортименте продукции (пример 7.2). Эта задача формулируется следующим образом:
максимизировать: Z = 3xj + 4x2
при следующих ограничениях: 2хх + Зх2 ^ 9
3*1 + 2Х2 < 13 Xj — х2 ^ 1 — 2
(доход); (сырье А), (сырье В), (спрос), (спрос).
Оптимальная симплекс-таблица имеет вид (табл. 7.18):
Таблица 7.18 Свободные неизвестные
Базисные неизвестные Свободный член У\ Уз 2,4 0,2 0,6 У2 3 -1 -1 У4 0,6 -0,2 0,4 1,4 0,2 -0,4 7
^т ах 12,8 1,4 0,2
В таблице ypj = 1,4 — выравнивающие переменные.
Оптимальное решение. С точки зрения практического использования результатов решения задач линейного программирования классификация переменных на базисные и небазисные не имеет значения и при анализе оптимального решения может не учитываться. Переменные, отсутствующие в симплекс-таблице в столбце «базисные переменные», обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце «свободные члены».
При интерпретации результатов оптимизации в задаче об ассортименте продукции нас прежде всего интересуют объемы про-изводства продукции Пх и Я2, т. е. значения управляемых переменных хх и х2. Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно представить в следующем виде (табл. 7.19):
Управляемые Оптимальные Решение переменные значения 2,4 Объем производства продук ции Пі должен быть равен 2,4 ед. в сутки *2 1,4 Объем производства продук ции #2 должен быть равен 1,4 ед. в сутки 7
^тах 12,8 Доход от реализации продук ции будет равен 12,8 д. е. в сутки
Статус ресурсов. В подразд. 7.4 ресурсы относились либо к дефицитным, либо к недефицитным — в зависимости от того, полное или частичное их использование предусматривает оптимальное решение задачи. Сейчас цель состоит в том, чтобы получить соответствующую информацию непосредственно из оптимальной таблицы.
В модели, построенной для задачи об ассортименте продукции, фигурируют четыре ограничения со знаком «<». Первые два ограничения (определяющие допустимый расход исходного сырья) представляют собой истинные ограничения на ресурсы. Третье и четвертое ограничения относятся к спросу. Эти требования можно рассматривать как ограничения на соответствующие ресурсы, так как увеличение спроса на продукцию эквивалентно расширению представительства предприятия на рынке сбыта. В отношении финансовых средств такая ситуация имеет те же последствия, что и увеличение запасов ресурсов, требующее распределения дополнительных вложений.
Из вышеизложенного следует, что статус ресурсов (дефицитный или недефицитный) для любой модели линейного программирования можно установить непосредственно из результирующей симплекс-таблицы, обращая внимание на значения выравнивающих переменных. Применительно к нашей задаче можно привести следу-ющую сводную таблицу (табл. 7.20).
Положительное значение выравнивающей переменной указывает на неполное использование соответствующего ресурса, т. е. данный ресурс является недефицитным. Если же выравнивающая переменная равна 0, то это свидетельствует о полном потреблении соответствующего ресурса. Из сводной табл. 7.20 видно, что ресурсы 2 и 4 связаны с запасами сырья В и возможностями сбыта про-дукции Я2. Поэтому любое увеличение их запасов сверх установ- Ресурс Выравнивающая переменная Статус ресурса Сырье А Уі = 0 Дефицитный Сырье В ^2 = 3 Недефицитный Превышение объема производ Уз — 0 Дефицитный ства продукции Пх по отноше нию к объему производства продукции Пг Спрос на продукцию Пг У4 = 0,6 Недефицитный

ленного максимального значения приведет лишь к тому, что они станут еще более недефицитными. Оптимальное решение задачи при этом останется неизменным.
Ресурсы, увеличение запасов которых позволяет улучшить решение (увеличить доход), — это сырье А и возможности по сбыту продукции Пь поскольку из оптимальной симплекс-таблицы (табл. 7.18) видно, что они дефицитные. В связи с этим логично поставить вопрос: какому из дефицитных ресурсов следует отдать предпочтение при вложении дополнительных средств на увеличение их запасов, с тем чтобы получить от них максимальную отдачу? Ответ на этот вопрос будет дан в следующем разделе этой главы, где рассматривается ценность различных ресурсов.
Ценность ресурса. Ценность ресурса характеризуется величиной улучшения оптимального значения Z, приходящегося на единицу прироста объема данного ресурса. Графическая интерпретация этого определения применительно к условиям задачи об ассортименте продукции была дана в подразд. 7.4 (вторая задача на чувствительность). Графический анализ показывает, что ценность ресурсов 1, 2, 3 и 4 равна:
U\ = 1,4 д. е. на единицу прироста запасов ресурса сырья А; и2 = о, U4 = 0;
Щ = 0,2 д. е. на единицу прироста превышения производства продукции П\ по отношению к объему производства продукции П2.
Эта информация представлена в оптимальной таблице (табл. 7.18). Обратим внимание на значения коэффициентов Z-уравне- ния, стоящих при переменных начального базиса уь у2, у$ и у4. Значения указанных коэффициентов (1,4; 0; 0,2; 0) в точности соответствуют значениям Ux\ U2\ Щ.
Хотя в подразд. 7.4 были даны необходимые разъяснения, связанные с определением ценности ресурсов, покажем, каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы.
Рассмотрим Z-уравнение оптимальной симплекс-таблицы решения задачи об ассортименте продукции:
Z = 12,8 - (1,4 ¦ у{ + 0 • у2 + 0,2 • уъ + 0 ¦ у4).
Положительное приращение переменной у{ относительно ее текущего нулевого значения приводит к пропорциональному уменьшению Z, причем коэффициент пропорциональности равен 1,4 д. е. Однако из первого ограничения модели следует
2*1 + Зх2 +,i=9,
т. е. увеличение Уі эквивалентно снижению запаса ресурса 1 (сырья Л). Отсюда следует, что уменьшение запаса первого ресурса вызывает пропорциональное уменьшение целевой функции Zc коэффициентом пропорциональности, равным 1,4 д. е. Аналогичные рассуждения справедливы и для ресурса 3.
В отношении ресурсов 2 и 4 было установлено, что их ценность равна 0 (U2 = U4 = 0). Этого и следовало ожидать, так как ресурсы 2 и 4 оказались недефицитными. Такой результат получается всякий раз, когда соответствующие выравнивающие переменные имеют положительное значение.
Несмотря на то что ценность различных ресурсов, определяемая значениями переменных Uh была представлена в стоимостном (д. е.) выражении, ее нельзя отождествлять с действительными ценами, по которым возможна закупка соответствующих ресурсов. На самом деле речь идет о некоторой мере, имеющей экономическую природу и количественно характеризующей ценность ресурса только относительно полученного оптимального значения Z. При изменении ограничений модели соответствующие экономические оценки будут меняться даже тогда, когда оптимизируемый процесс предполагает применение тех же ресурсов. Поэтому при характеристике ценности ресурсов экономисты предпочитают использовать такие* термины, как теневая цена или двойственная оценка. Заметим, что теневая цена характеризует интенсивность улучшения оптимального решения Z. Однако при этом не фиксируется интервал значений увеличения запасов ресурсов, при которых интенсивность улучшения целевой функции остается постоянной. Для большинства практических ситуаций логично предположить наличие верхнего предела увеличения запасов, при превышении которого соответствующее ограничение становится избыточным, что в свою очередь приводит к новому ба- зисному решению и соответствующим ему новым теневым ценам. Ниже определяется интервал значений запасов ресурса, при которых соответствующее ограничение не становится избыточным.

Максимальное изменение запаса ресурса. При решении вопроса о том, запас какого из ресурсов следует увеличивать в первую очередь, обычно используются двойственные оценки (теневые цены). Чтобы определить интервал значений изменения запаса ресурса, при которых двойственная оценка данного ресурса, фигурирующая в за-ключительной симплекс-таблице, остается неизменной, необходимо выполнить ряд дополнительных вычислений. Положим, что в задаче об ассортименте продукции запас первого ресурса (сырья А) изменился на Aj, т. е. запас сырья А составит (9 + Aj) единиц. Введем это изменение в начальную симплекс-таблицу и затем выполним всю последовательность вычислений.
Поскольку элементы правых частей ограничений никогда не используются в качестве разрешающих, то очевидно, что на каждой итерации вычислений Aj будет оказывать влияние только на значения элементов столбца «свободные члены».
Результаты вычислений элементов столбца «свободные члены» сведены в табл. 7.21:
Таблица 7.21 Уравнение Значения элементов столбца «свободные члены» Начальная симплекс-таблица Оптимальная симплекс-таблица Z 0 12,8 + 1,4 • А, 1 9 + А, 2,4 + 0,2 • А, 2 13 3 - 1 • А, 3 1 0,6 - 0,2 • А, 4 2 1,4 + 0,2 • А,
Все изменения элементов столбца «свободные члены» определяются непосредственно по данным, содержащимся в симплекс- таблицах. Каждый элемент столбца «свободные члены» представляет собой сумму двух величин:
постоянной;
члена, линейно зависящего от Aj.
Постоянные соответствуют числам, которые фигурируют в оптимальной симплекс-таблице до введения Aj в столбце «свободные члены». Коэффициенты при Aj во вторых слагаемых равны коэффициентам при у{ в оптимальной симплекс-таблице.
Заметим, что при анализе изменений в правых частях второго, третьего и четвертого ограничений нужно пользоваться коэффици-ентами при переменных у2, Уз, У4 соответственно.
Так как введение Aj сказывается лишь на правой части ограничений (на элементах столбца «свободные члены»), изменение запаса ресурса может повлиять только на допустимость решения. Поэтому Aj не может принимать значений, при которых какая-либо из базисных переменных становится отрицательной. Из этого следует, что величина А{ должна быть ограничена таким интервалом значений, при котором выполняется условие неотрицательности правых частей ограничений в результирующей симплекс-таблице, т. е.:
х{ = 2,4 + 0,2 • Aj > 0; у2 = 3 - 1 • А! > 0;
у4 = 0,6 - 0,2 • А! > 0; х2 = 1,4 + 0,2 • А1 > 0.
Для определения допустимого интервала изменения А{ рассмотрим два случая.
Случай 7: А1 > 0.
Соотношения (7.51) и (7.54) всегда выполняются при Aj > 0. Соотношения (7.52) и (7.53) определяют следующие предельные значения Aj < 3; А{ < 3. Таким образом, все четыре соотношения выполняются при Aj < 3.
Случай 2: А{ < 0.
Соотношения (7.52) и (7.53) выполняются при А{ < 0. Соотношения (7.51) и (7.54) справедливы при А{ > — 12; А{ > —1 соответственно.
Таким образом, оба соотношения справедливы при А{ > —7.
Объединяя результаты, полученные для обоих случаев, можно сделать вывод, что при —7 < А{ < 3 решение рассматриваемой системы всегда будет допустимым. Любое значение А1? выходящее за предел указанного интервала (т.е. уменьшение запаса сырья А бо-лее чем на 7 единиц или увеличение более чем на 3 единицы), приведет к недопустимости решения и новой совокупности базисных переменных.
Анализ на чувствительность оптимального решения к вариации коэффициентов целевой функции. В подразд. 7.4 на основе графического представления модели было показано, что при определенных значениях изменения коэффициентов целевой функции оптимальные значения переменных остаются неизменными (хотя оптимальное значение Z при этом меняется). Возвращаясь к этому вопросу, покажем, каким образом интересующую нас информацию можно
получить из данных, содержащихся в оптимальной симплекс-таблице.
Следует отметить, что уравнение целевой функции также не используется в качестве ведущего уравнения. Поэтому любые изменения коэффициентов целевой функции окажут влияние только на Z-уравнение результирующей симплекс-таблицы. Это означает, что такие изменения могут сделать полученное решение неоптимальным. Наша цель заключается в том, чтобы найти интервалы изменений коэффициентов целевой функции, при которых оптимальные значения переменных остаются неизменными.
Чтобы показать, как выполняются соответствующие вычисления, положим, что доход, получаемый с единицы продукции Пь изменяется от 3 до 3 + 5j, где 8{ может быть как положительным, так и отрицательным числом. Целевая функция в этом случае принимает следующий вид:
^тах = (3 + 81)Х{ + 4Х2.
Если воспользоваться данными начальной симплекс-таблицы и выполнить все вычисления, необходимые для получения оптимальной симплекс-таблицы, то последнее Zmax-ypaBHeHHe будет выглядеть следующим образом: Свободные переменные Свободные члены У\ Уі 7 12,8 + 2,4 Ъх 1,4 + 0,2 8, 0,2 + 0,6 8,
Это уравнение (строка целевой функции) отличается от Z-уравнения до введения Sj только наличием членов, содержащих 6j. Коэффициенты при 5j равны коэффициентам при соответствующих переменных в jcj-уравнении (х{-строка) симплекс-таблицы для полученного ранее оптимального решения: Свободные ^^переменные Базисные^Х^ переменные ^v. Свободные члены У\ Уз 2,4 0,2 0,6
Мы рассматриваем х{-уравнение, так как коэффициент именно при этой переменной в выражении для целевой функции в начальной симплекс-таблице изменился на Sj.
Оптимальные значения переменных будут оставаться неизменными при значениях 5j, удовлетворяющих условию неотрицательности (задача на отыскание максимума) всех коэффициентов при свободных переменных в Z-уравнении. Таким образом, должны выполняться следующие неравенства:
1,4 + 0,2 5j > 0; 0,2 + 0,6 5! > 0.
Из первого неравенства получаем, что 8Х > -7, а из второго следует, что 8i>-j. Эти результаты определяют пределы изменения
коэффициента -j<8j<+°o.
/
/ «\
Таким образом, при уменьшении коэффициента целевой функ-
= 2—, или 3
3 +
ции при переменной Хі до значения, равного
'JJ
при его увеличении до +°о оптимальные значения переменных остаются неизменными. Этот вывод совпадает с результатом, полу-ченным в подразд. 7.4.
Следует отметить, что оптимальное значение Z будет изменяться в соответствии с выражением (12,8 + 2,4 где <+°°-
Мы рассмотрели случай изменения коэффициента при базис-ной переменной хх. В случае изменения коэффициента при свободной переменной в целевой функции происходит изменение коэффициента только при данной переменной в оптимальной симплекс-таблице. Рассмотрим в качестве иллюстрации случай, когда коэффициент при свободной переменной у{ (первая выравнивающая переменная) изменяется от 0 до 52. Выполнение преобразований, необходимых для получения заключительной симплекс-таблицы, приводит к следующему результирующему Z-уравнению: Свободные переменные Свободные члены У\ Уг z
^тах 12,8 1,4 - 52 0,2
Из приведенного фрагмента заключительной симплекс-таблицы видно, что единственное отличие от Z-уравнения до введения
S2 состоит в том, что коэффициент при уз уменьшился на 82. Таким образом, коэффициент при свободной переменной в результирую-щем Z-уравнении нужно уменьшить на ту же величину, на которую он увеличивался в исходном Z-уравнении.

22. Нелинейные системы: хаос и странные аттракторы.

Основная статья: Динамический хаос

Пример чувствительности системы к первоначальным условиям,где x → 4 × (1 – x) и y → x + y,если x + y < 1 (иначе x + y – 1). Здесь четко видно, что ряды значений x и y через какое-то время заметно отклоняются друг от друга хотя в первоначальных состояниях отличия микроскопические

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

1. она должна быть чувствительна к начальным условиям

2. она должна иметь свойство топологического смешивания

3. её периодические орбиты должны быть всюду плотными.

Более точные математические условия возникновения хаоса выглядят так:

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

Линейные системы никогда не бывают хаотическими. Для того, чтобы динамическая система была хаотической, она должна быть нелинейной. По теореме Пуанкаре-Бендиксона (Poincaré-Bendixson), непрерывная динамическая система на плоскости не может быть хаотической. Среди непрерывных систем хаотическое поведение имеют только неплоские пространственные системы (обязательно наличие не менее трёх измерений или неевклидова геометрия). Однако дискретная динамическая система на какой-то стадии может проявить хаотическое поведение даже в одномерном или двумерном пространстве.

Чувствительность к начальным условиям [править | править исходный текст]

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

Чувствительность к начальным условиям более известна как «Эффект бабочки». Термин возник в связи со статьёй «Предсказание: Взмах крыльев бабочки в Бразилии вызовет торнадо в штате Техас», которую Эдвард Лоренц в 1972 году вручил американской «Ассоциации для продвижения науки» в Вашингтоне. Взмах крыльев бабочки символизирует мелкие изменения в первоначальном состоянии системы, которые вызывают цепочку событий, ведущих к крупномасштабным изменениям. Если бы бабочка не хлопала крыльями, то траектория системы была бы совсем другой, что в принципе доказывает определённую линейность системы. Но мелкие изменения в первоначальном состоянии системы могут и не вызывать цепочку событий.

Топологическое смешивание [править | править исходный текст]

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

Тонкости определения [править | править исходный текст]

Пример топологического смешивания,где x → 4 × (1 – x) и y → x + y,если x + y < 1 (иначе x + y – 1). Здесь синий регион в процессе развития был преобразован сначала в фиолетовый, потом в розовый и красный регионы и в конечном итоге выглядит как облако точек, разбросанных поперек пространства

В популярных работах чувствительность к первоначальным условиям часто путается с самим хаосом. Грань очень тонкая, поскольку зависит от выбора показателей измерения и определения расстояний в конкретной стадии системы. Например, рассмотрим простую динамическую систему, которая неоднократно удваивает первоначальные значения. Такая система имеет чувствительную зависимость от первоначальных условий везде, так как любые две соседние точки в первоначальной стадии впоследствии случайным образом будут на значительном расстоянии друг от друга. Однако её поведение тривиально, поскольку все точки кроме нуля имеют тенденцию к бесконечности, и это не топологическое смешивание. В определении хаоса внимание обычно ограничивается только закрытыми системами, в которых расширение и чувствительность к первоначальным условиям объединяются со смешиванием.

Даже для закрытых систем, чувствительность к первоначальным условиям не идентична с хаосом в смысле изложенном выше. Например, рассмотрим тор (геометрическая фигура, поверхность вращения окружности вокруг оси лежащей в плоскости этой окружности — имеет форму бублика), заданный парой углов (x, y) со значениями от нуля до 2π. Отображение любой точки (x, y) определяется как (2x, y+a), где значение a/2π является иррациональным. Удвоение первой координаты в отображении указывает на чувствительность к первоначальным условиям. Однако, из-за иррационального изменения во второй координате, нет никакихпериодических орбит — следовательно отображение не является хаотическим согласно вышеупомянутому определению.

Аттракторы[править | править исходный текст]

График аттрактора Лоренца для значений r = 28, σ = 10, b = 8/3

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

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

Странные аттракторы[править | править исходный текст]

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

Большинство типов движения описывается простыми аттракторами, являющиеся ограниченными циклами. Хаотическое движение описывается странными аттракторами, которые очень сложны и имеют много параметров. Например, простая трехмерная система погоды описывается известным аттрактором Лоренца (Lorenz) — одной из самых известных диаграмм хаотических систем, не только потому, что она была одной из первых, но и потому, что она одна из самых сложных. Другим таким аттрактором является — отображение Рёслера (Rössler), которая имеет двойной период, подобно логистическому отображению. Странные аттракторы появляются в обеих системах, и в непрерывных динамических (типа системы Лоренца) и в некоторых дискретных (например отображения Хенона (Hénon)). Некоторые дискретные динамические системы названы системами Жулиа по происхождению. И странные аттракторы и системы Жулиа имеют типичную рекурсивную, фрактальную структуру. Теорема Пуанкаре-Бендиксона доказывает, что странный аттрактор может возникнуть в непрерывной динамической системе, только если она имеет три или больше измерений. Однако это ограничение не работает для дискретных динамических систем. Дискретные двух- и даже одномерные системы могут иметь странные аттракторы. Движение трёх или большего количества тел, испытывающих гравитационное притяжение при некоторых начальных условиях может оказаться хаотическим движением.