Вершина допустимого многогранника 47 [c.461]
Такое условие не нарушает общности задачи, поскольку в том случае, когда эта величина отрицательна, знак минус можно отнести к числителю. Как и в случае основной задачи линейного программирования, экстремальное значение целевая функция (2.1) принимает в одной из вершин допустимого многогранника (естественно, при условии, что эта задача имеет оптимальный план). [c.461]
Другое направление решения задачи линейного программирования с переменными векторами условий, заданными на сепарабельных выпуклых множествах, связано с предварительным определением всех вершин" допустимых значений технологических коэффициентов и последующим формированием и решением задачи линейного программирования, в которой для процессов с переменными технологическими коэффициентами рассматривается несколько вариантов, полученных в результате определения вершин" [17-20]. Одна из первых задач подобного типа [17] включала элементарный случай варьирования технологических коэффициентов, когда область их допустимых значений представляла собой многогранник, образованный пересечением и-мерного параллелепипеда одной гиперплоскостью. [c.15]
Поэтому первым шагом должно быть получение координат одной из вершин многоугольника (многогранника) допустимых планов. Для этого необходимо преобразовать систему уравнений таким образом, чтобы с ее помощью можно было легко получать координаты вершин многоугольника (многогранника) области допустимых планов. [c.66]
Помимо примеров оптимизации конкретных производств описан метод определения координат вершин выпуклых многогранников, задающих допустимые области варьирования коэффициентов и используемых в ходе решения задачи дана блок-схема программы для определения вершин многогранников на ЭВМ. [c.2]
В работе были даны постановка задач , и метод решения. Постановка имеет вид задачи билинейного программирования, т.е. задачи линейного программирования с неизвестными, однако, коэффициентами. Для решения выполняется эквивалентная линеаризация модели, коэффициенты которой поддаются разложению по вершинам выпуклых.многогранников эти многогранники задают допустимые области изменения коэффициентов. [c.3]
Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
Так как ограничения в виде уравнений представляют собой плоскости в -мерном пространстве, а также условия х,.> 0, то решение ЗЛП ищется в вершинах образованного в -мерном пространстве многогранника, который сам по себе представляет область допустимых решений. [c.200]
У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных [c.171]
Если в задачах линейного программирования точка экстремума является вершиной многогранника, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума. [c.347]
Ясно, конечно, что и в этом случае оптимальным решением является одна или несколько вершин многогранника допустимых решений. Однако если число переменных и ограничений задачи сравнительно велико, то количество вершин выражается астрономическими числами и вычисление значений целевой функции во всех вершинах практически неосуществимо. Например, если п = 50 (число переменных) и т = 25 (число ограничений), тогда число вершин порядка Ю14. Если время, необходимое для вычисления значения целевой функции в каждой точке равно одной миллионной секунды, то перебор всех вершин многогранника займет примерно две тысячи лет. Срок явно неприемлемый. [c.18]
Итак, задача состоит в отыскании минимума линейной функции при линейных ограничениях, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Выше указывалось, что этот минимум обязательно достигается в одной или нескольких вершинах многогранника. Уточним так дело обстоит, если многогранник ограничен. В противном случае решение задачи может и не существовать. Для решения задачи необходимо иметь возможность устанавливать, оптимален ли план без непосредственного сравнения с планами, соответствующими остальным вершинам многогранника. Эта возможность и дается признаком оптимальности плана, формулируемым в виде такой теоремы. [c.29]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
В моделях с переменными параметрами, допускающих в некоторых случаях эффективную линеаризацию, в зависимости от алгоритма решения предусмотрена 1) генерация аппроксимационных вариантов, осуществляемая по ходу реализации алгоритма решения, или 2) предварительное определение множества аппроксимирующих вариантов путем разложения варьируемых векторов технологических параметров по вершинам выпуклых многогранников, определяющих допустимые области технологических параметров. [c.43]