В линейном программировании область допустимых решений допустимый многогранник) всегда выпукла и всегда находится в неотрицательном подпространстве многомерного (п-мерного) пространства решений. [c.231]
Вершина допустимого многогранника 47 [c.461]
Такое условие не нарушает общности задачи, поскольку в том случае, когда эта величина отрицательна, знак минус можно отнести к числителю. Как и в случае основной задачи линейного программирования, экстремальное значение целевая функция (2.1) принимает в одной из вершин допустимого многогранника (естественно, при условии, что эта задача имеет оптимальный план). [c.461]
Предположим, что задача имеет многогранник решений (рис. 8.3). Если наложить требование целочисленности, то допустимое множество решений выразится в систему точек и уже не является выпуклым. [c.126]
Другое направление решения задачи линейного программирования с переменными векторами условий, заданными на сепарабельных выпуклых множествах, связано с предварительным определением всех вершин" допустимых значений технологических коэффициентов и последующим формированием и решением задачи линейного программирования, в которой для процессов с переменными технологическими коэффициентами рассматривается несколько вариантов, полученных в результате определения вершин" [17-20]. Одна из первых задач подобного типа [17] включала элементарный случай варьирования технологических коэффициентов, когда область их допустимых значений представляла собой многогранник, образованный пересечением и-мерного параллелепипеда одной гиперплоскостью. [c.15]
Рассмотренная геометрическая интерпретация задачи линейного программирования возможна лишь при наличии двух независимых переменных. При трех переменных наглядное представление существенно усложняется, так как в этом случае имеет место некоторый выпуклый многогранник в трехмерном пространстве, соответствующий объему допустимых планов. [c.65]
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получать координаты вершин многоугольника (многогранника) области допустимых планов. [c.66]
Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
Так как ограничения в виде уравнений представляют собой плоскости в -мерном пространстве, а также условия х,.> 0, то решение ЗЛП ищется в вершинах образованного в -мерном пространстве многогранника, который сам по себе представляет область допустимых решений. [c.200]
Следует заметить, что подобное графическое решение очень трудно провести для задач с тремя переменными решения. В этом случае область допустимых планов представляет собой многогранник сложной формы в 3-мерном пространстве. Что же касается задач с числом переменных более трех, то графически изобразить область допустимых планов вообще нельзя, поскольку это многогранник в многомерном пространстве. [c.59]
Выпуклые многогранники и выпуклые многогранные конусы принадлежат к числу наиболее распространенных понятий математической экономики. В линейном и выпуклом программировании используются обязательно выпуклые области изменения переменных (допустимые множества по теоретико-множественной терминологии, многогранники — по геометрической) и выпуклые целевые функции. [c.57]
Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л. п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве выпуклый многогранник). [c.172]
У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных [c.171]
I Если сравнить данное решение с оптимальным планом =3,25 шт. х2=0 шт. A 3=5 шт. х4=0 шт. /г=64 руб.), то видим -существенное отклонение, как по величине прибыли, так и по объему производства. Это и не удивительно, так как для построения задачи объединения использованы исходные планы A, D, Я, М. Образованные ими аппроксимирующие многогранники ОАО и OHM не включают в себя как раз те части области допустимых планов, которые близки к точкам (3,25 0) и (5 0), т. е. точкам оптимального плана. Очевидно (см. рис. 5.1 и 5.2), что использова- [c.199]
Помимо примеров оптимизации конкретных производств описан метод определения координат вершин выпуклых многогранников, задающих допустимые области варьирования коэффициентов и используемых в ходе решения задачи дана блок-схема программы для определения вершин многогранников на ЭВМ. [c.2]
В работе были даны постановка задач , и метод решения. Постановка имеет вид задачи билинейного программирования, т.е. задачи линейного программирования с неизвестными, однако, коэффициентами. Для решения выполняется эквивалентная линеаризация модели, коэффициенты которой поддаются разложению по вершинам выпуклых.многогранников эти многогранники задают допустимые области изменения коэффициентов. [c.3]
Следует учитывать, что не всякий допустимый план является опорным. Из всех допустимых планов опорным может быть тот план, который лежит на границах многогранника, состоящего из ограничений, в нашем случае это ограничения, поставленные в математическом условии задачи. [c.145]
Поскольку решение задачи должно удовлетворять всем поставленным ограничениям, то все прямые преобразований надо совместить и выделить область, общую для всех треугольников. Такое совмещение и сделано на рис. 1, где все прямые преобразований, пересекаясь в поле графика, образуют нек-рый выпуклый многогранник L, к-рый т. о. и представляет собой область допустимых решений. Это значит, что в решение задачи могут войти только такие комбинации значений х1 а х,,, к-рые представляют координаты точек, лежащих внутри многоугольника L. Например, комбинация х,=3 и х2=3, лежащая вне поля L, представляет недопустимое решение действительно, она не удовлетворяет требованию // ограничения 1-3+2-3=9 (т. е.>8). [c.22]
Если в задачах линейного программирования точка экстремума является вершиной многогранника, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума. [c.347]
Ясно, конечно, что и в этом случае оптимальным решением является одна или несколько вершин многогранника допустимых решений. Однако если число переменных и ограничений задачи сравнительно велико, то количество вершин выражается астрономическими числами и вычисление значений целевой функции во всех вершинах практически неосуществимо. Например, если п = 50 (число переменных) и т = 25 (число ограничений), тогда число вершин порядка Ю14. Если время, необходимое для вычисления значения целевой функции в каждой точке равно одной миллионной секунды, то перебор всех вершин многогранника займет примерно две тысячи лет. Срок явно неприемлемый. [c.18]
Итак, задача состоит в отыскании минимума линейной функции при линейных ограничениях, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Выше указывалось, что этот минимум обязательно достигается в одной или нескольких вершинах многогранника. Уточним так дело обстоит, если многогранник ограничен. В противном случае решение задачи может и не существовать. Для решения задачи необходимо иметь возможность устанавливать, оптимален ли план без непосредственного сравнения с планами, соответствующими остальным вершинам многогранника. Эта возможность и дается признаком оптимальности плана, формулируемым в виде такой теоремы. [c.29]
Множество допустимых планов, определяемое условиями 1—3, представляет собой выпуклый многогранник. Таким образом, требуется найти минимум выпуклой функции, задан- [c.74]
Итак, задача состоит в отыскании минимума линейной функции при линейных ограничениях, или, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Признак оптимальности плана формулируется в виде такой теоремы. [c.34]
Здесь величины ai - (Э), bf (Э) и j (Э) принимают случайные значения в зависимости от значения, принимаемого случайным параметром Э. Каждая реализация Э определяет многогранник допустимых планов соответствующей задачи линейного программирования (реализация параметра Э носит название состояния природы или элементарного события, а множество возможных значений этого параметра Л называется множеством возможных состояний природы или пространством элементарных событий). При любом состоянии природы должны удовлетворяться все поставленные ограничения, поэтому допустимым, естественно, считать план, который принадлежит всем возможным многогранникам допустимых планов. Если пересечение этих многогранников пусто, то допустимого плана задачи не существует. [c.119]
Такое ограничение называют правильным отсечением. В первой геометрической интерпретации правильному отсечению соответствует гиперплоскость, отсекающая от выпуклого многогранного множества допустимых планов D некоторый многогранник, не содержащий целочисленных планов. [c.143]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Доминирование альтернатив 94 Доминирование фирмы 239 Домохозяйство, домашнее хозяйство 94 Дополняющая нежесткость 94 Допустимая альтернатива 18 Допустимая траектория 94 Допустимое множество 94, 95 Допустимое преобразование 279 Допустимое решение 95 Допустимое состояние системы 95 Допустимость, допустимый 95 Допустимые типы предприятий 364 Допустимые управления 371 Допустимый вектор "затрат-выпуска" 43 Допустимый вектор 95 Допустимый многогранник 95 Допустимый план 95 Достоверность информации 95 Доступность системы массового обслуживания 95, 197 Доу Джонса индекс 95 Доходность 95 Доходы 95 [c.465]
В моделях с переменными параметрами, допускающих в некоторых случаях эффективную линеаризацию, в зависимости от алгоритма решения предусмотрена 1) генерация аппроксимационных вариантов, осуществляемая по ходу реализации алгоритма решения, или 2) предварительное определение множества аппроксимирующих вариантов путем разложения варьируемых векторов технологических параметров по вершинам выпуклых многогранников, определяющих допустимые области технологических параметров. [c.43]
Название методы отсечений связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. Метод отсекающих плоскостей, разработанный Р. Гомори, используется при решении полностью целочисленных задач. [c.466]
Во-вторых, каждое из J -и условий /2.2/ описывает выпуклую допустимую область - выпуклый многогранник. Так, для 1-го столбца / j 1/ эта область задается системой i Lii ZV/ и, например, условиями [c.31]
При большем числе переменных геометрич. изложение задачи путем двухмерного изображения ее на плоскости становится невозможным. При трех переменных она может быть изображена в виде трехмерной фигуры область допустимых решений приобретает форму многогранника, а целевая функция — секущей плоскости. При числе переменных более трех изложение задачи переходит в область многомерных представлений, поэтому практически возможным становится решение задачи только аналитич. приемами — посредством применения соответствующего расчетного алгоритма, напр, алгоритма С. м. л. п. [c.22]