Tooprogram.ru

Компьютерный справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Соотношение дополняющей нежесткости

Соотношение дополняющей нежесткости

Существование зависимости между решениями прямой и двойственной задач характеризуются следующими леммами и теоремами двойственности.

Лемма 11.1 (основное неравенство теории двойственности). Если – некоторый план исходной задачи, а – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане всегда не превосходит значение целевой функции двойственной задачи при плане , т.е.

Лемма 11.2. Если и – допустимые решения взаимно двойственных задач, для которых выполняется равенство , то – оптимальное решение исходной задачи, а – оптимальное решение двойственной задачи.

Теорема 11.1. Первая теорема двойственности (основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план , то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

.

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то область допустимых решений другой задачи пустая.

Из этой теоремы вытекают необходимые и достаточные условия:

a) разрешимости задач – существование хотя бы одного допустимого плана у каждой задачи;

б) оптимальности допустимых планов X и Y – выполнение равенства F ( X ) = T ( Y ).

Теорема 11.2. Вторая теорема двойственности (теорема о дополнительной нежесткости). Для того чтобы два допустимых решения и пары двойственных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений

(*)

(**)

Данная теорема позволяет:

a) установить оптимальность решения одной задачи по свойствам решения двойственной;

б) найти оптимальное решение одной задачи по решению двойственной.

Теорема верна для симметричной двойственной пары. Для задач в канонической и общей формах соотношения (*) и (**) верны только для ограничений в виде неравенств и для неотрицательных переменных.

Полученные выше результаты непосредственно характеризуют взаимосвязь прямой и двойственной задач:

2. На любой итерации процесса решения прямой задачи

Эти соотношения позволяют дать важную экономическую интерпретацию двойственности и переменным двойственной задачи. Чтобы сделать это с помощью некоторых формальных категорий, рассмотрим прямую задачу как задачу распределения ограниченных ресурсов с целевой функцией, подлежащей максимизации. Условия прямой задачи можно интерпретировать следующим образом. Коэффициент представляет собой прибыль, приходящуюся на единицу продукции -го вида производственной деятельности. Расход ресурса , запасы которого ограничены величиной , на единицу продукции -го вида производственной деятельности равен единицам этого ресурса. Переменные двойственной задачи представляют ценность единицы ресурса (в экономической литературе они получили различные названия: неявные, учетные, теневые).

Двойственные оценки могут быть использованы для определения приоритета используемых ресурсов в соответствии с их вкладом в величину целевой функции.

В соответствии с основным неравенством теории двойственности в случае неоптимальных допустимых решений . Формулировка этого неравенства в рамках экономической интерпретации выглядит следующим образом:

Из этого соотношения следует, что до тех пор, пока прибыль меньше суммарной ценности ресурсов, решение остается неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов.

Чтобы дать представление о соответствующих обозначениях, часто встречающихся в литературе по линейному программированию, введем следующее определение:

– суммарная оценка ресурсов, используемых при производстве единицы продукции -го вида.

Разность равна фигурирующему в симплекс-таблице -коэффициенту при переменной (в наших обозначениях ). Ее часто называют приведенными издержками -го вида производственной деятельности.

Условие оптимальности (в задаче максимизации), используемое в симплекс-методе, состоит в том, что вид производственной деятельности, не представленный в текущем решении (ему соответствует независимая переменная ) должен вводиться в последующее решение с отличным от нуля и положительным уровнем использования ( ) только в том случае, когда -коэффициент при данной переменной отрицателен. Дадим экономическую интерпретацию этому условию. Неиспользованный вид производственной деятельности должен быть представлен в решении только в том случае, если , т.е. когда

Таким образом, пока прибыль превышает суммарную оценку ресурсов, уровень использования данного вида производственной деятельности следует увеличивать. Следует заметить, что мы увеличиваем уровень его использования до того значения, при котором -коэффициент при данной переменной станет равным нулю. Это эквивалентно полной реализации всех возможностей, связанных с получением прибыли от данного вида производственной деятельности.

Читать еще:  Не отображается жесткий

Соотношение дополняющей нежесткости

В нашей онлайн базе уже более 10821 рефератов!

Навигация
Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

Вы можете воспользоваться поиском готовых работ или же получить помощь по подготовке нового реферата практически по любому предмету. Также вы можете добавить свой реферат в базу.

УКРАИНСКИЙ INTEL НАГРАДИТ ШКОЛЬНИКОВ И СТУДЕНТОВ ЗА НАУЧНЫЕ ПРОЕКТЫ
О своем намерении поддержать талантливых школьников и студентов заявил украинский офис компании Intel – в уанете появился проект “Интеллектуализация”, в рамках которого идет конкурс лучших практических проектов среди молодежи.

—>

Анализ экономических задач симплексным методом

Теорема. (малая теорема двойственности)

Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.

§5. Основные теоремы двойственности

и их экономическое содержание

Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функ­ций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

Экономическое содержание первой теоремы двойствен­ности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продук­ции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммар­ной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были опти­мальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойст­венные оценки, обладают тем свойством, что они гаранти­руют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от опти­мального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.

Теорема. (о дополняющей нежесткости )

Для того, чтобы планы и пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:

(1)

(2)

Условия (1), (2) называются условиями допол­няющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обра­щается в строгое неравенство, то соответствующая компо­нента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента опти­мального плана одной из задач положительна, то соответ­ствующее ограничение в двойственной задаче ее опти­мальным планом должно обращаться в строгое равенство.

Экономически это означает, что если по некоторому оптимальному плану производства расход i -го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы это­го ресурса равна нулю. Если же в некотором оптимальном плане оценок его i -я компонента строго больше нуля, то в оптимальном плане производства расход соответствую­щего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положитель­ную оценку, а ресурс избыточный (используемый не полно­стью) имеет нулевую оценку.

Теорема .(об оценках). Двойственные оценки пока­зывают приращение функции цели, вызванное малым из­менением свободного члена соответствующего ограниче­ния задачи математического программирования, точнее

(3)

§6. Примеры экономических задач

5.1 Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объеди­нение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресур­сов, может выпускать n различных видов продукции (то­варов), известных под номерами, обозначаемыми индек­сом j . Ее будем обозначать . Предприятие при производстве этих видов продукции должно ограни­чиваться имеющимися видами ресурсов, технологий, дру­гих производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингре­диентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким обра­зом, — вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпуск­ной цене товара, его прибыльности, издержкам произ­водства, степени удовлетворения потребностей и т. д. При­мем в качестве такой меры, например, цену реализации

, т. е. —вектор цен. Известны также технологические коэффициенты , кото­рые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обо­значают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно произво­дить и в каких количествах, чтобы обеспечить предприя­тию максимум объема реализации при имеющихся ре­сурсах.

Так как — цена реализации единицы j’-й продукции, цена реализованных единиц будет равна , а общий объем реализации

Это выражение — целевая функция, которую нужно мак­симизировать.

Так как — расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосхо­дить единиц:

Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции:

.

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

(1)

(2)

(3)

Сформулируйте 2-ю теорему двойственности в задаче ЛП (условия дополняющей нежесткости)

Сформулируйте 2-ю теорему двойственности в задаче ЛП (условия дополняющей нежесткости).

Условие дополняющей нежесткости:

Как найти оптимальное решение прямой задачи линейного программирования, если найдено оптимальное решение ее двойственной задачи?

Сформулируйте теорему Куна-Таккера для задачи выпуклого программирования в дифференциальной форме.

Сформулируйте достаточное условие существования глобального экстремума (теорема Вейерштрасса). Назовите возможные причины отсутствия оптимального решения, приведите примеры.

Чем вызвана необходимость разработки и применения численных методов?

Как выбирается длина шага в градиентном методе с полным шагом?

В каких случаях градиентный метод медленно сходится?

Что такое лексикографическая оптимизация?

ЛЕКСИКОГРАФИЧЕСКОЕ УПОРЯДОЧЕНИЕ (оптимизация) — упорядочение объектов (в многокритериальной задаче, в задаче выявления предпочтений) таким образом, что, напр., объект a′ предпочитается объекту a′′, если он имеет бомльшую оценку по наиболее важному критерию x1, невзирая на то, насколько он является хорошим или же плохим по другим менее важным критериям. Но если значения x1 для них совпадут, вводится в рассмотрение следующий по важности критерий x2 и по нему выбирается предпочитаемый объект. Соответственно в случае совпадения оценок по критериям x1, x2 вводится критерий x3 и т. д. Определение “лексикографическое” объясняется тем, что эта процедура напоминает построение словаря.

Сформулируйте и докажите достаточные условия оптимальности по Парето в форме линейной свертки (теорема 1).

Оптимальность по Парето — такое состояние системы, при котором значение каждого частного критерия, описывающего состояние системы, не может быть улучшено без ухудшения положения других элементов.

Почему Парето-оптимальное решение оптимально по Слейтеру?

Изложите метод последовательных уступок.

Все частные критерии располагают и нумеруют

в порядке их относительной важности; максимизируют первый, наиболее важный критерий затем назначают величину допустимого снижения значения этого критерия и максимизируют второй по важности частный критерий при условии, что значение первого критерия не должно отличаться от максимального более чем на величину установленного снижения (уступки); снова назначают величину уступки, но уже по второму критерию и находят максимум третьего по важности критерия при условии, чтобы значения первых двух критериев не отличались от ранее найденных максимальных значений больше чем на величины соответствующих уступок; далее подобным же образом поочередно используются все остальные частные критерии; оптимальной обычно считают любую стратегию, которая получена при решении задачи отыскания условного максимума последнего по важности критерия.

Таким образом, при использовании метода последовательных уступок многокритериальная задача сводится к поочередной максимизации частных критериев и выбору величин уступок. Величины уступок характеризуют отклонение приоритета од них частных критериев перед другими от лексикографического: чем уступки меньше, тем приоритет жестче.

Что такое арбитражное решение Нэша, почему оно оптимально по Парето?

Сформулируйте необходимые и достаточные условия оптимальности по Парето в многокритериальной задаче линейного программирования.

Выделяют три условия обеспечения оптимальности по Парето.

Первое условие. Оптимальное распределение благ между потребителями исходит из соблюдения условия, согласно которому предельная норма замещения двух благ должна быть одинаковой для обоих потребителей. Предположим, что в экономике производятся два блага X и Y и имеются два потребителя А и В, то MUxa/MUya = MUxb/MUyb

Второе условие. Оптимальное распределение ресурсов в производстве. Для производства благ X и Y имеется два ресурса i и j. В этом варианте должно соблюдаться равенство, согласно которому соотношение предельных продуктов i и j, используемых для производства блага X, равно соотношению предельных продуктов i и j в производстве блага Y, а именно:

Третье условие. Оптимальный объем производства. Граница производственных возможностей показывает количество благ X и Y, которые могут быть произведены в условиях полного использования ресурсов.

Оптимальный объем производства для любых двух благ будет при соблюдении следующих соотношений: MUx/MCx = MUy/MCy

Это значит, что отношение предельных издержек к предельной полезности должно быть одинаковым для обоих благ.

Если ваш вопрос один из следующих, то вам не повезло, ответы найти не получилось:

Сформулируйте необходимые и достаточные условия выпуклости и строгой выпуклости дважды дифференцируемой функции нескольких переменных (в терминах Гессиана).

Может ли оптимальная по Парето оценка быть внутренней точкой множества достижимых оценок?

Может ли оптимальное по Парето решение быть внутренней точкой множества допустимых решений?

Что такое среднеквадратическое решение? К какой задаче Математического Программирования сводится его вычисление в многокритериальной задаче ЛП?

В чем сущность метода целевого программирования? При каком определении расстояния в критериальном пространстве возможно решение задачи целевого программирования методами линейного программирования?

Теорема о дополняющей нежесткости

Читайте также:

  1. S-M-N-теорема, приклади її використання
  2. Б1 1.Системы линейных алгебраических уравнений (СЛУ). Теорема Кроникера-Капелли. Общее решение СЛУ.
  3. Базисный минор и ранг матрицы. Теорема о базисном миноре
  4. Билет 22Понятие евклидова пространства, неравенство Коши-Буняковского. Теорема Кронекера Капелли.
  5. Билет 5 Теорема Безу и следствия из неё. Основная теорема алгебры.
  6. Внешние эффекты (экстерналии). Теорема Коуза.
  7. Внешние эффекты трансакционные издержки. Теорема Коуза
  8. Внешние эффекты, их виды и последствия. Теорема Коуза
  9. Внешние эффекты. Теорема Коуза.
  10. Внешние эффекты. Теорема Коуза.
  11. Вопрос 1 теорема сложения вероятностей
  12. Вопрос 24 Теорема Остроградского-Гаусса для электрического поля в вакууме

Допустимые векторы хи у являются решениями задач (4.4) и (4.5) тогда и только тогда, когда они удовлетворяют условиям дополняющей нежесткости:

. (4.11)

Это утверждения вытекает из предыдущей теоремы и системы условий (4.10).

Ввиду практической важности последней теоремы для решения задач графическим способом рассмотрим условия (4.8) подробнее. Для этого представим их в скалярной форме:

(4.12)

Поскольку мы рассматриваем только допустимые точки, то и , а значит , т.е. каждое слагаемое в первом неравенстве (4.12) неположительно. Однако сумма их равна нулю. Очевидно, это возможно только при равенстве нулю каждого слагаемого. Таким образом, , а это, в свою очередь, означает, что в каждом таком произведении хотя бы один из сомножителей равен нулю.

Иными словами, можно сказать, что если в оптимальной точке (прямой задачи) , то , или, что то же самое, , т.е. соответствующее ограничение в оптимальной точке двойственной задачи превращается в равенство (активно). И наоборот, если в оптимальной точке двойственной задачи , т.е. некоторое ограничение не активно, то соответствующая переменная в оптимальной точке прямой задаче равна нулю: .

Аналогичные рассуждения справедливы относительно второго равенства из (4.12) с той лишь разницей, что там все сомножители неотрицательны.

Суммируя сказанное, теорему о дополняющей нежесткости можно сформулировать следующим образом:

1 0 Если в оптимальной точке прямой задачи некоторое ограничение не активно (неравенство выполняется строго), то в оптимальной точке двойственной задачи соответствующая переменная равна нулю.

2 0 Если в прямой задаче некоторая переменная не равна нулю (строго положительна), то в оптимальной точке двойственной задачи соответствующее ограничение обращается в равенство (активно).

Напомним, что понятия прямой и двойственной задач относительны: любую из взаимно двойственных задач можно считать прямой, тогда другая будет двойственной к ней.

Двойственные задачи допускают следующую экономическую интерпретацию.

Будем называть прямой задачей задачу на максимум вида (4.4), а двойственной – задачу на минимум вида (4.5).

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.028 сек.)

Ссылка на основную публикацию
Adblock
detector