Методика решения двойственных задач линейного программирования

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Составить двойственную задачу и найти ее оптимальное решение по теореме равновесия

Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования:

Составьте двойственную задачу и найдите ее оптимальное решение по теореме равновесия.

1.1 Решение двойственной задачи

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

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

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

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

Табл. 1. Расширенная матрица A

1	2	1	1	2
1	?2	2	?2	7
?8	?7	?14	?4

Табл. 2. Транспонированная матрица AT

1	1	?8
2	?2	?7
1	2	?14
1	?2	?4
2	7

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

Неравенства, соединенные стрелочками (-), называются сопряженными.

y1 + y2 ? ?8

2y1 ? 2y2 ? ?7

y1 + 2y2 ? ?14

y1 ? 2y2 ? ?4

2y1 + 7y2 > min

y1 ? 0

y2 ? 0

Табл. 3

Исходная задача I		Двойственная задача II
x1 ? 0	-	y1 + y2 ? ?8
x2 ? 0	-	2y1 ? 2y2 ? ?7
x3 ? 0	-	y1 + 2y2 ? ?14
x4 ? 0	-	y1 ? 2y2 ? ?4
?8x1?7x2?14x3?4x4 > max	-	2y1 + 7y2 > min
x1 + 2x2 + x3 + x4 ? 2	-	y1 ? 0
x1 ? 2x2 + 2x3 ? 2x4 ? 7	-	y2 ? 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Находим оптимальный план двойственной задачи:

Из теоремы двойственности следует, что:

Y = C?A?1.

Оптимальный план двойственной задачи равен:

y1 = 3,5, y2 = 0, Z(Y) = ? 2?3,5 + 7?0 = ?7

1.2 Решение двойственной задачи симплексным методом (с использованием симплексной таблицы)

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

Определим максимальное значение целевой функции:

F(X) = -8x1-7x2-14x3-4x4

при следующих условиях-ограничений.

x1+2x2+x3+x4?2

x1-2x2+2x3-2x4?7

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

В 1-м неравенстве смысла (?) вводим базисную переменную x5 со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x6.

1x1 + 2x2 + 1x3 + 1x4-1x5 + 0x6 = 2

1x1-2x2 + 2x3-2x4 + 0x5 + 1x6 = 7

Введем искусственные переменные x:

в 1-м равенстве вводим переменную x7;

1x1 + 2x2 + 1x3 + 1x4-1x5 + 0x6 + 1x7 = 2

1x1-2x2 + 2x3-2x4 + 0x5 + 1x6 + 0x7 = 7

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = -8x1-7x2-14x3-4x4 - Mx7 > max

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

x7 = 2-x1-2x2-x3-x4+x5

которые подставим в целевую функцию:

F(X) = -8x1-7x2-14x3-4x4 - M(2-x1-2x2-x3-x4+x5) > max

Или:

F(X) = (-8+M)x1+(-7+2M)x2+(-14+M)x3+(-4+M)x4+(-M)x5+(-2M) > max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Табл. 4

1	2	1	1	-1	0	1
1	-2	2	-2	0	1

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

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

Решим систему уравнений относительно базисных переменных: x7, x6ю

Полагая, что свободные переменные равны 0, получим первый опорный план:

X0 = (0,0,0,0,0,7,2)

Базисное решение называется допустимым, если оно неотрицательно.

Табл. 5

Базис	B	x1	x2	x3	x4	x5	x6	x7
x7	2	1	2	1	1	-1	0	1
x6	7	1	-2	2	-2	0	1
F(X0)	-2M	8-M	7-2M	14-M	4-M	M	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация № 0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (2 : 2 , - ) = 1

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

двойственный коэффициент целевой базисный

Табл. 6

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x7	2	1	2	1	1	-1	0	1	1
x6	7	1	-2	2	-2	0	1		-
F(X1)	-2M	8-M	7-2M	14-M	4-M	M	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x7 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

Табл. 7

B	x1	x2	x3	x4	x5	x6	x7
2 : 2	1 : 2	2 : 2	1 : 2	1 : 2	-1 : 2	0 : 2	1 : 2
7-(2 * -2):2	1-(1 * -2):2	-2-(2 * -2):2	2-(1 * -2):2	-2-(1 * -2):2	0-(-1 * -2):2	1-(0 * -2):2	0-(1 * -2):2
(0)-(2 * (7-2M)):2	(8-M)-(1 * (7-2M)):2	(7-2M)-(2 * (7-2M)):2	(14-M)-(1 * (7-2M)):2	(4-M)-(1 * (7-2M)):2	(M)-(-1 * (7-2M)):2	(0)-(0 * (7-2M)):2	(0)-(1 * (7-2M)):2

Получаем новую симплекс-таблицу:

Табл. 8

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	1	1/2	1	1/2	1/2	-1/2	0	1/2
x6	9	2	0	3	-1	-1	1	1
F(X1)	-7	41/2	0	101/2	1/2	31/2	0	-31/2+M

Проверка критерия оптимальности

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Табл. 9

Базис	B	x1	x2	x3	x4	x5	x6	x7
x2	1	1/2	1	1/2	1/2	-1/2	0	1/2
x6	9	2	0	3	-1	-1	1	1
F(X2)	-7	41/2	0	101/2	1/2	31/2	0	-31/2+M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x1 = 0, x2 = 1, x3 = 0, x4 = 0

F(X) = -8*0 -7*1 -14*0 -4*0 = -7

Анализ оптимального плана

В оптимальный план вошла дополнительная переменная x6.

Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 9.

Значение 41/2> 0 в столбце x1 означает, что использование x1 ? не выгодно.

Значение 0 в столбце x2 означает, что использование x2 ? выгодно.

Значение 101/2> 0 в столбце x3 означает, что использование x3 ? не выгодно.

Значение 1/2> 0 в столбце x4 означает, что использование x4 ? не выгодно.

Значение 31/2 в столбце x5 означает, что теневая цена (двойственная оценка) равна y1=31/2.

1.3 Проверка решения двойственной задачи табличным Симплекс-методом

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

-1X1-2X2-1X3-1X4+X5=-2

1X1-2X2+2X3-2X4+X6=7

-1X1+0X2+0X3+0X4+X7=0

0X1-1X2+0X3+0X4+X8=0

0X1+0X2-1X3+0X4+X9=0

0X1+0X2+0X3-1X4+X10=0

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком.

Из данных задачи составляем исходную симплекс таблицу.

Табл. 10

	X1	X2	X3	X4	Своб член
F	8	7	14	4	0
X5	-1	-2	-1	-1	-2
X6	1	-2	2	-2	7
X7	-1	0	0	0	0
X8	0	-1	0	0	0
X9	0	0	-1	0	0
X10	0	0	0	-1	0

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -2, он задает ведущую строку - X5. В этой строке так же находим максимальный по модулю отрицательный элемент: -2 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

Табл. 11

	X1	X5	X3	X4	Своб член
F	4.5	3.5	10.5	0.5	-7
X2	0.5	-0.5	0.5	0.5	1
X6	2	-1	3	-1	9
X7	-1	0	0	0	0
X8	0.5	-0.5	0.5	0.5	1
X9	0	0	-1	0	0
X10	0	0	0	-1	0

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение:

F = ? 7

при значениях переменных, равных:

X2 = 1, X3=X4=X1=0.

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

2.1 Математическая модель задачи нелинейного программирования (ЗНП)

(*)

Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода решения. В зависимости от вида целевой функции и системы ограничений (*) разработаны специальные методы решения, например, метод множителей Лагранжа для ЗНП с системой ограничений, состоящей только из уравнений, и при условии, что все функции в (*) имеют непрерывные частные производные.

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

ЗНП с двумя переменными может быть решена графически.

Графическое решение задачи может быть разбито на следующие части:

1. В прямоугольной системе координат Х1OX2 определяется область решений системы (*).

2. Определяется тип линий уровня целевой функции Z(x1, x2) = c.

3. Находится линия уровня целевой функции с наибольшим (или наименьшим) значением уровня или устанавливается неразрешимость задачи из-за неограниченности функции на множестве решений системы (*).

4. Определяются координаты точки области решений системы (*), через которую проходит линия уровня, найденная в пункте 3.

2.2 Графическое решение задачи нелинейного программирования

Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую интерпретацию.

Так как то линиями уровня функции Z являются окружности разных радиусов с центром в точке C(6; 2), а областью допустимых решений задачи - область, ограниченная прямыми:

L1:2 • x1 + 5 • x2 = 30 x1?x, x2?y, > y = ? (2/5) ? x + 6

L2:2 • x1 + x2 = 14 x1?x, x2?y, > y = ? 2 ?x + 14

x1, x2 ? 0

Z(x1, x2) = (x1 ? 6 )2 + (x2 ? 2)2 > min

(Используя систему ограничений и условие не отрицательности, построили Область Допустимых Решений (ОДР), для чего в системе (*) знаки неравенств заменили на знаки равенств).

В результате получим уравнения прямых, которые построим по точкам в системе координат Х1ОХ2. Так как у нас две переменные, то геометрически неравенства будут изображаться полуплоскостями, а их границы - прямыми линиями. При этом x1 ? 0, x2, ? 0, т.е. все решения будут располагаться в I-й четверти.

Z(x1, x2) = (x1 ? 6 )2 + (x2 ? 2)2 > min

x1 ? x, x2 ? yZ(x1, x2) ? Z(x;y) = (x ? 6 )2 + (y ? 2)2 > min

Итак, условия ограничения определили четырехугольник, координаты точке которого являются неотрицательными решениями системы (*).

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

Если проводить эти окружности из точки C, то легко видеть, что минимальное значение функция Z принимает в точке C (когда окружность вырождается в точку): пересечения центра окружности с прямой L2: C(6; 2):

Рис. 1

Рис. 2

Графическое решение:

ZMIN = Z (6; 2) = (x ? 6 )2 + (y ? 2)2 = (6 ? 6 )2 + (2 ? 2)2 = 0 + 0 = 0

2.3 Проверка: Исследование функции на экстремум

Исследуем на экстремум функцию:

1. С помощью необходимого существования экстремума, т.е. из системы

Найдем координаты стационарных (критических) точек:



2. Проверим выполнение достаточного условия существования экстремума в стационарной точке. Для этого составим:

2. Решим вопрос о характере экстремума.

· точка M0 (x,y) будет точкой максимума, если A (M0) < 0 (или C (M0) < 0), и точкой минимума, если A (M0) > 0 (или C (M0) > 0);

· если то в точке М0 экстремума нет (достаточные условия наличия или отсутствия экстремума);

· если то требуется дальнейшее исследование (сомнительный случай).

В данном случае получили:

В точке М0 экстремум есть, причем точка М0 является точкой минимума:

Размещено на Allbest.ru