Симплексная форма общего перестановочного многогранника, заданного неприводимой системой

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

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2014
Main Authors:	Емец, О.А., Леонова, М.В.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Subjects:	Оптимальное управление и методы оптимизации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/207721
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой / О.А. Емец, М.В. Леонова // Проблемы управления и информатики. — 2014. — № 1. — С. 68-79. — Бібліогр.: 19 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860123691995627520
author	Емец, О.А. Леонова, М.В.
author_facet	Емец, О.А. Леонова, М.В.
citation_txt	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой / О.А. Емец, М.В. Леонова // Проблемы управления и информатики. — 2014. — № 1. — С. 68-79. — Бібліогр.: 19 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Одержано симплексну форму загального переставного многогранника, заданого незвідною системою лінійних обмежень, за допомогою перетворення його з використанням алгоритму перетворення задачі лінійного програмування в стандартній формі до вигляду, необхідного для застосування алгоритму Кармаркара. Розглянуто ілюстративний приклад. The simplex shape of general permutational polyhedron, given by irreducible system of linear constraints by converting it using an algorithm converting the linear programming problem in standard form to the form required for applying the Karmarkar algorithm, is obtained. An illustrative example is considered.
first_indexed	2025-12-07T17:40:41Z
format	Article
fulltext	© О.А. ЕМЕЦ, М.В. ЛЕОНОВА, 2014 68 ISSN 0572-2691 УДК 519.85 О.А. Емец, М.В. Леонова СИМПЛЕКСНАЯ ФОРМА ОБЩЕГО ПЕРЕСТАНОВОЧНОГО МНОГОГРАННИКА, ЗАДАННОГО НЕПРИВОДИМОЙ СИСТЕМОЙ Введение Задачи комбинаторной оптимизации (см., например, [1–14]) — актуальное направление исследований в теории оптимизации. Существенным для разработки эффективных методов является знание свойств комбинаторных множеств и их выпуклых оболочек — комбинаторных многогранников, в частности перестано- вочного многогранника. Его структура и свойства достаточно хорошо исследова- ны [2, 5, 6, 14, 15]. Свойства общего перестановочного многогранника при преоб- разовании его в форму, необходимую для применения алгоритма Кармаркара, по- ка недостаточно изучены. Исследования комбинаторных многогранников важны, поскольку они используются при разработке методов решения задач комбинатор- ной оптимизации. Применяя алгоритм Кармаркара, необходимо найти симплекс- ную форму многогранника, под которой понимают многогранник, полученный из многогранника исходной задачи согласно алгоритму преобразования задачи ли- нейного программирования (ЗЛП) в форму, необходимую для алгоритма Кармар- кара (см., например, [16, 17]). Известна [18] симплексная форма перестановочного многогранника без учета возможного наличия избыточных ограничений. Поскольку неприводимая система перестановочного многогранника имеет только необходимые ограничения, то с точки зрения вычислительной сложности в алгоритмах целесообразно использо- вать симплексную форму перестановочного многогранника, которая обусловли- вается его неприводимой системой. Поэтому актуальной является задача установ- ления симплексной формы общего перестановочного многогранника, заданного неприводимой системой линейных ограничений. Такая форма необходима, в част- ности, для применения алгоритма Кармаркара (АК) в методах решения комбина- торных оптимизационных задач. 1. Постановка задачи Поставим задачу исследования общего перестановочного многогранника при преобразованиях, необходимых для приведения ЗЛП в нужную форму при при- менении алгоритма Кармаркара (АК). Используем терминологию из [2]. Рассмотрим решения линейной условной частично комбинаторной задачи оптимизации на перестановках вида: найти упорядо- ченную пару  ** ),( yyC такую, что ,extr)( 1 * jj m jRy ycyC m    (1) jj m jRy ycy m    1 * extrarg (2) при комбинаторных условиях kk nk RGExxx   )()...,,( 1 (3) и дополнительных ограничениях , 1 ijij m j bya   ,rJi , 1 ijij m j bya   ,\ rs JJi (4) Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 69 где )(GEkn — евклидово множество перестановок, образованных элементами муль- тимножества G; ;)...,,,...,,( 11 m mkk Ryyxxy   ii yx  ;kJi skrm ,,, — на- туральные константы );( km  ,jc ,ija ib — заданные действительные числа ,mJj ;rJi mR — m-мерное евклидово арифметическое пространство. Под kJ подразумевается множество первых k натуральных чисел },...,,2,1{ kJk  а .0 J При решении задачи (1)–(4) методом комбинаторного отсечения [4] важным является решение вспомогательной задачи линейного программирования (ВЗЛП), которая образуется из задачи вида (1)–(4) заменой ограничения (3) условием при- надлежности точки x общему перестановочному многограннику :)(Gkn ).(Gx kn Пусть мультимножество }...,,{ 1 kggG  имеет основу )...,,()( 1 neeGS  и пер- вичную спецификацию )....,,,(][ 21 nG  Пусть элементы в G и в )(GS прону- мерованы так, что ;...21 kggg  ....21 neee  (5) Задание общего перестановочного многогранника неприводимой системой линейных ограничений известно [2, 5, 15]: , 11 j k j j k j gx    (6) 1 1      jk j j j gx ,kJ (7) для которых ,I )).\(})1{\((\ 121 1  kkk JJJJI n 2. Алгоритм преобразования многогранника в симплексную форму Рассмотрим алгоритм преобразования (АП) ЗЛП в стандартной форме к виду, необходимому для применения алгоритма Кармаркара, способом, изложенным в [16, 17]. Матричную запись ЗЛП приведем в стандартной форме: найти maxcx при условиях: ;bAx ,0x (8) где );...,,( 1 kccc  x — вектор, транспонированный к вектору );...,,( 1 T kxxx  ;)( ,1 ,1 ri kjijaA    .)...,,( T 1 rbbb  Символическая запись 0x здесь и далее означа- ет, что все координаты вектора x неотрицательные. Общий алгоритм преобразования ЗЛП с системой ограничений (8) можно представить следующей последовательностью шагов. Шаг 1. Сводим заданную систему (8) к так называемому каноническому [19, с. 17] виду: ;byAx  ,0, yx (9) где .)...,,( T 1 ryyy  Шаг 2. Вводим дополнительное ограничение вида , 1 1      k j r i ij Uyx (10) 70 ISSN 0572-2691 где U — достаточно большое действительное положительное число такое, что все допустимые точки исходного множества решений системы (8) удовлетворя- ют (10). Добавляя еще одну неотрицательную переменную u, сводим неравенст- во (10) к равенству . 1 1      k j r i ij Uuyx (11) Шаг 3. Сводим систему уравнений (9) к эквивалентной ей однородной сис- теме. Это можно сделать, умножив правую часть уравнений системы на равное единице выражение: . 1 1 U uyx k j r i ij     Уравнения системы (9) приобретут вид ,0 buyAxA yx (12) где матрица ri kj x ij x aA ,1 ,1 )(    имеет элементы Ubaa iij x ij / kJj , ;rJi матрица ri kj y ij y aA ,1 ,1 )(    имеет элементы Uba i y ii /1 ;rJi ,/Uba i y ij  ,ij  ,rJi ;kJj вектор rR T)0...,,0,0(0 — нулевой вектор-столбец арифметического евклидова пространства .rR Шаг 4. Превращаем условие (11) в такое, которое вместе с остальными усло- виями задачи определяет симплекс с вершиной в начале координат и с основани- ем, которое отсекает единичные отрезки на положительных направлениях коор- динатных осей. Это делается введением новых переменных: U x X j j  ,kJj U y Y i i  .rJi (13) Обозначим также .V U u  (14) С учетом (12)–(14) рассматриваемая ЗЛП принимает вид maxUcX (15) при условиях ,0 bVYAXA YX (16) ,1 11   VYX r i i k j j (17) ,0)...,,( T 1  kXXX ,0)...,,( T 1  rYYY ,0V (18) где ;)( ,1 ,1 ri kj X ij X aA    iij X ij bUaa  ,rJi ;kJj ;)( ,1 ,1 ri kj Y ij Y aA    i Y ii bUa  ;rJi i Y ij ba  ,ji  ,rJi .kJj Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 71 Шаг 5. Обеспечиваем выполнение условия удовлетворения системе ограни- чений точкой , 1 ...,, 1 , 1 NR NNN       являющейся центром (барицентром) симплекса, где N — размерность пространст- ва, которая определяется на этом шаге. С этой целью в каждом из однородных уравнений системы (16) с номером і вычтем в левой части дополнительную неотрицательную искусственную пере- менную ,iZ ,rJi с коэффициентом, равным алгебраической сумме всех коэф- фициентов левой части этого же уравнения. Причем эта переменная в виде штра- фа также добавляется и к функции цели (15) с коэффициентом .M Число 0M должно быть достаточно большим, чтобы обеспечить соответствующей перемен- ной нулевое значение при максимизации модифицированной целевой функции при полученных условиях. Сумма ri JiZ  добавляется и в левую часть (17). ЗЛП (15)–(18) преобразуется к виду max, 1    r i iZMUcX (19) ,0 bVZAYAXA ZYX (20) ,1 111    VZYX r i i r i i k j i (21) ,0X ,0Y ,0)...,,( T 1  rZZZ ,0V (22) где ;)( ,1 ,1 ri kj Z ij Z aA    iij k j iiiiij k j Z ii bkUaUbbkbUkbaUa )12()1( 11    ;rJi 0Z ija ,ji  ,rJi .kJj Очевидно, что для полученной системы ограничений (20)–(22) точка NR NNN VZYX        1 ...,, 1 , 1 ),,,( ** является допустимым решением, где N VZYX jji 1**  ,kJi ,rJj а размерность пространства вычисляет- ся так: .12  rkN 3. Преобразования с помощью АП ЗЛП с допустимой областью — перестановочным многогранником, заданным неприводимой системой ограничений Установим вид ЗЛП, в котором перестановочный многогранник является до- пустимой областью, при сведении ее к форме, необходимой для применения алго- ритма Кармаркара. Докажем следующий факт. Теорема. Симплексная форма общего перестановочного многогранника, за- данного неприводимой системой (6), (7), имеет вид , ,0 \ \|\| 1 1 \|\| 1 1 k I J j Jjj jk j j j jk J WVYXgYXgU kk                                             (23) ,0 111                              k k Jk k j I J j k j j k j j WVYgXgU (24) 72 ISSN 0572-2691 ,1 1           k j J I J I J j k kk WWVYX (25) где ;)(2 11 1 1 1 1 1 1                       j i i j i ik j k k j njj n j ggCeekeU n (26) ;;; V U u Ji U y YJj U x X r i ik j j  (27) ;1)1( 1 1                 jk j k I gkCU (28) ;1 1              k j jk I k gkCkU (29) kJWW , — дополнительные неотрицательные искусственные переменные с ко- эффициентами соответственно k  , . Доказательство. Обоснование теоремы будет конструктивным (алгоритми- ческим) с доказательством необходимых вспомогательных утверждений. Оно фактически применимо к системе (6), (7) АП. Шаг 1. Сводим (6), (7) к каноническому виду, вводя неотрицательные пере- менные :y 1 1        jk j j j gyx ,kJ ,I (30) . 11    k j j k j j gx (31) Шаг 2. Вводим дополнительное ограничение        k j I J j Uyx k1 (32) в форме , 1        k j I J j Uuyx k (33) где .0u Следующее утверждение устанавливает возможность вычисления U. Утверждение 1. Для общего перестановочного многогранника, заданного в виде неприводимой системы (6), (7) при выполнении условий (5), справедливо неравенство , 1 Uyx I J k j j k      (34) где U определяется по формуле (26). Доказательство. Каждое неравенство из (7) 1 1      jk jj j gx (35) Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 73 эквивалентно при условиях (5), (6) такому неравенству: . \ 1\ j J j j Jj gx k k     (36) Объединяя неравенства вида (35), (36) для одинаковых сумм переменных в их левых частях, получаем . 1 1 1         j jk j j j j gxg (37) Из (30) имеем , 1 1 j jj jk xgy       (38) а из левой части (37) справедливо . 1     j j j j gx (39) Учитывая (38) и (39), получаем . 11 1        j j j jk ggy (40) Поскольку количество подмножеств в kJ с одинаковым j равно коли- честву сочетаний с k элементов по j, то второе слагаемое в левой части (34) оце- нивается по формуле (40) следующим образом. 1. Если ,1,11  n то , !1)!1( !1 k k k Ck    . )!1(!1 !1 k k k Ck k    Исходя из (40) и состава множества І, имеем .)(2 1 1 11 11                  k j j i i j i ik j kk I J nk ggCggky 2. Если ,1,11  n то ).(2 1 11 1 1 1 1 ggkggCy k j i i j i ik j k k j I J k                   3. Общий случай при 1,11  n .)(2 1 1 11 11 1                  k j j i i j i ik j kk I J nk ggCggky (41) Объединяя три случая соотношения 1 и ,n а также учитывая обозначение основы, первичную спецификацию и равенство (6): , 11    n j jj k j j ex получаем, что справедливо (34), где 74 ISSN 0572-2691                           1 1 11 11 1 1 ,2 k j j i i j i ik j kn n j jj n ggCeekeU т.е. U определяется по (26), что и требовалось доказать. Шаг 3. Сводим систему (30), (31) к эквивалентной однородной системе, умно- жая правые части уравнений системы на выражение, равное согласно (33) единице: .1 1                    Uuyx k j I J j ky После приведения подобных получаем следующую систему: ,, 01 \ \|\| 1 1 1 \|\| 1 1 1 IJ uyxgUyxgU k I JJj j j jk j j j jk kk                                                 (42) .01 1 1 11 1                              uygUxgU I J k j j k j j k j j k (43) Шаг 4. Выполняем замену переменных согласно формулам (27) и из (33), (42) и (43) и получаем систему: ,, 0 \ \|\| 1 1 \|\| 1 1 IJ VYXgYXgU k I JJj j j jk j j j jk kk                                               (44) ,0 111                            I J k j j k j j k j j k VYgXgU (45)        k j I J j VYX k1 .1 (46) При такой замене переменных целевая функция ВЗЛП max 1   k j jj Xc при- нимает вид .max 1   k j jj XcU (47) Шаг 5. В каждом из уравнений (44), (45) из левой части вычтем свою неот- рицательную переменную ,W ,kJ с коэффициентами , которые опре- деляются соответственно по формулам (28), (29). Утверждение 2. При фиксированном подмножестве ,, IJk  сумма коэффициентов при переменных в уравнениях (44), (45) равна величине , вы- числяемой по формулам (28), (29). Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 75 Доказательство. Справедливость утверждения обосновывается непосредст- венной проверкой. Первое слагаемое в (44) содержит  переменных ,, jX j и одну пере- менную Y с коэффициентом при каждой . 1 1    j jkgU Второе алгебраическое слагаемое в (44) содержит \kJ переменных ,\,  kj JjX а также 1    k I C переменных ,,, IJY k  и переменную V. Все эти переменные имеют множитель .1 1     jk j g Отметим, что .\  kJk Таким образом, U входит в сумму 1 раз. Общее количество вхождений слагаемого     1 1 j jkg выражается формулой .11)( kCCk k I k I       Учитывая это, для  получаем формулу (28). Аналогично, подсчитывая коэффициенты в (45), имеем формулу (29). Утверждение доказано. Выполнив шаг 5 АП, для ВЗЛП (1), (2), (6), (7) имеем такую задачу: max 1     WMXcU kJ k j jj при условиях ,, 0 \ \|\| 1 1 \|\| 1 1 IJ WVYXgYXgU k I J j Jjj jk j j j jk kk                                             ,0 111                         k k Jk I J k j j k j j k j j WVYgXgU ,1 1           k j J I J I J j k kk WWVYX где kU   ,, определяются соответственно согласно (26), (28), (29), а связь старых и новых переменных устанавливает формула (27). Выполнив шаг 5, получаем, что точка NR NN WVYX        1 ...,, 1 );;;( является допустимым решением последней задачи, здесь .22     k I CkN Сравнивая полученные на шаге 5 ограничения с формулами (23)–(29), видим, что теорема доказана. 76 ISSN 0572-2691 4. Иллюстративный пример Получим симплексную форму перестановочного многогранника для та- кой задачи. Пусть в (1), (2), (6), (7) ,4k },2;2;1;0{G т.е. ].2,1,1[][ G По- скольку 2,1 321  n и ,211411 k то  })1{\((\ 23 JJI }.3,1{}2{\))\( 322  JJJ Запишем функцию цели: max44332211  xcxcxcxcz и в ВЗЛП систему (6), (7) в таком виде:                        .5 ,5 ,5 ,5 ,5 ,2 ,2 ,2 ,2 4321 432 431 421 321 4 3 2 1 xxxx xxx xxx xxx xxx x x x x После приведения системы к каноническому виду (шаг 1) получим                        .5 ,5 ,5 ,5 ,5 ,2 ,2 ,2 ,2 4321 234432 134431 124421 123321 44 33 22 11 xxxx yxxx yxxx yxxx yxxx yx yx yx yx Введем дополнительное ограничение (шаг 2) в таком виде: .23413412412343214321 Uyyyyyyyyxxxx  На этом же шаге сводим введенное ограничение к равенству, добавляя до- полнительную неотрицательную переменную u в левую часть: ,23413412412343214321 Uuyyyyyyyyxxxx  (48) где согласно (26) .21U Далее (шаг 3) преобразовываем систему уравнений к однородной, умножив правую часть уравнений системы на равное единице выражение: .23413412412343214321 U uyyyyyyyyxxxx  Таким образом, после приведения подобных выражений запишем ,0)( 2 )( 2 1 23413412412343243211        uyyyyyyyxxx U yx U ,0)( 2 )( 2 1 23413412412343143122        uyyyyyyyxxx U yx U ,0)( 2 )( 2 1 23413412412342142133        uyyyyyyyxxx U yx U Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 77 ,0)( 2 )( 2 1 23413412412332132144        uyyyyyyyxxx U yx U ,0)( 5 )( 2 1 23413412443214123321        uyyyyyyyx U yxxx U ,0)( 5 )( 2 1 23413412343213124421        uyyyyyyyx U yxxx U ,0)( 5 )( 5 1 23412412343212134431        uyyyyyyyx U yxxx U ,0)( 5 )( 5 1 13412412343211234432        uyyyyyyyx U yxxx U .0)( 5 )( 5 1 23413412412343214321        uyyyyyyyy U xxxx U Вводя новые переменные V U u U y Y U x X i i j j  ,, в последней системе и в уравнении (48) (шаг 4), получаем симплексную форму заданного перестановочно- го многогранника: ,0)(2))(2( 23413412412343243211  VYYYYYYYXXXYXU ,0)(2))(2( 23413412412343143122  VYYYYYYYXXXYXU ,0)(2))(2( 23413412412342142133  VYYYYYYYXXXYXU ,0)(2))(2( 23413412412332132144  VYYYYYYYXXXYXU ,0)(5))(5( 23413412443214123321  VYYYYYYYXYXXXU ,0)(5))(5( 23413412343213124421  VYYYYYYYXYXXXU ,0)(5))(5( 23412412343212134431  VYYYYYYYXYXXXU ,0)(5))(5( 13412412343211234432  VYYYYYYYXYXXXU ,0)(5))(5( 23413412412343214321  VYYYYYYYYXXXXU .123413412412343214321  VYYYYYYYYXXXX На шаге 5 из каждого из 9r однородных уравнений вычтем неотрицатель- ную переменную ,, kJW  с коэффициентом ,i ,kJi равным алгебраиче- ской сумме всех коэффициентов левой части уравнения. Эти же переменные при- бавим к целевой функции с коэффициентом .M Их же добавляем в последнее равенство. Функция цели с учетом этого и замены переменных преобразуется к виду  )( 44332211 XcXcXcXcU max,)( 12342341341241234321  WWWWWWWWWM а система ограничений — ,0)(2))(2( 1123413412412343243211  WVYYYYYYYXXXYXU ,0)(2))(2( 2123413412412343143122  WVYYYYYYYXXXYXU 78 ISSN 0572-2691 ,0)(2))(2( 3123413412412342142133  WVYYYYYYYXXXYXU ,0)(2))(2( 4123413412412332132144  WVYYYYYYYXXXYXU ,0)(5))(5( 123323413412443214123321  WVYYYYYYYXYXXXU ,0)(5))(5( 124323413412343213124421  WVYYYYYYYXYXXXU ,0)(5))(5( 134323412412343212134431  WVYYYYYYYXYXXXU ,0)(5))(5( 234313412412343211234432  WVYYYYYYYXYXXXU ,0)(5))(5( 1234423413412412343214321  WVYYYYYYYYXXXXU  VYYYYYYYYXXXX 23413412412343214321 .123412341341241234321  WWWWWWWWW Используя формулы (28), (29) или непосредственно по уравнениям, опреде- ляем значения коэффициентов: .19,19,16 431  Таким образом, симплексная форма перестановочного многогранника, обра- зованного перестановкой элементов мультимножества },2;2;1;0{G имеет вид ,016)(2)(19 123413412412343243211  WVYYYYYYYXXXYX ,016)(2)(19 223413412412343143122  WVYYYYYYYXXXYX ,016)(2)(19 323413412412342142133  WVYYYYYYYXXXYX ,016)(2)(19 423413412412332132144  WVYYYYYYYXXXYX ,019)(5)(16 12323413412443214123321  WVYYYYYYYXYXXX ,019)(5)(16 12423413412343213124421  WVYYYYYYYXYXXX ,019)(5)(16 13423412412343212134431  WVYYYYYYYXYXXX ,019)(5)(16 23413412412343211234432  WVYYYYYYYXYXXX ,019)(5)(16 123423413412412343214321  WVYYYYYYYYXXXX  VYYYYYYYYXXXX 23413412412343214321 .112342341341241234321  WWWWWWWWW Отметим, что 222)(24 3 4 1 4  CCN , что равно количеству переменных в симплексной форме перестановочного многогранника. Заключение Здесь получена симплексная форма общего перестановочного многогранни- ка, заданного неприводимой системой линейных ограничений. Получение сим- плексной формы общего перестановочного многогранника является актуальным, поскольку эта форма может использоваться в методах решения комбинаторных оптимизационных задач. Как направление дальнейших исследований интересно изучить трансформацию множества перестановок и его выпуклой оболочки при переходе к ее симплексной форме. Международный научно-технический журнал «Проблемы управления и информатики», 2014, № 1 79 О.О. Ємець, М.В. Леонова СИМПЛЕКСНА ФОРМА ЗАГАЛЬНОГО ПЕРЕСТАВНОГО МНОГОГРАННИКА, ЗАДАНОГО НЕЗВІДНОЮ СИСТЕМОЮ Одержано симплексну форму загального переставного многогранника, зада- ного незвідною системою лінійних обмежень, за допомогою перетворення його з використанням алгоритму перетворення задачі лінійного програмування в стандартній формі до вигляду, необхідного для застосування алгоритму Кар- маркара. Розглянуто ілюстративний приклад. O.A. Iemets, M.V. Leonova SIMPLEX SHAPE OF GENERAL PERMUTATIONAL POLYHEDRON, GIVEN BY IRREDUCIBLE SYSTEM The simplex shape of general permutational polyhedron, given by irreducible system of linear constraints by converting it using an algorithm converting the linear pro- gramming problem in standard form to the form required for applying the Karmarkar algorithm, is obtained. An illustrative example is considered. 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за- дач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 2. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ : Інститут систем досліджень освіти, 1993. — 188 с. — http://dspace.uccu.org.ua/handle/123456789/487 3. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. — Киев : Наук. думка, 1986. — 268 с. 4. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи. — Полтава : РВЦ ПУСКУ, 2005. — 103 с. — http://dspace.uccu.org.ua/handle/123456789/376. 5. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклі- дової комбінаторної оптимізації на переставних множинах. — Полтава : Легат, 1999. — 64 с. — http://dspace.uccu.org.ua/handle/123456789/488. 6. Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: властиво- сті та розв’язування. — Полтава : РВЦ ПУСКУ, 2006. — 129 с. — http://dspace.uccu. org.ua/handle/123456789/377. 7. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. — Київ : Наук. думка, 2005. — 117 с. — http://dspace.uccu.org.ua/handle/123456789/474. 8. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. — Киев : Наук. думка, 2008. — 159 с. — http://dspace.uccu.org.ua/handle/123456789/473. 9. Емец О.А., Черненко О.А. Оптимизация дробно-линейных функций на размещениях. — Киев : Наук. думка, 2011. — 154 с. — http://dspace.uccu.org.ua/handle/123456789/467 10. Ємець О.О., Парфьонова Т.О. Транспортні задачі комбінаторного типу: властивості, розв’язування, узагальнення. — Полтава: ПУЕТ, 2011. — 174 с. — http://dspace.uccu.org. ua/handle/123456789/353. 11. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. — Пол- тава : РВВ ПУЕТ, 2011. — 309 с. 12. Гуляницький Л.Ф. Розробка моделей і наближених методів комбінаторної оптимізації та їх застосування в інформаційних технологіях : Автореф. дис. … д-ра техн. наук: 01.05.02. — Київ, 2005. — 32 с. 13. Гребеннік І.В. Математичні моделі і методи комбінаторної оптимізації в геометричному проектуванні : Автореф. дис. … д-ра техн. наук: 01.05.02. — Харків, 2006. — 30 с. 14. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинатор- ная теория многогранников). — М. : Наука, 1981. — 344 с. 15. Ємець О.О., Недобачій С.І. Загальний переставний многогранник: незвідна система лінійних обмежень та рівняння всіх гіперграней // Наукові вісті НТУУ «КПІ». — 1998. — № 1 (2). — С. 100–106. 16. Зайченко Ю.П. Исследование операций: Учебн. — Киев : Видавничий дім «Слово», 2003. — 688 с. 17. Таха Х.А. Введение в исследование операций. — М. : Издательский дом «Вильямс», 2005. — 912 с. 18. Ємець О.О., Ємець Є.М., Ольховський Д.М. Оптимізація лінійної функції на переставлен- нях: перетворення переставного многогранника до вигляду, необхідного для використання в алгоритмі Кармаркара // Наукові вісті НТУУ «КПІ». — 2010. — № 2. — С. 43–49. 19. Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы иссле- дования операций: Учебн. пособие для вузов. — Киев : Вища шк., 1979. — 312 с. Получено 25.12.2012 http://dspace.uccu/ http://dspace.uccu/
id	nasplib_isofts_kiev_ua-123456789-207721
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2025-12-07T17:40:41Z
publishDate	2014
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Емец, О.А. Леонова, М.В. 2025-10-13T12:36:28Z 2014 Симплексная форма общего перестановочного многогранника, заданного неприводимой системой / О.А. Емец, М.В. Леонова // Проблемы управления и информатики. — 2014. — № 1. — С. 68-79. — Бібліогр.: 19 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207721 519.85 10.1615/JAutomatInfScien.v46.i2.40 Одержано симплексну форму загального переставного многогранника, заданого незвідною системою лінійних обмежень, за допомогою перетворення його з використанням алгоритму перетворення задачі лінійного програмування в стандартній формі до вигляду, необхідного для застосування алгоритму Кармаркара. Розглянуто ілюстративний приклад. The simplex shape of general permutational polyhedron, given by irreducible system of linear constraints by converting it using an algorithm converting the linear programming problem in standard form to the form required for applying the Karmarkar algorithm, is obtained. An illustrative example is considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Симплексная форма общего перестановочного многогранника, заданного неприводимой системой Симплексна форма загального перестановного могогранника, заданого ненаведеною системою Simplex shape of general permutational poly-hedron, given by irreducible system Article published earlier
spellingShingle	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой Емец, О.А. Леонова, М.В. Оптимальное управление и методы оптимизации
title	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой
title_alt	Симплексна форма загального перестановного могогранника, заданого ненаведеною системою Simplex shape of general permutational poly-hedron, given by irreducible system
title_full	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой
title_fullStr	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой
title_full_unstemmed	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой
title_short	Симплексная форма общего перестановочного многогранника, заданного неприводимой системой
title_sort	симплексная форма общего перестановочного многогранника, заданного неприводимой системой
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207721
work_keys_str_mv	AT emecoa simpleksnaâformaobŝegoperestanovočnogomnogogrannikazadannogoneprivodimoisistemoi AT leonovamv simpleksnaâformaobŝegoperestanovočnogomnogogrannikazadannogoneprivodimoisistemoi AT emecoa simpleksnaformazagalʹnogoperestanovnogomogogrannikazadanogonenavedenoûsistemoû AT leonovamv simpleksnaformazagalʹnogoperestanovnogomogogrannikazadanogonenavedenoûsistemoû AT emecoa simplexshapeofgeneralpermutationalpolyhedrongivenbyirreduciblesystem AT leonovamv simplexshapeofgeneralpermutationalpolyhedrongivenbyirreduciblesystem

Симплексная форма общего перестановочного многогранника, заданного неприводимой системой

Institution

Similar Items