Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, определение для каждой из них значений переменных (j = 1, 2,. .., 6) и вычисление по ним в каждой вершине величины целевой функции. [c.69]
Так как ограничения в виде уравнений представляют собой плоскости в -мерном пространстве, а также условия х,.> 0, то решение ЗЛП ищется в вершинах образованного в -мерном пространстве многогранника, который сам по себе представляет область допустимых решений. [c.200]
В линейном программировании применяются линейные ограничения, которые изображаются прямыми линиями или полуплоскостями, ограниченными прямыми. Область допустимых решений может ограничиваться прямыми линиями. Область является выпуклой, т. е. она ограничена таким образом, что всякая прямая линия, вышедшая за границы этой области, никогда в нее не возвращается. Наконец, область допустимых решений характеризуется вершиной, образуемой пересечением прямых. [c.189]
Если в задачах линейного программирования точка экстремума является вершиной многогранника, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума. [c.347]
Благодаря этому множество поиска решений радикально сокращается, поскольку "устройство" графов с заданной высокой симметрией известно из аналитического решения. Все л-вершинные графы, имеющие заданную симметрию, оказываются в области допустимых решений. Следовательно, вообще говоря, решение получается неоднозначным и выбор решения надо производить среди графов с одинаковой симметрией. Таким образом, от полного перебора л-вершинных графов задачу удалось свести к полному перебору всех л-вершинных графов с заданной (высокой) симметрией, структура и способ генерации которых известны и поддаются сравнительно легкому перечислению, а при наличии естественных практических ограничений (число портов у вершин, т.е. степени вершин графа) это перечисление сводится к анализу всего нескольких решений. [c.241]
Следовательно, область допустимых значений параметров (хь х2) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит не ниже этих прямых). Область допустимых значений параметров (хь х2) можно назвать неограниченным многоугольником . Минимум целевой функции 3,8xj + 4,2х2 может достигаться только в вершинах этого многоугольника . Вершин всего три. Это пересечения с осями абсцисс (10, 0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина — это точка А пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений [c.167]
Если целевая функция имеет конечный экстремум, то по крайней мере одно оптимальное решение является базисным (вершиной допустимого множества). Это означает, что при поиске оптимального решения в допустимой области можно ограничиться базисными допустимыми решениями. [c.446]
Другое направление решения задачи линейного программирования с переменными векторами условий, заданными на сепарабельных выпуклых множествах, связано с предварительным определением всех вершин" допустимых значений технологических коэффициентов и последующим формированием и решением задачи линейного программирования, в которой для процессов с переменными технологическими коэффициентами рассматривается несколько вариантов, полученных в результате определения вершин" [17-20]. Одна из первых задач подобного типа [17] включала элементарный случай варьирования технологических коэффициентов, когда область их допустимых значений представляла собой многогранник, образованный пересечением и-мерного параллелепипеда одной гиперплоскостью. [c.15]
Решение задачи линейного программирования находится в вершине или на границе допустимой области, поэтому достаточно рассмотреть значения целевой функции только в вершинах. [c.271]
Каждую точку пространства решений можно определить с помощью переменных Х, АЗ, АЗ, X, Х . Увеличение переменных АЗ, Аф АЗ будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Нас интересует прежде всего алгебраическое представление вершин допустимого множества. Анализируя рис. 1.3, можно записать [c.447]
Помимо примеров оптимизации конкретных производств описан метод определения координат вершин выпуклых многогранников, задающих допустимые области варьирования коэффициентов и используемых в ходе решения задачи дана блок-схема программы для определения вершин многогранников на ЭВМ. [c.2]
В работе были даны постановка задач , и метод решения. Постановка имеет вид задачи билинейного программирования, т.е. задачи линейного программирования с неизвестными, однако, коэффициентами. Для решения выполняется эквивалентная линеаризация модели, коэффициенты которой поддаются разложению по вершинам выпуклых.многогранников эти многогранники задают допустимые области изменения коэффициентов. [c.3]
Для иллюстрации того, как устроена модель проблемной области и как планировщик может использовать ее при поиске решения для достижения поставленной цели управления, рассмотрим один класс таких моделей, часто встречающийся на практике. Это так называемые функциональные модели. Всякая функциональная модель представляет собой сеть без ориентации, включающую в себя вершины двух типов дескрипторы и спецификаторы. При графическом изображении функциональных моделей дескрипторы принято обозначать кружками, а спецификаторы — прямоугольниками. Всякому спецификатору сопоставляется некоторое функциональное выражение вида f(xlt xz, . ., яя)=0, причем предполагается, что / допускает явное разрешение хотя бы относительно одного из аргументов Х[. Другими словами, хотя бы для одного xt это уравнение можно переписать в виде Xi=f (xi,. . ., x i, xi+i,. . ., xn). Такая операция называется допустимым разрешением спецификатора. Допускается, что для одного спецификатора может быть от 1 до п допустимых разрешений. Со спецификатором f(xi, хг,. . ., л )=0 связано п ребер функциональной модели, каждое из которых соединено с одним из дескрипторов множества хг, х2,. . ., хп . Два спецификатора в функциональной модели соединены друг с другом некоторым дескриптором, если последний определяет аргумент, общий для обоих спецификаторов. [c.234]
БАЗИСНОЕ РЕШЕНИЕ (опорный план) [basi solution] — термин линейного программирования, одно из допустимых решений, находящихся в вершинах области допустимых решений, либо (если линия уровня параллельна одному из отрезков границы области) Б.р. — весь этот отрезок (см. рис. Л.2 к ст. "Линейное программирование"). Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений. [c.26]
БАЗИСНОЕ РЕШЕНИЕ — термин линейного программирования. Так называют одно из допустимых решений, находящихся в вершинах области допустимых решений (рис. 10 к статье Линейное программирование ). Почему оно базисное Дело в том, что при решеиии задачи линейного программирования можно поступить так найти любое из вершинных решений, на обязательно оптимальное, и принять №0 за исходный пункт расчетов. Оно и будет базисным. Если окажется, что оно и оптимальное, расчет на том закопчен. Если нет—последовательно проверяют, не будут ли оптимальными соседние вершинные точки ту из них, в которой план эффективнее, принимают снова за исходную точку, и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строится так называемый симплекс—метод решения задач линейного программирования. [c.116]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Описанная процедура С. м. л. п. на языке геометрич. представлений, изложенных выше, означает, что оптимальное решение находится путем постепенного передвижения прямой или плоскости равных значений целевой функции параллельно самой себе в направлении от начала координат, соответствующего нулевому значению целевой функции, через вершины га-мерного симплекса к крайней вершине, за к-рой отыскиваемая совокупность значений переменных Xj (при =1, 2,. .., и.) выходит за пределы симплекса, а следовательно, за пределы области допустимых решений. В этой вершине и находится искомая точка, координаты к-рой указывают значения переменных, образующих оптимальное решение задачи. [c.22]
Для линеаризации используется разложение коэффициентов модели по вершинам их допустимых областей. Разложение обеспечивает эквивалентность исходной н линейной модели и линеаризованной ее формы. По решению линейной задачи восстанавливают далее искомые оптимальные значения X и о . [c.31]
В моделях с переменными параметрами, допускающих в некоторых случаях эффективную линеаризацию, в зависимости от алгоритма решения предусмотрена 1) генерация аппроксимационных вариантов, осуществляемая по ходу реализации алгоритма решения, или 2) предварительное определение множества аппроксимирующих вариантов путем разложения варьируемых векторов технологических параметров по вершинам выпуклых многогранников, определяющих допустимые области технологических параметров. [c.43]
Вальц (см. [47]) изучил случаи, когда программа Гузмана не справляется с разбиением изображения. В результате он усовершенствовал метод Гузмана за счет учета при описании несколько большей информации относительно изображения. Так, при обозначении отдельных ребер тел учитывалась относительная освещенность образующих их граней и другая информация. Для своей системы описания Вальц установил, что отрезки, образующие каждый тип вершин на изображении, не могут иметь любую комбинацию обозначений. Для каждого типа вершин физически возможно сравнительно небольшое число комбинаций. Это обстоятельство позволило разработать более эффективный аппарат разбиения изображения на области, соответствующие отдельным телам. Говоря словами Уинстона [47], язык описания Вальца имеет несколько более глубокие семантические корни, чем язык описания Гузмана. Однако и это усовершенствование метода не дает окончательного решения проблемы разбиения, не говоря уже о том, что при методе Вальца сохраняются те же жесткие ограничения на допустимую форму объектов. [c.34]