Full Text

Введение Теория математического программирования является основным аналитическим средством изучения реальных объектов экономики и ее процессов [1]. Одним из первых и наиболее подробно изученных разделов математического программирования является линейное программирование. Оно широко используется при решении множества экономических проблем: оптимизация грузоперевозок в целях уменьшения расстояний [2], составление графика труда для экономии времени или минимизации заработной платы сотрудников [3], распределение персонала с целью увеличить эффективность работы [4, с. 95; 5, с. 267], распределение средств между различными методами управления рисками при условии максимизации прибыли [6] и прочее [7-10]. Однако, например, из-за крупномасштабного производства или сложной технологии производства возникает ситуация, когда на переменные накладывается большое количество ограничений [11]. Это обусловлено тем, что любое производство связано с затратами сырья, земли, электроэнергии, рабочей силы и так далее, и при решении задачи приходится учитывать все эти факторы. Из-за чего возникает потребность в нахождении различных методов упрощения решения таких задач. В статье рассматривается общая задача линейного программирования. Делается предположение, что среди ее ограничений можно выделить группу неравенств, которая будет определять принадлежность решения многогранному выпуклому конусу с вершиной, расположенной в неотрицательном ортанте. Тогда такая задача будет не только обладать всеми качествами линейных задач оптимизации, но и иметь ряд дополнительных полезных свойств, которые позволяют разработать специальный метод ее решения. В результате предлагается рассматривать задачу в пространстве новых переменных [12], благодаря чему уменьшается количество ограничений, а это, в свою очередь, приводит к существенным упрощениям при ее решении. В конце работы приведена методика поиска матрицы, помогающей совершить переход в новое пространство переменных. 1. Постановка задачи Рассмотрим задачу линейного программирования в общем виде: (1) где Здесь t - знак транспонирования. Предполагаем, что среди ограничений задачи (1) можно выделить группу из неравенств: (2) которые описывают принадлежность решения многогранному выпуклому конусу T, вершина которого расположена в неотрицательном ортанте. Тогда существует такая матрица D, что группа неравенств (2) равносильна неравенству [13]. Здесь вектор-столбец B подобран так, чтобы записанное неравенство было равносильно неравенствам (2). Другими словами, предполагаем, что среди ограничений задачи (1) можно выделить множество точек таких, что . При этом существует такая единственная точка что выполняется равенство . В таком случае неравенства называются ограничениями конусного типа, а - вершиной конуса T [14]. Поскольку все точки выделяемого множества по условию принадлежат неотрицательному ортанту, рассматриваемый конус T также будет полностью располагаться в этом ортанте. Благодаря этому требованию при решении задачи (1) будет обеспечиваться принадлежность оптимального решения рассматриваемому конусу T. Ограничения конусного типа можно задать другим способом: если ранг матрицы D равен n, а именно числу переменных, то матричное уравнение имеет единственное решение [14]. При этом считается, что конус T вместе со своей вершиной полностью расположен в . Тогда группу неравенств называют конусными ограничениями. Очевидно, что при m2 = 0 вершина не будет принадлежать ни одной из координатных осей. При m1 = 0 конус T будет представлять собой неотрицательный ортант, а задача (1) будет являться задачей линейного программирования в стандартной форме. Если же правая часть неравенств в группе неравенств (2) будет равна нулю - , то вершина конуса будет совпадать с началом координат, что уже было рассмотрено в работе [15]. В таком случае задачу (1) можно представить в следующем виде: (3) где . Назовем постановку (3) задачей линейного программирования с ограничениями типа многогранного смещенного конуса. Ранее в работах [15, 16] рассматривались ограничения специального вида, выполнение которых гарантирует, что искомое решение будет принадлежать конусу с вершиной в начале координат. И также предоставлялся алгоритм упрощения нахождения оптимального решения. Вследствие этого для удобства решения поставленной задачи (3) совершим параллельный перенос системы координат [17, с. 18] из точки в вершину конуса . Тогда можно установить связь одной и той же точки в старых и новых системах координат: где x и - старые и новые координаты соответственно. В таком случае после преобразований неравенство станет однородным: , а вершина нового конуса относительно системы координат будет расположена в начале координат (рисунок). Рис. Параллельный перенос осей координат для случая R2 При параллельном переносе осей координат условие неотрицательности переменных преобразовывается и принимает вид . Но в силу требования можно неравенство заменить на , что упростит решение задачи. В итоге получилась следующая задача линейного программирования с ограничениями конусного типа: (4) Для того чтобы ее решить, необходимо перенести задачу (4) из старой декартовой системы координат (из n-мерного пространства) в новую систему координат, в новое s-мерное пространство. Для этого по матрице конусных ограничений D находим точки , принадлежащие образующим конуса n-мерного пространства, и по ним определяем векторы , сонаправленные этим образующим. Затем строим матрицу перехода (размером n s), которая будет осуществлять перенос задачи (4) в новое пространство переменных. Пусть и - координаты точки в старой и новой системах координат соответственно. В таком случае старые переменные задачи (4) будут выражаться через новые по формуле [18, с. 188], а задача (4) запишется в виде (5) Заметим, что количество ограничений в задаче (5) будет меньше, чем у исходной (1), причем на оптимальных планах значения целевых функций соответственно совпадают: . Решаем новую задачу (5), возвращаемся обратно к переменным по формуле и находим искомый оптимальный план задачи (1). При выделении конусных ограничений предполагалось, что выполняется следующее требование: . Однако может возникнуть ситуация, когда это условие нарушается: либо конус только частично расположен в , либо . Чтобы такого избежать, следует проверить одновременное выполнение двух условий, которые подтверждают наличие в T только неотрицательных элементов: 1) - вершина смещенного конуса не должна быть отрицательной; 2) P - неотрицательная матрица. Другими словами, векторы не должны содержать отрицательных элементов, т.е. все углы между осями координат и данными векторами принадлежат отрезку [0°; 90°]. Если эти два условия выполняются для некоторого конуса T, описанного ограничениями , то можно выполнять переход в другое пространство и это не повлечет за собой добавление новых n неравенств в имеющуюся систему ограничений задачи. 2. Нахождение матрицы перехода Как уже говорилось ранее, для перевода задачи в новое пространство необходимо найти векторы, сонаправленные образующим конуса. Возьмем произвольный -мерный положительный вектор-строку и составим уравнение . При пересечении полученной плоскости и конуса T появляется некоторый многогранник, у которого крайние точки (векторы) принадлежат образующим конуса, причем каждая точка принадлежит только одной образующей, количество которых ограничено и равно s. Обозначим через S систему конусных неравенств , а через систему, которая получается в результате замены в всех знаков неравенства равенствами и добавления составленного уравнения . Далее находим точки многогранника, построенного по ограничениям , применяя способ поиска вершин выпуклой многогранной области [19]. Для этого перечислим все неоднородные подсистемы из n уравнений в и найдем их решения. Число таких подсистем будет равно . Полученные точки, которые удовлетворяют ограничениям исходной системы S, называем крайними точками . По найденным результатам можно отыскать векторы и матрицу перехода P: Если число точек будет совпадать с числом переменных n = s, то будут составлять линейно-независимую систему векторов, если же , то здесь следует уже говорить о линейной зависимости векторов, однако этот факт не помешает перенести задачу в новое пространство, воспользовавшись матрицей P. Заключение В заключение отметим, что в статье рассмотрена задача линейного программирования с ограничениями типа многогранного конуса. Ограничения берутся такого вида, что из них можно выделить группу неравенств, описывающих многогранный конус со смещенной вершиной. Предполагается, что конус лежит в неотрицательном ортанте. В этом случае в работе вводятся новые координаты, а задача преобразуется соответствующим образом. Новая задача, оказывается, имеет меньше ограничений по сравнению с исходной. Таким образом, в статье указан путь упрощения задачи линейного программирования при определенных условиях, что является чрезвычайно важным при решении прикладных задач [20].

About the authors

M. A Sevodin

Perm National Research Polytechnic University

E. O Starkova

Perm National Research Polytechnic University

References

Statistics

Views

Abstract - 44

PDF (Russian) - 55

Refbacks

• There are currently no refbacks.