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

ЛИНЕЙНОЕ

ПРОГРАММИРОВАНИЕ

(для бакалавров 1-го курса

очной формы обучения)

Часть II

Ростов-на-Дону

УДК 517(07)

Линейное программирование (для бакалавров 1-го курса очной формы обучения). Часть II. – Ростов н/Д: Рост. гос. строит. ун-т, 2011. – 24 с.

Изложены двойственная задача ЛП и ее решение, транспортная задача ЛП и ее решение, особенности решения транспортных задач с неправильным балансом. Приведён образец индивидуального задания, снабжённый подробным решением входящих в него задач.

Предназначены для бакалавров 1-го курса очной формы обучения специальностей ОБД, АС дорожно-транспортного института, а также для бакалавров экономических специальностей.

Электронная версия методических указаний находится в библиотеке, ауд. 224.

УДК 517(07)

Составители: канд. физ.-мат. наук, доц. М. М. Цвиль

канд. физ.-мат. наук, доц.

В. В. Шамраева

ассист. И. В. Цветкова

ассист. В. В. Новиков

Рецензент: канд. физ.-мат.наук, доц. Г.А. Можаев

Редактор Т.М. Климчук

Доп. план 2011 г., поз. 183

Подписано в печать 12.07.11. Формат 60´84/16. Бумага писчая. Ризограф.

Уч.-изд.л. 1,8. Тираж 20 экз. Заказ 385

Редакционно-издательский центр

Ростовского государственного строительного университета

344022, Ростов-на-Дону, ул. Социалистическая, 162

Ó Ростовский государственный
строительный университет, 2011

Теория двойственности

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

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

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

Имеется Построение двойственной задачи - student2.ru видов сырья в количестве Построение двойственной задачи - student2.ru , которые используются для изготовления Построение двойственной задачи - student2.ru видов продукции. Известно: Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru – расход Построение двойственной задачи - student2.ru -го вида сырья на единицу Построение двойственной задачи - student2.ru -й продукции; Построение двойственной задачи - student2.ru прибыль от реализации единицы Построение двойственной задачи - student2.ru -го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Математическая модель данной задачи имеет вид (в матричной форме):

Построение двойственной задачи - student2.ru ;

Построение двойственной задачи - student2.ru ;

Построение двойственной задачи - student2.ru . (6.1.1)

Здесь Построение двойственной задачи - student2.ru , Построение двойственной задачи - student2.ru объём производства Построение двойственной задачи - student2.ru -го вида продукции.

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

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

Построение двойственной задачи - student2.ru .

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

Построение двойственной задачи - student2.ru , Построение двойственной задачи - student2.ru .

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

Построение двойственной задачи - student2.ru ;

Построение двойственной задачи - student2.ru ;

Построение двойственной задачи - student2.ru . (6.1.2)

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

В теории двойственности используются 4 пары двойственных задач:

Исходная задача Двойственная задача
Симметричные пары
1. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru 1. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru
2. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru 2. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru
Несимметричные пары
3. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru 3. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru  
4. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru 4. Построение двойственной задачи - student2.ru Построение двойственной задачи - student2.ru ,  

где

С = (c1, c2, …, cn); Y = (y1, y2, …, ym);

Построение двойственной задачи - student2.ru ; Построение двойственной задачи - student2.ru ; Построение двойственной задачи - student2.ru .

Наши рекомендации