Решение подобных задач требует определенности в формулировании их условий установления количества игроков и правил игры, выявления возможных стратегий игроков, возможных выигрышей (отрицательный выигрыш понимается как проигрыш). Важным элементом в условии задач является стратегия, т. е. совокупность правил, которые в зависимости от ситуации в игре определяют однозначный выбор данного игрока. Количество стратегий у каждого игрока может быть конечным и бесконечным, отсюда и игры подразделяются на конечные и бесконечные. При исследовании конечной игры задаются матрицы выигрышей, а бесконечной - функции выигрышей. Для решения задач применяются алгебраические методы, основанные на системе линейных уравнений и неравенств, итерационные методы, а также сведение задачи к некоторой системе дифференциальных уравнений. [c.51]
Оптимальное f надо искать следующим образом. Сначала вы должны определиться с методом поиска Можно просто перебрать числа от 0 до 1 с определенным шагом (например 0,01), используя итерационный метод, или применить метод [c.114]
Суть метода структурной минимизации заключается в том, что сначала берется предельно грубая модель, а затем эта модель постепенно усложняется до достижения оптимального соотношения между точностью аппроксимации эмпирического материала и надежностью результата в условиях ограниченного объема данных. Для того чтобы применить этот метод, иначе называемый итерационным методом моделирования, необходимо задать, во-первых, способ усложнения модели, а во-вторых - предельную степень сложности [237]. [c.85]
Для решения такого уравнения используются итерационные методы. [c.322]
Примеры практического применения итерационных методов см. в ст. "Базисное решение", "Симплексный метод". [c.137]
В работах, в которых сходимость итерационных методов доказывается на основании стохастических аналогов прямого метода Ляпунова, существо дела заключается в следующем. [c.354]
Дальнейшее развитие численных методов было связано со стремлением учесть как ограничения u U, так и дополнительные условия F1=.. =Fm=Q (обычно они имели форму условий на правом конце траектории Ф( [х(Т)]=0). Кроме того, предметом особых усилий были ограничения в фазовом пространстве (Ф [х (t)] 0 при всех t) и ограничения общего вида (Ф [х (t), и (f)] 0). Именно связанные с учетом таких условий трудности стимулировали развитие методов вариаций в фазовом пространстве ( 15, 16 см. также [55], [56]). Эти методы настолько успешно справлялись с ограничениями в фазовом пространстве, что возникающие на этом пути серьезные трудности (отсутствие сходимости в методе локальных вариаций, медленная сходимость, ненадежные и неточные результаты, учет условий u U) в какой-то мере выпали из поля зрения. К тому же на основании спорных оценок числа операций был сделан вывод о преимуществе метода локальных вариаций перед другими итерационными методами (метод трубки, см. 16), и эта форма вариаций в фазовом пространстве стала, видимо, основным вычислительным инструментом. [c.112]
Итерационный метод работы с неравенствами, как с равенствами, был предложен в [51]. Суть дела поясним на самом простом примере. Пусть в задаче есть одно условие-неравенство 9 1и (t)] < 0. Тогда процесс построения вариации 8ц (t) начинается с того, что все неравенства игнорируются и проекция градиента вычисляется классическими методами. Найденная вариация 8ц (t) может привести к нарушению условия 9 0- Пусть на некотором интервале Ult tz] окажется 9 I" ( )+ ц (t)] > 0. Тогда на этом интервале условие 9 0 заменяется условием-равенством 9 [и ( )]=0, и находится новая вариация 8ц (t) в задаче, поставленной только в терминах равенств, снова проверяется условие 9 0 и т. д. Однако этот эрзац операции проектирования теоретически несостоятелен в простых ситуациях он может привести к 8u (i)=0, хотя варьируется траектория очевидным образом неоптимальная, и правильное проектирование градиента привело бы, конечно, к 8ц ( ) 0. [c.162]
Формально получена сложная задача, однако и здесь напрашивается итерационный метод ее решения, при котором все условия (12) берутся в линейной форме, а квадратичные члены берутся из предыдущей итерации. Таким образом, каждый шаг этой процедуры потребует решения задачи на минимум квадратичного функционала при линейных ограничениях, что уже значительно проще соответствующие алгоритмы описаны, например, в 51. Мы ограничимся этим беглым и общим описанием, потому что в такой форме методы второго порядка, учитывая всю громоздкость предварительных вычислений, в сложных задачах применять будет, видимо, очень трудно и едва ли рационально. Однако можно ввести некоторые упрощения и получить более практичные, хотя и не столь последовательные, методы. [c.206]
Эту задачу автор решал итерационным методом, подробно описанным в 19 — 21. Коротко опишем структуру одного шага процесса. [c.289]
Точное решение задачи. На основании численных расчетов была угадана структура точного решения задачи, после чего найти его уже нетрудно, — тоже, конечно, с использованием численных методов, но гораздо более простых и точных, чем итерационные методы решения вариационных задач. Структура эта такова интервал [О, Т] разбивается на четыре части точками 0 < t1 < t2 < t3 < Т оптимальное управление имеет форму [c.316]
Разумеется, в расчетах е > 0, его назначение и регулирование обсуждаются ниже. Заметим, что в задаче (12), (13) границы s , s (t) не совпадают с s , s (t) в (8). При их вычислении, кроме обычных соображений о малости 8и и выполнении условия 0 и+8цз 7, используется еще одно. Задача (12), (13) есть задача квадратичного программирования, однако в расчетах она решалась итерационным методом, причем на каждой итерации решалась задача линейного программирования (являющаяся линеаризацией (12)) [c.351]
SB S - Таким образом, лишь один коэффициент Aj +1=l, остальные А°=0. Задача оказывается существенно вырожденной, и опыт ее решения в такой форме (итерационным методом 48) оказался неудачным требовалось слишком большое число итераций для достижения нужной точности. Поэтому в таких задачах использовался следующий прием, приводящий, как показали вычисления, к существенно более простой и легко решаемой задаче. Запишем задачу в виде [c.436]
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ИТЕРАЦИОННЫЙ МЕТОД 437 [c.437]
Имеющийся у автора опыт (впрочем, существенно связанный с итерационным методом 48) заставляет осторожно относиться к этому сведению, отдавая предпочтение тому способу решения (с е= 1, 1,. . ., 1, 0,. . ., 0 ), который был изложен выше. [c.437]
Линейное программирование. Итерационный метод [c.437]
Вычисления начинаются заданием вектора g, нормированного условием (g, e) = l (например, g=e/iie 2), параметра if и вектора 8= 80, х,. . ., ш . Число i и малый вектор 8 определяют требуемую от решения точность. Итерационный метод дает нам не точное решение, а приближенное в следующем смысле вместо соотношения [c.438]
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ИТЕРАЦИОННЫЙ МЕТОД 439 [c.439]
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ИТЕРАЦИОННЫЙ МЕТОД 441 [c.441]
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ИТЕРАЦИОННЫЙ МЕТОД 443 [c.443]
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ИТЕРАЦИОННЫЙ МЕТОД 445 [c.445]
Опыт вычислений. Итерационный метод решения задач линейного программирования систематически использовался автором начиная с 1963 г. Разумеется, опыт эксплуатации метода приводил к различным усовершенствованиям, и выше алгоритм изложен таким, каким он сложился ко времени написания книги. (Впрочем, в изложении опущены некоторые несущественные де- [c.450]
ИТЕРАЦИОННЫЙ МЕТОД РЕШЕНИЯ СПЕЦИАЛЬНОЙ ЗАДАЧИ 453 [c.453]
Итерационный метод решения специальной задачи квадратического программирования [c.453]
Метод сопряженных градиентов является итерационным методом нахождения минимума квадратичной формы. Характерная его особенность — конечность минимум достигается не более, чем за п шагов (тг-размерность пространства). Вычислительная схема метода сопряженных градиентов была обобщена на задачи нахождения минимума общих функций, не являющихся квадратичными. Опыт вычислений показал высокую эффективность метода, особенно в ситуациях, когда метод простого спуска по градиенту оказывался практически неработоспособным в силу крайне меД ленной сходимости. Ниже излагается вычислительная схема ме -тода в случае квадратичной функции, затем будет приведено его формальное обоснование. В заключение будет приведено обобщение вычислительной схемы в случае неквадратичной функции. [c.469]
Поляк В. Т. О некоторых способах ускорения сходимости итерационных методов. — ЖВМ и МФ, 1964, 4, № 5, с. 791—803. [c.481]
Итерационные методы поиска оценок [c.298]
Таким образом, алгоритм метода неподвижной точки представляет из себя комбинацию метода наименьших квадратов и итерационного метода Якоби решения системы линейных алгебраических уравнений. На практике, однако, было установлено, что этот алгоритм далеко не всегда является сходящимся. Для улучшения сходимости были предложены различные его модификации. Например, в релаксационном методе неподвижной точки приближение Ys для Y находится по формуле [c.422]
Итерационные методы поиска мнк-оценок 298 [c.472]
В настоящее время разработан ряд методов исчисления обратных матриц и, следовательно, получения коэффициентов полных затрат. Среди них можно выделить два основных способа обращения матриц, основанные на итерационных методах (методах последовательного приближения) и на использовании метода прямого обращения матриц. При итерационном методе многократно повторяются однотипные вычисления, постепенно приближающиеся к искомому результату. При втором способе расчеты сводятся к решению системы уравнений и нахождению коэффициентов полных затрат путем инверсии (обращения) матрицы коэффициентов прямых затрат. Полученная в результате сложных математических расчетов, произведенных на электронно-вычислительных машинах, матрица коэффициентов полных затрат обладает рядом особенностей, имеющих большое значение для производства экономических расчетов. Так, матрица коэффициентов полных затрат, умноженная на вектор конечной продукции, дает объем производства продукции по каждой отрасли. Расчет осуществляется по следующей формуле [c.507]
Теория игр разработана пока еще недостаточно. Существуют методы решения для игр двух лиц с нулевой суммой при ограниченном числе возможных стратегий. Для решения матричных игр можно использовать методы линейного программирования и итерационные методы. Наиболее просто решаются матричные игры, имеющие седловую точку. Слабее разработаны методы решения др. игр, в особенности бесконечных. Научная работа в области Т. и. направлена не только на совершенствование ее математич. аппарата, но и на подбор и соответствующую формулировку реальных задач, в частности экономических. [c.154]
Во-первых, иногда обучение необходимо проводить в режиме on-line, т.е. на ходу адаптироваться к меняющемуся потоку данных. Примером может служить борьба с нестационарными помехами в каналах связи. Итерационные методы идеально подходят в этой ситуации, когда нет возможности собрать воедино весь набор примеров и произвести необходимые матричные операции над ним. [c.76]
Рассматривая вычислительные аспекты решения задач на основе модели МОБ, отметим, что основной объем расчетов связан с вычислением матрицы коэффициентов полных материальных затрат В. Если матрица коэффициентов прямых материальных затрат А задана и является продуктивной, то матрицу В можно находить либо по формулам прямого обращения матриц, либо с использованием итерационных методов. Одним из наиболее употребительных методов обращения матриц явля- [c.513]
Для расчета ВИД используют специальные итерационные методы (например, метод Ньютона— Рафсона). [c.285]
Как мы видели выше, общие методы решения двухэтапной задачи стохастического программирования достаточно трудоемки. Трудности численного анализа двухэтапной задачи возрастают, если нет явного выражения для множества К предварительных планов задачи. Один из подходов к приближенному анализу решения двухэтапной задачи заключается в оценке оптимального значения ее целевой функции. Двухэтапной задаче приводятся в соответствие детерминированные задачи, оптимальные значения показателей качества которых оценивают сверху и снизу целевую функцию стохастической задачи на оптимальном предварительном плане х. Обычно решения соответствующих детерминированных задач являются неплохими начальными приближениями для итерационных методов решения двухэтатшых задач. Далее предполагается, что В и q детерминированы. [c.190]
Хотя для решения задачи линейного программирования существуют четкие конечные методы (они описаны в 47), не прекращается работа по созданию итерационных, приближенных методов. Для этого есть по крайней мере две причины. Дело в том, что реализация симплекс-метода встречает определенные трудности в экономических задачах высокой размерности (N, т 103). В таких задачах работа с матрицей объемом 108 ячеек памяти становится очень сложной. В то же время исходная матрица задачи, будучи слабо заполненной, часто может быть размещена в оперативной памяти машины. Встречаются задачи, элементы матрицы которой можно вообще не запоминать, а вычислять по сравнительно простым формулам. В таких ситуациях итерационные методы, не преобразующие исходной формы задачи и не порождающие новых объектов типа матрицы общего положения (как, например, биорто-гональный базис ф ), несмотря на значительно меньшую надежность, могут оказаться предпочтительными и даже единственно реализуемыми. Для нас же будет важна и другая причина, заставляющая обратиться к итерационным методам. Ведь задачи линейного программирования, возникающие при решении задач оптимального управления, являются конечно-разностными аппроксимациями континуальных задач найти функцию 8u (t) из условий [c.437]
Метод сопряженных градиентов использовался автором не только в серийных расчетах задач оптимального управления (в качестве одного из блоков решения задачи линейного или квадратичного программирования), но и в методических расчетах в условиях сравнительно высокой размерности. В частности, в 48 представлены результаты решения задачи линейного программирования итерационным методом, включающим и метод сопряженных градиентов. Видно, что сходимость метода не соответствует теоретическим предсказаниям, что приводит к определенному (и заметному) перерасходу машинного времени. Были проведены и специальные эксперименты по минимизации формы (Вх, Вх) (G=B B) со случайной матрицей В размером 100x100. Использовалась схема типа III. Алгоритм не давал нужной точности после 300 — 400 шагов. Для уменьшения влияния ошибок округления была применена комбинация схем II и III четыре итерации проводились с вычислением В по схеме III, а каждая пятая — по более громоздкой формуле схемы II. Это привело к улучшению сходимости (выигрыш можно оценить числом л 2), но проблемы не решило. [c.477]
П о л я к Б. Т., Третьяков Н. В. Об одном итерационном методе линейного программирования и его экономической интерпретации. — Экономика и матем."методы, 1973, УШ, вып. 5, с. 740—751. [c.481]