ГЛОССАРИЙ 2 страница

ГРАДИЕНТНЫЕ МЕТОДЫ [gradient methods] — методы решения задач математиче- ского программирования (вычислительные алгоритмы), основанные на поиске экстре- мума (максимума или минимума) функции путем последовательного перехода к нему с помощью градиента этой функции.

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

· Формально решение в случае спуска состоит в построении последовательности векто- ров x0, x1,..., xn, удовлетворяющих условию

f (x0) > f(x2) >... f(xk)... > f(xn).

Такие последовательности называют релаксационными. Точки этой последовательности [xk] вычисляются по формуле xk+ 1 = xk+ γkpk,

где γ k— направление спуска, определяемого градиентом; pk— длина шага вдоль этого направления (длина шага может быть постоянной и переменной, причем оптимальный ее размер обеспечивает наискорейший спуск или подъем).

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

ГРАФ [graph] — основной объект изучения теории графов, математически определяет- ся двояко. С одной стороны, как совокупность двух множеств: множества элементов x

□ X и множества соответствий, бинарных отношений между этими элементами t ∈ T. С другой стороны, как некая геометрическая схема, тогда элементы множества X будут точками (их называют вершинами x), а соответствия t — отрезками (ребрами), соеди- няющими элемент x с элементами, которые с ним связаны. В соответствии с этим су- ществуют и два подхода к определению предмета теории графов: теоретико- множественный и геометрический.

Граф g = (X, T) называется конечным, если число его вершин конечно. Практически используются только конечные Г., бесконечные же пока представляют лишь теоретиче- ский интерес. Г. называется ориентированным или направленным, если всякая пара то- чек упорядочена, т. е. соединяющее их ребро имеет начало и конец (тогда оно называ- ется дугой). Две точки, определяющие ребро или дугу, называются смежными. Смеж- ными называются и две дуги, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. В слу- чае ненаправленного Г. применяют термин цепь. Если начало и конец пути совпадают, образуется контур или цикл.

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

В экономике особенно широко используются два вида Г. — дерево и сеть.

Для описания Г. часто используется квадратная матрица, именуемая матрицей смежно- сти. У нее как строки, так и столбцы отвечают вершинам Г. (i, j = 1, 2,..., n), а элемент rij несет информацию о наличии ребра, связывающего произвольные вершины xi и xj. Напр., можно обозначить наличие ребра между ними единицей, а отсутствие — нулем. Это называется матричным представлением рассматриваемого Г. Для графа, показан- ного на рис. Г. 2, имеем матрицу.

ГРАФИК БЕЗУБЫТОЧНОСТИ ПРОИЗВОДСТВА [breakeven graph] — график, по- зволяющий определить убыточность или прибыльность производства при разных ценах на факторы производства, различных уровнях цены продукта и разных объемах произ- водства (см. рис. Г. 3).

ДВОЙСТВЕННАЯ ЗАДАЧА [dual problem] (другие названия: сопряженная, обратная задача) — одно из фундаментальных понятий теории линейного программирования; инструмент, позволяющий установить, оптимально ли данное допустимое решение за- дачи ЛП, без непосредственного сравнения его со всеми остальными допустимыми ре- шениями.

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

Д. з. состоит в минимизации затрат при заданных лимитах ресурсов и формулируется следующим образом (в обозначениях, приведенных в ст. “Линейное программирова- ние”):

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

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

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

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [duality in linear

programming] — принцип, заключающийся в том, что для каждой задачи линейного

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

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

1. “Теорема двойственности”. Если обе задачи имеют допустимые решения, то они имеют и оптимальные решения, причем значение целевых функций у них будет одина- ково:

(обозначения см. в ст. “Линейное программирование”). Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения.

2. “Признак оптимальности”. Чтобы допустимое решение x прямой задачи было опти- мальным, необходимо и достаточно, чтобы нашлось такое решение двойственной зада- чи v, что

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

ДЕРЕВО [tree] — в теории графов связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять чис- ло вершин (элементов графа), то он содержит ровно n – 1 ребро, не имеет циклов; если добавить ребро, соединяющее две несмежные вершины, то образуется один цикл; при удалении любого ребра граф становится несвязным; каждая пара вершин соединяется одной, и только одной цепью. Исходная вершина называется корнем, пути от нее к крайним вершинам — ветвями.

ДИНАМИЧЕСКАЯ СИСТЕМА [dynamic system] — всякая система, которая изменя- ется во времени (в отличие от статической системы). Математически это принято выражать через переменные (координаты). Процесс их изменения характеризуется траек- торией:

Q(t) = [q1(t), q2(t),..., qn(t)],

где координаты q1,..., qnявляются функциями времени t.

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

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

ДИНАМИЧЕСКИЕ МОДЕЛИ ЭКОНОМИКИ [dynamic economic models] — модели, описывающие экономику в развитии (в отличие от статических, характеризующих ее состояние в определенный момент). Модель является динамической, если, как мини- мум, одна ее переменная относится к периоду времени, отличному от времени, к кото- рому отнесены другие переменные.

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

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

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

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

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

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

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [dynamic programming] — раздел ма- тематического программирования, совокупность приемов, позволяющих находить оп- тимальные решения, основанные на вычислении последствий каждого решения и выра- ботке оптимальной стратегии для последующих решений.

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

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

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

Такая процедура проводится до самого начала, а затем (второй раз) выполняется от на- чала к концу, в результате чего находятся уже не условные, а действительно оптималь- ные шаговые управления на всех шагах операции (см. пример в ст. “Дерево решений”).

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

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

ЕДИНИЧНАЯ ЭЛАСТИЧНОСТЬ СПРОСА [unitary elastic demand] — эластичность спроса от цен, при которой процентное изменение цены товара вызывает такое про- центное изменение спроса, что общий доход производителя (расход покупателя) оста- ется неизменным.

ЖЕСТКОСТЬ И НЕЖЕСТКОСТЬ ОГРАНИЧЕНИЙ ЛП [hardness and slackness of LP constraints] — характеристика ограничений задачи линейного программирования по степени их влияния на оптимум (см. Чувствительность оптимального решения). Огра- ничение является нежестким, когда малые изменения константы ограничения не отра- жаются на решении задачи. Напр., в распределительной задаче это означает, что спрос строго меньше предложения, в результате чего объективно обусловленные оценки рав- ны нулю. Решение не зависит от общего объема возможного предложения товара, так как имеющееся количество его превышает ту потребность в нем, которая соответствует его использованию в оптимальной точке.

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

ЗАДАЧА О КОММИВОЯЖЕРЕ, О БРОДЯЧЕМ ТОРГОВЦЕ [travelling salesman problem] — вид задачи математического программирования; состоит в отыскании наи- лучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд.

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

З. о к. — одна из типичных задач, решаемых методом динамического программирова- ния. О сложности ее говорит такой факт: если рассматриваются 4 города (точки), то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн допустимых маршрутов. В общем случае, когда число городов n, количество маршру- тов равно (n – 1)!, т. е. 1 × 2 ×... (n – 1). Задача, следовательно, заключается в поиске сокращенных способов расчета, позволяющих отказаться от сплошного перебора воз- можных маршрутов. Такие способы есть. Они основаны на использовании сетевых и матричных моделей.

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

ЗАДАЧА О НАЗНАЧЕНИЯХ [assignment problem] — вид задачи линейного програм- мирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации “рабочий — станок” характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т. д.

Математически такие задачи — частный случай распределительных задач с той осо- бенностью, что в них объемы наличных и требующихся для выполнения каждой рабо- ты ресурсов равны единице, т. е. aj = bj = 1, и все xij= 1, если работник i назначен на ра- боту j, или нулю в остальных случаях (обозначения см. в ст. “Распределительные зада- чи”). Иначе говоря, для выполнения каждой работы расходуется только один вид ре- сурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таб- лице, которая называется матрицей оценок, результаты — в матрице назначений.

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

ЗАДАЧА О РАЗМЕЩЕНИИ СКЛАДОВ [warehouse location problem] — одна из задач исследования операций, обычно решаемая методом нелинейного программирования (но при некоторых условиях она может сводиться и к обычной транспортной задаче линейного программирования). Заключается в минимизации общей суммы транспорт- ных и складских расходов при следующих ограничениях: с каждого завода должна быть отгружена вся продукция, емкость любого склада не должна быть превышена, по- требности всех покупателей должны быть удовлетворены. По существу дело сводится к отысканию трехчленных комбинаций предприятие — склад — потребитель, в совокуп- ности обеспечивающих минимум расходов.

ЗАДАЧА О РАСКРОЕ [cut problem, trim problem] — частный случай задач о ком- плексном использовании сырья, обычно сводящихся к методу линейного программиро- вания.

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

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

при условии, что переменные xj удовлетворяют ограничению

Это означает, что соблюдена комплектность: все необходимые заготовки сделаны в достаточном числе ri(aij— число заготовок i-го типа при j-м способе раскроя; xj— число листов, раскроенных j-м способом). Наконец, принимается условие неотрица- тельности: xj≥ 0, т. е. число листов не может быть отрицательно.