![]() Главная страница Случайная лекция ![]() Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика ![]() Мы поможем в написании ваших работ! |
Двойственность в линейном программировании
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП. Пусть в качестве исходной дана задача:
a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≤ b2, ... am1x1 + am2x2 + ... + amnxn ≤ bm; xj ≥ 0, Задача линейного программирования, двойственная задаче (6), будет иметь вид: a11y1 + a21y2 + ... + am1ym ≥ c1, a12y1 + a22y2 + ... + am2ym ≥ c2, ... a1ny1 + a2ny2 + ... + amnym ≥ cn; yi ≥ 0, Можно сформулировать правила получения двойственной задачи из задачи исходной. 1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум. 2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи. 3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”. 4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга. 5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой. 6. Условие неотрицательности переменных сохраняется в обеих задачах. Связь между оптимальными планами взаимно двойственных задач устанавливают теоремы двойственности. Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают: Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы. Теорема 2 (о дополняющей нежесткости). Для того чтобы план
Таким образом, если компонент оптимального плана Теорема об оценках. Значения переменных
Компоненты оптимального решения двойственной задачи 4x1 + 6x2 ≤ 120, 2x1 + 6x2 ≤ 72, x2 ≤ 10; x1 ≥ 0, x2 ≥ 0. Получим двойственную задачу. 4y1 + 2y2 ≥ 2, 6y1 + 6y2 + y3 ≥ 4, y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 В результате решения получим следующие оптимальные планы:
Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64. Перейдем к рассмотрению свойств двойственных оценок. Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки Последнее утверждение легко подтвердить, подставив 4ּ24 + 6ּ4 = 120, 2ּ24 + 6ּ4 = 72, 4 < 10 Откуда видно, что при реализации оптимального плана фонд рабочего времени участка С, действительно, расходуется не полностью. Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса. Теневая цена - это стоимость единицы ресурса в оптимальном решении. Необходимо учитывать, что двойственные оценки позволяют измерить эффективность лишь незначительного изменения объема ресурсов. При значительных изменениях может быть получен новый оптимальный план и новые двойственные оценки. Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3ּ12). Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δj) вычисляется как:
В том случае, если Δj ≤ 0, вариант производства является выгодным, если Δj > 0 – вариант невыгоден. Вернемся к примеру. Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию? Для ответа на вопрос рассчитаем Δj по формуле (11): Δj = 3ּ Δj < 0, значит производить бейсбольные биты выгодно. Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение В нашем примере двойственные оценки первого и второго ресурсов равны. Это означает, что, например, при уменьшении фонда времени на участке А на 1 н-час необходимо увеличить фонд времени на участке В на 1 н-час, чтобы общая получаемая предприятием прибыль осталась неизменной. Завершая рассмотрение вопроса, отметим, что применение теорем двойственности позволяет, зная оптимальное решение одной из взаимно двойственных задач, без труда отыскать оптимальное решение другой задачи. Проиллюстрируем это утверждение примером. Для производства четырех видов изделий А1, А2, А3 и А4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц. Технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) и прибыль от реализации единицы каждого изделия приведены в таблице 12.
Дата добавления: 2014-02-27; просмотров: 706; Нарушение авторских прав ![]() Мы поможем в написании ваших работ! |