Cтраница 1
Алгоритм решения задач линейного программирования составлен из нескольких процедур. Их объединение в определенной последовательности с помощью процедуры problem позволяет решить большое число задач, связанных с решением линейных уравнений при наличии ограничений. [1]
Вторая причина рассмотрения здесь алгоритмов решения задач линейного программирования обусловлена их связью с динамическими и многошаговыми моделями детерминированного класса, изложенными в гл. Алгоритмы отыскания кратчайшего пути ( маршрута), приведенные в данной главе в самом общем виде, можно считать основой для получения решений задач на таких моделях. [2]
В настоящее время существует множество алгоритмов решения задач линейного программирования. Наиболее распространенным среди них является так называемый симплекс-метод. [3]
В § § 47, 48 алгоритмы решения задач линейного программирования изложены так, что решение задачи ( 14) осуществляется по общей схеме. [4]
Здесь вполне правомерно поставить вопрос о целесообразности дальнейшего рассмотрения алгоритмов решения задач линейного программирования. [5]
Все это требует конечного числа арифметических операций и может быть названо конечным алгоритмом решения задач линейного программирования. [6]
Доказанная теорема носит принципиальный характер, так как она предлагает теоретическое обоснование алгоритма решения задач линейного программирования. Согласно этой теоремы, вместо того чтобы исследовать бесконечное множество допустимых решений для нахождения среди них оптимального, необходимо исследовать лишь конечное число угловых точек многогранника решений. Метод аналитического нахождения угловых точек предлагает следующая теорема. [7]
A [ Is, Js) так, как это описано в четвертом параграфе предыдущей главы. На основе сказанного можно было бы построить алгоритм решения задачи линейного программирования, приспособленный для использования рассмотренной двухступенчатой окай-мленности. Мы этого делать не будем, поскольку такой метод будет описан в более общем виде. [8]
Сразу после Второй мировой войны Данциг и фон Нейман, независимо друг от друга, открыли новое направление исследований. Более того, гигантский шаг в этом направлении был совершен благодаря работе Данцига ( 1951), предложившего первый ( и пока что наилучший) алгоритм решения задач линейного программирования, - широко известный ныне симплекс-метод. С той поры линейное программирование стало одной из наиболее широко и успешно применяемых ветвей математики. Причины этого успеха кроются не только в том, что задачи линейного программирования составляют сердцевину обширного многообразия математических моделей в экономике, технике и науке, но и в наличии симплекс-метода, решающего эти задачи. [9]
Рассмотрены аналитические методы решения задач поиска экстрем / ма функций многих переменных на основе необходимых и достаточных условий. Изложены численные методы нулевого, первого и второго порядков решения задач безусловной минимизации, а также численные методы поиска условного экстремума. Описаны алгоритмы решения задач линейного программирования, целочисленного, программирования, транспортных задач. Приведены методы решения задач поиска безусловного и условного экстремума функционалов на основе метода вариаций. [10]
Рассмотрены аналитические методы решения задач поиска экстремума функций многих переменных на основе необходимых и достаточных условий. Изложены численные методы нулевого, первого и второго порядков решения задач безусловной минимизации, а также численные методы поиска условного экстремума. Описаны алгоритмы решения задач линейного программирования, целочисленного программирования, транспортных задач. Приведены методы решения задач поиска безусловного и условного экстремума функционалов на основе метода вариации. [11]
С 1; похожие результаты справедливы и для других, достаточно естественных случайных моделей. Отсюда следует, что для задачи пересечения N полуплоскостей получается линейная оценка среднего поведения алгоритма. А это немедленно ведет к оценке 0 ( N) для среднего поведения алгоритма решения задачи линейного программирования с двумя переменными. Мы видим, что математическое ожидание числа избыточных полуплоскостей - таких, которые не определяют ребер допустимой области, - очень велико, что может, в частности, объяснить прекрасное поведение симплекс-метода. [12]
Эта задача легко решается с любой необходимой точностью. Хотя сходимость алгоритма доказана, попытка использования его в практических расчетах оказалась неудачной из-за крайне медленной сходимости. Именно поэтому реализация метода проекции градиента потребовала создания специального алгоритма, работающего намного быстрее. Правда, он ( см. § 49) дает не точное, а лишь приближенное решение задачи ( 11) - ( 13), но точное нам и не нужно, так как им определяется лишь вариация управления. Этот алгоритм, по существу, близок к используемому в методе последовательной линеаризации алгоритму решения задачи линейного программирования. [13]