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

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

Читайте также:
  1. I. 1.2. Общая постановка задачи линейного программирования
  2. I.5.3. Подготовка данных для задачи линейного программирования
  3. I.5.4. Решение задачи линейного программирования
  4. II.2. Задача о назначениях
  5. II.4. МЕТОД ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
  6. V2: ДЕ 57 - Фундаментальная система решений линейного однородного дифференциального уравнения
  7. VI. Общая задача чистого разума
  8. Аксиомы линейного пространства
  9. Анализ чувствительности задач линейного программирования
  10. Апофеоз: двойственная роль развития речи
  11. Архитектура программирования SSAS.

 

Каждой задаче линейного программирования

 

 

со смешанными ограничениями вида

 

 

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

 

при ограничениях

 

 

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

· если прямая задача является задачей максимизации, то двойственная – минимизации и наоборот;

· коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

· свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

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

· число переменных двойственной задачи равно числу ограничений прямой задачи и наоборот.

 

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

 

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

 

... ... ... ...
... ... ... ...
... ... ... ...

 

Отсюда имеем оптимальный план двойственной задачи.

· Если прямая задача решается на максимум:



 

 

· Если прямая задача решается на минимум:

 

Рассмотрим пример.

 

Приведем задачу к каноническому виду

 

 

Таблица I.

 

№ 1    

 

Здесь в условиях наших обозначений: (количество истинных переменных) и (количество дополнительных переменных = количеству ограничений задачи):

 

 

Заметим так же, что задача решается на максимум.

 

Таблица II.

 

№ 2    
-2

 

Таблица III.

 

№ 3    
-
-

 

 

Оптимальный план двойственной задачи, судя по вектору , будет иметь вид

 

 


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 |



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