RESTRICTIONS OF THE TYPE OF POLYHEDRAL DISPLACED CONE IN LINEAR PROGRAMMING PROBLEMS

Abstract


The paper considers the linear programming problem. A method is proposed to simplify its solution by identifying a class of constraints of a special type, due to which the desired plan will belong to a polyhedral convex cone located in a non-negative orthant. In this case, you must perform the following algorithm of actions. First, the original coordinate system is parallel transferred to the top of the selected cone. Then a transition to another space is made, which will lead to significant changes: a decrease in the number of restrictions. Next is the solution to the problem in any convenient way, for example, by the simplex-method - the most frequently used algorithm for finding solutions to linear extremal problems. One of its features is that with a large number of restrictions, its effectiveness decreases. This is a significant drawback in solving a number of problems, in particular, those of an economic nature, which, as a rule, striving to most accurately reflect the real state of affairs, impose a large number of restrictions on the desired plan. Therefore, if possible, it is better to reduce their number, even by increasing the variables, as this can happen in the proposed method for solving the selected class of problems. After finding the optimal plan, you need to return to the original space, and then to the old coordinate system. An important condition of this algorithm is the non-negativity of the cone elements. Thanks to this assumption, when a task is modified, new constraints are excluded. To track the implementation of this requirement, a condition is given in the work that guarantees its fulfillment. At the end of the work, the technique of searching for the operator (transition matrix) is described, with the help of which the task is transferred to another space. It is based on the search for vectors aligned with the generators of the cone.

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

  1. Анисимова Н.П., Ванина Е.А. Линейное программирование: учеб.-метод. пособие / НИУ ВШЭ. - СПб., 2012. - 70 с.
  2. Бунтова Е.В., Нестерова М.А., Серкова А.Д. Использование транспортной задачи для определения оптимального плана грузоперевозок [Электронный ресурс] // Human Progress. - 2018. - Т. 4, № 2. - URL: http://progress-human.com/images/2018/Tom4_2/Buntova.pdf (дата обращения: 08.06.2020).
  3. Богомольный М.А. Метод составления оптимального графика работы персонала // Экономика и современный менеджмент: теория и практика: материалы VIII Междунар. науч.-практ. конф., г. Новосибирск, 21 декабря 2011 г. / СибАК. - Новосибирск, 2011. - С. 44-49.
  4. Банди Б. Основы линейного программирования: пер. с англ. / под ред. В.А. Волынского. - М.: Радио и связь, 1989. - 176 с.
  5. Компьютерное моделирование менеджмента: учеб. / А.Ф. Горшков, Б.В. Евтеев, В.А. Коршунов [и др.]. - 2-е изд., перераб. и доп. - М.: Экзамен, 2007. - 622 с.
  6. Ростова Е.П., Верховец О.А. Постановка задачи линейного программирования для распределения средств по управлению рисками промышленного предприятия // Вестник ОмГУ. Сер. Экономика. - 2013. - № 2. - С. 116-119.
  7. Применения линейного программирования / А.С. Кабардов, С.А. Ульбашева, И.З. Кардангушев, Л.З. Хуранова, С.Т. Жабелов, И.А. Ниязов // International Scientific Review. - 2017. - № 7 (38). - С. 7-10.
  8. Лаптева М.В., Сергеева Д.А., Иремадзе Э.О. Решение задачи по максимизации прибыли от реализации в АО «Караван» с использованием симплекс-метода // Colloquium-Journal. - 2019. - № 15 (39). - С. 56-57.
  9. Лисин П.А., Мартемьянова Л.Е., Савельева Ю.С. Моделирование рецептурной смеси многокомпонентных мясных продуктов с применением симплекс-метода // Технические науки. - 2014. - № 1(13). - С. 73-76.
  10. Харитонова Н.Д., Бурамбаева З.А., Чекушкина М.Н. Проверка экономической эффективности плана по изготовлению хлеба двух видов с помощью математического моделирования // Электронный научно-методический журнал Омского ГАУ. - 2019. - № 1 (16). - С. 6. - URL: http://e-journal.omgau.ru/images/issues/2019/1/00695.pdf (дата обращения: 08.06.2020).
  11. Васильев О.В., Леденева Т.М. Транспортная задача и оптимизация грузоперевозок // Вестник ВГТУ. - 2011. - № 11. - С. 82-84.
  12. Старкова Е.О. О задаче линейного программирования с ограничениями специального вида // Аллея науки. - 2018. - Т. 4, № 11 (27). - С. 141-145.
  13. Никайдо Х. Выпуклые структуры и математическая экономика. - М.: Мир, 1972. - 519 с.
  14. Кофман А. Методы и модели исследования операций: пер. с фр. - М.: Мир, 1966. - 523 с.
  15. Севодин М.А., Старкова Е.О. О производственной задаче с ограничениями конусного типа // Московский экономический журнал. - 2018. - № 5 (3). - С. 378-388.
  16. Старкова Е.О., Севодин М.А. О задаче кредитной политики банка с ограничениями конусного типа // Integral: междунар. журн. прикл. наук и техн. - 2018. - № 4. - С. 504-510.
  17. Краткий курс высшей математики: учеб. пособие для втузов / В.Е. Шнейдер [и др.]. - М.: Высш. шк., 1972. - 640 с.
  18. Александров П.С. Лекции по аналитической геометрии. - М.: Наука, 1968. - 912 с.
  19. Тищенко А.В. Линейная алгебра. Элементы аналитической геометрии. - М.: Финакадемия, 2009. - 116 с.
  20. Таха Х.А. Введение в исследование операций. - М.: Вильямс, 2005. - 912 с.

Statistics

Views

Abstract - 56

PDF (Russian) - 71

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies