Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Виды математических моделей двойственных задач


ТЕОРИЯ ДВОЙСТВЕННОСТИ

 

 

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

Составим двойственную задачу к следующей задаче.

Имеется т видов сырья в количестве b1, b2,..., bт, которые используются для изготовления п видов продукции. Известно: аij — расход i-го вида сырья на единицу j-ой продукции; сj. — прибыль при реализации единицы j-го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль.

Математическая модель данной задачи имеет вид

F(X) = с1 х1 + с2 х2 + ... + сп хпmax,

Здесь х j, j = 1,2, ..., п — объем производства j-го вида продукции.

Предположим, что второй производитель хочет перекупить сырье. Составим двойственную задачу, решение которой позволит определить условия продажи сырья. Введем вектор оценок (цен) видов сырья Y=(у1, у2,… …,ут). Затраты на приобретение i -го вида сырья в количестве bi равны biуi . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид

Z(Y) =b1у1 +b2у2 +…+bтут min.

Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-й продукции, т.е. а1j у1 + а2j у2 +…+ аmj ут, меньше прибыли сj получаемой при реализации этого изделия. Система ограничений задачи имеет вид

Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности уi0, i = 1, 2, …, т.

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



Рассмотренная пара задач относится к симметричным парам двойственных задач. В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи):

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

Симметричные пары

1. F(X)=CX→max, Z(Y)=YA0→min

AXA0 , YAC,

X≥θ; Y≥θ.

2. F(X)=CX→min, Z(Y)=YA0→ max,

AXA0 , YAC,

X≥θ; Y≥θ.

Несимметричные пары

3. F(X)=CX→max, Z(Y)=YA0→min

AX= A0 , YAC.

X≥θ;

2. F(X)=CX→min, Z(Y)=YA0→ max,

AX=A0 , YAC.

X≥θ;

Здесь С=(с1, с2,…, сn), Y= (у1, у2,… …,ут),

 

<== предыдущая лекция | следующая лекция ==>
Задачи для самостоятельного решения. Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц | Общие правила составления двойственных задач

Дата добавления: 2014-01-04; Просмотров: 384; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.