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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет технологий управления и гуманитаризации

Кафедра «Менеджмент»

Расчетно-графическая работа по дисциплине

«Экономико-математические методы и модели»

Тема расчетно-графической работы:

«Решение оптимизационных управленческих задач на основе

методов и моделей линейного программирования»

Вариант № 17

Исполнитель:

студент(ка) группы 108158

Ядревская Юлия Сергеевна

Руководитель:

Калачёва Татьяна Александровна

Минск 2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ ТЕХНОЛОГИИ СИМПЛЕКС-МЕТОДА

5. АНАЛИЗ РЕЗУЛЬТАТОВ БАЗОВОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ И ПРЕДЛОЖЕНИЯ ПО МОДИФИКАЦИИ

6. ПРОВЕРКА ОПТИМАЛЬНОГО РЕШЕНИЯ В СРЕДЕ MS EXCEL. С ИСПОЛЬЗОВАНИЕМ ПРОГРАМНОЙ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» (ПАКЕТ «SOLVER»)

7. ПРИМЕРЫ ПОСТАНОВОК, ФОРМАЛИЗАЦИИ И РЕШЕНИЯ ПЕРСПЕКТИВНЫХ ОПТИМИЗАЦИОННЫХ УПРАВЛЕНЧЕСКИХ ЗАДАЧ

8. ЗАКЛЮЧЕНИЕ

9. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

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

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

Основные этапы процесса моделирования.

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

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

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

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

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

Одна из важных особенностей математических моделей - потенциальная возможность их использования для решения разнокачественных проблем. Поэтому, даже сталкиваясь с новой экономической задачей, не нужно стремиться "изобретать" модель; вначале необходимо попытаться применить для решения этой задачи уже известные модели.

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

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

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

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

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

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

Обычно расчеты по экономико-математической модели носят многовариантный характер. Благодаря высокому быстродействию современных ЭВМ удается проводить многочисленные "модельные" эксперименты, изучая "поведение" модели при различных изменениях некоторых условий. Исследование, проводимое численными методами, может существенно дополнить результаты аналитического исследования, а для многих моделей оно является единственно осуществимым. Класс экономических задач, которые можно решать численными методами, значительно шире, чем класс задач, доступных аналитическому исследованию.

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

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

Особенности исследования операций.

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

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

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

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

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

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

В литературе, посвященной вопросам экономико-математического моделирования, в

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Виды сырья	Запас (т)	Расход сырья на 1 т удобрений (т)
		"Флора"	"Росток"
Азотная кислота Аммиак Калийная соль	900 1000 800	1 2,5 3	4 2 2
Прибыль (ден.ед.)	5	8

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

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

5. Выполняется преобразование симплекс-таблицы по следующим правилам:

Новая ведущая строка =

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

6. Находится новое базисное решение, соответствующее новой структуре небазисных и базисных переменных. Осуществляется переход к шагу 2.

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

4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ ТЕХНОЛОГИИ СИМПЛЕКС-МЕТОДА

Математическая модель решаемой задачи имеет следующий вид:

Х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.

Составим исходную симплекс-таблицу (табл.1):

Таблица 1

Базис	Х1	Х2	Х3	Х4	Х5	Решение
E	-5	-8	0	0	0	0
Х3	1	4	1	0	0	900
Х4	2,5	2	0	1	0	1000
Х5	3	2	0	0	1	800

Определяется переменная для включения в базис.

Для рассматриваемого примера в базис необходимо включить переменную X2, так как ей соответствует максимальный по модулю отрицательный коэффициент E-строки (-8). Это означает увеличение выпуска удобрения «Росток». Из условия задачи и целевой функции видно, что увеличение выпуска удобрения «Росток» приводит к более быстрому росту целевой функции, чем увеличение выпуска удобрения «Флора»: выпуск каждой тонны удобрения «Росток» увеличивает целевую функцию (прибыль) на 8 ден. ед., а выпуск каждой тонны удобрения «Флора» - только на 5 ден. ед.

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

900/4=225; 1000/2=500; 800/2=400.

Смысл поиска переменной, исключаемой из базиса в следующем: при включении новой переменной в базис, её значение увеличивается. При этом чтобы соблюдать исходные ограничения задачи необходимо уменьшать базисные переменные. Уменьшение переменных возможно только до 0. Симплексное отношение показывает через сколько увеличений переменой, включаемой в базис, данная базисная переменная приблизится к нулю. Поэтому переменная, имеющая минимальное симплексное отношение, исключается из базиса. Строка с переменной, исключаемой из базиса, называется ведущей строкой. Итак, исключаем из базиса переменную Х3 (симплексное отношение минимальное и равно 225), строка Х3 является ведущей. Элемент, находящийся на пересечении ведущей строки Х3 и ведущего столбца Х2, называется ведущим (разрешающим) элементом. Для данной таблицы ведущий элемент равен 4.

Выполним преобразования таблицы по правилам симплекс-метода, описанным в разделе 3: ведущая строка Х3 делится на ведущий элемент, равный 4; ведущий столбец Х2 заполняется нулями; все остальные элементы таблицы пересчитываются по “правилу прямоугольника”. Например, коэффициент на пересечении Е-строки и столбца Х1 пересчитывается следующим образом: [4*(-5)-1*(-8)] /4= -3. Полученная симплекс-таблица приведена в табл.2.:

Таблица 2- Симплекс-таблица 2

Базис	Х1	Х2	Х3	Х4	Х5	Решение
E	-3	0	2	0	0	1800
Х2	0,25	1	0,25	0	0	225
Х4	2	0	-0,5	1	0	550
Х5	2,5	0	-0,5	0	1	350

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

Таблица3- Симплекс-таблица 3

Базис	Х1	Х2	Х3	Х4	Х5	Решение
E	0	0	1,4	0	1,2	2220
Х2	0	1	0,3	0	-0,1	190
Х4	0	0	-0,1	1	-0,8	270
Х1	1	0	-0,2	0	0,4	140

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

Х1=140;

Х2=190;

Х4=270;

Х3= Х5=0;

Е=2220.

5. АНАЛИЗ РЕЗУЛЬТАТОВ БАЗОВОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ И ПРЕДЛОЖЕНИЯ ПО МОДИФИКАЦИИ

Проанализируем полученный результат решения задачи:

Х1=140;

Х2=190;

Х4=270;

Х3= Х5=0;

Е=2220.

Значения переменных X1 = 140, X2 = 190 показывают, что предприятие по плану должно выпускать 140 тонн удобрения «Флора» и 190 тонн удобрения «Росток». В этом случае будет получена максимальная прибыль в размере 2220 ден. ед. (значение целевой функции). Так как X3 = 0, значит, весь запас азотной кислоты (900 тонн) расходуется на выпуск удобрений. Аналогично можно показать, что переменная X4 представляет собой неизрасходованный остаток аммиака, а X5 - калийной соли. Таким образом, остается неизрасходованным 270 тонн аммиака (расход аммиака на выпуск всех удобрений составит 1000 - 270 = 730 тонн). Неизрасходованный остаток калийной соли равен нулю, значит, все 800 тонн калийной соли расходуются на производство удобрений.

Проведем анализ полученного решения на чувствительность. Для начала определим статус имеющихся в задаче ресурсов. По статусу все ресурсы делятся на дефицитные и недефицитные. Если для реализации оптимального решения ресурс расходуется полностью, то он называется дефицитным, если не полностью - недефицитным. Статус ресурсов определяется по значениям остаточных переменных. В данной задаче дефицитными ресурсами являются азотная кислота и калийная соль, т.к. они полностью расходуются в процессе производства (Х3=0; Х5=0). Аммиак - недефицитный ресурс, так как 270 тонн аммиака остаются неизрасходованными (X4 = 270). Увеличение запасов дефицитных ресурсов позволяет увеличить целевую функцию (прибыль). Снижение запасов дефицитных ресурсов приводит к снижению прибыли. Увеличение запасов недефицитных ресурсов всегда нецелесообразно, так как оно приводит только к увеличению неизрасходованных остатков. Запас недефицитного ресурса можно снизить на величину его остатка; это никаким образом не влияет на оптимальное решение (в том числе на оптимальные объемы производства и на прибыль), уменьшается только неизрасходованный остаток ресурса. Если запас недефицитного ресурса снизится на величину, превышающую его остаток, то для определения нового оптимального плана производства необходимо решать задачу заново. В нашем случае увеличение запасов азотной кислоты и калийной соли позволит увеличить прибыль. Запас аммиака можно снизить на 270 т (т.е. до 730 т); эти 270 т аммиака предприятие может, например, продать или использовать в другом цехе. Например, если запас аммиака составит не 1000 т, а только 800 т, то оптимальное решение задачи будет следующим: X1 =140; X2 = 190; X₃ = 0; X4 = 70; X5 = 0; E = 2220 ден. ед. Таким образом, оптимальное решение не изменится (кроме снижения неизрасходованного остатка аммиака). Если запас стали снизится более чем на 270 т (т.е. составит менее 730 т), то для определения нового оптимального плана производства необходимо решать задачу заново. Для нового оптимального решения изменятся не только значения переменных, но и состав переменных в оптимальном базисе (т.е. в оптимальный базис будут входить не переменные X1, X2 и X5, а другие переменные). Значение целевой функции при этом снизится, т.е. составит менее 2220 ден. ед.

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

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

В нашем случае ценность азотной кислоты равна 1,4 ден. ед./т, ценность калийной соли - 1,2 ден. ед./т. Это означает, например, что увеличение запаса азотной кислоты на единицу (т.е. на 1 т) приводит к увеличению прибыли предприятия в среднем на 1,4 ден. ед. Например, если запас азотной кислоты увеличится на 100 т (т.е. составит 1000 т), то прибыль составит примерно 2220 + 1,4*100 =2360 ден. ед. Снижение запаса азотной кислоты приведет к соответствующему снижению прибыли.

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

Ценность ресурса показывает максимальную (предельную) цену, по которой выгодно закупать ресурсы. Например, в рассматриваемой задаче предприятию выгодно закупать азотную кислоту по цене не более 1,4 ден. ед./т, калийную соль - по цене не более 1,2 ден. ед./т. Закупка ресурса по цене, превышающей его ценность, означает, что затраты предприятия на закупку ресурса превышают прибыль от его использования.

6. ПРОВЕРКА ОПТИМАЛЬНОГО РЕШЕНИЯ В СРЕДЕ MS EXCEL С ИСПОЛЬЗОВАНИЕМ ПРОГРАМНОЙ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» (ПАКЕТ «SOLVER»)

Для решения оптимизационных задач в среде MS Excel используется инструмент «Поиск решения» (пункт меню «Данные Поиск решения»).

Для решения задачи необходимо выполнить следующие этапы:

ь Внести исходные данные;

ь Определить ячейки, в которые будет помещен конечный результат (изменяемые ячейки);

ь Внести в определенную ячейку формулу для расчета целевой функции;

ь Внести в ячейки формулы для расчета ограничений.

В результате получается следующее:

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

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

1.Для повторного решения задачи оптимизации следует удалить содержимое ячеек с элементами решения и сбросить полученные результаты (клавиша «Delete»).

2.Фрагмент рабочего листа MS Excel с результатами решения задачи оптимизации сохраняется и переносится в документ MS Word (например, с помощью команд «Ctrl&PrintScreen» в среде MS Excel и «Вставить» в документе MS Word или с помощью команд «Копировать» и «Вставить», расположенных на панели инструментов во всех приложениях пакета MS Office).

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

7. ПРИМЕРЫ ПОСТАНОВОК, ФОРМАЛИЗАЦИИ И РЕШЕНИЯ ПЕРСПЕКТИВНЫХ ОПТИМИЗАЦИОННЫХ УПРАВЛЕНЧЕСКИХ ЗАДАЧ

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

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

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

ь построить ОДР на плоскости в системе координат (X1; X2),

ь определить все угловые точки ОДР,

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

Решим графическим методом следующую задачу: предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 25 ден.ед., выпуск одной тонны серной кислоты - 40 ден.ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты - 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

Составим математическую модель задачи. Для этого введем переменные. Обозначим через X1 количество выпускаемой соляной кислоты (в тоннах), через X2 - количество серной кислоты (в тоннах).

Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200т. соляной кислоты. Это ограничение можно записать следующим образом: X1 ? 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100т. серной кислоты: X2 ? 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5т. опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5·X1 т. При выпуске серной кислоты образуется 1,2·X2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5·X1 + 1,2·X2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5·X1 + 1,2·X2 ? 600.

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

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден.ед.; значит, прибыль от выпуска соляной кислоты составит 25·X1 ден.ед. Прибыль от выпуска серной кислоты составит 40·X2 ден.ед. Таким образом, общая прибыль от выпуска кислот составит 25·X1+40·X2 ден.ед. Требуется найти такие значения переменных X1 и X2, при которых эта величина будет максимальной.

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

E = 25·X1+40·X2 > max.

Приведем полную математическую модель рассматриваемой задачи:

X1 ? 200

X2 ? 100 (1.3)

0,5·X1 + 1,2·X2 ? 600

X1 ? 0, X2 ? 0.

E = 25·X1+40·X2 > max.

В этой задаче имеется два ограничения “больше или равно” и одно ограничение “меньше или равно”. Целевая функция подлежит максимизации.

Ограничение X1 ? 200 задается вертикальной линией X1=200. Все точки (X1; X2), расположенные справа от этой линии, удовлетворяют ограничению X1 ? 200, расположенные слева - не удовлетворяют. Ограничение X2 ? 100 задается горизонтальной линией X2=100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению X2 ? 100, расположенные снизу - не удовлетворяют.

Для построения линии, задающей ограничение 0,5·X1 + 1,2·X2 ? 600, удобно записать его в виде равенства: 0,5·X1 + 1,2·X2 = 600. Выразим одну из переменных через другую: X2 = -0,417·X1 + 500. Это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой - не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5·X1 + 1,2·X2 ? 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

Пересечение всех полуплоскостей, удовлетворяющих ограничениям задачи, представляет собой ОДР. На рис.2 она выделена цветом.

Рисунок 2. Решение задачи графическим методом

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

E(A) = 25·200 + 40·100 = 9000;

E(B) = 25·200 + 40·416,67 = 21666,8;

E(C) = 25·960 + 40·100 = 28000.

Таким образом, оптимальное решение находится в точке C=(960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5·960 + 1,2·100 = 600 т.

ЗАКЛЮЧЕНИЕ

В рамках данной работы была решена одна из задач линейного программирования. В результате применения процедуры симплекс-метода было получено оптимальное решение поставленной задачи, в соответствии с которым предприятию требуется выпустить 140 тонн удобрения «Флора» и 190 тонн удобрения «Росток». При этом количество неиспользованного аммиака составит 270 тонн, а азотная кислота и калийная соль будут использованы полностью. При этом предприятие получит максимальную прибыль равную 2220 денежных единиц.

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

Проверка результатов решения задачи в среде MS Excel показала аналогичное решение данной задачи оптимизации.

При выполнении данной работы на примере был рассмотрен графический метод решения задач.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Замков О.О., Толстопятенко А.В., Черешных Ю.Н. Математические методы в экономике: Учебник. - М.: МГУ им. М.В.Ломоносова, Издательство «ДИС», 1997.

2. Конспект лекций по предмету «Экономико-математические методы и модели».

3. Минюк С.А. Математические методы и модели в экономике: Учеб. пособие / Минюк С.А., Ровба Е.А., Кузьмич К.К. - Мн.: ТетраСистемс, 2002.

4. Смородинский С.С., Батин Н. В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003.

5. Экономико-математические методы и модели/ Под. ред. А. В. Кузнецова. Мн.: БГЭУ.1999.