Студопедия  
Главная страница | Контакты | Случайная страница

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

Двойственные задачи в линейном программировании. Понятие двойственности, формулировка двойственной задачи, правило построения пары взаимнодвойственных задач, примеры

Читайте также:
  1. I. ЦЕЛИ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ
  2. I. Цели и задачи освоения дисциплины
  3. I. Цель и задачи преддипломной практики.
  4. I.1.1. Цели и задачи дисциплины
  5. II. Задачи и направления деятельности методического объединения
  6. II. Основные цели и задачи концепции
  7. II. Цели и задачи выпускной квалификационной работы
  8. II. ЦЕЛИ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ
  9. II. Цели и задачи службы
  10. II. Цели и задачи фестиваля

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

Прямая - maxZ = Xj>=0

Двойственная minZ = Xj>=0

Задача, состоящая в нахождении минимального значения функции

При условиях:

Называется двойственной по отношению к прямой задаче.

Экономическая интерпретация:

Прямая – Сколько и какой продукции Xj надо произвести чтобы при заданных стоимостях единицы продукции Cj объемах ресурсов Bi и нормах расхода Aijмаксимизироваит выпуск продукции в стоимостном выражениии.

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

Правила построения:

1.Упорядочивается запись исходной задачи, т.е. если целевая функция задачи максимизируется, то ограничения неравенства должны быть < или =(для минимиз> или =) Достигается умножением ограничений на -1.

2.Если прямая задача решается на максимум, то двойственная на минимум.

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот.

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

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

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

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

 

Двойственные задачи в ЛП. Вторая теорема двойственности, т.е. условия нежесткости, соответствие между переменными прямой и двойственной задачи, экономическая интерпретация дополнительных переменных двойственной задачи.

Вторая теорема двойственности (теорема о дополняющей нежесткости):

Пусть Х = (х1, х2, …хn) допустимое решение прямой задачи, а У = (у1, у2,..уm) допустимое решение двойственной задачи. Для того, чтобы они были оптимальными решениями соответствующих взаимодвойственных задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:

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

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

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

 

Транспортная задача. Постановка ТЗ в матричной и математической форме, методы нахождения начального опорного плана.

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

ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1, А2,..., Аm в n пунктов назначения B1, B2,..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:

- объем производства (запас) i-го поставщика, i=1, m;

- объем потребления (спрос) j-го потребителя, i=1, n;

- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

Всякое неотрицательное решение систем линейных уравнений, определяемое матрицей, называется планом транспортной задачи.

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

Самым простейшим из методов поиска начального опорного плана является "метод северо-западного угла", отправной точкой для которого является левый верхний угол таблицы.Пусть m=3, A=(17, 33, 20); n=5, B=(14, 14, 14, 14, 14). Т.к. условие баланса здесь соблюдается, то приступаем к поиску начального опорного плана в табличной форме (для удобства перенесем в "оцифровку" таблицы значения A, B). Имеем X11=min(17, 14)=14, X21=X31=0.

Продолжаем поиск с угла незаполненной части таблицы

X12=min(17-14, 14)=3, X13=X14=X15=0, X22=min(33, 14-3)=11,

X32 = 0, X23=min(33-11, 14)=14, X33=0; X24=min(33-11-14, 14)=8,

X25=0; X34=14-8=6, X35=20-6=14.

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

Пусть значения A, B те же, что и в рассмотренном примере, а стоимости перевозок определяются матрицей С. Так как минимальная стоимость cоответствует C22, то начинаем поиск компонент опорного плана с элемента X22=min(33, 14)=14, X12=X32=0; затем

X13=min(17, 14)=14, X23=X33=0,

X34=min(20, 14)=14, X14=X24=0,

X35=min(20-14, 14)=6, X31=0;

X21=min(33-14, 14)=14, X11=0;

наконец, X15=17-14=3; X25=33-14-14=5.

 

Транспортная задача (нахождение начального опорного плана, теорема о ранге матрицы).

Самым простейшим из методов поиска начального опорного плана является "метод северо-западного угла", отправной точкой для которого является левый верхний угол таблицы.Пусть m=3, A=(17, 33, 20); n=5, B=(14, 14, 14, 14, 14). Т.к. условие баланса здесь соблюдается, то приступаем к поиску начального опорного плана в табличной форме (для удобства перенесем в "оцифровку" таблицы значения A, B). Имеем X11=min(17, 14)=14, X21=X31=0.

Продолжаем поиск с угла незаполненной части таблицы

X12=min(17-14, 14)=3, X13=X14=X15=0, X22=min(33, 14-3)=11,

X32 = 0, X23=min(33-11, 14)=14, X33=0; X24=min(33-11-14, 14)=8,

X25=0; X34=14-8=6, X35=20-6=14.

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

Пусть значения A, B те же, что и в рассмотренном примере, а стоимости перевозок определяются матрицей С. Так как минимальная стоимость cоответствует C22, то начинаем поиск компонент опорного плана с элемента X22=min(33, 14)=14, X12=X32=0; затем

X13=min(17, 14)=14, X23=X33=0,

X34=min(20, 14)=14, X14=X24=0,

X35=min(20-14, 14)=6, X31=0;

X21=min(33-14, 14)=14, X11=0;

наконец, X15=17-14=3; X25=33-14-14=5.

Теорема о ранге матрицы:

Ранг матрицы транспортной задачи на 1 меньше числа уравнений(r=m+n-1).

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

 




Дата добавления: 2015-04-20; просмотров: 37 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | 3 | <== 4 ==> | 5 | 6 | 7 | 8 | 9 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав