МИНИСТЕРСТВООБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
БЕЛОРУССКИЙНАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Факультеттехнологий управления и гуманитаризации
Кафедра«Менеджмент»
Расчетно-графическаяработа по дисциплине
«Экономико-математическиеметоды и модели»
Тема расчетно-графической работы:
«Решение оптимизационных управленческих задач наоснове
методов и моделей линейного программирования»
Вариант № 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, ...,Xn), таки дополнительные, введенные при приведении к стандартной форме (Xn+1,Xn+2, ...,Xk). Для задач, содержащих только ограничения «меньше или равно»,дополнительные переменные Xn+1, Xn+2, ..., Хк~ этоостаточные переменные;
• в первой колонке таблицы («Базис») перечисляютсяпеременные, составляющие начальный базис задачи. Их количество всегдаравно количеству ограничений. Для задач, содержащих толькоограничения «меньше или равно», начальный базис состоит из остаточныхпеременных Xn+1, Xn+2, ..., Xk. В этой же колонке указываетсяобозначение целевой функции E;
• в строке целевой функции указываются коэффициенты целевойфункции с обратным знаком. Для переменных, не входящих в целевую функцию(например, для остаточных переменных Xn+1,Xn+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 Х3 1 4 1 900 Х4 2,5 2 1 1000 Х5 3 2 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 2 1800 Х2 0,25 1 0,25 225 Х4 2 -0,5 1 550 Х5 2,5 -0,5 1 350
Т.к. в строке целевой функции естьотрицательные коэффициенты, то данное решение не является оптимальным.Пересчитаем таблицу по описанному выше примеру.
Таблица3- Симплекс-таблица 3Базис Х1 Х2 Х3 Х4 Х5 Решение E 1,4 1,2 2220 Х2 1 0,3 -0,1 190 Х4 -0,1 1 -0,8 270 Х1 1 -0,2 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; X3= 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 срезультатами решения задачи оптимизации сохраняется и переносится в документ MSWord (например, с помощью команд «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.