Каталог Рефератов - Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Zmin = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y* = C*D-1, где матрица D-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5, A4, A2 ; значит, Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

1 -1 2 D = (A5, A4, A2) = -1 2 -4 1 0 3 Обратная матрица D-1 образована из коэффициентов, стоящих в столбцах A1, A3, A6 четвертой итерации: Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

2 1 0 D-1 = -1/3 1/3 2/3 -2/3 -1/3 1/3 Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

Из этой же итерации следует С* = (— 3; —1; 1). Таким образом 2 1 0 Y = С*D-1 = (-3; -1; 1) · -1/3 1/3 2/3 -2/3 -1/3 1/3 Y*=(-19/3; -11/3; -1/3), т. е. yi = С*Хi, где Хi — коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса. Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней прибавить соответствующее значение коэффициента линейной функции: у1 = — 19/3 + 0 = — 19/3; y2 = -11/3 + 0 = -11/3; у3 = -1/3+0 = -1/3. При этом плане max f = -46/3.

3. Симметричные двойственные задачи

Разновидностью двойственных задач линейного , программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. Исходная задача. Найти матрицу-столбец Х = (x1, x 2, ., xn), которая удовлетворяет системе ограничений (1.12). АХ>А0, Х>0 и минимизирует линейную функцию Z = СХ. Двойственная задача. Найти матрицу-строку Y = (y1, y 2, ., yn), которая удовлетворяет системе ограничений YA £ C, Y ³ 0 и максимизирует линейную функцию f = YA0. Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана. Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления. Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях

2x1 + 2x2 - x3 ³ 2, x1 - x2 - 4x3 £ -3, xi ³ 0 (i=1,2,3) x1 + x2 - 2x3 ³ 6, 2x1 + x2 - 2x3 ³ 3, Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1. Двойственная задача. Найти максимум линейной функции f = 2y1 + 3y2 + 6y3 + 3y4 при ограничениях

2y1 - y2 + y3 + 2y4 £ 1, 2y1 + y2 + y3 + y4 ³ 2, -y1+ 4y2 - 2y3 - 2y4 ³ 3, Для решения исходной задачи необходимо ввести четыре дополнительные переменные и после преобразования системы - одну искусственную. Таким образом, исходная симплексная таблица будет состоять из шести строк и девяти столбцов, элементы которых подлежат преобразованию. Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов. Двойственную задачу решаем симплексным методом (табл. 1.3). Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2. Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2. Т а б л и ц а 1.3

i	Базис	С базиса	A0	2				3		6			3		0		0		0
				A1				A2		A3			A4		A5		A6		A7
1 2 3	A5 A3 A7	0 0 0	1 2 3	2 2 -1				-1 1 4		1 1 -2			2 -1 -2		1 0 0		0 1 0		0 0 1
m + 1	Zi - Cj		0	-2				-3		-6			-3		0		0		0
1 2 3	A3 A6 A7	6 0 0	1 1 5	2 0 3				-1 2 6		1 0 0			2 -1 2		1 -1 2		0 1 0		0 0 1
m + 1	Zi - Cj		6		10		-9				0		9		6		0		0
1 2 3	A3 A2 A7	6 3 0	3/2 ½ 2			2 0 3			0 1 0			1 0 0		3/2 -1/2 4		½ -1/2 5		½ ½ 3	0 0 1
m + 1	Zi - Cj		21/2			10			0			0		9/2		3/2		9/2	0

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

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов. Н е с и м м е т р и ч н ы е з а д а ч и (1) Исходная задача Двойственная задача Zmin = CX; fmax = YA0; AX = A0; YA £ С. X ³ 0. (2) Исходная задача Двойственная задача Zmax = CX; fmin = YA0; AX = A0; YA ³ С. X ³ 0. С и м м е т р и ч н ы е з а д а ч и (3) Исходная задача Двойственная задача Zmin = CX; fmax = YA0; AX ³ A0; YA £ С. X ³ 0. Y ³ 0. (4) Исходная задача Двойственная задача Zmax = CX; fmin = YA0; AX £ A0; YA ³ С. X ³ 0. Y ³ 0. Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Запишем, например, математическую модель двойственной задачи для следующей исходной. Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях

x1 – x2 – x3 £ 4, x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3). 2x1 – x2 + 3x3 ³6, Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель должна иметь вид (3). Переход осуществляется умножением первого неравенства на -1. Исходная задача: Zmin = 2x1 + x2 + 5x3 при ограничениях

-x1 + x2 + x3 ³ -4, x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3). 2x1 – x2 + 3x3 ³6, Двойственная задача: fmin = -4x1 + 5x2 + 6x3 при ограничениях

-y1 + y2 + 2y3 £ 2, y1 – 5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3). 2y1 + y2 + 3y3 £ 5, Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

5. Двойственный симплексный метод

В п. 2 и п. 3 настоящего параграфа было показано, что для получения решения исходной задачи можно перейти к двойственной и используя оценки ее оптимального плана, определить оптимальное решение исходной задачи. Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана исходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит название двойственного симплексного метода, Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA £ С. Допустим, что выбран такой базис D = (A1 , А2, ..., Аi, ..., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ..., xi, ..., xm) отрицательная (например, xi < 0), но для всех векторов Aj выполняется соотношение Zj – Cj £ 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными. Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствующий отрицательной оценке,— включить в базис двойственной задачи. Для выбора вектора, включаемого в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q0j= min (xi/xij) ³ 0 и определяем вектор, соответствующий max q0j(Zj — Cj) при решении исходной задачи на минимум и min q0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой. Если q0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за разрешающий элемент только в том случае, если xij > 0. Такой выбор разрешающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X. Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи. В процессе вычислений по алгоритму двойственного симплексного метода условие Z j – Cj £ 0 можно не учитывать до исключения всех х i < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все хi < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j= max (xi/xij) > 0. Двойственным симплексным методом можно решать задачи линейного программирования, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размеры симплексной таблицы.

6. Список используемой литературы

1. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г. 2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

Страницы: 1, 2

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.