Cтраница 2
Третья проблема заключается в описании систем линейных неравенств, задающих полиэдры с целочисленными точками в качестве вершин. Заметим, что не каждый комбинаторный тип многогранника можно задать в Еп так, чтобы все его вершины были целочисленными точками ( см. задачу 30 гл. [16]
Синтез элемента, требующий решения системы линейных неравенств, существенно упрощается, если произвести упорядочение переменных по значению весов входов. [17]
Очевидно, что возможно множество записей систем линейных неравенств в виде эквивалентных им систем нелинейных равенств. Например, при помощи тригонометрических функций, что мы применили в [193] и др. На пути реализации этого приема могут встретиться трудности, связанные с вычислительной процедурой, однако и тогда его следует рассматривать как эффективный теоретический аппарат для анализа поведения системы, что нами раньше [202] и выше было показано. Заметим, что на базе эквивалентности двух неравенств аг gs 0 и bi 1 О ( / 1, т) одному неравенству а - bi l - ] / а Ь1 0 ( i 1, т) произвольная система неравенств последовательно сводится к одному эквивалентному ей неравенству, что существенно понижает размерность задачи. [18]
Метод, используемый для нахождения решения системы линейных неравенств а уг0, состоит в определении функции критерия / ( а), которая минимизируется при условии, что а является вектором решения. Данный подход сводит рассматриваемую задачу к минимизации скалярной функции, что часто можно осуществить при помощи процедуры градиентного спуска. Принцип процедуры спуска очень прост. [19]
Таким образом, задача нахождения решения системы линейных неравенств заменяется более строгой, но более понятной задачей определения решения системы линейных уравнений. [20]
В случае когда все левые части системы линейных неравенств равны нулю [ как это имеет место в ( 1) ], система линейных соотношений называется однородной. Заметим, что решение Xj 0 для всех значений / является тривиальным допустимым решением, для которого чистый доход равен нулю. Допустим, что существует некоторый набор нетривиальных значений xj, для которого чистый доход принимает положительное значение. Таким образом, если для данной модели существует хотя бы одно допустимое решение, то значение целевой функции может быть сделано произвольно большим. В этом случае мы говорим, что имеет место неограниченное оптимальное решение. [21]
Приведенное понятие комитета является обобщением понятия решения системы линейных неравенств на несовместный случай. [22]
Они вводятся для того, чтобы преобразовать систему линейных неравенств в систему линейных равенств. [23]
Идея базисных решений оказывается полезной применительно к системам линейных неравенств. Мы могли бы, конечно, добавив слабые переменные, превратить неравенства в уравнения и затем применить к ним данное выше определение. [24]
Как следует из теоремы 2.17, множество решений системы линейных неравенств выпукло и замкнуто. [25]
Переборными задачами оказываются также задачи выяснения: совместности системы целочисленных линейных неравенств ( как в смысле существования целочисленного, так и вещественного, решений), задача коммивояжера и многие другие - грубо говоря, все дискретные задачи. [26]
Выражение ( 3 - 2) представляет собой систему линейных неравенств. [27]
Исследование этой простейшей модели математической игры приводит к системе линейных неравенств и функции цели. Определение оптимальной смешанной стратегии для каждого из игроков в отдельности выполняется одновременным решением двух задач линейного программирования с использованием так называемых теорем двойственности. [28]
Для построения ортогональных проекций многогранных множеств, заданных системами линейных неравенств, могут быть использованы алгоритмы свертывания. Суть их заключается в последовательном построении новых систем неравенств ( так называемых сверток исходной системы), таких, что в каждой следующей системе число переменных меньше на единицу, а множество решений совпадает с проекцией исходного многогранного множества в соответствующее подпространство. В результате алгоритм удается использовать лишь в простейших случаях. [29]
Математическая модель задачи г) приводит к отысканию решения системы линейных неравенств, удовлетворяющего определенному требованию, что в конечном счете сводится к многократному решению систем линейных уравнений. Линейные системы приходится решать и во многих других прикладных задачах. [30]