При постановке задачи организационного управления, прежде всего, важно

1. Определить цель, преследуемую субъектом управления.

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

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

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

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

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

Найти оптимум

(целевая функция) при ограничениях

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

линейное программирование оптимизационная модель

2. Основные понятия теории оптимизации

2.1 Общая постановка задачи оптимизации

2.2 Ограничения на допустимое множество

2.3 Классическая задача оптимизации

2.4 Функция Лагранжа

3.1 Задача ЛП

3.2 Графическое решение задачи ЛП

4.2 Симплекс-метод

4.2.2 Вычислительные процедуры симплекс-метода

Симплекс-алгоритм:

Шаг 0: Используя линейную модель стандартной формы, определяют НДБР путём приравнивания к нулю n-m (небазисных) переменных.

Шаг 1: Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если её нет - текущее базисное решение оптимально, иначе переход к Шагу 2.

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

Шаг 3: Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных. Переход к Шагу 1.

Если xE=xI=0, то

(соответствует точке A Ha) - начальное допустимое решение.

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

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

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

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

Поиск нового базисного решения осуществляется методом исключения переменных (метод Жордана-Гаусса). Этот процесс включает в себя вычислительные процедуры двух типов.

Тип 1. Формирование ведущего уравнения

Новая ведущая строка = предыдущая ведущая строка/ведущий элемент

Тип 2. Формирование остальных уравнений

Новое уравнение = предыдущее уравнение - (коэффициент ведущего столбца предыдущего уравнения) * (новая ведущая строка)

Новая симплекс-таблица, полученная после проведения рассмотренных операций:

xI - вводимая переменная (т.к. коэффициент в -уравнении - 1/2). Исключаемая переменная s1, (отношение 4/3 - минимальное). Снова проведём вычисления двух типов. Последняя симплекс-таблица соответствует оптимальному решению задачи, т.к. в -уравнении ни одна из небазисных переменных не фигурирует с отрицательными коэффициентами.

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

4.2.3 Искусственное начальное решение

Для получения начального базисного решения мы использовали остаточные переменные. Однако когда исходное ограничение записано в виде равенства или имеет знак, нельзя сразу же получить НДБР. Поэтому были разработаны два метода, в которых используется "штрафование" искусственных переменных.

1. Метод больших штрафов (М-метод)

Рассмотрим линейную модель, приведённую к стандартной форме:

минимизировать

при ограничениях

В первом и втором уравнениях нет переменных, исполняющих роль остаточных. Поэтому введём в каждое из этих уравнений по одной из искусственных переменных R1 и R2:

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

Минимизировать

при ограничениях

Теперь если

,

то начальное допустимое решение:

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

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

получим выражение для :

Решение представлено в сводной таблице:

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

.

Т.к. в оптимальном решении отсутствуют искусственные переменные, имеющие положительное значение, то данное решение - допустимое оптимальное решение задачи в её стандартной постановке.

3. Двухэтапный метод

Этап 1. Вводятся искусственные переменные, необходимые для получения стартовой точки. Записывается новая целевая функция, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях, видоизменённых за счёт искусственных переменных. Если минимальное значение новой целевой функции равно нулю (т.е. все искусственные переменные в оптимуме равны нулю), то исходная задача имеет допустимое решение и переходим к Этапу 2.

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

Рассмотрим на примере.

Этап 1.

Минимизация

при ограничениях

Т.к. , можно переходить к Этапу 2.

Этап 2. Исходную задачу сформулируем следующим образом:

минимизировать

при ограничениях

Теперь, приравняв x3=0, получим НДБР

Для решения задачи необходимо подставить в целевую функцию выражения для базисных переменных x1 и x2:

5. Двойственность

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

Прямая задача ЛП в стандартной форме:

максимизировать (минимизировать)

при ограничениях

В состав включаются избыточные и остаточные переменные.

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

· каждому ограничению прямой задачи соответствует переменная двойственной задачи;

· каждому переменной прямой задачи соответствует ограничение двойственной задачи;

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

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

Рассмотрим пример:

Прямая задача:

максимизировать

при ограничениях

Прямая задача в стандартной форме: максимизировать

при ограничениях

Двойственная задача:

Минимизировать

при ограничениях:

(означает, что y1>0). y1, y2 не ограничены в знаке.

Размещено на Allbest.ru