Реферат: Математические методы оптимизации ресурсов

Введение.

Переход к рыночной экономике неотъемлем от процессов планирования,

регулирования, управления и прогнозирования производственных и

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

экономико-математических методов и моделей для решения возникающих

производственно-хозяйственных задач, определения и выбора

вариантов экономического развития на перспективу, обеспечения оптимального

распределения ресурсов для выполнения отдельных комплексов

работ и т.п. Определение оптимального варианта текущего и перспективного

развития часто связано с решением динамических задач оптимизации,

имеющих большую размерность и множество разнообразных условий

и ограничений (например, цело-численности переменных, сочетающейся с

требованием их не убывания во времени), что обусловливает сложность

решения из-за существенно многоэкстремального характера. Рассмотрим

основные экономико-математические методы оптимизации.

1. Разновидности экономико-математических моделей

и методов.

Все множество наук сегодня широко включает в себя как необходимые

инструментальные средства математические модели и методы,

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

и абстрактного описания наиболее важных, существенных

связей технико-экономических переменных систем и

объектов, оценивать форму и параметры зависимостей их переменных;

получать новые знания об объектах; определять наилучшие

решения в той или иной ситуации; формулировать выводы,

адекватные изучаемому объекту; компактно излагать основные

теоретические положения.

Любое технико-экономическое исследование всегда предполагает

объединение теории (математической модели) с практикой

(экспериментом и статистическими данными). В качестве примера

экономических моделей можно назвать модели: экономического

роста, равновесия на товарных и финансовых рынках, ценообразования

и конкурентного равновесия, социального и экономического

оптимума, потребительского выбора и др

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

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

и оптимизации ресурсов, прогнозировать их возможные

негативные последствия, использовать полученные оценки в

управлении.

Математическая модель объекта — это его гомоморфное

отображение в виде совокупности уравнений, неравенств, логических

отношений, графиков, условный образ объекта, созданный

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

или возможных ситуациях.

Математические модели, используемые, например, в экономике,

можно подразделить: по особенностям моделируемого объекта

— на макро- и микроэкономические; по целям моделирования

и используемому инструментарию — на теоретические и прикладные,

оптимизационные и равновесные, статические и динамические,

непрерывные и стохастические.

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

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

материальные и финансовые показатели: ВВП, потребление, инвестиции,

занятость, бюджет, инфляцию, ценообразование и др.

Микроэкономические модели описывают взаимодействие

структурных и функциональных составляющих экономики либо

их автономное поведение в переходной неустойчивой или стабильной

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

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

иф и т. п.

Теоретические модели отображают общие свойства экономики и

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

Прикладные модели обеспечивают возможность оценки параметров

функционирования конкретных технико-экономических объектов

и обоснования выводов для принятия управленческих решений

(к их числу относятся прежде всего эконометрические модели,

позволяющие статистически значимо оценивать числовые значения

экономических переменных на основе имеющихся наблюдений).

Равновесные модели, присущие рыночной экономике,

описывающие поведение субъектов хозяйствования как в

стабильных устойчивых состояниях, так и в условиях нерыночной

экономики, где неравновесие по одним параметрам компенсируется

другими факторами. Оптимизационные модели связаны

в основном с микроуровнем (оптимизация и распределение

ресурсов, максимизация полезности потребителем или прибыли

предприятием), на макроуровне результатом рационального

выбора поведения становится некоторое состояние равновесия.

Статические модели описывают состояние экономического

объекта в конкретный текущий момент или период времени;

динамические модели, напротив, включают взаимосвязи переменных

во времени, описывая силы и взаимодействия процессов

в экономике.

Детерминированные модели предполагают жесткие функциональные

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

модели допускают наличие случайных воздействий на исследуемые

показатели, используя в качестве инструментария методы

теории вероятностей и математической статистики.

В экономической науке выделяют следующие основные направления:

• математическую экономику, занимающуюся анализом

свойств и решений математических моделей технико-

экономических процессов и исследующую теоретические

модели, основанные на определенных предпосылках —

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

конкретных формулах взаимосвязи величин;

• эконометрику, занимающуюся статистической оценкой и

анализом экономических зависимостей и моделей на основе

изучения эмпирических данных.

Математическая экономика изучает вопросы, связанные с

существованием решения модели в условиях его неотрицательности,

стационарности, наличия других дополнительных

свойств. К ее основным классам моделей относятся: модели равновесия

в экономических системах (модели Эрроу—Дебре,

«затраты —выпуск» В. Леонтьева и др.) и модели экономического

роста (модели Солоу, Харрода—Домара, Гейла, Моришимы и

др., модели магистрального типа).

Основой эконометрики являются методы корреляционно-

регрессионного анализа, математической статистики, дисперсионного

анализа.

2.Математические модели оптимизации

ресурсов и принятия решений

Для рещения самых разнообразных задач оптимизации необходимо

иметь соответствующую математическую модель. В большинстве

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

частными случаями одной задачи оптимизации.

2.1. Общий случай математической постановки задачи

оптимизации

Если не рассматривать детально составление математической

модели на конкретных примерах, как это делается в большинстве

посвященных этой проблеме работ, например [16, 54, 82,

125—130], а Перейти к общему случаю, то задача оптимизации в

общем случае, включающая три компоненты (целевую функцию

F, ограничения gf и граничные условия), имеет следующую математическую

постановку:

(2.1)

где fly и bj —нижнее и верхнее предельно допустимые значения Xj.

Задачу (2.1) можно представить в еще более общей компактной

форме записи:

(2.2)

Граничные условия показывают предельно допустимые значения

искомых переменных, и в общем случае они могут бьггь

двусторонними типа aj < xj <, bj. Вместе с тем на практике достаточно

часто возникают следующие частные случаи:

1) в технических, экономических и других видах расчетов искомые

величины обычно являются положительными или равными

нулю. В этом случае в задаче (2.2) принимается оу = О, Лу = « и накладывается

только требование неотрицательности Xj>0;

2) в ряде случаев значение величины xj может задаваться. Если

принять, что должно выполняться требование Xj = х?, где х/

— заданное значение, то граничные условия в задаче (2.2) можно

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

Ограничения обычно выражают определенные зависимости

между переменными величинами, которые по своей сути могут

быть теоретическими (формульными) и статистическими. Теоретические

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

и для их получения не требуется никаких дополнительных

измерений. Однако на практике достаточно часто между параметрами

модели нет известной функциональной зависимости.

Так, например, если мы желаем оптимизировать использование

общественного транспорта города в течение суток, то нам необходимо

знать, как пассажиропоток распределен во времени. Естественно,

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

потребуется осуществить сбор и обработку статистических

данных, чтобы получить определенную аналитическую зависимость,

которая и будет тем офаничением, которое следует

включить в задачу оптимизации.

Значения переменных, удовлетворяющие заданным фанич-

ным условиям и офаничениям, называют допустимым решением

задачи. Иногда случается, что в задачу включаются противоречивые

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

Такая ситуация приводит к несовместным задачам, которые в

планировании называют несбалансированными планами (когда нет

и не может быть допустимых решений). Обычно же, если задача

составлена правильно, то в общем случае она имеет набор допустимых

решений. Чтобы из данного набора допустимых решений

лицо, принимающее решение (ЛПР), могло выбрать одно

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

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

потому что мы просто не з н а е м , что это такое. Мы будем говорить только об оптимальных решениях (от лат. optimus —

наилучший). Заметим, что наилучшего решения во всех смыслах

быть не может, оно может быть наилучшим (оптимальным)

только в одном, строго установленном смысле. ЛПР должно абсолютно

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

принимаемого решения, т. е. по какому критерию (от ф.

kriterion — мерило, оценка, средство для суждения) принимаемое

решение должно быть оптимально.

Критерий часто называют целевой функцией, функцией цели,

а в математических работах — функционалом. Критерий в

общем случае может оценивать качественные свойства объекта,

причем как желательные пдя субъекта (обычно с максимальным

уровнем или значением, например, прибыль, производительность,

надежность), так и нежелательные для него (или минимальные

— непроизводительные затраты, расход материала,

простои оборудования и др.). Если при принятии решения требуется

максимизировать какое-то свойство (к примеру, прибыль,

производительность или надежность), то в результате решения

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

решений. Если же требуется минимизировать критерий

(стоимость, расход материала, время простоев оборудования),

то в результате решения критерий будет иметь наименьшее

значение из всех допустимых.

Множество различных по смыслу задач оптимизации, окружающих

нас, например, из табл. 2.1, нельзя эффективно решить

без привлечения ЭВМ, без знаний экономико-математических

моделей, практических навыков составления математических

моделей решения задач и применения их в среде существующего

профаммного обеспечения

Таблица 2.1. Классификация задач оптимизации процессов и принятия решений.

Основные задачи управления деятельностью человека можно

отнести к классу задач распределения и оптимизации ресурсов.

Любой объект в процессе управления, проектирования или эксплуатации

характеризуется своим устройством и действием,

причем устройство определяется его структурой и параметрами,

а действие — процессом функционирования. Например, технологический

процесс можно определить как последовательность

работ, которые обусловливают превращение сырья в готовую

продукцию; такую последовательность работ называют маршрутом;

каждую операцию, входящую в марщрут, можно охарактеризовать

определенными режимами обработки, управления,

контроля, функционирования. Заметим, что и процессы функционирования

объекта проектирования, и технологические процессы

характеризуются изменением некоторых параметров во

времени, которые подразделяются на непрерывные и дискретные

(непрерывные процессы протекают в металлургии, энергетике,

химии и др., а дискретные — в машиностроении, экономике,

образовании и т. п.).

В любых математических моделях можно вьщелить следующие

элементы (рис. 2.1): исходные данные, зависимости, описывающие

целевую функцию, и ограничения.

Зависимости между переменными, как целевые функции, так

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

входят в первой степени и нет их произведения; если

переменные входят не в первой степени или есть произведение

переменных, то зависимости являются нелинейными. Сочетание

разнообразных элементов модели приводит к различным классам

задач оптимизации, требуюшим разных методов решения и

разных программных средств (табл. 2.2).

Для экономических систем наиболее характерны задачи оптимизации

и распределения ресурсов, решаемые методом линейного

профаммирования, для которого разработаны надежные

алгоритмы, реализованные в поставляемом с ЭВМ про-

фаммном обеспечении; более сложные задачи (целочисленные,

нелинейные) оптимизации можно свести к задачам линейного

профаммирования. Большинство задач оптимизации, присущих

техническим системам, как правило, относится к задачам нелинейного

программирования. В целом методы математического

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

исследованием операций

2.2Методы оптимизации и распределения ресурсов

на основе задачи линейного программирования

Подобные методы широко применимы в производстве,

транспорте, организации процессов, в об^'чении, руководстве

персоналом и др. К числу наиболее известных задач, решаемых этим методом, относятся задача о назначениях, транспортная

задача и др. [78, 82, 128—130].

Задача о назначениях и распределении работ является частным

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

допущения: число поставщиков т равно числу потребителей

л; запасы каждого поставщика о, = 1; заявки каждого потребителя

bj= 1; каждый поставщик может поставлять фузы только

одному потребителю; каждый потребитель может получать фузы

только от одного поставщика.

Если не учитывать направление оптимизации целевой функции

(шах или min), что не влияет на аналитические зависимости,

то модель транспортной задачи при принятых выше допущениях

получает вид модели задачи о назначениях. Если сумма

всех запасов А у поставщика равняется сумме всех заявок

В потребителей, то такую транспортную задачу называют сбалансированной;

если А 4t В, то задача является несбалансированной, и

ее математическая модель может иметь вид:

Знак неравенства в офаничениях для запасов а, означает,

что объем фуза, вывозимый от любого /-го поставщика по заявкам

всех потребителей, не может превышать имеющегося у

него запаса, при этом часть запаса фуза может остаться невы-

везенной. Аналогично знак неравенства в Офаничениях для

заявок bj означает, что фуз, получаемый ./-м поставщиком,

должен быть не меньше заявки, но превышение заявки при

этом допускается.

Модель сбалансированной задачи является частным случаем

модели несбалансированной задачи. Несбалансированная модель

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

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

ресурсов — работ, назначений, материальных и трудовых ресурсов,

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

знать ответы на вопросы:

• В каком смысле распределение средств должно быть наилучшим?

• Какой вклад дает каждый объект (субъект) в целевую

функцию?

Любая правильно составленная задача планирования имеет

бесчисленное множество допустимых решений. Какое же из них

выбрать? Мы уже знаем, чтобы ответить на этот вопрос, необходимо

прежде всего сформулировать задачу оптимизации, при

решении которой возможна лишь одна из двух взаимоисклю-

чаемых постановок: либо при заданных ресурсах максимизировать

получаемый результат, либо при заданном результате минимизировать

используемые ресурсы.

Если через Q обозначить ресурсы, через R —результат их применения,

то при заданных зависимостях результата и потребных

ресурсов от количества выпускаемой продукции R =f(,xj); Q =fixj)

две постановки задачи распределения ресурсов можно записать

следующим образом:

для первой постановки

для второй постановки

Значит, поставить ее можно в одном из двух следующих вариантов:

либо максимизирювать выпуск продукции с заданного

оборудования, либо минимизировать количество оборудования,

используемого при вьшуске заданного объема продукции.

В общем случае математическая модель задачи распределения

ресурсов с числом переменных я и офаничений т имеет

следующий вид:

где Cj — коэффициенты в целевой функции; а^ — норма расхода /-го

ресурса для выпуска единицы у-й продукции; 6, —имеющийся ресурс; dj

и Dj — минимальное и максимальное допустимые значения Xj

Так как в эту модель все переменные входят в первой степени,

т. е. все зависимости являются линейными, то данную модель

называют задачей линейного программирования. С помощью

этих задач можно решать достаточно большой класс задач распределения

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

производством и экономическими объектами, но и в проектировании

изделий и технологических процессов.

Если сравнить систему (2.4) с общей постановкой задачи оптимизации

(2.2), то можно утверждать, что задача линейного

программирования представляет собой частный случай задачи

оптимизации в общем виде.

В современных условиях рьшочных отношений при дефиците

материальных и финансовых ресурсов, несбалансированности производственных

планов по номенклатуре, нормам расходов материалов и

сьфья возникают договорные, производственные, финансовые и

прочие нарушения, корректировки планов, приписки и др.

Сбалансированность планов по номенклатуре, заданным показателям

и ресурсам можно оперативно проверить с помощью

моделирования на ЭВМ не спустя какое-то время, когда обнаружатся

ошибки и просчеты и когда изменить что-либо уже

трудно, а сразу же при решении задачи. При этом необходимо

опираться на достоверную нормативную базу, в частности, на

нормы расхода ресурсов на единицу выпускаемой продукции.

Именно математические модели позволяют проанализировать

причины несбалансированности планов и выявлять недостоверность

исходных данных.

Чем же может помочь ЭВМ в анализе несбалансированных задач?

1. Решая задачу распределения ресурсов на ЭВМ, до получения

окончательного результата нам неизвестно, сбалансирована

она или нет. Однако, если существует подозрение, что задача

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

так составить математическую модель, чтобы она учитывала

возможную недостачу ресурсов.

2. Если нам желательно минимизировать дополнительные

ресурсы у,- при получении прибыли от производства и выпуска

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

этого условия

а условие получения прибыли включить в состав ограничений.

Результаты решения подобных задач на ЭВМ позволяют

промоделировать возможные ситуации и определить, сколько и

какие ресурсы требуются и каким станет план, если полностью

изыскать необходимые дополнительные ресурсы. Конечно, ЭВМ

не может заменить недостающие ресурсы, но она позволяет при

составлении полной и корректно сформулированной математической

модели показать, что необходимо осуществить, чтобы

выполнить несбалансированный план. Польза от такого анализа

несомненна в любых ситуациях.

В общем преодолеть несбалансированность производственного

плана можно или увеличением ресурсов при возможности

их изыскания, а при невозможности добавления дополнительных

ресурсов путем уменьшения нижнего предела выпуска продукции,

или сокращения норм расходов каждого ресурса на выпуск

единицы продукции. Если удастся преодолеть несбалансированность

планов за счет увеличения ресурсов или снижения

выпуска продукции и расхода ресурсов, то план производства

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

Определение координат вершин области допустимых решений

(ОДР) в реальных задачах со многими переменными и ограничениями

связано с очень большими объемами вычислений. Поэтому

для аналитического решения задач линейного профамми-

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

вершин, называемый симплекс-методом, с переходом от

одной вершины к другой в направлении, при котором значение

целевой функции от вершины к вершине улучшается. Определе-

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

считается и т е р а ц и е й . Число итераций зависит от числа

искомых переменных и в реальных задачах может измеряться

сотнями. Вручную с помощью симплекс-метода можно решать

задачи, Содержащие не более десяти переменных. В реальных

ситуациях без ЭВМ и прикладных профамм вычислений поиск

оптимального решения практически невозможен.

Так как оптимальное решение задачи линейного профамми-

рования соответствует вершине ОДР, то можно сформулировать

следующие выводы:

,1) если оптимальным решением являются координаты вершин

ОДР, то сколько вершин имеет ОДР, столько оптимальных

решений может иметь задача;

2) чем больше существует офаничений в модели задачи, тем

больше будет число вершин и, следовательно, число оптимальных

решений;

3) введение дополнительных ограничений никогда не улучшает

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

практики планирования: если мы хотим улучшить принятую целевую

функцию, т. е. результат работы, мы должны стремиться к

тому, чтобы иметь как можно меньше ограничений).