Дельно от модели ЛП а затем вычесть их из величины прибыли

3 дельно от модели ЛП а затем вычесть их из величины прибыли.

4) Произвести параметрическое изменение мощностей и повторить шаги, начиная с шага 1.

Целевая функция будет выражаться в тыс. долл/рабочий день, так что если Xi выражается в единицах MBSD, то стоимость Ci должна выражаться в долл/баррель.

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

ПОСТРОЕНИЕ МАТРИЦЫ БОЛЬШОГО РАЗМЕРА

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

Уравнения из нашего примера поясняют как составляются таблицы. С помощью этих уравнений детально описаны сырьевые потоки, входящие в блок газового насыщения, и потоки продуктов, выходящие из него. Входам сырьевых потоков BOLNP и COLNP отвечают два столбца LNB и LNC на это указывают коэффициенты +1. 0 в соответствующих этим потокам баласовых строках, отрицательные коэффициенты в балансовых строках потока продкта представляют выход этого продукта на единицу сырья, поступающего в блок. Можно составить таблицу, описывающую весь блок газового насыщеия, добавив столбцы, которые представляют входы в этот блок сырьевых потоков 90BBG, 9BBG, HYDBBG.

При составлении таблиц, описывающих блоки предприятия, мы будем руководствоваться следующими правилами:

1) Определить столбец j для каждого сырьевого потока, входящего в блок (тогда Xj - количество j-го сырья). Выполнить шаги 2 - 6 для каждого такого столбца.

2) Записать коэффициент равный +1. 0 в балансовую строку, отвечающую входящему сырьевому потоку.

3) Для каждого продукта, произведенного в блоке из этого сырьевого потока, записать коэффициент -Aij в соответствующую балансовую строку потока продукта, где Aij - количество продукта i, полученного из единицы сырья j.

4) Если для блока существует ограничение по мощности определяемое количеством сырья, записать коэффициент +1. 0 в строку ограничения по мощности. Компонента вектора ограничений, соответствующая этой строке, равна предельному значению суммарного сырьевого па.

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

6) Каждой единице сырья j приписать коэффициент затрат Cj в строке целевой функции.

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

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

1) Определить столбец j для каждого сырьевого потока, поступающего в смеситель (Xj - количество j-го сырья). Выполнить шаги 2 - 6 для каждого такого столбца.

2) Записать коэффициент равный +1. 0 в балансовую строку, отвечающую входящему сырьевому потоку.

3) Записать соответствующий коэффициент -1. 0 в балансовую строку для конечного продукта (например EVOLPROD).

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

5) В строку, соответствующую ограничению сверху на какое-то свойство смеси записать коэффициент +Pi.

6) Выполнив шаги 2 - 5 для всех сырьевых потоков j, определить столбец для конечного продукта (смеси), (например B, тогда Xb количество конечного продукта). В этот столбец записать следующие коэффициенты:

а) в балансовую строку (EVOLPROD) этого конечного продукта записать +1. 0,

б) в строку, отвечающую ограничению снизу на какое-то свойство конечного продукта, записать коэффициент равный +Pb,

в) в строку, отвечающую ограничению сверху на какое-то свойство конечного продукта, записать коэффициент -Pb,

г) если есть ограничения на потребление конечного продукта, записать +1. 0 в соответствующую строку, отвечающую этому ограничению (либо учесть его просто как ограничение на переменную Xb),

д) ввести в строку целевой функции коэффициент стоимости конечного продукта Cb.

Классификация экономико-математических моделей

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

Классификацию задач оптимизации, возникающих на производстве, выполним по следующим признакам: 1. Область применения 2. Содержание задачи 3. Класс математической модели 1. Обеспечение производства включает в себя : 1. 1 Организацию и управление 1. 2 Проектирование изделий 1. 3 Разработку технологических процессов

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

Объект проектирования устройством и действием. Устройство определяется структурой и параметрами. Действие характеризуется процессом функционирования. При решении этих трех вопросов возникают задачи: 1. 2. а Оптимизация параметров объекта проектирования. 1. 2. б Оптимизация структуры объекта проектирования. 1. 2. в Оптимизация функционирования

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

Важным признаком классификации является класс математической модели. Проведем классификацию по элментам математической модели: 1 Исходным данным 2 Искомым переменным 3 Зависимостям, описывающим ограничения и целевую функцию

1. 1 Исходные данные, которые заданы определенными величинами называют детерминированными 1. 2 Исходные данные, которые зависят от случайных факторов, например от своевременности поставки ресурсов, исправности оборудования и. т. д. называют случайными величинами.

2. 1 Переменные могут быть непрерывными и дискретными. Непрерывными называют такие величины, которые в заданном интервале могут принимать любые значения. Так масса добываемого угля или объем выпуска ткани представляют собой непрерывные величины. 2. 2 Дискретными называют такитолько целые значения. Так например нельзя выпустить 0. 7 тепловоза или сдать строительный объект из 1. 45 здания.

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

Сочетание различных элементов модели приводит к различным классам задач оптимизации. Различные классы задач требуют разных методов решения а сле

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

Математическое моделирование в управлении и планировании

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

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

РУКОВОДСТВО ПРЕДПРИЯТИЕМ

Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими ресурсами располагает, но общие запасы ресурсов ограничены. Поэтому возникает важная задача: выбор оптимального варианта, обеспечивающего достижение цели с минимальными затратами ресурсов. Таким образом эффективное руководство производством подразумевает такую организацию процесса, при которой не только достигается цель, но и получается экстремальное (MIN, MAX) значение некоторого критерия эффективности: К = F(X1, X2, . . . , Xn) => MIN(MAX) Функция К является математическим выражением результата действия, направленного на достижение поставленной цели, и поэтому ее называют целевой функцией.

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

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

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

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

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

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

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

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

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

2) Другая задача состоит в тщательном, количественном изучении систем определенного класса. При этом необходимо дать подробное математическое описание объектов интересующего класса и столь же подробное математическое описание происходящих в них процессов.

3) Наконец третий подход с которым часто приходится сталкиваться связан со стремлением использовать для анализа какие-то конкретные виды математических моделей.

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

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

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

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

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

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

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

При заданных ограничениях B1. . . Вn найти такие элементы управления X1. . . Xm которые с учетом случайных воздействий Q1. . . Qr по возможности обеспечивают максимальное значение критерия эффективности К max(min). Теперь нет уверенности в том, что можно будет получить решение, а если оно будет получено то нет гарантии в том, что оно будет правильным. Именно поэтому в формулировке задачи приходится делать оговорку "по возможности". Таким образом при решении проблем возникющих в реальной жизни математическая теория и научно обоснованные методы не дают точного решения. Причина этого в том, что когда нет точных данных, то есть нет полной информации остается лишь предполагать и строить догадки но нельзя считать что все предсказания сбудутся. И все таки решение, принятоматематических расчетов будет лучше чем взятое наугад. Задача состоит в том, чтобы это решение в возможно большей степени содержало черты разумности, именно в этом смысле следует понимать определение " по возможности оптимальное". Сложность математического моделирования в условиях неопределенности зависит от того какова природа неизвестных факторов. По этому признаку задачи делятся на два класса.

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

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

Вот пример стохастической задачи:

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

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

Двойственные оценки, экономическая интерпретация и свойства

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

1. Максимум прибыли.

2. Минимум себестоимости.

3. Максимум выпуска продукции в заданном ассортиментном соотношении.

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

$ 1 Оценки ресурсов - экономическая интерпретация

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

E Aij*Xj + Xs = Bi

Так как Xs вне базиса равна нулю исходное ограничение

E Aij*Xj <= Bi можно рассматривать как равенство в точке оптимума, т. е. E Aij*Xj = Bi

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

_

E Aij*Xj = Bi + 1

или после перестановки _

E Aij*Xj +(-1) = Bi

то есть дополнительная переменная Xs должна принять значение равное -1 чтобы i-ое ограничение оставалось равенством а относительная оценка даст соответствующее приращение целевой функции. Таким образом относительная оценка i-ой дополнительной переменной дает величину прироста целевой функции на единицу увеличения элемента Bi вектора ограничений. Так как элемент Bi обычно представляет собой объем i-го ресурса то относительная оценка равная Yi называется оценкой ресурса (оценкой единицы i-го ресурса) ибо она представляет относительную ценность единицы дополнительного ресурса. Эти относительые оценки являются маргинальными оценками в том смысле что они действительны лишь при таком диапазоне изменения ресурсов Bi когда текущий базис остается оптимальным. в) Если дополнительная переменная является базисной в точке оптимума то ее относительная оценка по определению равна нулю. Это также имеет смысл так как если ресурс использован не полностью

_
E Aij*Xj < Bi то цена которую мы должны были бы заплатить за дополнительную единицу этого ресурса равна нулю. Это приводит к условию дополняющей нежесткости:

В оптимальном решении или E Aij*Xj = Bi или Yi = 0 (либо и то и другое)

или E Aij*Yi = Cj или Xj = 0 (либо и то и другое)

Заметим что переменные Y недопустимы на протяжении всех итераций симплекс-метода до тех пор пока не будет достигнуто оптимальное решение.

МАРГИНАЛЬНЫЕ ОЦЕНКИ

Оценки ресурсов связаны скорее с ограничениями а не с переменными.

Однако они часто используются для вычисления оценочных или стоимостных показателей, связанных с переменными прямой задачи. Рассмотрим пример. Пусть в задаче связанной с суточной переработкой нефти некоторая переменная Xj соответствует объему неочищенной нефт закупаемой по цене 12. 65 долл/баррель (Сj = -12. 65) Существует ограничение сверху на объем закупаемой по этой цене неочищенной нефти равный 50 тыс. баррель/день.

Это можно записать уравнением: Xj + Xs = 50

Где Xs - это дополнительная переменная. Пусть она имеет относительную оценку равную 1. 04 долл/баррель в оптимальном решении - что это означает ? Оценка ресурса неочищенной неочищенной нефти равна 1. 04 долл/баррель, но это вовсе не означает, что мы должны были заплатить только 1. 04 долл за каждый дополнительный баррель неочищенной нефти. Это означает что мы должны быть готовы заплатить еще по 1. 04 долл/баррель за возможность покупать дополнительный объем этой нефти при условии, что последующие закупки будут осуществляться по цене 12. 65 долл/баррель: то есть целевая функция будет увеличиваться на 1. 04 долл за каждый дополнительный баррель, который мы сможем купить по цене Сj уже учтенной в целевой функции. Это означает, что м должны быть готовы к повышению цены до 12. 65 + 1. 04 = 13. 69 долл/баррель за дополнительную поставку неочищенной нефти.

Заметим, что 13. 69 долл/баррель - это равновесная цена при которой мы будем увеличивать нашу целевую функцию Р, если будем покупать по более дешевой цене чем эта: будем уменьшать Р если будем покупать за большую цену: сохраним Р неизменной если будем покупать точно за 13. 69 долл/баррель.

Если мы определим что МАРГИНАЛЬНАЯ ОЦЕНКА = РАВНОВЕСНАЯ ЦЕНА

ДЕЙСТВИТЕЛЬНАЯ ЦЕНА, то в нашем примере МАРГИНАЛЬНАЯ ОЦЕНКА = 13. 69 - 12. 65 = 1. 04 долл/баррель.

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

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

Маргинальная оценка остается постоянной только внутри некоторой окрестности существующего оптимума, соответствующей пределам, внутри

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

Так как компоненты вектора Aj (где j - номер небазисной переменной)

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

то их часто называют (маргинальными) нормами замещения, так что Aij

- это норма замещения способа производства i на способ

производства j.

ДИАПАЗОНЫ УСТОЙЧИВОСТИ

Часто говорят, что постоптимальный анализ - наиболее важная часть линейного программирования и нетрудно понять почему делается такой вывод. Большая часть параметров задачи ЛП точно не известна и на практике обычно берутся приближенные значения, которым должны быть равны эти параметры. Таким образом нас интересуют такие диапазоны изменения этих параметров, в которых оптимальное решение остается оптимальным в том смысле, что не меняется базис. Исследуем три класса параметров:

коэффициенты целевой функции Cj

компоненты вектора ограничений Bi

коэффициенты матрицы Aij

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

а) Небазисная переменая

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

Cj = Cj + q отсюда Dj = Dj - q

Например пусть матрицей А задан производственный процесс и пусть переменная Xj представляет количество некоторого производимого продукта, который может быть продан по цене Cj = 20 долл/ед В оптимальном решении эта переменная небазисная (=0) и ее относительная оценка = 1. 40 долл/ед Таким образом если цен возрастет до 21. 40 долл/ед продукта то относительная оценка станет = 0 и дальнейшее увеличение цены приведет к отрицательной относительной оценке. Это означает что текущее решение перестает быть оптимальным. В таком случае выгодно производить продукт представленный переменной Xj Следовательно 21. 40 долл/ед продукта это равновесная цена для Xj , при любой более низкой цене оптимальное решение будет состоять в том чтобы совсем не производить этот продукт ( Xj остается небазисным) а при более высокой цене выгодно ввести Xj в базис. Для небазисной переменной диапазон устойчивости в котором Cj может меняться так чтобы текущее решение оставалось оптимальным задается выражением _

Cj + q, где -оо < q <= Dj

и где Dj - относительная оценка переменной Xj отвечающая оптимальному решению. Заметим что при любом отрицательном q относительная оценка этой переменной останется положительной. Многие ППП ЛП дают информацию и о диапазоне изменения переменной Xj (от нулевого до некоторого предельного_значения) при котором не происходит смены базиса. Если q = Dj то относительная оценка = 0 что означает что Xj можно увеличивать не меняя значения целевой функции. Предельное значение до которого можно увеличивать Xj определяется формулой MIN (B/Aj)i Например предположим что в оптимальном решении вектор базисных переменных, -1 -1 текущий вектор ограничений B=B * b и вектор Aj=B *aj заданы в виде:

X5 3. 2 0. 6

Xb = X1 B = 1. 5 Aj = 0. 3

X6 5. 6 -1. 2

Тогда получаем MIN (Bi/Aij) = 1. 5/0. 3 = 5. 0

Таким образом мы можем сделать вывод о том что при цене в 21. 40 долл/ед продукта или более становится выгодным производить продукт Xj то есть продукт которому отвечает переменная Xj ; на каждую единицу произведенного продукта Xj переменные X5 X1 X6 уменьшаются соответственно на 0. 6 0. 3 -1. 2 единиц. Если мы произведем 5. 0 ед продукта Xj то переменная X1 обратится в нуль и дальнейшее увеличение Xj потребует смены базиса. Заметим, что мы получили всю информацию не решая задачу заново, для продолжения анализа нам потребуется лишь выполнить операцию исключения соответствующую изменению базиса.

б) Базисная переменная

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

_

Cb = Cb + q*Ei, где Ei - вектор специального вида i-ая компонента которого = 1 а остальные нулю. Например

E3 = 0

Относительная оценка j-ой небазисной переменной станет теперь равной

Dj = Dj + q*Aij

Для того чтобы решение оставалось оптимальным должно выполняться условие

Dj => 0 то есть Dj^ + q*Aij => 0, где Dj^ - относительная оценка соответствующая текущему оптимальному решению.

Для базисной переменной диапазон устойчивости в котором может изменяться Ci оставляя оптимальным текущее решение адается выражением Ci + q, где

MAX {Dj^/-Aij} <= q <= MIN {Dj^/-Aij}

i/Aij>0 i/Aij<0

Если отсутствуют коэффициенты Aij < 0 то q < +oo и аналогично если нет Aij > 0 то q > -oo

Например пусть оптимальное решение задано следующим образом:

Максимизировать Р= 31. 5 -3. 5X4 -0. 1X3 -0. 25X5

При условиях X1 = 3. 2 -1. 0X4 -0. 5X3 -0. 60X5

X2 = 1. 5 +0. 5X4 +1. 0X3 -1. 00X5

X6 = 5. 6 -2. 0X4 -0. 5X3 -1. 00X5

Если коэффициент целевой функции переменной X2 станет равным С2 + q то относительные оценки небазисных переменных изменятся следующим образом:

D4 = 3. 5 + q*(-0. 5)

D3 = 0. 1 + q*(-1. 0)

D5 = 0. 25 + q*(+1. 0)

Заметим что величины Aij имеют знаки противоположные тем, что приведены выше.

Диапазон значений для q вычисляется в соответствии с формулой:

(0. 25/-1. 0) <= q <= MIN (3. 5/0. 5 , 0. 1/1)

-0. 25 <= q <= 0. 1

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

Так в нашем примере при q = 0. 1 относительная оценка переменной X3 равна нулю так что если коэффициент целевой функции переменной X2 увеличится на 0. 1 или более станет выгодно производить X3 и мы сможем производить MIN {3. 2/0. 5 , 5. 6/0. 5} = 6. 4 единиц X3 когда X1 обратится в нуль и потребуется изменение базиса.

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

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