Читайте также:
|
|
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача – прямая или исходная. Пара симметричных двойственных задач ЛП имеет следующий вид:
Прямая - 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 | Поможем написать вашу работу | Нарушение авторских прав |