ВВЕДЕНИЕ

ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ
2.1 Параметры плана
2.2 Целевая функция (план)

3. ФУНКЦИЯ ОДНОЙ ПЕРЕМЕННОЙ
3.1 Определение функции одной переменной и ее свойства
3.2 Исследование функции в экономике. Нахождение максимума прибыли
3.3 Определение глобального экстремума
3.4 Выпуклость, вогнутость функции
3.5 Критерий оптимальности
3.6 Идентификация оптимумов

4. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ
4.1 Методы исключения интервалов
4.1.1 Метод сканирования
4.1.2 Метод деления отрезка пополам
4.1.3 Метод золотого сечения
4.1.4 Сравнительная характеристика методов исключения интервалов
4.2 Полиномиальная апроксимация и методы точечного оценивания
4.2.1 Метод параболической апроксимации
4.2.2 Метод Пуэлла
4.3 Сравнение методов одномерного поиска

5. ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ
5.1 Функции многих переменных, их обозначение и область определения
5.2 Некоторые многомерные функции, используемые в экономике
5.3 Частные производные функции многих переменных
5.4 Экономический смысл частных производных
5.5 Частные производные высших порядков
5.6 Свойства функции нескольких переменных
5.7 Производная по направлению. Градиент. Линии уровня функции
5.8 Экстремум функции многих переменных

6. МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ
6.1 Концепция методов
6.2 Метод градиентного спуска
6.3 Метод наискорейшего спуска

7. КРИТЕРИИ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ С ОГРАНИЧЕНИЯМИ
7.1 Задачи с ограничениями в виде равенств
7.2 Множители Лагранжа
7.3 Экономическая интерпретация множителей Лагранжа
7.4 Условия Куна-Таккера
7.4.1 Условия Куна-Таккера и задача Куна-Таккера
7.5 Теоремы Куна-Таккера
7.6 Условия существования седловой точки

8. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
8.1 Предмет динамического программирования
8.2 Постановка задачи динамического программирования
8.3 Принцып оптимальности и математическое описание динамического процесса управления
8.4 Общая схема применения метода динамического программирования
8.5 Двумерная модель распределения ресурсов
8.6 Дискретная динамическая модель оптимального распределения ресурсов
8.7 Выбор оптимальной стратегии обновления оборудования
8.8 выбор оптимального маршрута перевозки грузов
8.9 Построение оптимальной последовательности операций в коммерческой деятельности

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ РАСЧЕТНО-ГРАФИЧЕСКОГО ЗАДАНИЯ

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 1

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 2

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 3

ЛИТЕРАТУРА

ВВЕДЕНИЕ

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

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

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

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

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

Учебно-практическое пособие для системы дистанционного образования по дисциплине «Методы оптимизации и теория управления» предназначено для самостоятельной работы студента при нестационарной форме контроля знаний.

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

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

Глава 1. ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

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

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

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

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

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

Модель – это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте–оригинале.

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

· установить границы подлежащей оптимизации системы;

· определить количественный критерий, на основе которого можно произвести анализ вариантов с целью выявления «наилучшего»;

· осуществить выбор внутрисистемных переменных, которые используются для определения характеристик и идентификации вариантов;

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

Эта последовательность действий составляет содержание процесса постановки задачи оптимизации .

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

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

Имеется начальное количество средств Р 0 , которое необходи­мо распределить в течение п лет между S предприятиями. Сред­ства и ki (k = 1,..., n; i = 1,..., S) , выделенные в k-м году i-му пред­приятию, приносят доход в размере f ki (u ki) и к концу года возвращаются в количестве j ki (u ki) . В последующем распределе­нии доход может либо участвовать (частично или полностью), ли­бо не участвовать.

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

Количество ресурсов в начале k-го года будем характеризовать величиной P n 1 (параметр состояния). Управление на k-том шаге состоит в выборе переменных u k 1 , u k 2 , …, u ks , обозначающих ресурсы, выделяемые в k-том году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид

Если же некоторая часть дохода участвует в дальнейшем рас­пределении в каком-нибудь году, то к правой части последнего равенства прибавляется соответствующая величина.

Требуется определить п s неотрицательных переменных и ki , удовлетворяющих условиям (2) и максимизирующих функ­цию (1).

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

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

При формулировке задач управления запасами используют следующие понятия.

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

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

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

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

Запасами могут быть товары, поставляемые в магазин опреде­ленными партиями и предназначенные для удовлетворения непрерывного, но подверженного случайным колебаниям поку­пательского спроса. Критерий оптимальности - суммарные за­траты на поставки, хранение запасов и изменение производствен­ного ритма; связи с вариациями спроса.

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

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

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

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

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

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

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

Существует достаточно большое количество численных методов оптимизации. Основные из них можно классифицировать следующим образом:

· по размерности решаемой задачи: одномерные и многомерные;

· по способу формирования шага многомерные методы делятся на следующие виды:

q градиентные:

o по способу вычислений градиента: с парной пробой и с центральной пробой;

o по алгоритму коррекции шага;

o по алгоритму вычисления новой точки: одношаговые и многошаговые;

q безградиентные: с поочередным изменением переменных и с одновременным изменением переменных;

q случайного поиска: с чисто случайной стратегией и со смешанной стратегией;

· по наличию активных ограничений;

· без ограничений (безусловные);

· с ограничениями (условные);

· с ограничениями типа равенств;

· с ограничениями типа неравенств;

· смешанные.

Методы одномерной оптимизации являются базой для некоторых «многомерных» методов. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направлениям. При этом под улучшающей последовательностью понимается такая последовательность х 0 , х 1 , …, х i , …, в каждой точке которой значение критерия оптимальности лучше, чем в предыдущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Случайные методы используются в задачах высокой размерности. Многомерная условная оптимизация учитывает активные ограничения, выраженные в виде равенств и неравенств. В каждом из рассмотренных направлений имеется большое число методов, обладающих своими достоинствами и недостатками, которые зависят, прежде всего, от свойств функций, экстремум которых ищется. Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. Чем это число меньше, тем при прочих равных условиях эффективнее метод.

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

Вопросы к главе 1

1. Почему необходимо использование математики в экономике?

2. Что такое математическая модель?

3. Как строится математическая модель экономического явления и объекта? Приведите пример построения модели.

4. Что такое оптимизация?

5. Какие существуют методы оптимизации?

6. Какие экономические задачи решаются методами оптимизации?

Глава 2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ

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

Рассматривая некоторую произвольную систему, описываемую m уравнениями с n неизвестными, можно выделить три основных типа задач:

· если m = n , то з адачу называют алгебраической. Такая задача обычно имеет единственное решение;

· если m > n , то задача переопределена, как правило, не имеет решений ;

· если m < n , то задача недоопределена, имеет бесконечно много решений .

В практике чаще всего приходится иметь дело с задачами третьего типа.

Введем ряд определений.

2.1. Параметры плана

Определение. Параметры плана – это независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу.

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

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

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

Обозначения. Обычно число проектных параметров обозначают через n, х – сами проектные параметры с соответствующими индексами

х 1 , х 2 , …, х n – n проектных параметров задачи.

2.2. Целевая функция (план)

Определение. Целевая функция – выражение, значение которого стремимся сделать максимальным или минимальным.

Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (n+1) -мерную поверхность.

1) Если имеется только один проектный параметр, то целевую функцию можно представить кривой на плоскости (рис. 1).

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

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

Целевая функция в ряде случаев может быть представлена:

· кусочно-гладкой функцией;

· таблицей;

· только целыми значениями;

· двумя значениями – да или нет (дискретная функция).

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

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

Вопросы к главе 2

1. Что такое параметры плана?

2. Приведите пример параметров плана.

3. Дайте определение целевой функции.

4. Как изображается целевая функция?

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

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

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

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

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

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

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

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

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

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

2) строго определенный критерий оценки оптимальности;

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

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

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

Найти max (min) f(x) при условии, что переменная х (точка х) пробегает некоторое заданное множество Х:

f(x) ® max (min), х I Х (4.1)

Определенная таким образом задача называется задачей оптимизации. Множество Х называется допустимым множеством данной задачи, а функция f(x) – целевой функцией.

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

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

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), но и точку или точки, если их больше одной, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений называют оптимальным множеством.

Задача, описанная выше, есть общая задача оптимального (математического) программирования, в основе построения которой лежат принципы оптимальности и системности. Функция f называется целевой функцией, неравенства (равенства) qi (х1, х2, … , хn) {? , = , ?} 0, i = 1, 2, … , m – ограничениями. В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х1 ? 0, х2 ? 0, … , хn ? 0,

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

В зависимости от характера функций-ограничений и целевой функции различают разные виды математического программирования:

1. линейное программирование – функции линейны;

2. нелинейного программирования – хотя бы одна из этих функций нелинейна;

3. квадратичного программирования – f(х) является квадратичной функцией, ограничения линейны;

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

5. целочисленное (линейное или нелинейное) программирование – координаты искомой точки х являются только целыми числами;

6. выпуклое программирование – целевая функция – выпуклая, функции – ограничения – выпуклые, то есть рассматриваются выпуклые функции на выпуклых множествах и т. п.

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

а1х1 + а2х2 + … аnхn + b ,

то есть имеет место задача линейного программирования. Подсчитано, что в настоящее время примерно 80-85% всех решаемых на практике задач оптимизации относятся к задачам линейного программирования.

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

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

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

Говоря о развитии этого метода на Западе, следует сказать о Тьяллинге Купмансе, американском экономисте-математике голландского происхождения.

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

Купманс разработал аналитическую методи­ку, названную анализом деятельности, которая решительно изменила подход экономистов и руководителей к распре­делению маршрутов. Впервые он описал эту методику в 1942 г., назвав ее «Соот­ношение между грузами на различных маршрутах» ("Exchange Ratios Between Cargoes on Various Routes"), где показал возможность подхода к проблеме рас­пределения как к математической про­блеме максимизации в пределах ограни­чений. Величина, подлежащая макси­мальному увеличению, - это стоимость доставленного груза, равная сумме стои­мостей грузов, доставленных в каждый из портов. Ограничения были представ­лены уравнениями, выражающими отно­шение количества расходуемых факто­ров производства (например, судов, вре­мени, труда) к количеству груза, достав­ленному в различные места назначения, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.

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

В 1975 году Л.В. Канторовичу и Тьяллингу Ч. Купмансу была присуждена Нобелевская премия «за вклад в теорию оптимального распределения ресурсов».

Говоря о первых исследованиях в области линейного программирования, нельзя также не упомянуть еще об одном американском ученом – Джордже Д. Данциге. Конкретная формулировка метода линейного программирования восходит к его работе, выполненной им по заказу ВВС США во время Второй Мировой войны, когда возникла проблема координации действий одной большой организации в таких вопросах, как накопление запасов, производство и содержание оборудования и материально-технического снаряжения, причем имелись альтернативы и ограничения. Кроме того, в свое время Дж. Данцинг работал совместно с В.В. Леонтьевым, и симплекс-метод решения линейных оптимизационных задач (наиболее часто применяемый для их решения) появился в связи с одним из первых практических применений метода межотраслевого баланса.

Федеральное агентство по образованию ГОУ ВПО «Уральский государственный технический университет - УПИ» ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ РАДИОЭЛЕКТРОННЫХ СХЕМ Методические указания к лабораторной работе по курсу “Компьютерный анализ электронных схем” для студентов всех форм обучения специальности 200700 - Радиотехника Екатеринбург 2005 УДК 681,3,06:621.396.6 Составители В.В. Кийков, В.Ф. Кочкина, К.А. Вдовкин Научный редактор доц., канд. техн. наук В.И. Гадзиковский ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ РАДИОЭЛЕКТРОННЫХ СХЕМ: методические указания к лабораторной работе по курсу «Компьютерный анализ электронных схем” /сост. В.В. Кийко, В.Ф. Кочкина, К.А. Вдовкин. Екатеринбуг: ГОУ ВПО УГТУ-УПИ, 2005. 21с. Методические указания содержат сведения о постановке задач оптимизации, критериях оптимальности, теории поиска минимума целевой функции. Приведен обзор методов параметрической оптимизации, подробно описан метод Хука - Дживса, даны вопросы для самоконтроля. Библиогр.: 7 назв. Рис. 6. Подготовлено кафедрой “Радиоэлектроника информационных систем”.  ГОУ ВПО «Уральский государственный технический университет-УПИ», 2005 2 ОГЛАВЛЕНИЕ ЦЕЛЬ РАБОТЫ........................................................................................................... 4 1.ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ.......................................................... 4 2. ТЕОРИЯ ОПТИМИЗАЦИИ.................................................................................. 4 2.1. Формальная (математическая) постановка задачи оптимизации............. 4 2.2. Постановка задачи параметрической оптимизации РЭС............................ 5 2.3. Критерии оптимальности................................................................................... 7 2.4. Стратегия решения задач оптимального проектирования РЭС................ 9 2.5. Алгоритмы глобального поиска .................................................................. 9 2.5.1. Алгоритм случайного поиска....................................................................... 10 2.5.2. Монотонный алгоритм глобального поиска............................................. 10 2.5.3. Алгоритм сканирования на сетке кода Грея............................................. 10 2.6. Методы и алгоритмы локального поиска..................................................... 11 2.6.1. Прямые методы............................................................................................... 11 2.6.2. Градиентные методы оптимизации первого порядка............................. 13 2.6.3. Градиентные методы оптимизации второго порядка............................. 13 3. ОПИСАНИЕ КОМПЬЮТЕРНОЙ ПРОГРАММЫ АНАЛИЗА.................. 15 3.1. Запуск программы............................................................................................. 15 3.2. Составление задания на оптимизацию.......................................................... 15 3.3. Результаты оптимизации................................................................................. 17 4. СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ............................................... 19 4.1. Порядок выполнения........................................................................................ 19 4.2. Задание к лабораторной работе....................................................................... 19 5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ ИСХОДНЫХ ДАННЫХ.................................................................................................................... 20 6. СОДЕРЖАНИЕ ОТЧЕТА................................................................................ 20 7. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ............................................................ 20 СПИСОК ЛИТЕРАТУРЫ........................................................................................... 21 3 ЦЕЛЬ РАБОТЫ Получить представление и практические навыки параметрической оптимизации РЭС при автоматизированном схемотехническом проектировании радиоэлектронной аппаратуры (РЭА). 1.ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ Данная работа является третей в комплексе лабораторных работ по методам расчета, анализа и оптимизации радиоэлектронных схем. В комплекс входят следующие работы: 1. Расчет радиоэлектронных схем методом узловых потенциалов. 2. Анализ электронных схем модифицированным методом узловых потенциалов. 3. Параметрическая оптимизация радиоэлектронных схем. 4. Анализ радиоэлектронных схем с помощью схемных функций. В первой и второй лабораторных работах выполнены частотный анализ, определены чувствительности коэффициента усиления по напряжению от вариаций внутренних параметров, рассчитаны переходная и импульсная характеристики при номинальных значениях параметров элементов РЭС, которые первоначально выбраны (заданы или рассчитаны) не лучшим образом. В этой работе выполняется параметрическая оптимизация проектируемой РЭС для обеспечения соответствия выходных параметров требованиям технического задания. 2. ТЕОРИЯ ОПТИМИЗАЦИИ 2.1. Формальная (математическая) постановка задачи оптимизации Оптимизацией параметров (параметрической оптимизацией) принято называть задачу расчета оптимальных номинальных значений внутренних параметров объекта проектирования. Задачи оптимизации параметров в САПР радиоэлектронной аппаратуры сводятся к задачи математического программирования extr F(X), XXД, (1) где XД = {XX0| k (X) ≥ 0, r (X) = 0, k  , r  }. Вектор X=(x1, x2, . . . . xn) называется вектором управляемых (варьируемых) параметров; F(X) - целая функция (функция качества); XД - допустимая область; X0 - пространство, в котором определена целевая функция; k(X) и r(X) функции - ограничения. 4 Словесная формулировка задачи (1): найти экстремум целевой функции F(X) в пределах области XД, ограниченной в пространстве X0 N неравенствами k(X) ≥ 0 и М равенствами r (X) = 0. Целевая функция должна быть сформулирована исходя из имеющихся представлений о качестве проектируемого объекта: её значение должно уменьшаться с улучшением качества, тогда в (1) требуется минимизация (extr есть min), или увеличиваться, тогда в (1) требуется максимизация (extr есть max). Ограничения - неравенства, имеющие вид xi > xi min или xi < xi max , называют прямыми ограничениями, где xi min и xi max - заданные константы, остальные ограничения называют функциональными. Задача поиска максимума, как правило, сводится к задаче поиска минимума путем замены F(Х) на -F(Х). Функция F(Х) имеет локальный минимум в точке Х0, если в малой окрестности этой точки F(Х) ≥ F(Х0). И функция F(Х) имеет глобальный минимум в точке Х*, если для всех Х справедливо неравенство F(Х) ≥ F(Х*). Классическая теория оптимизации подробно изложена в соответствующей литературе, например . Ниже основное внимание уделено применению теории оптимизации для поиска оптимальных решений при проектировании радиоэлектронной аппаратуры. 2.2. Постановка задачи параметрической оптимизации РЭС Решение задачи проектирования обычно связана с выбором оптимального, наилучшим образом удовлетворяющего требованиям технического задания варианта устройства из некоторого допустимого множества решений. Эффективное решение задач базируется на формальных поисковых методах оптимизации и неформальных способах принятия оптимальных проектных решений. Поэтому решение задач оптимального проектирования необходимо рассматривать не только в вычислительном аспекте, но скорее в творческом, учитывая опыт и знания инженера-схемотехника на всех этапах автоматизированного проектирования. Одной из наиболее cложных операций при решении задач оптимального проектирования является этап математической формулировки задачи, которая включает в себя выбор критерия оптимальности, определение варьируемых параметров и задание ограничений, накладываемых на варьируемые параметры . Среди задач схемотехнического проектирования, которые целесообразно решать с привлечением методов оптимизации, выделяют следующие задачи параметрического синтеза и оптимизации: - определение параметров компонентов схемы, обеспечивающих экстремальные характеристики при заданных ограничениях; - определение параметров функциональных узлов схем исходя из требований технического задания на характеристики устройства в целом; - адаптация существующих схемных решений с целью подбора параметров, удовлетворяющих новым требованиям к схеме; 5 - уточнение значений параметров компонентов схемы, полученных в результате ручного инженерного расчета. Для схем приемно-усилительной техники оптимизация ведется по отношению к таким выходным параметрам, как: - коэффициент усиления и полоса пропускания: - форма частотной характеристики; - устойчивость усилителя или активного фильтра; - время запаздывания, длительность фронта импульса. Примечание. Класс задач, связанный с определением значений параметров компонентов, при которых проектируемая схема удовлетворяет совокупности условий технического задания на разработку, принято называть параметрическим синтезом (по отношению к определяемым параметрам) или параметрической оптимизацией (по отношению к реализуемым характеристикам). В любой из перечисленных задач реализуемые характеристики проектируемого устройства являются функциями вектора варьируемых (настраиваемых) параметров, составляющих некоторое подмножество полного набора параметров компонентов схемы. Целью параметрического синтеза или оптимизации является определение вектора параметров X, обеспечивающего наилучшее соответствие характеристик устройства Y = Y(X) требованиям технического задания. Для решения этой задачи необходимо, прежде всего, выбрать формальный критерий оценки качества каждого из вариантов проектируемого устройства, который позволил бы различать их между собой и устанавливать между ними отношения предпочтения. Такая оценка может быть представлена функциональной зависимостью вида F(X) =F(Y(X)), называемой обычно критерием оптимальности, функцией качества или целевой функцией. Задача поиска параметров компонентов схемы сводится к классической задаче оптимизации - нахождения экстремума некоторой функции качества F(X) при наличии ограничений (равенств, неравенств или двухсторонних границ), накладываемых на варьируемые параметры и характеристики проектируемой схемы . Разнообразные задачи оптимизации аналоговых радиоэлектронных схем имеют общие черты, основные из которых: - многокритериальность оптимизационных задач; - отсутствие явных аналитических зависимостей выходных параметров от внутренних параметров, связь между внутренними и внешними параметрами выражается системами уравнений и оценивается количественно только через численное решение этих систем. Эти особенности обуславливают трудности постановки и решения задач оптимизации аналоговых радиоэлектронных схем. 6 2.3. Критерии оптимальности В процессе поиска оптимального решения для каждой конкретной задачи может оказаться предпочтительным определенный вид критерия оптимальности. Базовый набор критериев оптимальности, позволяющий удовлетворить разнообразные требования инженера-схемотехника к оптимизируемым характеристикам проектируемых устройств, изложен в . Так, для отыскания экстремума (минимума или максимума) показателя качества, например, как потребляемая схемой мощность, частота среза, используется само значение критерия оптимальности без преобразования: F1(X) = Y(X), (2) В задачах, требующих максимального соответствия оптимизируемой характеристики и некоторой желаемой, например, при оптимизации частотных характеристик, наиболее целесообразно использовать критерий среднего квадратического отклонения F2 ()  (Y() - Y )2 , (3) где Y* - желаемое или требуемое по техническому заданию значение характеристики, () - знак усреднения. Для характеристики, заданной дискретным набором точек, целевая функция 1 F2 (X)  N N  (Y(X , p i 1 i)  Yi)2 , * i (4) где N - число точек дискретизации независимой переменной р; Y(Х, рi) - значение оптимизируемой характеристики в i-ой точке интервала дискретизации; i - весовой коэффициент i-го значения оптимизируемой характеристики, отражающей важность i-ой точки по сравнению с другими (как правило, 0 < i > 1). Минимизация функции (3) и (4) обеспечивает близость характеристик по среднему квадратическому отклонению. Функция (4) используется при численных методах вычисления Y(Х). В некоторых задачах оптимизации необходимо обеспечить превышение или не превышение оптимизируемой характеристикой некоторого заданного уровня. Эти критерии оптимальности реализуются следующими функциями: - для обеспечения превышения заданного уровня F3 (X)  0 при Y (X)  YH* ; (Y  Y (X)) 2 приY (X)  YH* ; 7 (5) - для обеспечения непревышения заданного уровня F4 (X)  0 при Y (X)  YB* (Y (X)  YB*) 2 при Y (X)  YB* , (6) где YH*,YB* - нижняя и верхняя границы допустимой области для характеристики Y(X). Если необходимо, чтобы оптимизируемая характеристика проходила в некоторой допустимой зоне (коридоре), используют комбинацию двух предыдущих критериев оптимальности: 0приYH*  Y (X)  YB* ; F(X)  (Y (X)  YB*) 2 приY (X)  YB* , (YH*  Y (X)) 2 приY (X)  YH* . (7) В тех случаях, когда требуется реализовать лишь форму кривой, игнорируя при этом постоянное смещение по вертикали, используется критерий сдвига N F6 (X)    i (Yi *  Y (X , pi)  Yср) 2 , (8) i 1 где Yср  1 N *  (Yi  Y (X , pi)). N i 1 От вида целевой функции зависят важные характеристики вычислительного процесса и, в первую очередь, сходимость процесса оптимизации. Знаки производных целевой функции по управляемым параметрам не остаются постоянными во всей допустимой области. Для целевых функций вида (4) и (8) последнее обстоятельство ведет к их овражному характеру . Таким образом, особенностью целевых функций при решении задач схемотехнического проектирования является их овражный характер, что приводит к большим вычислительным затратам и требует особого внимания к выбору метода оптимизации. Другой особенностью целевых функций является то, что они обычно многоэкстремальные и наряду с глобальным минимумом имеются локальные минимумы. Особенность задач оптимизации электронных схем заключается и в том, что внутренние параметры не могут принимать произвольных значений. Так, величины резисторов и конденсаторов ограничены некоторыми максимальными и минимальными значениями. Кроме того, из нескольких внешних параметров обычно можно выделить один основной, по которому проводится оптимизация, а для других указать допустимые границы изменения. 8 Оптимизационная задача с ограничениями сводится к задаче оптимизации без ограничений с помощью введения штрафных функций. Целевая функция при этом приобретает вид M N r 1 k 1  (X)  Fi (X)   r ( Т (X)) 2    k ( k (X)) 2 , (9) где r , k - численные коэффициенты, учитывающие важность того или иного ограничения относительно других. Они равны нулю при удовлетворении соответствующему неравенству из (1) и принимают некоторые значения в противном случае; Fi(X) - одна из функций качеств, описанных соотношением (2) - (8). Тем самым выход за пределы допустимой области ХД приводит к увеличению минимизируемой функции цепи и промежуточные решения X j удерживаются «барьером» на границе области ХД. Высота «барьера» определяется значениями  и , которые на практике находятся в широких пределах (1-1010). Чем больше  и , тем меньше вероятность выхода за пределы допустимой области. Одновременно возрастает и крутизна склона оврага на границе, что замедляет или полностью нарушает сходимость процесса минимизации. В связи с невозможностью указать оптимальные значения  и  целесообразно начать оптимизацию с малых значений, увеличивая их затем при получении решения за пределами допустимой области. 2.4. Стратегия решения задач оптимального проектирования РЭС Задачи оптимального проектирования РЭС обладают специфическими особенностями, к которым относят многоэкстремальность и овражность функции качества, наличие ограничений на внутренние и выходные параметры проектируемого устройства, большую размерность вектора варьируемых параметров. Стратегия решения задач оптимального проектирования предусматривает применение глобальных процедур оптимизации на начальных этапах поиска и уточнение полученного глобального решения быстросходящимися в окрестности оптимальной точки локальными алгоритмами. Такая стратегия позволяет, вопервых, с достаточной надежностью и точностью определить значение глобального экстремума и, во-вторых, существенно снизить вычислительные затраты на поиск. При этом этапы глобального поиска могут выполняться с невысокой точностью, а этапы локального уточнения проводятся в области притяжения глобального экстремума, что требует значительно меньшего числа вычислений. 2.5. Алгоритмы глобального поиска Алгоритмы глобального поиска, как правило, дают достаточно грубую оценку глобального экстремума при небольших затратах вычислительных 9 ресурсов и требуют значительного увеличения числа вычислений для получения более точной оценки положения экстремума. 2.5.1. Алгоритм случайного поиска Наиболее простым, с точки зрения реализации вычислительного процесса, является алгоритм поиска глобального экстремума, основанный на зондировании допустимой области ХД последовательностью равномерно распределенных в ней точек с отбором наилучшего варианта из полученных. Качество работы алгоритма во многом определяется свойствами датчика равномерно распределенных случайных чисел, используемых для генерации векторов Х  ХД 2.5.2. Монотонный алгоритм глобального поиска Многомерная оптимизация этим алгоритмом основана на построении развертки (кривой Пеано), отображающей отрезок вещественной оси в гиперкуб допустимой области ХД. С помощью развертки осуществляется однозначное и непрерывное отображение Х(), которое для любой точки 0,1 позволяет получить точку Х  ХД. Тогда задача минимизации F(X) в области ХД эквивалентна поиску минимума * одномерной функции F(X) = F(X()). Для проведения глобальной одномерной минимизации функции F() на интервале 0,1 в подсистеме оптимизации системы схемотехнического проектирования ДИСП используется монотонная модификация алгоритма глобального поиска, реализующая для ускорения сходимости монотонное преобразование F() в виде  ()  { 1  [ 1  F ()] 2 }0 ,5 , (10) которое сохраняет расположение точки глобального экстремума, но делает функцию более гладкой. Алгоритм дает достаточно хорошую оценку глобального экстремума в пределах первых 50-100 итераций. Наилучшие результаты получаются, если число переменных не превышает 5-7. Для рассмотренного алгоритма в ряде случаев лучшие результаты удается получить при использовании преобразования пространства поиска по логарифмическому закону. Такое преобразование особенно эффективно, если границы поиска различаются на несколько порядков, что актуально в задачах оптимизации РЭА, и если экстремум находится вблизи границ области. 2.5.3. Алгоритм сканирования на сетке кода Грея Основная идея метода состоит в последовательном изменении специфической сферы поиска с характерными лучами, содержащими точки испытаний, при накоплении и обработке полученной информации. Направление сканирования осуществляется на особой сетке, задаваемой двоичным кодом 10 Грея. Сфера поиска на сетке кода Грея в рассматриваемом алгоритме отличается от традиционной (круг при числе переменных, равном 2) и имеет дополнительно к кругу характерные лучи. Лучи направлены от центра сферы к границам области ХД и тем самым как бы «просвечивают» всю область до ее границ. Рассматриваемый алгоритм имеет единственный настраиваемый параметр -чувствительность функции качества к вариациям параметров, которая используется для определения шага дискретности по каждой из переменных. 2.6. Методы и алгоритмы локального поиска Методы и алгоритмы локального поиска чаще всего отыскивают ближайший локальный экстремум, а траектория их движения сильно зависит от выбора начальной точки и характера целевой функции. 2.6.1. Прямые методы Методы нулевого порядка (прямые методы) в основе своей не имеют строгого математического обоснования и строятся на основании разумных предложений и эмпирических данных. Простейшим методом нулевого порядка является метод покоординатного спуска (Гаусса-Зейделя). На каждом шаге фиксируются все переменные, кроме одной, по которой определяется минимум целевой функции. Последовательным перебором переменных достигается оптимизация. Этот алгоритм оказывается неэффективным, если целевая функция содержит выражения типа x1x2. Для задач схемотехнического проектирования, в которых не удается получить аналитического выражения целевой функции, характерна ее сложная зависимость от компонентов схемы, и поэтому этот метод обычно неприменим. Из методов нулевого порядка в случае овражных целевых функций хорошие результаты дает метод Розенброка , в котором объединены идеи покоординатного спуска и идеи преобразования координат. Наилучшим направлением поиска экстремума является движение вдоль оврага. Поэтому после первого цикла покоординатного спуска производится поворот осей координат так, чтобы одна из них совпадала с направлением оврага Xk - Xk - n, k = n, 2n, 3n…. Метод Розенброка не дает информации о попадании в точку минимума. Поэтому счет прекращается либо после того, как уменьшение F(X) станет меньше некоторого малого числа , либо после определенного количества циклов. Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным . Поиск минимума целевой функции состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой в случае успеха следует поиск по образцу. Эта процедура состоит из следующих шагов: 1. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j=1,2,…,n скалярной целевой функции F(X). 11 2. Вычислить F(X) в базисной точке b1 с целью получения сведений о локальном поведении функции F(X). Эти сведения будут использоваться для нахождения направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции F(X). Значение функции F(X) в базисной точке b1 находиться следующим образом: a) вычисляется значение функции F(b1) в базисной точке b1; б) каждая переменная по очереди изменяется изменением шага. Таким образом, вычисляется значение F(b1 + he1), где e1- единичный вектор в направлении оси x1. Если это приводит к уменьшению значений функции, то b1 заменяется на b1 + he1. В противном случае вычисляется значение функции F(b1 - he1), и если ее значение уменьшилось, то b1 заменяется на b1 - he1. Если не один из проделанных шагов не приводит к уменьшению значений функции, то точка b1 остается неизменной и рассматривают изменения в направлении оси x2, т. е. находится значение функции F(b1 + h2e2) и т. д. Когда будут рассмотрены все n переменные, определяется новая базисная точка b2; в) если b2 = b1 , т. е. уменьшение функции F(X) не было достигнуто, то исследование продолжается вокруг той же базисной точке b1 , но с уменьшенной длиной шага. Как правило, на практике шаг уменьшают в 10 раз от начальной длины; г) если b2  b1 , то производится поиск по образцу. 3. При поиске используется информация, полученная в процессе исследования, и минимизация целевой функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом: а) движение осуществляется из базисной точке b2 в направлении b2 - b1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции F(X). Поэтому вычисляется значения функции в точке образца P1 = b2 + (b2 - b1). В общем случае Pi = 2bi+1 - bi; б) выполняется исследование вокруг точки P1(Pi); в) если наименьшее значение на шаге 3,б меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3(bi+2), после чего повторяется шаг 3,а. В противном случае не производится поиск по образцу из точки b2 (bi+1). 4. Завершается процесс поиска минимума, когда длина шага (длины шагов) будет уменьшена до заданного малого значения. 12 2.6.2. Градиентные методы оптимизации первого порядка Методы отыскания экстремума, использующие производные, имеют строгое математическое обоснование . Известно, что при отыскании экстремума не существует лучшего направления, чем движение по градиенту . Из градиентных методов одним из наиболее эффективных является метод Флетчера-Пауэлла (сопряженных градиентов), являющихся разновидность метода наискорейшего спуска. Метод наискорейшего спуска состоит из следующих этапов: 1) задается начальная точка (вектор Xk k=0); 2) вычисляются F(Xk) и F(Xk); 3) производится изменение X в направлении Sk = -F(Xk) до тех пор, пока F(X) перестанет убывать; 4) полагается k = k+1, вычисляется новое значение F(Xk) и процесс повторяется с 3-го этапа. Недостаток метода заключается в том, что при овражных функциях приближение к минимуму имеет зигзагообразный характер и требует большое число итераций. Суть метода Флетчера-Пауэлла состоит в том, что при всех итерациях, начиная со второй (на первой итерации этот метод совпадает с методом наискорейшего спуска), используются предыдущие значения F(X) и F(X) для определения нового вектора направления   S k  F X k  d k S k 1 , где (11) [F (X k)]T  F (X k) d . [F (X k 1)]T  F (X k 1) Тем самым исключается зигзагообразный характер спуска и ускоряется сходимость. Этот алгоритм прост для программирования, и при этом требуется умеренный объем машинной памяти (необходимо заполнить только предыдущее направление поиска и предыдущий градиент). 2.6.3. Градиентные методы оптимизации второго порядка Итерационный метод, основанный на знании вторых производных, в общем случае известен как метод Ньютона. Пусть функция F(X) разложена в ряд Тейлора и в нем удержано три члена. Результат запишем в следующем виде: 1 F (X k  X)  F (X k)  (X)T F k  (X)T G k X 2 (12) Требуется максимизировать разность, стоящую в левой части. Это можно сделать дифференцированием (12) по Х и приравниванием результата к нулю: 13  [ F (X k  X)  F (X k)]  F k  G k X  0, X G k X  F k . Это уравнение можно решить, например, методом LU-разложения, относительно Х. Формально можно записать X  (G k) 1 F k   H k F k где Н=G-1. Направление поиска полагаем теперь совпадающим с вектором S k  X k   H k F k . (13) При переходе к минимуму матрица Гессе1 будет положительно определенной и можно использовать полный размер шага dk=1 (т.е. не нужен поиск в направлении Sk). Однако вдали от минимума матрица Гессе может и не быть положительно определенной. Более того, вычисление этой матрицы требует больших затрат. Поэтому разработан целый класс других методов, называемых методами с переменной метрикой или квазиньютоновскими, которые лишены этих недостатков . Эти методы были разработаны довольно давно, но обобщены только в последнее время. Они базируются на оценке градиентов и на аппроксимации матрицы Гессе или обратной к ней. Аппроксимация достигается изменением исходной положительно определенной матрицы специальным образом так, чтобы сохранить положительную определенность. Только при достижении минимума полученная матрица аппроксимирует матрицу Гессе (или обратную к ней). Во всех методах этого класса направление поиска определяется, как и в методе Ньютона (13). На каждой итерации по матрице Hk согласно специальной формуле получают матрицу Hk+1. В качестве примера приведем формулу, полученную Дэвидоном, Флетчером и Пауэллом , и ее иногда называют ДФП-формулой:  2F 2F 2F  . . .   x1x n   x1x1 x1x 2  2F 2F 2F  . . .   1 Матрица Гессе - матрица вторых производных G (x)   x 2 x1 x 2 x 2 x 2 x n   .  . .    2F 2F 2F   x x x x . . . x x  n 2 n n   n 1 14 H k 1 X (X)T H k  T H k H   T k (X)T   H  k (14) Эта формула пригодна только в случае, если (X)Т   0,  ТHk  0. Здесь k=Fk+1-Fk. 3. ОПИСАНИЕ КОМПЬЮТЕРНОЙ ПРОГРАММЫ АНАЛИЗА Программа имеет удобный графический пользовательский интерфейс для работы в среде операционной системы Windows. Исходным описанием оптимизируемой электронной схемы является информация в файле, созданном при выполнении второй лабораторной работы. Загрузив этот файл и выбрав элементы для оптимизации, с помощью этой программы выполняется расчет новых значений элементов. Критерием правильности расчетов является значение минимума целевой функции, которая рассчитывается как взвешенное среднеквадратическое отклонение требуемой и реальной характеристики РЭС: амплитудно-частотной, переходной или импульсной характеристик. Программа имеет стандартный набор элементов управления - меню, панель инструментов … . Автоматически создается отчет о проведенной лабораторной работе в html - формате. Примечание. После всех заполнений диалоговых окон значениями, нажимается кнопка <Далее>. Если отображаемый в последующем окне результат не устраивает, то нажатием кнопки <Назад> можно вернуться к предыдущим шагам и изменить условия поиска. 3.1. Запуск программы При запуске программы открывается окно, в котором в строке меню Файл необходимо открыть файл, сохраненный после выполнения второй лабораторной работы (рис. 1). 3.2. Составление задания на оптимизацию В файле с описанием схемы содержатся параметры элементов, включая схему замещения транзистора. В левом окне необходимо выбрать варьируемые параметры для параметрической оптимизации. Требуемая характеристика, например АЧХ, задается значениями частоты (в Гц) и соответствующими значениями коэффициента усиления (в Дб). На следующем этапе задается начальный шаг измерения параметров при оптимизации (рис. 2). 15 Рис. 1. Окно открытия входного файла Рис. 2. Окно выбора значений оптимизации 16 3.3. Результаты оптимизации На следующем этапе программа представляет результаты расчетов:  минимум целевой функции;  параметры варьируемых элементов до и после оптимизации;  количество вычислений целевой функции;  количество уменьшений длины шага и поисков по образцу. Критерием правильности полученных результатов является значение минимума целевой функции. Для биполярного транзистора оно должно быть примерно 10-7 I10-8, а для полевого транзистора - 10-4 I 10-5 (рис. 3). Если результаты оптимизации устраивают, то переходим к следующему этапу - построению амплитудно-частотной или временных характеристик (рис. 4, 6,). Для точного определения (нахождения) полосы пропускания РЭС, т.е. верхней и нижней граничных частот, а так же для определения времени переходных процессов имеются таблицы расчетов (рис. 5). Рис. 3. Окно расчетов после оптимизации 17 Рис. 4. Окно построения АЧХ Рис. 5. Значения АЧХ в таблице 18 Рис. 6. Окно временных характеристик 4. СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ 4.1. Порядок выполнения 1. Подготовленный этап включает ознакомление с методическими указаниями к лабораторной работе, изучение теории оптимизации по конспекту лекций, литературным источникам и разделу 2 данных методических указаний. 2. Второй этап включает в себя выполнение теоретической работы: - формирование требований к оптимизируемой характеристике РЭС; - выбор элемента или элементов схемы, по параметрам которых предполагается осуществлять оптимизацию. 3. Загрузка программы-оптимизации с описанием оптимизируемой схемы и заданием на параметрическую оптимизацию. 4. Выполнение оптимизации. 5. Расчет характеристики схемы с оптимизированными параметрами. 6. Заключительный этап. На этом этапе сравниваются характеристики РЭС до и после оптимизации. По полученным материалам составляется отчет на листах формата А4 (297х210) с обязательным приложением распечаток результатов. 4.2. Задание к лабораторной работе 1. По результатам анализа АЧХ усилителя, полученной во второй лабораторной работе, сформировать требования к идеальной АЧХ. Выбрать способ задания идеальной АЧХ и координаты точек на графике АЧХ. 19 2. Определить группу элементов, по параметрам которых предполагается осуществить оптимизацию. 5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ ИСХОДНЫХ ДАННЫХ 5.1. По графику АЧХ, рассчитанной при выполнении второй лабораторной работы, определяются верхняя и нижняя граничные частоты и выясняется влияние высокочастотной индуктивной коррекции. 5.2. Пользуясь знаниями схемотехники усилительных устройств, определяются компоненты, параметры которых определяют верхнюю и нижнюю граничные частоты. 5.3. На графике АЧХ строится идеальная (требуемая по техническому заданию) характеристика. Выбираются точки оптимизации. Для того чтобы сохранить вид АЧХ в полосе пропускания, необходимо также выбрать точки и в этой части характеристики. 6. СОДЕРЖАНИЕ ОТЧЕТА 1. Цель работы. 2. Исходные данные в виде принципиальной электрической схемы усилительного каскада и параметров его элементов до оптимизации. 3. Листинг результатов машинного анализа. 4. Анализ результатов. Выводы. 7. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Назовите необходимое и достаточное условие существования минимума функции. 2. Какая матрица называется положительно определенной? 3. Почему целевую функцию называют функцией качества? 4. Назовите основное свойство целевой функции. 5. Какие задачи называют параметрическим синтезом, а какие - параметрической оптимизацией? 6. В каких случаях задача численного поиска минимума целевой функции относятся к задачам нелинейного программирования? 7. В чем отличие градиентных методов поиска экстремума функции от прямых методов? 8. Поясните понятие глобальный и локальный минимум. 9. Чем обусловлены ограничения при параметрической оптимизации радиоэлектронных устройств? 10. Поясните метод покоординатного спуска. 11. Чем отличается метод сопряженных градиентов от метода наискорейшего спуска? 12. Что означает в методе Хука - Дживса «поиск по образцу»? 13. Каковы критерии окончания итерационного процесса оптимизации? 20 СПИСОК ЛИТЕРАТУРЫ 1. Системы автоматизированного проектирования в радиоэлектронике: Справочник/Е.В. Авдеев, А.Т. Еремин, И.П. Норенков, М.И. Песков; Под ред. И.П.Норенкова. М.: Радио и связь, 1986. 368с. 2. Банди Б. Метода оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. 128с. 3. Влах И., Сингхал К. Машинные методы анализа и проектирования электронных схем. М.: Радио и связь. 1988. 560с. 4. Сборник задач по микросхемотехнике: Автоматизированное проектирование: Учебное пособие для вузов /В.И. Анисимов, П.П. Азбелев, А.Б. Исаков и др.; Под ред. В.И. Анисимова. Л.:Энергоатомиздат, Ленинградское отд-ие, 1991. 224с. 5. Диалоговые системы схемотехнического проектирования/ В.Н. Анисимов, Г.Д. Дмитриевич, К.Б. Скобельцын и др.; Под ред. В.Н. Анисимова. М.: Радио и связь, 1988. 288с. 6. Разевич В.Д., Раков В.К., Капустян В.И. Машинный анализи оптимизация электронных схем: Учебное пособие по курсам «Усилительные устройства» и «Радиоприемные устройства». М.:МЭИ, 1981. 88с. 7. Учебник по матанализу/ Табуева В.А. Математика, математический анализ: Учебное пособие. Екатеринбург: УГТУ-УПИ, 2001. 494с. 8. Кийко В.В. Кочкина В.Ф. Вдовкин К.А. Анализ электронных схем модифицированным методом узловых потенциалов. Екатеринбург: УГТУУПИ, 2004. 31с. 21

3.2.1. Линейное программирование

Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F (X ) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х 1 - число изготовленных стульев, Х 2 - число сделанных столов. Задача оптимизации имеет вид:

45 Х 1 + 80 Х 2 → max ,

5 Х 1 + 20 Х 2 ≤ 400 ,

10 Х 1 + 15 Х 2 ≤ 450 ,

Х 1 ≥ 0 ,

Х 2 ≥ 0 .

В первой строке выписана целевая функция - прибыль при выпуске Х 1 стульев и Х 2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х 1 и Х 2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х 1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х 1 положительно. Но невозможно представить себе отрицательный выпуск - Х 1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х 1 , а по вертикальной оси ординат - значения Х 2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х 1 , Х 2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на

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

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х 1 , Х 2), или, в других терминах, множество А , задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

5 Х 1 + 20 Х 2 = 400 ,

10 Х 1 + 15 Х 2 = 450 .

Из первого уравнения: 5 Х 1 = 400 - 20 Х 2 , Х 1 = 80 - 4 Х 2 . Подставляем во второе уравнение:

10 (80 - 4 Х 2) + 15 Х 2 = 800 - 40Х 2 + 15 Х 2 = 800 - 25 Х 2 = 450,

следовательно, 25 Х 2 = 350, Х 2 = 14, откуда Х 1 = 80 - 4 х 14 = 80 -56 =24.

Итак, четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х 1 + 80 Х 2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х 1 + 80 Х 2 = 2200 проходит между прямыми ограничений 5 Х 1 + 20 Х 2 = 400 и 10 Х 1 + 15 Х 2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.

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

45 Х 1 + 80 Х 2 → max , 400 W 1 + 450 W 2 → min ,

5 Х 1 + 20 Х 2 ≤ 400 , 5 W 1 + 10 W 2 ≥ 45,

10 Х 1 + 15 Х 2 ≤ 450 , 20 W 1 + 15 W 2 ≥ 80,

Х 1 ≥ 0 , W 1 ≥ 0,

Х 2 ≥ 0 . W 2 ≥ 0.

Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют "объективно обусловленными оценками" сырья и рабочей силы.

Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

Рассмотрим несколько типовых задач линейного программирования (см. также ).

Задача о диете (упрощенный вариант). Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).

Таблица 1.

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

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

3,8 К + 4,2 С → min ,

0,10 К + 0,25 С ≥ 1,00 ,

1,00 К + 0,25 С ≥ 5,00 ,

110,00 К + 120,00 С ≥ 400,00 ,

К ≥ 0 ,

С ≥ 0 .

Ее графическое решение представлено на рис.4.

Рис.4. Графическое решение задачи об оптимизации смеси.

На рис.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00 К + 0,25 С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С ) лежат выше прямой (1) или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования.

Прямая (2) - это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К =0, прямая (1) проходит через точку (0,20), а прямая (2) - через расположенную ниже точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений

1,00 К + 0,25 С = 5,00 ,

110,00 К + 120,00 С = 400,00 .

Из первого уравнения К = 5 - 0,25 С . Подставим во второе: 110 (5- 0,25 С ) + 120 С = 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С , т.е. решение достигается при отрицательном С . Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.

Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К , С ) лежат выше прямой (4) или на ней, как и для прямой (1).

Следовательно, область допустимых значений параметров (К , С ) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых, а также включает граничные отрезки). Область допустимых значений параметров, т.е. точек (К , С ), можно назвать "неограниченным многоугольником". Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого "многоугольника". Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина - это точка А пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений

0,10 К + 0,25 С = 1,00 ,

1,00 К + 0,25 С = 5,00 .

Из второго уравнения К = 5 - 0,25 С , из первого 0,10 (5 - 0,25 С ) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 = 40/9. Итак, А = (40/9; 20/9).

Прямая (3) на рис.4 - это прямая, соответствующая целевой функции 3,8 К + 4,2 С . Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А , через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.

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

3,8 К + 4,2 С → min , W 1 + 5 W 2 + 400 W 3 → max ,

0,10 К + 0,25 С ≥ 1,00 , 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8 ,

1,00 К + 0,25 С ≥ 5,00 , 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2 ,

110,00 К + 120,00 С ≥ 400,00 , W 1 ≥ 0 ,

К ≥ 0 , W 2 ≥ 0 ,

С ≥ 0 . W 3 ≥ 0 .

Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация двойственных переменных: W 1 - "стоимость" единицы вещества Т, а W 2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W 3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W 1 , W 2 , W 3 - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).

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

Таблица 2.

Производственные мощности (в шт.)

		Кофеварки	Самовары
Штамповка
Объем выпуска
Удельная прибыль (на одно изделие)

При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.

Задача линейного программирования имеет вид:

Х 1 ≥ 0 , Х 2 ≥ 0 , Х 3 ≥ 0 , (0)

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 , (1)

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 , (2)

Х 1 / 200 ≤ 100 , (3)

Х 2 / 120 ≤ 100 , (4)

Х 3 / 80 ≤ 100 , (5)

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

(0) - обычное в экономике условие неотрицательности переменных,

(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),

(2) - ограничение по возможностям отделки,

(3) - ограничение по сборке для кухонь,

(4) - то же для кофемолок,

(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.

Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно из формулировки задачи линейного программирования ислючить.

Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане Х 3 = 0, т.е. самовары выпускать невыгодно.

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

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

Простой перебор . Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х 1 + 5Х 2 ≤ 10, то, очевидно, 0 ≤ Х 1 ≤ 10/2 = 5 и 0 ≤ Х 2 ≤ 10/5 = 2. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10 n последовательно при n =2,3,…, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10 n .)

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно – с помощью т.н. метода случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆. Если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл.2.

Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 ,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 ,

Х 3 / 80 ≤ 100 .

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

В соответствии с симплекс-методом введем т.н. "свободные переменные" Х 4 , Х 5 , Х 6 , соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 + Х 4 = 100 ,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 + Х 5 = 100 ,

Х 3 / 80 + Х 6 = 100 ,

15 Х 1 + 12 Х 2 + 14 Х 3 = F .

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

Х 1 = Х 2 = Х 3 = 0, Х 4 = Х 5 = Х 6 = 100, F = 0.

В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.

В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х 1 .

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х 1:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.

Умножим первую строку на 200, чтобы получить Х 1 с единичным коэффициентом:

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х 1 , получим

7/900 Х 2 + 4/900 Х 3 - 2/3 Х 4 + Х 5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F , получим:

2 Х 2 - 11 Х 3 - 3000 Х 4 = F - 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х 1 входит только в первое уравнение:

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000 ,

7/900 Х 2 + 4/900 Х 3 - 2/3 Х 4 + Х 5 = 100/3,

Х 3 / 80 + Х 6 = 100 ,

2 Х 2 - 11 Х 3 - 3000 Х 4 = F - 300000.

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

Х 1 = 20000, Х 2 = Х 3 = Х 4 = 0, Х 5 = 100/3, Х 6 = 100, F = 300000.

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

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

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х 2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х 2 , предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х 2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х 1 + 9/7 Х 3 + 1800/7 Х 4 - 600/7 Х 5 = 120000/7 ,

Х 2 + 4/7 Х 3 - 600/7 Х 4 + 900/7 Х 5 = 30000/7,

Х 3 / 80 + Х 6 = 100 ,

85/7 Х 3 - 19800/7 Х 4 - 1800/7 Х 5 = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х 3 = Х 4 = Х 5 = 0. Из остальных уравнений следует, что при этом Х 1 = 120000/7 = 17143, Х 2 = 30000/7 = 4286, Х 6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.

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

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

В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3.

В табл.3, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i , i = 1,2,3, потребителю j , j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Таблица 3.

Исходные данные к транспортной задаче.

	Потреби-тель 1	Потреби-тель 2	Потреби-тель 3	Потреби-тель 4	Запасы на складах
Потреб-ности

Надо спланировать перевозки, т.е. выбрать объемы Х ij поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X 11 + Х 12 + Х 13 + Х 14 = 60 ,

X 21 + Х 22 + Х 23 + Х 24 = 80 ,

X 31 + Х 32 + Х 33 + Х 34 = 60 .

Во-вторых, известны потребности клиентов:

X 11 + Х 21 + Х 31 = 50 ,

X 12 + Х 22 + Х 32 = 40 ,

X 13 + Х 23 + Х 33 = 70 ,

X 14 + Х 24 + Х 34 = 40 .

Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +

3 X 31 + Х 32 + 5 Х 33 + 2 Х 34 → min .

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

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

3.2.2. Целочисленное программирование

Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач.

Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м 2 . Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м 2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):

С = 7 Х + 3 У → max .

При этом должны быть выполнены следующие ограничения:

по стоимости (в тыс. долларов США)

5 Х + 2 У ≤ 20,

по занимаемой площади (в м 2)

8 Х + 4 У ≤ 38,

а также вновь появляющиеся специфические ограничения по целочисленности, а именно,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 4. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.

Если Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.

Если Х = 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С У =2, а именно С = 21 + 6 = 27.

Если Х = 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.

Если Х = 1, то из первого ограничения имеем У ≤ 7, из второго также У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.

Если Х = 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.

Все возможные случаи рассмотрены. Максимальная производительность С = 29 (тысяч единиц продукции за смену) достигается при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.

Задача о ранце . Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.

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

С точки зрения экономики предприятия и организации производства более актуальна другая интерпретация задачи о ранце, в которой в качестве «предметов» рассматриваются заказы (или варианты выпуска партий тех или иных товаров), в качестве полезности – прибыль от выполнения того или иного заказа, а в качестве веса – себестоимость заказа.

Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные Х k , k = 1,2,…, n (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом Х k = 1, если предмет размещают в ранце, и Х k = 0, если нет, k = 1,2,…, n . Для каждого предмета известны две константы: А k - вес k -го предмета, и С k - полезность k -го предмета, k = 1,2,…, n . Максимально возможную вместимость ранца обозначим В . Оптимизационная задача имеет вид

C 1 Х 1 + С 2 Х 2 + С 3 Х 3 + …. + С n Х n → max ,

А 1 Х 1 + А 2 Х 2 + А 3 Х 3 + …. + А n Х n ≤ В .

В отличие от предыдущих задач, управляющие параметры Х k , k = 1,2,…, n , принимают значения из множества, содержащего два элемента - 0 и 1.

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

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

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

Методы направленного перебора . Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х 0 ставится в соответствие число - "граница" А(Х ). При решении задачи минимизации необходимо, чтобы А (Х 1) ≥ А(Х 2 ), если Х 1 входит в Х 2 или совпадает с Х 2 .

Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества Х С на два - Х 1С и Х 2С . При этом пересечение Х 1С и Х 2С пусто, а их объединение совпадает с Х С . Затем вычисляют границы А (Х 1С) и А (Х 2С ) и выделяют "ветвь" Х С +1 - то из множеств Х 1С и Х 2С, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

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

3.2.3. Теория графов и оптимизация

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

	Рис.5. Примеры графов.

На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных графов.

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

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

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

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

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

Задача о кратчайшем пути . Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

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

Таблица 4.

Исходные данные к задаче о кратчайшем пути.

Начало дуги	Конец дуги	Время в пути

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С (Т ) - длина кратчайшего пути из вершины 1 в вершину Т . (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С (4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.7 и в табл.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С (3) = 1. Кроме того, очевидно, что С (1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С (4) = min {С(2) + 4; С (5) + 5}.

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение С(4) сведено к нахождению С(2) и С (5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С (5) = min {С (3) + 2; С (6) + 3}.

Мы знаем, что С (3) = 1. Поэтому

С(5) = min {3; С (6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С (5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С (2) = min {С(1) + 7; С(3) + 5; С (5) + 2}.

Нам известно, что С(1) = 0, С (3) = 1, С (5) = 3. Поэтому

С (2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С (4):

С (4) = min {С (2) + 4; С (5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С (5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.4) полностью решена.

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

Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?

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

Рис.8. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.5).

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Таблица 5.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.6).

Таблица 6.

Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М . Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM , а именно, Х 01 , Х 02 , Х 03 , Х 12 , Х 13 , Х 14 , Х 23 , Х 24 , Х 34 . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max ,

Х 01 + Х 02 + Х 03 = F (0)

- Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

- Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

- Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

- Х 14 - Х 24 - Х 34 = - F (4)

Х 01 ≤ 2

Х 02 ≤ 3

Х 03 ≤ 1

Х 12 ≤ 4

Х 13 ≤ 1

Х 14 ≤ 3

Х 23 ≤ 1

Х 24 ≤ 2

Х 34 ≤ 2

Х КМ ≥ 0 , К, М = 0, 1, 2, 3, 4

F ≥ 0 .

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) - это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем в системе ограничений задачи линейного программирования указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

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

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

Представляют интерес задачи оптимизации с нечеткими переменными , а также задачи оптимизации, возникающие в эконометрике . Они рассматриваются в соответствующей литературе.

Литература

1. Гасс С. Путешествие в страну линейного программирования / Пер. с англ. - М.: Мир, 1973. - 176 с.

2. Кофман А., Фор Р. Займемся исследованием операций / Пер. с франц.. - М,: Мир, 1966. -280 с.

3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа, 1976. - 392 с.

4. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. – М.: Синтег, 2001. – 124 с.

5. Орлов А.И. Задачи оптимизации и нечеткие переменные. – М.: Знание, 1980. – 64 с.

6. Орлов А.И. Эконометрика. – М.: Изд-во «Экзамен», 2002. – 576 с.

Задачи по методам принятия решений

1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

400 W 1 + 450 W 2 → min ,

5 W 1 + 10 W 2 ≥ 45,

20 W 1 + 15 W 2 ≥ 80,

W 1 ≥ 0, W 2 ≥ 0.

2. Решите задачу линейного программирования:

W 1 + 5 W 2 → max ,

0,1 W 1 + W 2 ≤ 3,8 ,

0,25 W 1 + 0,25 W 2 ≤ 4,2 ,

W 1 ≥ 0 , W 2 ≥ 0 .

3. Решите задачу целочисленного программирования:

10 Х + 5 У → max .

8 Х + 3 У ≤ 40,

3 Х + 10 У ≤ 30,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

4. Решите задачу о ранце:

Х 1 + Х 2 + 2 Х 3 + 2Х 4 + Х 5 + Х 6 → max ,

0,5 Х 1 + Х 2 + 1,5 Х 3 + 2Х 4 + 2,5Х 5 + 3Х 6 ≤ 3.

Управляющие параметры Х k , k = 1,2,…, 6 , принимают значения из множества, содержащего два элемента - 0 и 1.

5. Транспортная сеть (с указанием расстояний) приведена на рис.9. Найдите кратчайший путь из пункта 1 в пункт 4.

Рис.9. Исходные данные к задаче о кратчайшем пути.

7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл.7.

Таблица 7.

Исходные данные к задаче коммивояжера

Город отправления	Город назначения	Затраты на проезд

8. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис.10) ограничена (табл.8)?

Рис.9. Транспортная сеть к задаче о максимальном потоке.

Таблица 8.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность

Темы докладов и рефератов

1. Классификация оптимизационных задач принятия решений.

2. Решения, оптимальные по Парето.

3. Многокритериальные задачи принятия решений: различные методы свертки критериев.

4. Задачи оптимизации и нечеткие переменные (на основе работы ).

5. Моделирование и экспертные оценки при принятии решений.

6. Интерактивные системы принятия решений.

7. Методы учета неопределенностей принятия решений: вероятностные модели, теория нечеткости, интервальная математика.

8. Эконометрические методы принятия решений (на основе монографии ).

9. Имитационное моделировании и метод статистических испытаний (Монте-Карло) при принятии решений.

11. Методы теории игр (теория конфликтов), роль информации и равновесие по Нэшу в теории принятия решений.

12. Проблемы комбинированного применения различных методов в конкретных прикладных работах.

13. Информационные технологии поддержки принятия решений.

Предыдущая

УДК 711.4 МАЗАЕВ А. Г

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

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

Ключевые слова: оптимизация в градостроительстве, теория оптимизации, критерии и методы оптимизации, критерий Парето.

METHODS AND CRITERIA OPTIMIZATION IN THE MODERN THEORY OF SETTLEMENT

In clause the concept of town-planning optimization is considered. The origin of the term optimization, its communication with the basic concepts in the field of methodology of a science, economy is shown. Opportunities of development of concept of optimization in modern town-planning are considered. The set of criteria of optimization which is possible in modern town-planning activity is offered.

Keywords: optimization in town-planning, theory of optimization, oriteria and methods of optimization, сriterion Pareto.

Мазаев Антон

Григорьевич

кандидат архитектуры, советник РААСН, зав. лабораторией Филиала ФГБУ «ЦНИИП Минстроя России» УралНИИпроект

e-mail: [email protected]

Цель данной статьи состоит в том, чтобы представить теоретическое рассмотрение понятия «оптимизация» применительно к градостроительным объектам - городам и системам расселения. Оптимизация расселения крупного региона России на примере Уральского федерального округа является темой проводимого автором научного исследования. Актуальность этой темы связана с назревшим вопросом упорядочения развития региональных систем расселения Национальной системы России, развитие которой приняло неуправляемый и неравновесный характер. Методология разработки темы строится на формируемой в настоящее время теории геополитического развития расселения.

Понятие оптимизации в современной науке

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

математическое программирование... (Оно) занимается математическими методами решения задач нахождения наилучших вариантов из всех возможных» . Большая Советская Энциклопедия уточняет: «Оптимизация - процесс нахождения экстремума (глобального максимума или минимума) определенной функции или выбора наилучшего (оптимального) варианта из множества возможных. Наиболее надежным способом нахождения наилучшего варианта является сравнительная оценка всех возможных вариантов (альтернатив)» . Иными словами, критериев оптимизации может быть много в отношении одного и того же явления, системы. Оптимизировать можно что угодно и по значительному количеству критериев оптимизации. Причем критерии эти могут находиться между собой в противоречии, и для оптимизации необходимо определиться с ними, иначе решение оптимизационной задачи окажется неверным, т. е. ложным, опасным и неэффективным. Источники по-разному толкуют содержание оптимизации, исходя из целей и задач конкретной научной дисциплины. Например, словарь по экономике так трактует это понятие: «Оптимизация - это определение значений экономических показателей, при которых достигается оптимум, то есть оптимальное, наилучшее состояние системы. Чаще всего оптимуму соответствует достижение наивысшего результата при данных затратах ресурсов

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

Понятие оптимизации в экономической теории

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

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

Наиболее емкое и глубокое определение оптимизации дал в свое время В. Парето: «...Любое изменение, которое никому не причиняет убытков и которое приносит некоторым людям пользу (по их собственной оценке), является улучшением» . Этот критерий имеет весьма широкий смысл: он применяется при решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались, а также таких, когда реализуется композиционный подход к построению плана развития экономической системы, учитывающий интересы составляющих ее подсистем (групп экономических объектов). Приведенное выше определение можно формализовать следующим утверждением: состояние экономики S* считается лучшим, по В. Парето, чем другое состояние Б1, если хотя бы один экономический субъект предпочитает S*, а все остальные, по меньшей мере, не делают различий между этими состояниями, но в то же время нет таких, кто предпочитает 81; согласно В. Парето, состояние 8* безразлично состоянию Б1, если все экономические субъекты не делают между ними различий; наконец, оно оптимально, если не существует такого допустимого состояния экономики, которое было бы лучше, чем это. Критерий оптимальности В. Парето имеет большое методологическое значение, так как дает понимание, какое изменение в экономической системе можно назвать позитивным, т. е. направленным на общее ее улучшение, а какое нет. Рост экономического благосостояния одних субъектов за счет других не может быть признан позитивным по данному критерию. На Иллюстрации 1 показано действие критерия В. Парето в виде графика, показана область «приемлемых значений», которые обеспечивают улучшение хотя бы одного показателя, не приводя к ухудшению остальных.

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

Иллюстрация 1. Оптимальность по В. Парето

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

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

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

Реализация концепции ГСНМ была предпринята в рамках Генеральной схемы расселения СССР, разработанной в 1970-е гг. Создание ГСНМ предполагалось для оптимизации набравшего к тому времени процесса агломерирования больших и средних городов. Вместо произвольного «слипания» населенных пунктов должна была быть создана их иерархическая организация. Другим следствием оптимизации в градостроительстве

Иллюстрация 2. Основные методы решения задач оптимизации. Систематическое обобщение ее различных методик

стало выяснение вопроса относительно так называемой «оптимальной величины» городов. Подразумевалось, что раз существует чрезмерное перенаселение некоторых городов, то есть и оптимальная его величина, которая может быть вычислена градостроительной наукой. «...Понятие "оптимального"города оставалось одним из наиболее существенных элементов советской градостроительной политики. .Не было сомнения в том, что такой оптимум существует. Разногласия начинались при попытке определить, какую именно людность следует считать оптимальной. В 1920-е гг. оптимальным казалось 50-тысячное население. Оно было достаточным для того, чтобы проявились выгоды от экономии на масштабе производства и городской инфраструктуре, и в то же время не столь большим, чтобы разрушить чувство общности и социалистическую коммунальную этику. В середине 1950-х гг. оценки оптимума колебались между 150 тысячами и 200 тысячами, а к 1960 г. они подскочили уже к 250-300 тысячам человек, и сама правомерность этой концепции. была поставлена под сомнение» . Спор оказался схоластичен, потому что оптимальность размера города зависит не от абсолютной ве-

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

Вопрос об этой оптимальной величине города по-новому остро встал в 1960-1970-е гг., когда в СССР наметился рост числа крупных и крупнейших городов, стали заметны их недостатки. В статье с характерным названием «Максимальные размеры города» (1970) утверждалось: «С точки зрения городского хозяйства, наиболее экономичны города, в которых меньше сумма капиталовложений и эксплуатационных расходов в пересчете на одного жителя. Неэкономичными оказываются как слишком маленькие города, так и города-гиганты. В городском строительстве проявляется общий для всех областей экономики принцип, в соответствии с которым крупная хозяйственная единица эффективнее малой. В маленьких городках с числом жителей до 20 тысяч приходится создавать мелкие, малопроизводительные коммунальные и бытовые предприятия. С ростом городов, они становятся экономичнее. <.> С дальнейшим ростом численности населения положение ухудшается, <.> невозможно

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

Авторы статьи считают, что им удалось найти ответ на оптимизационную задачу: «Взвешивая все "за" и "против", во многих странах, в том числе и в СССР, градостроители и экономисты пришли к выводу, что в настоящее время следует ограничить рост городов с миллионным населением, стимулируя развитие городов средней величины (курсив наш. - А. М.)» .

Видим, что оптимальным признается город средней величины, с численностью населения от 50 тыс. до 100 тыс. жителей. С этим выводом не согласен В. И. Переведенцев, который видит решение вопроса опять-таки в сфере экономики, но более глубоко. Он показывает нелинейный характер зависимостей экономической эффективности от величины города: «Город - это не только дома, где живут люди, но и заводы, где они работают. Оказывает ли размер города влияние на производительность труда? Да, оказывает. Большой город выгоден с точки зрения производства. Это выгоды совместного использования

энергетики, транспорта, водопроводного и канализационного хозяйств. Это обеспеченность квалифицированной рабочей силой... Территориальная концентрация промышленности повышает производительность труда. Поэтому большой город сам создает предпосылки для дальнейшей концентрации производства» . Далее автор отмечает, что «содержание» человека в очень большом городе обходится дороже, чем в среднем, но отдача от человека в таком городе, по его мнению, больше. Он указывает: «Принятое сейчас понимание оптимальных размеров города, на мой взгляд, неверно принципиально, методологически. Если иметь в виду не только потребление, но и производство, то оптимальным будет не тот город, в котором содержание человека дешевле, а тот, в котором разница между тем, что дает человек, и тем, что тратится на него, будет наибольшая» [Там же]. Получается модель «затраты - издержки» применительно к жителю данного города, которая показывает, что рост экономической эффективности может быть весьма длительным по мере роста размеров города, так как за счет кооперационного эффекта производительность труда может расти в широких пределах. Иными словами, оптимальным размером города может быть сколь угодно большой, если сохранится тенденция к росту экономической отдачи от каждого индивидуума.

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

Надо сказать, что по этому критерию найти оптимальные города весьма непросто, потому что, как показывают многочисленные исследования, ключевые положения генеральных планов практически никогда не выполнялись. Получается, что российские города хронически находятся в «неоптимизированном» состоянии.

В качестве завершения этой дискуссии стоит привести симптоматичную жалобу самого В. И. Пере-веденцева о том, что города в своем развитии уходят от состояния оптимальности, а не приходят к нему: «... Наиболее высокие темпы прироста населения имели города, в которых в 1959 г. было от 400 до 600 тысяч человек - свыше 35 процентов. По господствующим в нашем градостроительстве воззрениям, оптимальными считаются города с населением 50-200 тысяч человек, допустимыми - до 400 тысяч. Значит, быстрее всего росли города, вышедшие за пределы "допустимых". "Оптимальные" города росли тоже быстро, становясь неоптимальными (курсив наш. - А. М.)» .

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

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

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

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

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

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

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

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

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

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

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

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

1) Природно-экологическая подсистема.

2) Социально-демографическая подсистема.

3) Экономическая подсистема.

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

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

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

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

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

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

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

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

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

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

Заключение

Таким образом, мы теоретически имеем целых четыре варианта ответа на поставленный вопрос о том, каков должен быть характер оптимизации в градостроительстве:

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

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

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

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

в качестве идеального конечного результата.

Список использованной литературы

1 Шупер В. А. Самоорганизация городского расселения/Рос. открытый ун-т. М., 1995.

2 Покшишевский В. В. Заселение Сибири. Историко-географиче-ские очерки. М., 1951.

3 Бразовская Н. В. Методы оптимизации: учеб. пособие / Алтайский гос. техн. ун-т им. И. И. Ползунова [Центр дистанц. обучения]. Барнаул, 2000.

4 Большая Советская Энциклопедия. 3-е изд. М., 1975. Т. 19.

5 Райзберг Б. А., Лозовский Л. Ш., Стародубцева Е. Б. Современный экономический словарь. 2-е изд., испр. М., 1999.

6 Экономика: толковый словарь. М., 2000.

7 Переведенцев В. И. Методы изучения миграции населения, М., 1975.

8 Дубровский П. Н. Максимальные размеры города // Наука и техника. 1970. № 6.

9 Мазаев А. Г. Национальная территориальная система расселения как фактор контроля: геополитический подход // Академический вестник УралНИИпроект РААСН. 2008. № 1. С. 32-37.

10 Мазаев А. Г. Формирование и развитие системы расселения Урала (XVII-XIX вв.): этапы и геополитические особенности // Академический вестник УралНИИпроект РААСН. 2014. № 1. С. 10.

11 Мазаев А. Г. Анализ развития структуры системы расселения Урала (конец XIV - XX век) методом скользящих средних // Академический вестник УралНИИпроект РААСН. 2014. № 3. С. 34.