Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович




Скачать 446.07 Kb.
НазваниеЭкономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович
страница4/6
Дата публикации05.08.2013
Размер446.07 Kb.
ТипМетодические указания
lit-yaz.ru > Математика > Методические указания
1   2   3   4   5   6
^

4. Двойственность в задачах линейного программирования


С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной или прямой.
Исходная задачаДвойственная задача







Две приведенные задачи образуют двойственную пару.

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид "Ј", в задаче на минимум — вид "і";

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица Ат в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) если переменная xj исходной задачи может принимать только положительные значения, то j-ое условие в системе ограничений двойственной задачи является неравенством вида "≥". Если же переменная может принимать как положительные, так и отрицательные значения, то j-ое условие представляет собой уравнение. И наоборот, если i-ое соотношение в системе ограничений исходной задачи является неравенством, то i-ая переменная двойственной задачи yi. В противном случае переменная yi может принимать как положительные, так и отрицательные значения.

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

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

Первая теорема двойственности.

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

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то другая задача вообще не имеет планов.
Вторая теорема двойственности.

План исходной задачи и план двойственной задачи являются оптимальными планами этих задач тогда и только тогда, когда для любых i и j выполняются равенства:





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

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





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





Преобразованную систему уравнений запишем в векторной форме:

,

где ; ; ; ; ; .

Среди векторов P1, P2, P3, P4, P5, только два единичных вектора (P3 и P4), т.е. единичного базиса нет. Поэтому составим расширенную задачу. Для этого в левую часть третьего уравнения системы ограничений добавим искусственную переменную . Её нужно как можно быстрее вывести из базиса. Поэтому в целевую функцию в задаче максимизации новая переменная войдёт с очень большим отрицательным коэффициентом –М. Расширенная задача имеет опорный план , определяемый системой трёх единичных векторов: .

Составим симплексную таблицу для I итерации:
Базис23000-М101-1210002082101003-М32100-114F00-2-300005-3-2-10010

Вычислим оценки разложений векторов по базису опорного решения по формуле , где zj находится как скалярное произведение вектора Pj (j=1,m) на вектор Сб=(с1, с2, ...,сm):

.



Оценки векторов, входящих в базис, всегда равны нулю.

Значение F0 равно скалярному произведению вектора P0 на вектор Сб: F0=1*0+8*0+3*(-М) = -3М.

Значения F0 и состоят из двух слагаемых . Слагаемое, которое не содержит М, записываем в 4-й строке, а число, стоящее при М – в 5-й.

Начальное опорное решение не является оптимальным, так как в 5-й строке имеется два отрицательных числа и . Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов. Чтобы перейти к новому опорному решению в базис можно ввести любой из векторов P1 и P2. Выберем P1, так как ему соответствует наибольшая по модулю оценка. Для определения вектора, подлежащего выводу из базиса, находят для всех aij>0. Для вектора P1 получим (, поэтому отношение не рассматриваем). Минимум достигается при i=3. В третьей строке столбца «Базис» находится вектор Р6. Следовательно, его из базиса исключаем.

Далее выполним преобразование Жордана с разрешающим элементом =2: 1) разделим всю третью строку на 2 и запишем результат в новую симплексную таблицу; 2) остальные элементы первого столбца нужно занулить, для этого полученную 3-ю строку сложим с первой, результат запишем в первую строку новой симплексной таблицы; 3) умножим 3-ю строку на -2 и сложим со второй строкой, результат запишем во вторую строку новой симплексной таблицы.

Получим симплексную таблицу для II итерации:
Базис23000-М105/205/210-1/21/220500011-1323/211/200-1/21/2430-200-11

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

Получили новый опорный план и значение целевой функции F0 = 3.

Рассмотрим элементы 4-й строки. В столбце векторов и имеются отрицательные числа, значит, найденный план не является оптимальным. Вводить в базис будем вектор , исключать . Получим симплексную таблицу для III итерации.

Базис23000-М131012/50-1/51/520500011-132110-1/50-2/52/545004/50-7/57/5

Последняя строка снова содержит отрицательное число. В базис вводим вектор , исключаем .
Базис23000-М132012/51/50020500011-132310-1/52/500412004/57/500

В 4-й строке последней симплексной таблицы нет отрицательных чисел. Значит найденный опорный план является оптимальным. Значение целевой функции .
Составим двойственную задачу.

Умножим третье ограничение на -1, тогда все неравенства будут содержать знак «≤». Задача примет вид исходной задачи симметричной пары 1:



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

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функцию: .

Целевая функция исходной задачи исследуется на максимум, следовательно, целевая функция двойственной задачи исследуется на минимум.

Матрица системы ограничений исходной задачи имеет вид: . Транспонируем её и получим аналогичную матрицу двойственной задачи - . правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи.

Окончательно двойственная задача имеет следующий вид:

.



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

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



Третье ограничение выполняется в виде строгого неравенства, следовательно, .

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

Учитывая, что , получим:

Решив систему, получим

Окончательно

Решение двойственной задачи можно получить другим способом, используя формулу .

Матрица находится в последней симплексной таблице. Ее столбцы расположены под столбцами единичной матрицы, образующими базис начального опорного решения, т. е. под векторами (именно для этой цели мы продолжали вычислять вектор ):

Ответ: , ;


1   2   3   4   5   6

Похожие:

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconОтчет по лабораторной работе №1 по предмету «Экономико-математические...
Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению 6

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания по дисциплине «Экономика организации»
Методические указания составлены в соответствии с примерной программой по дисциплине

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по выполнению курсового проекта с использованием...
Изложены общие указания по курсовому проектированию, приведены задания на проекты, даны методические указания по отдельным этапам...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к контрольной работе по дисциплине «Экономический...
Методические указания предназначены для обучающихся по специальности 051800 «Учет и аудит (по отраслям)»

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания для студентов заочной...
Методические указания составлены в соответствии с Учебно-методическим комплексом дисциплины на основе требований Государственного...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по контрольно-курсовой работе по дисциплине эксплуатацияэвми систем
Методические указания по ккр составлены доц каф ЭВМ лебеденко Ю. И. и обсуждены на заседании кафедры ЭВМ факультета кибернетики

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к лабораторным работам по курсу «Информатика»
Методические указания предназначены для выполнения лабораторных работ по написанию программ на языке C. Работы проводятся с использованием...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и задания к выполнению курсовой работы по курсу «базы данных»
Методические указания и задания к выполнению курсовой работы по курсу «Базы данных» (направление подготовки 050103 ”Программная инженерия”)....



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница