Мегаобучалка Главная | О нас | Обратная связь


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



2015-12-14 465 Обсуждений (0)
ТЕОРИЯ ДВОЙСТВЕННОСТИ 0.00 из 5.00 0 оценок




 

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

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

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

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

Имеется m видов сырья в количестве которые используются для изготовления n видов продукции. Известно: - расход i-ого вида сырья на единицу j-ой продукции; - прибыль при реализации единицы j-ого вида продукции.

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

(4.1.1)

(4.1.2)

xj ≥ 0, j = 1,2,…,n. (4.1.3)

Здесь - объем производства j-ого вида продукции.

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

(4.1.4)

Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-ой продукции, т.е.

Меньше прибыли , имеет вид:

(4.1.5)

Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности (4.1.6)

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

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

 

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

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

1. (4.1.7)

 

2. (4.1.8)

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

3. (4.1.9)

 

4. (4.1.10)

Здесь

 

 



2015-12-14 465 Обсуждений (0)
ТЕОРИЯ ДВОЙСТВЕННОСТИ 0.00 из 5.00 0 оценок









Обсуждение в статье: ТЕОРИЯ ДВОЙСТВЕННОСТИ

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (465)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.006 сек.)