Контент-платформа Pandia.ru:     2 872 000 материалов , 128 197 пользователей.     Регистрация


Двойственные задачи линейного программирования

 просмотров


2.9. Двойственные задачи линейного программирования

Каждой задаче ЛП соответствует другая задача, называемая двойственной по отношению к исходной.

2.9.1 Экономическая интерпретация

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

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

.

Соотношение прямой и двойственной задач ЛП показано в таблице:

Прямая задача

Двойственная задача

.

.

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

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

Цены ресурсов в экономической литературе получили различные названия: учётные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен на продукцию, известных, как правило, до начала производства, цены ресурсов являются внутренними, ибо задаются не извне, а определяются непосредственно в результате решения задачи.

2.9.2 Двойственные задачи и их свойства

Рассмотрим двойственные задачи в общей форме.

Прямая задача:

,

.

Двойственная задача:

.

Двойственная задача по отношению к прямой составляется следующим образом:

1. Целевая функция исходной задачи задаётся на максимум, а в двойственной – на минимум.

2. Матрицы коэффициентов прямой и двойственной задач получаются друг из друга заменой строк столбцами, а столбцов – строками (операция транспонирования):

.

3. Число переменных в двойственной задаче равно числу ограничений в исходной задаче (и наоборот).

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в ограничениях исходной задачи, а правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи.

Задача 7. Составить задачу, двойственную следующей задаче:

,

Поскольку прямая задача на максимум, то приведём все неравенства системы ограничений к виду «£» (обе части первого и четвёртого неравенства умножим на –1):

Составим расширенную матрицу системы:

.

Транспонированная матрица:

.

Сформулируем двойственную задачу:

,

.

2.9.3 Теоремы двойственности

Сначала сформулируем основное неравенство теории двойственности.

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

или в координатном виде

.

Теперь сформулируем достаточный признак оптимальности.

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

,

то – оптимальное решение прямой задачи, а – двойственной задачи.

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

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

или .

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

Экономический смысл первой теоремы двойственности состоит в следующем.

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

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

Пусть даны двойственные задачи.

Прямая:

,

.

Двойственная:

,

.

Если каждую из этих задач решать симплекс-методом, то необходимо привести их к каноническому виду, для чего в систему ограничений

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

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

прямая задача –

,

двойственная задача –

.

Соответствие между переменными двойственных задач иллюстрирует таблица:

Переменные прямой задачи

Первоначальные

Дополнительные

Дополнительные

Первоначальные

Переменные двойственной задачи

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

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

Следствие. Если в оптимальном решении одной из двойственных задач какая-либо переменная не равна нулю, то соответствующее ей ограничение двойственной задачи на оптимальном решении выполняется как равенство, и наоборот, если на оптимальном решении одной из двойственных задач какое-либо ограничение выполняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении двойственной задачи равна нулю.

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

Задача 8. Решив симплексным методом задачу

,

получим: , .

Перейдём к неравенствам типа “”:

.

Двойственная задача:

,

Соответствие между переменными (см. табл. выше):

.

На оптимальном решении прямой задачи имеем:

Так как третье и четвёртое ограничения выполняются как строгие неравенства, то, согласно следствию, , , причём оба ограничения двойственной задачи выполняются как равенства:

Подставляя сюда и решая систему, оптимальное решение двойственной задачи .

2.9.4 Объективно обусловленные оценки

Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными) оценками прямой задачи. Академик Л. В.Канторович назвал их объективно обусловленными оценками.

Рассмотрим двойственные задачи об использовании ресурсов (из четырёх видов ресурсов можно изготовить два вида продукции или продать ресурсы).

Прямая Двойственная

. .

Решения: , ; , .

Связь между решениями прямой и двойственной задач иллюстрирует таблица:

Компоненты оптимального решения прямой задачи

Число единиц продукции

Остатки ресурсов, единиц

Превышение затрат на ресурсы

над ценой реализации

Объективно обусловленные оценки ресурсов

(условные цены ресурсов)

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

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

Ресурсы по оптимальному плану полностью использованы (), и объективно обусловленные оценки этих ресурсов ненулевые (). Ресурсы использованы в оптимальном плане не полностью () и объективно обусловленные оценки этих ресурсов нулевые ().

Таким образом, объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (то есть полностью используемые) ресурсы получают ненулевые оценки, а недефицитные – нулевые оценки.

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

Таким образом, в оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции (правда, критерий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при её изготовлении ресурсы, а в точности равна им).

Контрольные вопросы

1. Сформулировать понятие о взаимно-двойственной задаче.

2. Дать экономическую интерпретацию пары взаимно-двойственных задач.

3. Сформулировать свойства пары взаимно-двойственных задач.

4. Сформулировать первую теорему двойственности и ее экономическое содержание.

5. Сформулировать вторую теорему двойственности и ее экономическое содержание.

5. Дать определение понятию объективно-обусловленные оценки.

Мы в соцсетях:


Подпишитесь на рассылку:
Посмотрите по Вашей теме:

Проекты по теме:

Основные порталы, построенные редакторами

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумагиНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыБюджетФинансовые услугиКредитыКомпанииЭкономикаМакроэкономикаМикроэкономикаНалоги
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьер

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказЭкономикаРегионы РоссииПрограммы регионов
История: СССРИстория РоссииРоссийская ИмперияВремя2016 год
Окружающий мир: Животные • (Домашние животные) • НасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШкола
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовМуниципалитетыМуниципальные районыМуниципальные образованияМуниципальные программыБюджетные организацииОтчетыПоложенияПостановленияРегламентыТермины(Научная терминология)

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства