АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. 1.1. Пример разработки модели задачи технического контроля
  3. I. 1.2. Общая постановка задачи линейного программирования
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.1. Двойственная задача линейного программирования
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  8. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  9. I. Ситуационные задачи и тестовые задания.
  10. I. Цель и задачи дисциплины
  11. I.5.3. Подготовка данных для задачи линейного программирования
  12. I.5.4. Решение задачи линейного программирования

 

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

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

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

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

Матрица

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

в двойственной задаче получаются друг из друга транспо­нированием. Число переменных в двойственной задаче (т) равно числу соотношений (ограничений) в прямой задаче, а число ограничений двойственной задачи (п) - числу пе­ременных в прямой задаче.

Коэффициенты при неизвестных в целевой функции двойственной задачи - свободные члены (bi), а правые ча­сти в ограничениях двойственной задачи (сj) - коэффици­енты при неизвестных в целевой функции прямой задачи.

Если переменная xj прямой задачи может принимать только положительные значения (хj 0), то j -еусловие двой­ственной задачи - условие неравенства вида «≥». Если 1-е соотношение в прямой задаче - неравенство, то i -я пере­менная двойственной задачи zi 0.

Если прямая задача имеет решение, то и двойствен­ная задача тоже имеет решение, причем max(min) L1= min(max) L2, поэтому для отыскания оптимума доста­точно решить одну какую-либо из задач двойственной пары. Обычно решают ту, которая проще.

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

Пример. Для производства изделий А, В, С использу­ются три различных вида ресурсов. Каждый из видов ре­сурсов может быть использован в количестве, соответствен­но не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на ед. продукции и цена ед. продукции каждого вида (табл. 15).

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

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

Решение. Обозначим через х1 искомый план произ­водства изделий А, через х2 - В, x3 - С, а через z 1- двойственную оценку дефицитности первого вида ресурса, через z2 - второго, z3 - третьего.

Таблица 15

Вид ресурса Норма расхода ресурса на единицу продукции
А В С
       
       
       
Цена продукции      

 

Тогда прямая и двойственная задачи формулируются:

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

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

Решение прямой задачи дает оптимальный план произ­водства изделий А, В, С, а решение двойственной задачи - оптимальную систему оценок ресурсов, используемых для производства этих изделий:

Исходя из анализа оптимальных двойственных оценок, можно сделать следующие выводы.

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

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

Так, увеличение количества ресурса первого вида на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при кото­ром общий доход возрастает на 5,75 д. е. и станет равным 1340 + 5,75 = 1345,75 д. е. Анализ полученных оптималь­ных значений новой прямой задачи показывает, что это увеличение общего дохода достигается за счет увеличения производства изделий В на 0,625 ед. и сокращения выпус­ка изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.

Точно так же увеличение на 1 ед. количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастёт на 1,25 д. е. и составит 1340 + 1,25 = 1341,25 д. е., что достигается за счет увеличения выпуска изделий С на 0,25 ед, и уменьшения выпуска В на 0,25 ед., причем объем используемого ресур­са, второго вида возрастает на 0,625 ед.

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

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

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

где - величина возможного (при сохранении оптималь­ного плана первоначальной двойственной задачи) измене­ния (увеличения или уменьшения) ресурса i -го вида.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



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