Принцип двойственности в линейном программировании позволяет получить аналогичные результаты для следующей задачи [c.291]
ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [c.56]
Все результаты по двойственности в линейном программировании распространяются и на квадратичный случай. [c.7]
Теоремы двойственности в линейном программировании [c.203]
Экономическая интерпретация двойственности в линейном программировании [c.205]
Существует много методов оценки напряженности заданий коэффициентный метод оценки напряженности плана по темпам роста к предыдущему периоду метод оценки напряженности плана с точки зрения нормативного использования производственных ресурсов метод применения апостериорного статистического критерия качества планирования. Для этих же целей широко применяются методы линейного программирования, объективно обусловленные оценки В. Новожилова, вытекающие из процедуры решения двойственных задач линейного программирования. В последние годы для оценки напряженности плана разработаны специальные методики, базирующиеся на методах теории статистических распределений, компонентного анализа, современного факторного анализа, других математико-статистических методах. [c.236]
В тех случаях, когда задачи АСУ решаются с использованием дисковой операционной системы ДОС ЕС, программное обеспечение задачи планирования строится на основе пакета LPS-360 [30]. Эта система позволяет при объеме оперативной памяти свыше 64 К эффективно решать задачи, системы ограничений которых включают до 1500 строк. Пакет осуществляет решение прямой и двойственной задачи линейного программирования, выдает информацию о значениях ошибок, позволяет создавать контрольные точки, объединять блоки, вносить изменения и дополнения в систему ограничений и целевую функцию. Разработанные с целью привязки пакета к задачам планирования нефтеперерабатывающих производств Генератор модели" и Интерпретатор" обеспечивают автоматическое построение модели планирования НПП на основе исходных данных о структуре производства, технологических агрегатов и установок, а также представление результатов решения в виде выходных документов, используемых планово-экономическими службами завода. [c.179]
Наоборот, если L (b, с)<оо, то в силу теоремы двойствен ности-линейного программирования существует вектор у, для которого [c.280]
Подробное описание связи между разрешимостью пар двойственных задач линейного программирования и нахождением их решений, с одной стороны, и решениями матричных игр - с другой, содержится в следующей теореме. [c.85]
Тогда согласно п. 25.1 и 25.2 векторы X=X/vA и Y- Y/vA являются решениями пары двойственных задач линейного программирования, и по ним в соответствии с формулами (25.17) и (25.18) мы получаем некоторую. оптимальную стратегию любого из игроков в симметричной игре [c.91]
Применяя изложенный математический аппарат двойственной задачи линейного программирования, рассмотрим пример выбора оптимального ассортимента и объема продукции швейного предприятия. Эта социальная задача сферы сервиса связана с удовлетворением потребностей населения в бытовых услугах и направлена на улучшение основных производственных показателей эффекта бытового обслуживания, заключающегося в снижении стоимости товаров, экономии свободного времени и улучшении качества обслуживания. [c.98]
Количественный анализ предполагает численную оценку рисков, определение их степени и выбор оптимального решения. Во второй главе рассмотрена система количественных оценок экономического риска. Опираясь на теорию матричных игр, применяя различные критерии эффективности, используя теорию двойственных задач линейного программирования дан целостный подход для различных экономических задач выбора оптимальных решений в условиях неопределенности. Количественная оценка риска проводится также с использованием методов математической статистики и теории вероятностей, которые позволяют предвидеть возникновение неблагоприятной ситуации и по возмож- [c.274]
Равенство Сх = у В в модели экономического равновесия выводится не из свойств решений прямой и двойственной задачи линейного программирования, а из условий экономического равновесия (из определения равновесия (3.46) — (3.48)). [c.69]
В дальнейшем целесообразно исследовать возможность улучшения полученного варианта путем изменения объема выделенных ресурсов С., что достигается путем решения двойственной задачи линейного программирования и определения величин двойственных оценок. [c.135]
В линейном программировании кроме симметричных двойственных пар существуют несимметричные двойственные пары, которые имеют следующий вид [c.239]
Запишем в общем виде прямую и двойственную задачи линейного программирования [c.241]
Таким образом, в общем случае для решения матричной антагонистической игры размерностью /ихл необходимо решить пару двойственных задач линейного программирования, в результате чего находится набор оптимальных стратегий , / и цена игры v. [c.229]
Замечание отметим, что решение прямой и двойственной задач линейного программирования всегда может быть сведено к отысканию оптимальных смешанных стратегий двух игроков в прямоугольной игре с нулевой суммой. Таким образом, методы теории игр могут применяться при решении задач линейного программирования и, наоборот, аппарат линейного программирования может применяться в теории игр. [c.31]
Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой экстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) и называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного программирования. [c.56]
Теоремы двойственности и их применение. Фундаментальные свойства, которыми обладают двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности. [c.60]
В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность их вид можно варьировать, включая в множество X часть ограничений [c.106]
Можно доказать и более общее утверждение о свойствах двойственных переменных. При описании метода множителей Лагранжа для задач с ограничениями типа равенств мы показали, что множитель Лагранжа равен производной критерия по правой части равенства. Этим же свойством множители Лагранжа обладают и в задачах линейного программирования [c.56]
Конечно, в задачах, встречающихся в практических исследованиях, сети бывают значительно сложнее, так что для расчета требуется провести значительное число описанных здесь шагов. Тем не менее во многих случаях с помощью метода потенциалов удалось решить практические задачи даже без использования ЭВМ. По своему смыслу потенциалы близки к двойственным переменным соответствующей задачи линейного программирования в матричной постановке (см., например, [13]). [c.191]
В теории линейного программирования доказывается, что независимо от экономической интерпретации исходной и двойственной задач, а также от характера ограничений (< или >), если решение ЛП-задачи на максимум или на минимум существует, то оптимальное (максимальное или минимальное) значение целевой функции в исходной задаче должно быть в точности равно оптимальному (минимальному или максимальному) значению целевой функции двойственной задачи. [c.72]
ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [duality in linear programming] — принцип, заключающийся в том, что для каждой задачи лилейного программирования можно сформулировать двойственную задачу, [c.71]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Рассмотрим двойственную задачу линейного программирования, которая получается по общей схеме. Ограничениям вида (2.17) поставим в соответствие переменные щ, а ограничени- [c.486]
Следующее свойство оптимальных стратегий игроков в матричной игре называется "дополняющей нежесткостью" по аналогии со сходным свойством решений пар двойственных задач линейного программирования (ср. далее в 26). По своей формулировке и своему доказательству оно сходно с частью 1) теоремы предыдущего пункта и двойственным ей утверждением. [c.60]
Итак, получается, что двойственные оценки (множители Лаг-ранжа) являются ценами и выполняют, по крайней мере, распределительную функцию цен (в силу единственности решения двойственной задачи линейного программирования). [c.69]
На самом деле вероятность однозначна, если при анализе того или иного расчетного состояния системы под ней понимать не факт наличия дефицита мощности в ЭЭС, зависящего как раз от принятого принципа взаиморезервирования, а факт потенциальной возможности распределения дефицита мощности (РДМ) в рассматриваемую ЭЭС. В линейной постановке вероятность дефицита мощности в отдельных ЭЭС объединения однозначно определяется по двойственным оценкам линейного программирования [164]. Можно констатировать, что эти вероятности первичны по отношению к вероятностям дефицита мощности, полученным в результате решения задачи устранения неоднозначности РДМ (локальный или другие принципы). Такой трактовке вероятностей отвечает коллективный принцип РДМ, при котором в ЭЭС, потенциально определяющие дефицит мощности объединения, распределяется его часть. В связи с вышесказанным, чтобы не вносить путаницу, ПН, пригодные для целей нормирования при централизованной системе управления объединением ЭЭС, правильнее именовать интегральными вероятностями потенциального дефицита генерирующей мощности (J - для отдельных ЭЭС и Ju - для связей). Эти показатели являются част- [c.77]
Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи1. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким. [c.71]
Разберите ход вычислений в методе Лемке с искусственной переменной применительно к паре двойственных задач линейного программирования. [c.29]
Идея о построении системы цен на основе оптимального планирования производства была высказана Л. В. Канторовичем в процессе разработки методов линейного программирования и их использования для решения экономических задач [39J. Аналогично тому, как в нашей задаче множитель Лаг-ранжа являлся выражением рациональной цены продукта при единичной цене ресурса, так и двойственные оценки ограничений в линейных задачах планирования производства могут быть использованы для построения системы стимулирования, согласованной с плановым заданием. Рассмотрим этот важный вопрос более подробно. [c.346]
Построение систем стимулирования на основе двойственных оценок задач линейного программирования. Пусть изучаемая экономическая система состоит из п производственных единиц каждая из которых описывается в виде совокупности технологических процессов (см. 1 гл. 3). Мы не станем каким-либо образом помечать принадлежность технологических процессов к отдельным предприятиям и рассмотрим их в целом. При этом одинаковые технологические процессы, принадлежащие различным предприятиям, будем считать различными. Пусть всего в системе имеется т технологических процессов. Обозначим через х — = (xt,. .., хт) вектор интенспвностей использования этих процессов. Будем считать, что всего в системе имеется k продуктов (внешних ресурсов), используемых и производимых в системе. Тогда вектор конечной продукции у = (у,,. .., гд) связан с ин-тснсивностями производства соотношением [c.347]
Для решения подобных задач имеется ряд алгоритмов, которые строятся на основе принципа декомпозиции. Наиболее широко известны декомпозиционные алгоритмы, предложенные Данцигом и Вольфом [26], Корнай и Липтаком [61]. В терминах задачи распределения производственной программы отрасли с использованием моделей, решаемых методами линейного программирования, идея алгоритма Данцига-Вольфа следующая. Центральный орган управления отраслью устанавливает цены (двойственные оценки) на продукцию. Исходя из максимизации прибыли при этих ценах, каждое предприятие разрабатывает свою производственную программу. Центральный орган обобщает планы предприятий и сравнивает их с потребностями народного хозяйства в разных видах продукции отрасли. Затем производится корректировка цен если предложенный выпуск продукции данного вида меньше потребности, то цена на нее повышается если выпуск превышает потребность, то цена понижается. Новые цены сообщаются предприятиям для проведения следующей итерации и т. д. [c.189]
С помощью линейного программирования можно решить и следующую задачу имеет личсмысл увеличить количество доступного ресурса. Например, каков результат увеличения рабочего времени в сборочном цехе на 1 ч в неделю. Этот результат — добавочная валовая прибыль, которая может быть получена, называется двойственной оценкой данного ресурса. [c.113]