Оптимизация – это вектор наилучших решений. Для использования процедуры оптимизации необходимо прежде всего сформулировать рассматриваемую задачу, т. е. построить модель объекта оптимизации, которая бы описывала исследуемый процесс. В модели необходимо провести различие между теми величинами, значения которых можно варьировать и выбирать с целью достижения наилучшего результата. Эти величины называются управляемыми переменными. Другие величины являются фиксированными или определяются как внешние. Определение тех значений управляемых переменных, которым соответствует наилучшая оптимальная ситуация, и представляет задачу нашей оптимизации. При военнотехническом сотрудничестве (ВТС) на выбор управляемых переменных (в нашем случае прежде всего финансовых и др.), как правило, наложены ограничения, связанные с ограниченностью имеющихся финансовых средств у головного предприятия при ВТС, а у смежных предприятий (поставщиков заказываемого оборудования головным предприятием), например, недостаточно мощностей и профессионального коллектива. При построении модели эти ограничения мы будем записывать в виде равенств и неравенств или указывать множества, которым должны принадлежать значения управляемых переменных. Совокупность всех ограничений на управляемые переменные будем определять допустимым множеством нашей задачи. Обязательной составной частью модели в поставленной задаче объекта оптимизации (распределения финансов) является числовой критерий – максимальный доход для смежных предприятий от финансовых средств, выделенных им головным предприятием. Величина этого критерия полностью определяется выбранными значениями управляемых переменных, т. е. финансовыми средствами, выделяемыми для смежных предприятий при ВТС. В итоге этот критерий является функцией указанных переменных и называется целевой функцией. Теперь можно сформулировать поставленную задачу оптимизации в следующем виде. Максимизировать целевую функцию, т. е. получение финансовой выручки – прибыли от средств, выделенных смежным организациям головным предприятием при ВТС, с учетом ограничений на управляемые переменные, т. е. денежные выделяемые суммы. Поставленную задачу оптимизации в экономической интерпретации будем решать методом ветвей и границ, т. к. данная задача является дискретной, ибо управляемые переменные в ней носят дискретный характер. Допустимое множество на управляемые переменные, т. е. финансы, выделяемые смежным организациям, которое является дискретным, обозначим . Идея метода ветвей и границ состоит в последовательном разбиении этого допустимого множества и записывается в виде (1) на взаимно непересекающиеся подмножества (этот процесс называется ветвлением) и получении оценок снизу (границ) значений целевой функции на этих подмножествах . Схему решения нашей задачи методом ветвей и границ мы представляем в виде некоторого дерева, состоящего из множества вершин и соединяющихся ветвей (рис. 1). Рис. 1. Дерево решения поставленной задачи Начальной вершине 0 соответствует исходное допустимое множество , или исходная задача (1) – распределение финансов головным предприятием для смежных организаций. Для любой вершины К – подмножество , полученное в результате ветвления, или подзадача К нашей задачи . (2) Вершины, удовлетворяющие одному из условий , называются прозондированными. Непрозондированные вершины, из которых ветвление еще не произведено, будем называть активными, а совокупность всех таких вершин – активным множеством А. Процесс ветвления продолжается до тех пор, пока остается хотя бы одна активная вершина, т. е. А = Ø. По окончании процесса ветвления можно указать решение исходной задачи (1), для которого значение целевой функции максимально. Представим нашу дискретную задачу в виде математической модели оптимизации. Пусть финансовые средства в размере S млн руб. распределяются головным предприятием по ВТС между N предприятиями (смежниками) в количестве кратных «а» млн руб., где S/a = m – целое число. При выделении k-му предприятию финансовых средств u млн руб. () оно приносит доход млн руб., k = 1, … n (функции заданы (табл. 1). Оптимальное, с точки зрения суммарного дохода, распределение средств смежным предприятиям записывается в виде: , , Теперь рассмотрим решение экономической задачи оптимизации распределения конкретных средств финансов в размере 4 млн руб. трем смежным предприятиям головной организацией по ВТС в количествах кратных 1 млн руб. Доход от выделения i-му предприятию-смежнику (например, выпускающему блок самонаведения для крылатой ракеты «Я», поставляемой иностранному партнеру) в размере приведен в таблице. Функция доходов от средств, выделенных головным предприятием смежникам Доход fi(u), млн руб. Выделенные средства u, млн руб. 0 1 2 3 4 f1(u) 0 8 14 15 16 f2(u) 0 6 8 9 10 f3(u) 0 7 9 10 11 В нашей задаче требуется найти средства , которые необходимо выделить предприятиям смежникам, чтобы суммарный доход был максимальным. В соответствии с общим правилом максимизации целевой функции можно перейти к минимизации противоположной величины –. Однако, чтобы показать экономическую интерпретацию, т. е. доход предприятий-смежников по ВТС, мы используем метод ветвей и границ в нашей задаче-максимизации, внеся в него некоторые изменения: вместо нижних границ на допустимых подмножествах будем получать верхние границы и на каждом шаге ветвления выбирать вершину с максимальной верхней границей. Могут быть и такие правила ветвления. Пусть в первую очередь просматриваются варианты ветвления средств первому предприятию-смежнику и каждому варианту соответствует ветвь дерева поиска, исходящая из вершины О. Затем из полученных вершин производится ветвление по вариантам выделения средств второму предприятию-смежнику с учетом уже израсходованных средств . В дальнейшем ветвлении (по вариантам финансовых средств для третьего предприятия) необходимости нет, т. к. полностью определяется выбранными значениями и : . Верхние границы для вершины дерева поиска определяются следующим образом. Пусть вершина К получена в результате ветвления из вершины О, т. е. для нее выбрана только величина . Тогда на первом предприятии-смежнике будет получен доход , а на остальных будет доход, не превышающий суммы доходов , т. к. ни второму, ни третьему предприятию-смежнику не может быть выделена сумма большая, чем . Поэтому для вершин, полученных в результате ветвления из вершины О, . (3) Если вершина К получена в результате последующего ветвления, т. е. выбора , то верхняя оценка . (4) Эта оценка соответствует полному решению нашей задачи. Дерево поиска решения у задачи по изложенному выше правилу ветвления и получения верхних границ представлено на рис. 2. Возле вершин дерева указаны верхние границы , найденные по формулам (3) и (4) с помощью таблицы. Как видно из рис. 2, максимальная из верхних границ для полных решений = 27, поэтому минимаксная функция на подмножествах , т. е. первому предприятию-смежнику следует выделить 2 млн руб., а второму и третьему – по 1 млн руб. При этом суммарный доход достигает максимального значения 27 млн руб. Рис. 2. Дерево поиска поставленной задачи Из представленного метода ветвей и границ и его применения для нашей задачи существенным является выполнение следующих условий [3, 4]: - должно быть известно правило ветвления, т. е. разбиение множества допустимых решений, представляемого вершиной, на несколько попарно непересекающихся множеств; - должен быть известен алгоритм получения нижней границы целевой функции на любом допустимом множестве. С учетом этих условий алгоритм метода ветвей и границ представляется в виде укрупненной схемы (рис. 3). Рис. 3. Блок-схема метода ветвей и границ Если при ветвлении из каждой вершины происходит разбиение соответствующего ей подмножества на две части, то схема метода изображается бинарным деревом (рис. 4). Рис. 4. Бинарное дерево оптимизации Процесс ветвления из данной вершины К не производится, если выполняется ряд условий [2–4]. В нашем случае дальнейший поиск решения поставленной исходной задачи на подмножестве не имеет смысла, и говорят, что вершина К «убита» вершиной ℓ, т. е. . Из этого выражения следует, что , т. е. минимальное значение функции f(x) на uk не может быть меньше, чем в уже найденной точке . Обозначение: число – есть точка глобального (абсолютного) минимума или максимума, или просто точка минимума-максимума суммы функции f(x) на множестве u, если f(x*) ≤ f(x) для всех . Множество всех точек (минимума-максимума) f(x) на u обозначено через u*. – есть экстремум функции f(x) на множестве u. Заключение Нами предложен методический подход для реализации наиболее эффективного военно-технического сотрудничества России с инопартнерами, в рамках которого сформулирована задача оптимизации финансовых средств, выделяемых головным разработчиком конечной продукции предприятиям-смежникам (т. е. предприятиям, участвующим в разработке элементов продукции, поставляемой на мировой рынок вооружения и военной техники). В результате применения метода оптимизации ветвей и границ представлена также укрупненная блок-схема алгоритма задачи оптимизации.