Линейная задача о дополнительности возникает как обобщение классических постановок из линейного и квадратичного программирования и теории матричных игр и является фундаментальной математической проблемой. [c.5]
Пусть заданы вектор q e W1 и вещественная (п х та) -матрица М. Линейной задачей о дополнительности называется задача решения следующей смешанной системы неравенств и уравнений, выписанных относительно векторов переменных w е R" и z е R" [c.5]
Нетрудно заметить, что задача (1.7), (1.8) имеет форму линейной задачи о дополнительности (1.1), (1.2), где [c.6]
В качестве последнего примера математических постановок, приводящих к линейным задачам о дополнительности, рассмотрим биматричную игру Т (А, В) (игру двух лиц с ненулевой суммой, задаваемую парой вещественных (т х та) матриц А и В). Каждая из сторон обладает конечным набором согласованных с правилами игры способов поведения или чистых стратегий, которые применяет в конкретной партии (реализации игры) втайне от другой стороны. Предполагается, что результат партии полностью определяется выбором чистых стратегий, а именно, если первый игрок применил свою чистую стратегию с номером г, а второй — чистую стратегию с номером j, их ожидаемые потери, которые игроки стремятся минимизировать, равны величинам а и 6 - соответственно. При проведении бесконечной серии партий с применением игроками смешанных, стратегий х = (жь. .., хт) > О, у = (yi,. ..,уп)>0, где x i = Y =i xi = > 1Mb = Z)"=i % = > ожидаемые средние потери игроков составят соответственно х1 Ау и х1 By (компоненты смешанных стратегий выступают как вероятности, с которыми игроки выбирают соответствующие им чистые стратегии в той или иной конкретной партии). [c.7]
В связи с линейными задачами о дополнительности рассматривают еще два важных матричных класса, определяемых не конструктивно. Это класс Q, состоящий из матриц, порождающих разрешимые задачи о дополнительности вне зависимости от выбора вектора свободных членов, и класс Q0 матриц, для которых свойство разрешимости задачи L P(q, M) эквивалентно свойству совместности системы ее ограничений. [c.12]
Рассмотрим класс QQ подробнее. Выпишем условия линейной задачи о дополнительности [c.12]
Множество К(М) устроено чуть сложнее. Поскольку в любом решении линейной задачи о дополнительности в каждой паре дополнительных переменных (wi, zi) no крайней мере одна из переменных обращается в нуль, то вектор свободных членов такой задачи лежит в конусе K s, порожденном векторами набора [c.13]
Лемма 4.1 позволяет сформулировать первый результат о существовании решения линейной задачи о дополнительности. [c.18]
Перейдем к изучению линейной задачи о дополнительности с матрицами более общего вида. Нам придется ввести в систему ее уравнений дополнительную переменную Z0 I [c.20]
Теорема 7.2. Линейная задача о дополнительности L P(q,M) имеет единственное решение при всех q тогда и только тогда, когда М — Р-матрица. [c.28]
В общем случае линейная задача о дополнительности не всегда разрешима, даже если ее ограничения совместны. [c.29]
Нелинейные задачи о дополнительности и вариационные неравенства являются обобщением для многих оптимизационных постановок, таких, как задачи математического (нелинейного) программирования, минимаксные задачи и задачи о седловой точке выпукло-вогнутых функций, задачи поиска равновесия в играх п лиц и др. Многие развиваемые для их решения итерационные методы могут быть с успехом применены и к линейным задачам о дополнительности. [c.30]
Выпишем линейную задачу о дополнительности L P(q, М) найти векторы z,w e W1 такие, что [c.77]
Перейдем к обсуждению того, что, собственно, делает алгоритм и почему он решает произвольную линейную задачу о дополнительности, матрица М которой строчно-достаточна. [c.82]
Не следует, однако, упускать из виду, что основное достоинство задач без дополнительных условий состоит в возможности использовать для выбора шага s задачу (43), не заботясь о том, какой, большой или малой, окажется при этом величина s. To же самое относится и к задаче с одним дополнительным условием и свободным временем. В этом случае мы все время имеем дело с траекториями, лежащими на многообразии Рг [и ( ), Т 1=0, и можем не заботиться о величине шага s и о влиянии неучтенных при выборе вариации управления величин 0(Ц8м 2). Это же относится еще к одному классу задач, в которых система уравнений x=f (x, и) линейна по а и и, а дополнительные условия поставлены также в терминах линейных как по х, так и по и функционалов (часто, например, такие условия имеют вид х (Т)=Х1). [c.157]
Примитивность линейного раскроя позволяет использовать приемы, упрощающие описанные в гл. I общие методы. В следующих трех параграфах указываются дополнительные приемы для решения задачи о раскрое, которые не имеют общего характера, а специально относятся к раскрою мерных линейных материалов по длине. [c.52]
Существуют и другие модели задачи о распределении производственной программы, учитывающие иные условия или дополнительные факторы и усложняющие обстоятельства. Например, если объем продукции задан и полной загрузки всего оборудования не требуется, то проблема состоит в распределении программы, при которой заданное количество продукции получалось бы с наименьшими затратами. Все эти и более сложные постановки задачи обычно решаются методами линейного (впрочем, иногда и нелинейного) программирования, в результате которых наряду с планом строится согласованная с ним система экономических показателей. [c.66]
В гл. 1, рассматривая вопрос о различии производственно-технологического и социально-экономического уровней экономико-математического моделирования, мы отмечали, что мастера производственного участка могут интересовать показатели, отличные от уровня материальных затрат (3.4) или общего поощрения (3.7), например зарплата, начисляемая каждому из рабочих. Если при составлении плана эти показатели не будут учитываться, то и полученный план может оказаться для мастера неприемлемым. При учете дополнительных показателей задача из обычной задачи линейного программирования превращается в многокритериальную. Кроме того, оценка эффективности плана только по критерию (3.4) или (3.7) также может вызвать возражение. Почему, например, не постараться уменьшить вре,мя выполнения плана в первом случае или уменьшить затраты во втором Таким образом, задача планирования деятельности производственного участка является многокритериальной, и это должно учитываться при анализе и внедрении результатов расчетов в задачах типа (3.1) — (3.4) или (3.5) — (3.7). [c.177]
Если для переменной х, не задано условие х > О, то могут быть введены, например, новые переменные xj и xj с дополнительными условиями xj > 0 и xj > О, причем х. = xj — xj. Поэтому в дальнейшем будем рассматривать в основном, задачи минимизации целевой функции Q(x) при условиях, заданных линейными уравнениями с неотрицательными членами b.t в предположении неотрицательных переменных. Эти задачи и будем называть ЗЛП. В математической литературе ЗЛП записывается в виде [c.198]
Задача (2.14), (2.17), (2.18), (2.19) с дополнительными ограничениями tl > О, /2 > 0 является задачей линейного программирования размерности 5, у которой число базисных переменных равно 2 (соответствует числу актуальных ограничений), а число свободных переменных равно 3. Принимая хг хг и х3 за свободные переменные, приведем задачу к следующему виду [c.72]
При естественных условиях, гарантирующих непустоту множества планов каждого этапа, нет необходимости <в дополнительном предположении о линейности решающих правил. Это свойство решающих правил задачи (8.4) — (8.7) может быть доказано. При этом могут быть получены оптимальные решающие правила задачи. [c.57]
При некоторых дополнительных предположениях о характере процессов т) и и, следовательно, об их корреляционных функциях уравнения (4.4) и (4.6) могут быть решены. Полученные при этом функции веса определяют схему линейного фильтра или линейную вычислительную процедуру сглаживания и прогнозирования, оптимальную в смысле задачи (4.1). [c.313]
Предлагаемое пособие написано на основе зарубежных и отечественных журнальных публикаций, а также оригинального материала и легло в основу лекций, прочитанных автором студентам 3-4 курсов математико-механического факультета Уральского госуниверситета, специализирующимся на применении математических методов и информатики в экономике. В пособие включены основные факты из качественной теории конечномерных вариационных неравенств и задач о дополнительности, а также краткий обзор методов их решения, главным образом тех, что используют свойства монотонности входящих в постановки отображений. Отдельно разобран случай линейной задачи о дополнительности и рассмотрены конечные методы ее решения. Приведены разнообразные экономические приложения, в том числе модели равновесия в транспортных сетях и модель общего экономического равновесия Вальраса. [c.3]
Перечисленные классы матриц и их свойства применяют при выводе теорем существования и единственности решения линейной задачи о дополнительности. Часть этих теорем будет представлена как следствие более общих результатов из раздела, посвященного нелинейным задачам. Другая часть будет получена ниже конструктивным образом из анализа метода Лемке—Хаусона и различных его обобщений. [c.12]
Рассмотрим итеративную технику Лемке—Хаусона, первоначально разработанную для нахождения точек равновесия в биматричных играх и в дальнейшем распространенную Лемке на общий случай линейной задачи о дополнительности. [c.14]
Матрица М = (т )пхп называется Z-матрицей, если все ее внедиагональные элементы неположительны. Покажите, что всякая допустимая линейная задача о дополнительности с Z-матрицей разрешима. [c.29]
Если отображение F аффинно, т. е. F(x) = q + Mx для некоторого q e W1 и матрицы М е Rraxra, задача (1.5) превращается в линейную задачу о дополнительности L P(g,M). [c.32]
Вообще говоря, допустимая область задачи (1.13) необязательно выпукла. Однако в случае аффинности F (т. е. в случае линейной задачи о дополнительности) постановка (1.13) есть просто задача квадратичного программирования (необязательно выпуклого). [c.35]
Метод проекции можно применять не только для решения вариационных неравенств и нелинейных задач о дополнительности, но и для решения линейных задач о дополнительности, матрицы которых положительно определены. Действительно, аффинное отображение F(x) = q + MX всегда является липшицевым, а в случае положительно определенной матрицы будет и сильно монотонным с константой 7 = max х1 Мх. [c.47]
В этом разделе приведен дополнительный материал по строчно- и столбцово-достаточным матрицам и методу Данцига—Коттла главных исключений для решения линейных задач о дополнительности. Последний в ряде случаев оказывается более предпочтительным по сравнению с методом Лемке. [c.76]
Метод Данцига—Коттла, подобно другим конечным методам решения линейных задач о дополнительности, использует симплексные преобразования системы уравнений [c.79]
Вернемся к методу Лемке из главы 1 и дадим иную интерпретацию его искусственной переменной. Будем трактовать ее как параметр, начальное положительное значение которого в ходе вычислений постепенно доводится до нуля. Такой подход позволяет более тесно увязать вопросы сходимости метода с типом матрицы в линейной задаче о дополнительности. [c.84]
Так, изложение ограничено однозначными отображениями, в то время как многие приложения приводят к задачам с отображениями точечно-множественного характера, анализ которых более сложен и требует большого числа новых понятий. Не рассмотрены также спорные и не до конца проработанные вопросы двойственности для перечисленных математических постановок, а также вопросы их устойчивости и параметрического анализа. Из всего разнообразия вычислительных методов решения нелинейных задач в основном отобраны те, что апеллируют к свойствам монотонности тех или иных отображений. Не описаны другие (кроме метода Лемке и Данцига—Коттла) конечные методы решения линейной задачи о дополнительности и матричные классы, связанные с ними. Не отмечены важные в прикладном отношении методы декомпозиции задач большой размерности. [c.89]
Пособие содержит вводный материал и упражнения по теории, методам и экономическим приложениям линейных и нелинейных задач о дополнительности, а также конечномерным вариационным неравенствам. Может быть полезно студентам математических и экономических специальностей вузов, аспирантам и специалистам в области вычислительной математики и математической экономики, а также всем, кто сталкивается с математическим моделированием экономических процессов и решением сложных нелинейных задач. [c.1]
Вариационные неравенства и линейные и нелинейные задачи о дополнительности стали изучаться с середины 1960-х годов, начиная с работ Дж.Стампаккьи, К.Лемке, Дж.Данцига, Р.Коттла и др. Эти постановки сыграли значительную роль в математическом программировании и являются центральными в моделировании, численном решении и анализе многих задач в экономических, физических, технических и социальных исследованиях. [c.3]
Почему так получилось Дело в том, что введенное дополнительное ограничение превратило нашу задачу о назначениях (по существу транспортную задачу) в обычную задачу линейного программирования. Для такой задачи специализированные "транспортные" методы решения неприменимы. А как указывалось раньше, только они обеспечивают целочисленные решения без введения явных требований целочисленности. Получившуюся общую ЛП-задачу MS-Ex el решают с помощью обычного симплекс-метода, а он отнюдь не гарантирует целочисленности переменных решения. [c.141]
ЗАДАЧА ДИЕТЫ [nutrient problem] (или задача о рационе питания) — задача линейного программирования, состоящая в определении такого рациона, который удовлетворял бы потребности человека или животного в питательных веществах при минимальной общей стоимости используемых продуктов. Это частный (наиболее распространенный) случай более общей задачи об оптимальном составе смеси. Задача составления оптимального рациона для человека сложна, так как приходится учитывать много дополнительных, не всегда формализуемых факторов вкусовые привязанности, разнообразие блюд и т.д. Однако в животноводстве определение рационов для скота с помощью задачи линейного программирования сегодня не просто реально, но и необходимо. Опыт показывает, что кормление скота рационами, рассчитанными по этому методу, дает существенную экономию (напр., в США ими пользуются многие фермеры). Это не означает, разумеется, что каждый сам решает задачу линейного программирования в разных районах [c.99]
Когда речь идет о задаче линейного программирования, существенная информация о влиянии изменения параметров на оптимальное решение накапливается программой, собственно, в ходе поиска решения. MS-Ex el представляет эту информацию в виде отчета об устойчивости. Ответ на многие вопросы может быть получен на основе анализа этого отчета. Другие вопросы могут потребовать проведения дополнительных расчетов типа "что, если...". [c.55]
В [318Ц принято дополнительное предположение о том, что решающие правила задачи (8.4) —(8.7) линейны и задача сводится к вычислению коэффициентов соответствующих линейных форм. [c.57]
Член-корреспондент АН СССР А. Г. Аганбегян рассказывал о том, как, будучи еще студентом, он задумал с noMoaibio математики рассчитать себе наиболее дешевый бюджет питания. Из работ по рациональному питанию он выбрал, показатели, характеризующие количество различных питательных веществ (жиров, белков, углеводов и т. п.), необходимых для здорового человека, затем по поваренной книге выписал примерно 60 продуктов и их питательный состав и приступил к решению. Он составил модель линейного программирования, в которой переменными служили виды продуктов и их цены, а целевой функцией — стоимость рациона. Результаты поразили молодого экономиста. Оказалось, что в оптимальный набор попали только пять продуктов, в том числе 800 г ржаной муки, около 3 кг капусты и т. д. Это показало, что для человека не так-то проста задача составления диеты — надо участь много дополнительных, не всегда формализуемых факторов вкусовые привязанности, разнообразие блюд и т. д. [c.119]
Таким образом, возникает следующая задача. Задан комплекс работ в виде сетевой модели. Каждой работе (i,j) соответствуют длительности t., неизвестные дополнительные средства (прямые затраты ..), которые можно вложить в работы с целью сокращения их длительностей ограничения /г.. на величины х. некоторые коэффициенты продолжительности работы коэффициент прямых затрат с,-,- = (с гу - с, -,- ) /( , -,- - t j ), где индексы и " — соответственно максимальное и минимальное значения соответствующих параметров. Величины с у и с" у получают суммированием составляющих прямых затрат по каждому из вариантов выполнения работы. Пусть общая продолжительность разработки Т велика и требуется уменьшить ее до удовлетворения неравенства Т < Тг, где Тг — заданное ограничение. Зависимость новой длительности работы ц от прежней t.. задана в виде Ц =tij(i-dijXij). Тогда возникает задача нахождения таких дополнительных вложений средств в работы, чтобы выполнялись условия [c.279]
И1, И2 и Ф1 являются постановками задач линейного программирования, ление которых позволяет контролировать рыночный риск, а в случае И2, — иск волатильности. Для того чтобы контролировать отраслевой риск, не-одимо добавить ограничения на диверсификацию портфеля, т. е. включить о состав платежные обязательства, связанные с различными финансовы-и промышленными секторами. Диверсификация также позволяет умень-гь несистематический риск, т. е. риск отдельных платежных обязательств, iop отраслей и инструментов, которые имеют достаточно высокий кредит-i рейтинг, позволяет добиться ограничения кредитного риска. Наличие транзакционных издержек, связанных с покупкой и продажей зательств, приводит к возникновению дополнительного вида риска, кото-[ не учитывается в задачах И1, И2 и Ф1. Если волатильность процентных зок будет высока, то перестраивать портфель придется более часто. Оценка ичины потерь, связанных с транзакционными издержками, может быть вы-нена в рамках динамических оптимизационных моделей [28]. [c.709]