Тема 15. Основные понятия теории оптимизации.
На практике постоянно встречаются такие ситуации, когда достичь какого-то результата можно не одним, а многими различными способами. В подобной ситуации может оказаться и отдельно взятый человек, например, когда он решает вопрос о распределении своих расходов, и целое предприятие или даже отрасль, если необходимо определить, как использовать имеющиеся в их распоряжении ресурсы, чтобы добиться максимального выхода продукции, и, наконец народное хозяйство в целом. Естественно, при большом количестве решений должно быть выбрано наилучшее.
Успешность решения подавляющего большинства экономических задач зависит от наилучшего, наивыгоднейшего способа использования ресурсов. И от того, как будут распределены эти, как правило, ограниченные ресурсы, будет зависеть конечный результат деятельности.
Суть методов оптимизации (оптимального программирования) заключается в том, чтобы, исходя из наличия определенных ресурсов, выбрать такой способ их использования (распределения), при котором будет обеспечен максимум или минимум интересующего показателя. [1]
Необходимым условием использования оптимального подхода к планированию (принципа оптимальности) является гибкость, альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать планово-управленческие решения. Именно такие ситуации, как правило составляют повседневную практику хозяйствующего субъекта (выбор производственной программы, прикрепление к поставщикам, маршрутизация, раскрой материалов, приготовление смесей).
Оптимальное программирование, таким образом, обеспечивает успешное решение целого ряда экстремальных задач производственного планирования. В области же макроэкономического анализа, прогнозирования и планирования оптимальное программирование позволяет выбрать вариант народнохозяйственного плана (программы развития), характеризующийся оптимальным соотношением потребления и сбережений (накоплений), оптимальной долей производственных капиталовложений в национальном доходе, оптимальным соотношением коэффициента роста и коэффициента рентабельности национальной экономики и т. д.
Оптимальное программирование обеспечивает получение практически ценных результатов, так как по своей природе оно вполне соответствует характеру исследуемых технико-экономических процессов и явлений. С математической и статистической точек зрения этот метод применим лишь к тем явлениям, которые выражаются положительными величинами и в своей совокупности образуют объединение взаимозависимых, но качественно различных величин. Этим условиям, как правило, отвечают величины, которыми характеризуются экономические явления. Перед исследователем экономики всегда имеется – некоторое множество разного рода положительных величин. Решая задачи оптимизации, экономист всегда имеет дело не с одной, а с несколькими взаимозависимыми величинами или факторами.
Оптимальное программирование можно применять лишь к таким задачам, при решении которых оптимальный результат достигается лишь в виде точно сформулированных целей и при вполне определенных ограничениях, обычно вытекающих из наличных средств (производственных мощностей, сырья, трудовых ресурсов и т. д.). В условия задачи обычно входит некоторая математически сформулированная система взаимозависимых факторов, ресурсы и условия, ограничивающие характер их использования.
Задача становится разрешимой при введении в нее определенных оценок как для взаимозависимых факторов, так и для ожидаемых результатов. Следовательно, оптимальность результата задачи программирования имеет относительный характер. Этот результат оптимален только с точки зрения тех критериев, которыми он оценивается, и ограничений, введенных в задачу.
Отталкиваясь от вышесказанного, для любых задач оптимального программирования характерны три следующих момента: [2]
1) наличие системы взаимозависимых факторов;
2) строго определенный критерий оценки оптимальности;
3) точная формулировка условий, ограничивающих использование наличных ресурсов или факторов.
Из многих возможных вариантов выбирается альтернативная комбинация, отвечающая всем условиям, введенным в задачу, и обеспечивающая минимальное или максимальное значение выбранного критерия оптимальности. Решение задачи достигается применением определенной математической процедуры, которая заключается в последовательном приближении рациональных вариантов, соответствующих выбранной комбинации факторов, к единственному оптимальному плану.
Математически это может быть сведено к нахождению экстремального значения некоторой функции, то есть к задаче типа:
Найти max (min) f(x) при условии, что переменная х (точка х) пробегает некоторое заданное множество Х:
f(x) ® max (min), х I Х (4.1)
Определенная таким образом задача называется задачей оптимизации. Множество Х называется допустимым множеством данной задачи, а функция f(x) – целевой функцией. [3]
Итак, оптимизационной является задача, которая состоит в выборе среди некоторого множества допустимых (т. е. допускаемых обстоятельствами дела) решений (Х) тех решений (х), которые в том или ином смысле можно квалифицировать как оптимальные. При этом допустимость каждого решения понимается в смысле возможности его фактического существования, а оптимальность – в смысле его целесообразности.[4]
Очень многое зависит от того, в каком виде задается допустимое множество Х. Во многих случаях это делается с помощью системы неравенств (равенств): [5]
q1 (х1, х2, … , хn) {? , = , ?} 0,
q2 (х1, х2, … , хn) {? , = , ?} 0, (4.2)
……………………………..
qm (х1, х2, … , хn) {? , = , ?} 0,
где q1, q2, … ,qm – некоторые функции, (х1, х2, … , хn) = х – способ, которым точка х задается набором из нескольких чисел (координат), являясь точкой n-мерного арифметического пространства Rn. Соответственно множество Х есть подмножество в Rn и составляет множество точек (х1, х2, … , хn) I Rn и удовлетворяющих системе неравенств (2.2.2).
Функция f(х) становится функцией n переменных f(х1, х2, … , хn), оптимум (max или min), который требуется найти.
Понятно, что следует найти не только само значение max (min) (х1, х2, … , хn), но и точку или точки, если их больше одной, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений называют оптимальным множеством. [6]
Задача, описанная выше, есть общая задача оптимального (математического) программирования, в основе построения которой лежат принципы оптимальности и системности. Функция f называется целевой функцией, неравенства (равенства) qi (х1, х2, … , хn) {? , = , ?} 0, i = 1, 2, … , m – ограничениями. [7] В большинстве случаев в число ограничений входят условия неотрицательности переменных:
х1 ? 0, х2 ? 0, … , хn ? 0,
или части переменных. Впрочем, это может быть и необязательным.
В зависимости от характера функций-ограничений и целевой функции различают разные виды математического программирования: [8]
1. линейное программирование – функции линейны;
2. нелинейного программирования – хотя бы одна из этих функций нелинейна;
3. квадратичного программирования – f(х) является квадратичной функцией, ограничения линейны;
4. сепарабельное программирование – f(х) представляет собой сумму функций, различных для каждой переменной, условия – ограничения могут быть как линейными, так и нелинейными;
5. целочисленное (линейное или нелинейное) программирование – координаты искомой точки х являются только целыми числами;
6. выпуклое программирование – целевая функция – выпуклая, функции – ограничения – выпуклые, то есть рассматриваются выпуклые функции на выпуклых множествах и т. п.
Наиболее простым и часто встречающимся является случай, когда эти функции линейны и каждая из них имеет вид:
а1х1 + а2х2 + … аnхn + b ,
то есть имеет место задача линейного программирования. Подсчитано, что в настоящее время примерно 80-85% всех решаемых на практике задач оптимизации относятся к задачам линейного программирования.[9]
Сочетая в себе простоту и реалистичность исходных посылок, этот метод вместе с тем обладает огромным потенциалом в области определения наилучших с точки зрения избранного критерия планов.
Первые исследования в области линейного программирования, ставившие своей целью выбор оптимального плана работы в рамках производственного комплекса относятся к концу 30-х годов нашего века и связаны с именем Л.В. Канторовича.[10] В отечественной научной традиции именно его принято считать первым разработчиком этого метода.
В 30-е гг., в период интенсивного экономического и индустриального развития Советского Союза, Канторович был в авангарде математических исследований и стремился применить свои теоретические разработки в практике растущей советской экономики. Такая возможность представилась в 1938 г., когда он был назначен консультантом в лабораторию фанерной фабрики. Перед ним была поставлена задача разработать такой метод распределения ресурсов, который; мог бы максимизировать производительность оборудования, и Канторович, сформулировав проблему с помощью математических терминов, произвел максимизацию линейной функции, подверженной большому количеству ограничителей. Не имея чистого экономического образования, он тем не менее знал, что максимизация при многочисленных ограничениях—это одна из основных экономических проблем и что метод, облегчающий планирование на фанерных фабриках, может быть использован во многих других производствах, будь то определение оптимального использования посевных площадей или наиболее эффективное распределение потоков транспорта.
Говоря о развитии этого метода на Западе, следует сказать о Тьяллинге Купмансе, американском экономисте-математике голландского происхождения.
В миссии торгового флота Купманс пытался так разработать маршруты флотов союзников, чтобы снизить до минимума затраты на доставку грузов. Задача была крайне сложной: тысячи торговых судов везли миллионы тонн грузов по морским путям между сотнями портов, рассеянных по всему миру. Эта работа предоставила возможность Купмансу применить свои математические знания к решению фундаментальной экономической проблемы – оптимальному распределению дефицитных ресурсов между конкурирующими потребителями.
Купманс разработал аналитическую методику, названную анализом деятельности, которая решительно изменила подход экономистов и руководителей к распределению маршрутов. Впервые он описал эту методику в 1942 г., назвав ее «Соотношение между грузами на различных маршрутах» ("Exchange Ratios Between Cargoes on Various Routes"), где показал возможность подхода к проблеме распределения как к математической проблеме максимизации в пределах ограничений. Величина, подлежащая максимальному увеличению, — это стоимость доставленного груза, равная сумме стоимостей грузов, доставленных в каждый из портов. Ограничения были представлены уравнениями, выражающими отношение количества расходуемых факторов производства (например, судов, времени, труда) к количеству груза, доставленному в различные места назначения, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.
При работе над проблемой максимизации Купманс разработал математические уравнения, которые нашли широкое применение как в экономической теории, так и в практике управления. Эти уравнения определяли для каждой из затрат на производство коэффициент, равный цене этой затраты в условиях идеальных конкурентных рынков. Таким образом была установлена основополагающая связь между теориями эффективности производства и теориями распределения через конкурентные рынки. Кроме того, уравнения Купманса представляли большую ценность для центральных планирующих органов, которые могли использовать эти уравнения для определения соответствующих цен на различные затраты, оставляя при этом выбор оптимальных маршрутов на усмотрение местных директоров, обязанность которых состояла в максимизации прибыли. Метод анализа деятельности мог широко применяться любыми руководителями при планировании процессов производства.
В 1975 году Л.В. Канторовичу и Тьяллингу Ч. Купмансу была присуждена Нобелевская премия «за вклад в теорию оптимального распределения ресурсов».
Говоря о первых исследованиях в области линейного программирования, нельзя также не упомянуть еще об одном американском ученом – Джордже Д. Данциге. Конкретная формулировка метода линейного программирования восходит к его работе, выполненной им по заказу ВВС США во время Второй Мировой войны, когда возникла проблема координации действий одной большой организации в таких вопросах, как накопление запасов, производство и содержание оборудования и материально-технического снаряжения, причем имелись альтернативы и ограничения. Кроме того, в свое время Дж. Данцинг работал совместно с В.В. Леонтьевым, и симплекс-метод решения линейных оптимизационных задач (наиболее часто применяемый для их решения) появился в связи с одним из первых практических применений метода межотраслевого баланса.