Выпуклые области, задаваемые условиями типа (2.1), (2.3), могут быть аппроксимированы в соответствии с основными положениями формализации, рассмотренной в [1, 33], с помощью одной гиперплоскости или выпуклого многогранника. [c.18]
Более широкими описательными возможностями обладает аппроксимация с помощью выпуклого многогранника. [c.20]
При использовании метода разложения возникает необходимость нахождения вершин выпуклых многогранников G/. [c.30]
Рассмотренная геометрическая интерпретация задачи линейного программирования возможна лишь при наличии двух независимых переменных. При трех переменных наглядное представление существенно усложняется, так как в этом случае имеет место некоторый выпуклый многогранник в трехмерном пространстве, соответствующий объему допустимых планов. [c.65]
Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
Эти понятия переносятся с двумерного пространства (плоскости) на многомерное. Напр., роль опорной прямой по отношению к и-мерному выпуклому многограннику в нем играет опорная гиперплоскость. [c.57]
Выпуклые многогранники и выпуклые многогранные конусы принадлежат к числу наиболее распространенных понятий математической экономики. В линейном и выпуклом программировании используются обязательно выпуклые области изменения переменных (допустимые множества по теоретико-множественной терминологии, многогранники — по геометрической) и выпуклые целевые функции. [c.57]
Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л. п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве выпуклый многогранник). [c.172]
Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции fix) и области М. Напр., если fix) линейна, а М— выпуклый многогранник, имеем задачу линейного программирования если же дополнительно ставится условие, чтобы переменные были целочисленными, то имеем задачу целочисленного программирования если зависимость U отд (т.е. форма f) носит нелинейный характер, то задачу нелинейного программирования. [c.187]
Выпуклая область 57 Выпуклая оболочка 57 Выпуклая целевая функция 385 Выпуклое программирование 57 Выпуклость 57 Выпуклость функции 57 Выпуклые множества 57 Выпуклые функции 57 Выпуклый многогранник 198 Выпуск (годовое производство) товаров и [c.462]
Надо найти максимум линейной функции на выпуклом многоугольнике. (В общем случае линейного программирования ищется максимум линейной функции на выпуклом многограннике, ле- [c.163]
Симплекс-метод. Это один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г.Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. [c.170]
Замечание. Совместно предположения 2.1 и 2.2 означают, что технологическое множество является выпуклым конусом. Предположение 2.3, выделяющее линейные технологии, означает, что этот конус является выпуклым многогранником в полупространстве [c.59]
I. Как было сказано, метод заключается в эквивалентной линеаризация. РПЯ линеаризация воспользуемся тем известным фактом, что вектор, принадлежащий выпуклому многограннику, можно разложить по вершинам этого многогранника. В нашем примере имеются векторы =( 1)и Vs (% Многогранники, которым принадлежат векторы, образуются пересечением соответственно областей ( ги, //), л + >и 4- для вектора Лл и ( ., Zi2), в чг + гг, / - для вектора eLz /см. рис. 10/. На рис заштрихованный прямоугольник - область, ограниченная условиями ( 4ц, в6 ), (g t t -ai) Пересечение прямоугольника с прямой du Att 4 выделяет отрезок -это и есть многогранник, которому принадлежит вектор, v , Аналогично, существует многогранник J t , которому принадлежит вектор < л . Отрезок Jft имеет 2 вершины I и 2. Их координаты ( ) и (JLM) Первый столбец относится к вершине 1, второй - к вершине . Вначале выписываем /сверху вниз/ аС , относящиеся к 1-й строке /модели /2.3//, затеи - относящиеся ко 2-й строке. [c.33]
Помимо примеров оптимизации конкретных производств описан метод определения координат вершин выпуклых многогранников, задающих допустимые области варьирования коэффициентов и используемых в ходе решения задачи дана блок-схема программы для определения вершин многогранников на ЭВМ. [c.2]
В работе были даны постановка задач , и метод решения. Постановка имеет вид задачи билинейного программирования, т.е. задачи линейного программирования с неизвестными, однако, коэффициентами. Для решения выполняется эквивалентная линеаризация модели, коэффициенты которой поддаются разложению по вершинам выпуклых.многогранников эти многогранники задают допустимые области изменения коэффициентов. [c.3]
ГЛАВА Е. ОПРЕДЕЛЕНИЕ ВЕРШИН ВЫПУКЛЫХ МНОГОГРАННИКОВ [c.31]
Пусть /С — выпуклый многогранник /С= д Лл й . В этом случае вычисление оператора проектирования сводится к решению задачи квадратичного программирования [c.184]
Итак, рассматривается следующая задача заданы (те+1)-мер-ные векторы А,, , X, е, и числа s , s+, n=l,. . ., N. Определено линейное отображение JV-мерного прямоугольника a s sn s в выпуклый многогранник Р в (/тг+1)-мерном пространстве [c.438]
То, что выпуклым многогранником является множество S (А), устанавливается аналогично ссылкой на систему неравенств (15.11). П [c.59]
Но максимум линейной формы на любом выпуклом многограннике, и в том числе на отрезке, треугольнике или выпуклом четырехугольнике, должен достигаться на его вершине (это утверждение известно из линейного программирования и широко применяется там фактически оно равносильно опирающейся на лемму о переходе к смешанным стратегиям из п. 9.4 лемме из п. 10.2). Поэтому для нахождения максимума в (21.8) достаточно найти вершины многоугольников 3 j п X, вычислить в них значения соответствующей формы XA.f и сравнить эти значения между собой. [c.74]
Точка у является либо внутренней в множестве у, либо принадлежит границе у и тогда содержится в пересечении у с некоторой опорной к у гиперплоскостью. В случае, когда имеется несколько таких пересечении, будет выбирать то из них, которое имеет наименьшую размерность. Ясно, что если эта размерность равна нулю, то у9 будет крайней точкой у, а если она положительна, то у будет внутренней точкой соответствующего пересечения. Обозначим это пересечение через у, допуская при этом и крайние случаи у -у и у = у. Для наглядности заметим, что если у есть выпуклый многогранник, то у есть наименьшая по размерности (или, что то же самое, по включению) грань у, содержащая . [c.137]
Во-вторых, отсюда же следует, что на X(s ) выражение ХА Y T представляет собой единую линейную форму от У, и на X(s ) система (13.2) оказывается системой именно линейных (а не билинейных ) неравенств, и множество ее решений составляет выпуклый многогранник, который зависит опять-таки не от конкретной стратегии X, и лишь от ее спектра ь% — ь Обозначим этот многогранник через 61 (s). [c.177]
Из условий предыдущей теоремы следует, что для принадлежности дележа с-ядру данной кооперативной игры необходимо и достаточно, чтобы его компоненты удовлетворяли некоторой конечной системе линейных неравенств. Это значит, что с-ядро в любой кооперативной игре является выпуклым многогранником. [c.236]
Допустим, что имеется L предприятий, каждое из которых имеет R опорных планов выпуска. Производственные возможности 1-го предприятия в аппроксимационной модели описываются выпуклым многогранником, заданным следующей системой ограничений [c.20]
При моделировании нефтеперерабатывающих производств в основном используется аппроксимация в виде выпуклых многогранников. Аппроксимирующие гиперплоскости могут быть применены для описания производственных возможностей отдельных процессов и производств. Практические аспекты применения аппроксимационных моделей для решения задач планирования нефтеперерабатывающих производств были рассмотрены в разработках ЦЭМИ АН СССР [5-7]. [c.21]
В планировании нефтеперерабатывающих производств нашел более успешное применение [1] другой тип аппроксимационной модели -аппроксимация с помощью выпуклых многогранников. [c.24]
Процедура построения выпуклого многогранника, аппроксимирующего области производственных возможностей, имеет определенное структурное xofl TBO j MeiofloM разложения Данцига - Вульфа [16]. Пусть имеется k (k = l,L) предприятий, производственные возможности которых описываются линейной моделью блочной структуры следующего вида k k k [c.24]
В отличие от метода Данцига — Вульфа, в котором производственные возможности отдельных предприятий представляются в виде линейной комбинации всех базисных решений х (s= , М ), в аппроксимаци-онных моделях выпуклые многогранники ооычно задаются на базе ограниченного множества опорных плановых решений. Ограниченность числа рассматриваемых в аппроксимационных моделях вариантов позволяет сократить размерность задач и объем обрабатываемой информации. [c.25]
С точки зрения математической корректности эквивалентного преобразования и технологической интерпретации модели и ее решения, представляют интерес методы линеаризации, основанные на принципе разложения варьируемых векторов //(") технологических коэффициентов я,-Дм) по вершинам выпуклых многогранников PJ, заданных ограничениями (2.21). Коэффициент аг-Дм)еС/- при этом может быть определен через координаты - = qj, a2q/< > anqj вершин выпуклого многогранника PJ-. [c.29]
В моделях с переменными параметрами, допускающих в некоторых случаях эффективную линеаризацию, в зависимости от алгоритма решения предусмотрена 1) генерация аппроксимационных вариантов, осуществляемая по ходу реализации алгоритма решения, или 2) предварительное определение множества аппроксимирующих вариантов путем разложения варьируемых векторов технологических параметров по вершинам выпуклых многогранников, определяющих допустимые области технологических параметров. [c.43]
Шелейховского (двумерной балансировки) 126, 130 ел. Аппроксимация с помощью выпуклого многогранника 18, 20 ел., 29, 30, 43, 45 [c.226]
Представим себе любую линейную оптимизационную задачу и кратко напомним основные особенности симплекс-метода. Его идея состоит в переходе от одного базисного (опорного) плана к другому таким образом, что линейная форма улучшается на каждом шаге и достигает экстремума. Переход происходит по вершинам выпуклого многогранника условий в я-мерном пространстве, причем на каждом шаге переход осуществляется в соседнюю вершину. При нахождении в такой вершине проводится проверка плана на оптимальность. Линейная форма (гиперплоскость) делит все пространство на две части. Вершинам, находящимся в верхней части, соответствуют отрицательные элементы целевой строки, а вершицам из нижней части — положительные. Переход осуществляется только в соседние вершины из верхнего полупространства до тех пор, пока в нем не останется ни одной вершины. Переход проводится в ту вершину, которой соответствует максимальный по абсолютной величине из отрицательных элементов целевой строки. Если на последнем шаге линейная форма имеет более одной общей точки с выпуклым многогранником условий, то имеется множество оптимальных пла- [c.60]
Во-вторых, каждое из J -и условий /2.2/ описывает выпуклую допустимую область - выпуклый многогранник. Так, для 1-го столбца / j 1/ эта область задается системой i Lii ZV/ и, например, условиями [c.31]
Образом а является выпуклый многогранник Р, и задача линейного программирования (1) — (3) может быть сформулирована так Задача А. Пусть задан вектор е а. = 1, 0,. . ., 0 в (т+1)-мерном пространстве. НайтивР точку х = е с наименьшим значением X, и ее прообраз s . Другими словами, нужно найти [c.418]
В данной работе описан пример гетерархической программы распознавания выпуклых многогранников по их изображению, полученному с помощью диссектора. Большинство работ других исследователей в этой области было связано с попыткой выделения на полном изображении сцены точек, обладающих определенными признаками, и построения полного контурного рисунка этой сцены. Если исходным материалом для процедуры распознавания служит полный контурный рисунок, как это [c.215]
В работе описана гетерархическая программа распознавания выпуклых многогранников. В основе программы лежит идея поэтапного распознавания объектов с использованием на каждом этапе той информации, которая была выделена на предшествующих этапах. Программа осуществляет поиск сначала контурных линий (границ объектов с фоном), затем граничных линий, которые разделяют тела, и, наконец, внутренних линий, которые соответствуют пересечениям граней одного тела. На каждом этапе обработки программа формулирует гипотезы о наиболее правдоподобных граничных или внутренних линиях и пытается их обнаружить. При формулировании каждой такой гипотезы программа определяет область, в которой может находиться предполагаемый отрезок линии, и осуществляет поиск в этой области. Если подходящий отрезок линии найден, программа отслеживает всю линию и находит ее концевую точку. После нахождения новой линии программа пытается по-новому интерпретировать сцену с учетом этой линии. Сравнительная эффективность программы обусловлена тем, что вместо исчерпывающего поиска линий она пользуется, как правило, поиском с предсказанием. Эксперименты по обработке сцен из параллелепипедов и призм, изображения которых получены при помощи диссектора, дали вполне удовлетворительные результаты. Хотя [c.242]
Выпуклые оболочки конечных множеств назьюаются выпуклыми многогранниками. [c.51]
Пересечение любого семейства выпуклых множеств само является выпуклым. В частнотсти, выпуклыми являются пересечения замкнутых полупространств. Оказывается, что все такие ограниченные пересечения и только они суть выпуклые многогранники ). [c.51]
Доказательство. Согласно п. 15.6 множество 8 (А) является множеством всех решений системы неравенств (15.10), т.е. пересечением конечного числа замкнутых полупространств. Кроме того, оно является ограниченным. Тем самым согласно п. 11.3 это множество является выпуклым многогранником. [c.59]
Заметим, что многогранность и выпуклость множеств оптимальных стратегий игроков в матричной игре являются элементарными и как бы непосредственно наблюдаемыми фактами (мы здесь оставляем в стороне возможные рассуждения по поводу нетривиальности утверждений о том, что ограниченное пересечение конечного числа замкнутых полупространств конечномерного евклидова пространства есть выпуклый многогранник, т.е. выпуклая оболочка конечного числа точек — вершин это наглядно и как бы очевидно). Напротив, доказательство непустоты этого многогранника потребовало, как мы видели, известных усилий. Эта теорема исторически не сразу поддалась доказательству, и даже высказывались сомнения в ее справедливости. [c.59]
Теорема. Если в игре Г = < х, у, Н) множества стратегий игроков х и у являются выпуклыми многогранниками в конечномерных евклидовых пространствах, а функция выигрыша Н непрерывна на х X у, го в этой игре игроки имеют оптимальные смешанные стратегии, а также — при любом е > 0 оптимальные стратегии, являющиеся смесями конечного числа чистых. [c.117]
Характеристическая функция задает свое с-ядро в виде выпуклого многогранника, определяемого как пересечение полупространств, т.е. "не вполне явным образом" (ср. замечание из п. 11.3 гл. 1 по поводу аналогичного задания множества оптимальных стратегий игроков в матричной игре). Поэтому вся теория с-ядра в кооперативных играх сводится в принципе к тому, чтобы переходить от такого задания этого многогранника к более явному его заданию путем указания его вершин (считаясь, разумеется, с тем, что этот многогранник может оказаться пустым). [c.237]