183656 (Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования), страница 2

в моделях; случайных факторов и т.п.) выделяют, например, такие модели:

1. Детерминированый модель(линейная модель, нелинейная модель, динамическая модель, графическая модель);

2. Стохастический модель;

3. Неопределенный модель (теория игр, имитационные модели).

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

*модели стохастического программирования, в которых либо в целевую функцию, либо в ограничения входят случайные величины;

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

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

Также к стохастическим моделям можно отнести модели теории полезности, поиска и принятия решений.

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

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

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

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

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

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

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

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

1. Графический метод;

2. Симплекс-метод;

3. Двухэтапный метод. Он позволяет получить сначала стартовую точку, т.е. начальное допустимое решение, а затем оптимальное решение. В ограничения вводятся искусственные переменные необходимые для получения стартовой точки;

4. Метод больших штрафов;

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

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

• оно должно быть линейным;

• должно отсекать найденный оптимальный нецелочисленный план;

• не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т. д.

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

1. ПОСТАНОВКА ЗАДАЧИ ОПЕРАЦИОННОГО ИССЛЕДОВАНИЯ

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

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

2. ПОСТРОЕНИЕ БАЗОВОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ

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

X1−количество выпускаемого удобрения «Флора» (в тоннах);

Х2−количество выпускаемого удобрения «Росток» (в тоннах);

Составим ограничения, учитывающие условие задачи.

Составим ограничение на расход азотной кислоты. На выпуск одной тонны удобрения «Флора» расходуется 1 т азотной кислоты, значит,

расход азотной кислоты на выпуск всего количества удобрения «Флора» составит X1 т. На выпуск удобрения «Росток» будет израсходовано 4X2т азотной кислоты. Таким образом, общий расход азотной кислоты составит

X1 + 4X2^т. Эта величина не должна превышать 900 т, так как запас азотной кислоты составляет 900т. Поэтому можно записать следующее ограничение:

X1+4X2 ≤ 900

Аналогично можно составить ограничение на аммиак:

2,5X1+2X2≤ 1000

и на расход калийной соли:

3Х1+2Х2≤800

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

X1>0, X2>0.

В данной задаче требуется определить количество тонн выпускаемых удобрений, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одной тонны удобрения «Флора» составляет 5 ден. ед.; значит, прибыль от выпуска удобрения «Флора» составит 5X1 ден. ед. Прибыль от выпуска удобрения «Росток» составит 8X2 ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 5X1 + 8X2 ден. ед. Требуется найти такие значения переменных X1 иX2, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е = 5X1 + 8X2 →max

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

Х1+4Х2+Х3=900

2,5Х1+2Х2+Х4=1000

3Х1+2Х2+Х5=800

Е = 5X1 + 8X2 →max

X1>0, X2>0.

Где:

Х3-остаток азотной кислоты;

Х4-остаток аммиака;

Х5-остаток калийной соли.

3. ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ

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

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

Рассмотрим алгоритм поиска оптимального решения на основе симплекс-таблиц:

1. Строится исходная симплекс-таблица.

2. Симплекс-таблица строится по следующим правилам:

• в первой строке перечисляются все переменные задачи, как исходные (X1, X2, ...,X_n), так и дополнительные, введенные при приведении к стандартной форме (X_n+1, X_n+2, ...,Xk). Для задач, содержащих только ограничения «меньше или равно», дополнительные переменные X_n+1, X_n+2, ...,Хк~ это остаточные переменные;

• в первой колонке таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений. Для задач, содержащих только ограничения «меньше или равно», начальный базис состоит из остаточных переменных X_n+1, X_n+2, ..., Xk. В этой же колонке указывается обозначение целевой функции E;

• в строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для остаточных переменных X_n+1, X_n+2, ..., Xk), указываются нули;

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

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

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

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

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

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