ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Пример решения задачи симплекс-методом

Симплекс-метод

Симплекс-метод является основным численным методом решения задач ЛП в канонической форме, т.е. в виде

Систему линейных уравнений можно записать в виде:

, (4.3)

где

, , …, — столбцы матрицы системы ограничений, — столбец свободных членов системы.

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

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

Теорема 2 (признак оптимальности опорного плана). Опорный план является оптимальным планом задачи (2.8), если относительные оценки

. (4.4)

При этом называют относительной оценкой замещения переменной ; — вектор коэффициентов целевой функции при базисных переменных , , …, т.е. ; — столбец матрицы ограничений при переменной ; — коэффициент при переменной в целевой функции.

Теорема 3 (признак неограниченности целевой функции). Если для некоторого номера и среди чисел — элементов столбца — нет положительных (т.е. все ), то целевая функция задачи (2.8) не ограничена на множестве её планов.

Теорема 4 (о возможности улучшения опорного плана). Если опорный план задачи (2.8) невырожден и некоторое , но среди чисел есть положительные (не все ), то существует опорный план такой, что .

Переход от одного опорного плана к новому опорному плану осуществляется исключением из числа базисных переменных , , …, одной из этих переменных и введением в число базисных одной из независимых переменных , …, по следующей схеме (схема 1):

1) выбирают разрешающий столбец , соответствующий отрицательному значению , ; переменная будет включена в число базисных переменных;

2) выбирают разрешающую строку, соответствующую наименьшему отношению элементов столбца свободных членов системы ограничений к соответствующим положительным элементам разрешающего столбца —

где минимум берется по всем номерам таким, что (по множеству ); переменная должна быть исключена из числа базисных переменных.

Затем систему ограничений преобразуют по схеме Жордана–Гаусса. Все вычисления записывают в таблицах, которые называют симплексными таблицами и составляют их следующим образом.

Пусть линейно независимы первые столбцов матрицы , , …, — базисные столбцы, и система преобразована так, что эти столбцы единичные, т.е.

, , …, , , .

Тогда симплекс-таблица имеет вид:

Слева в таблице указаны базисные переменные , , …, и вектор из коэффициентов целевой функции при базисных переменных, вверху — небазисные переменные , , …, ; соответствующие этим переменным коэффициенты целевой функции , , …, и столбцы , , …, матрицы ограничений , справа — столбец свободных членов и внизу — строка с обозначением « », в которой записаны значения относительных оценок небазисных переменных, вычисленные по формуле (4.4), и значение целевой функции , вычисленное на первом опорном плане .

Пример решения задачи симплекс-методом

Проиллюстрируем решение задачи ЛП симплекс-методом на примере решения задачи (4.1)–(4.2), ранее решенной геометрически.

Задачу (4.1)–(4.2) запишем в каноническом виде, введя три дополнительные переменные , , и заменив неравенства равенствами:

(4.5)

Пара двойственных задач

Парой (симметричных) взаимно двойственных задач называются задачи

f (x) = (c, x) → max, g (y) = (b^Т, y) → min,

Ax b, (4.10)

A^Ty c^Т, (4.11)

x 0, y 0,

где с, x R_n ; y, b R_m, i=( ), j =( ).

Задачи (4.10) и (4.11) взаимно двойственны, т.е. если прямая задача является задачей максимизации и все неравенства вида « », то двойственная — задача минимизации и ограничения неравенства « » и наоборот.

Если задача ЛП сформулирована в канонической форме:

f (x) = (c, x) → max,

Ax=b, (4.12)

x 0,

то двойственная к ней задача имеет вид:

g (y) = (b^T, y) → min,

A^Ty c^T, (4.13)

и наоборот.

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

Теорема 5. (Первая теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е. f (x^*) = g (y^*). Если же целевая функция одной из пары двойственных задач не ограничена, то другая задача вообще не имеет допустимых планов.

Теорема 6. (Вторая теорема двойственности). Для того, чтобы допустимые планы x^*, y^* прямой (4.10) и двойственной (4.11) задач были оптимальными, необходимо и достаточно, чтобы выполнялись условия:

(4.14)

т.е.

если х^*_j > 0, то , если y^*_i > 0, то ( ),

если , то y^*_i=0 ( ), если то x^*_j=0 .

Следовательно, если в оптимальном плане х^* какая-либо компонента x^*_j > 0, то соответствующее ей j-ое ограничение двойственной задачи на её оптимальном плане y^* обращается в равенство; если оптимальный план х^* обращает i-ое ограничение этой задачи в строгое неравенство, то соответствующая ему компонента y^*_i в оптимальном плане двойственной задачи равна нулю.

Задача 3. Дана задача ЛП:

f (x)=6x₁+11x₂+5x₃+x₄→ min, (4.15)

(4.16)

Требуется:

- сформулировать двойственную задачу к задаче (4.15)-(4.16);

- решить двойственную задачу геометрически и симплекс-методом;

- найти оптимальное решение прямой задачи (4.15)–(4.16), используя теоремы двойственности.

Сформулируем задачу, двойственную к задаче (4.15)–(4.16).

Прямая задача:

f (x)=(c,x)=6x₁+11x₂+5x₃+x₄→ min,

x_j .

Двойственная задача, по определению, будет иметь вид:

g (y) = (b^Т, y)=3y₁+7y₂ →max,

y₁ 0, y₂ 0.

Окончательно, в скалярной форме, задача, двойственная к задаче (4.15)–(4.16), имеет вид:

g (y) = (b^Т, y)=3y₁+7y₂ →max,

(4.17)

Полученная задача имеет две переменные y₁, y₂ , поэтому можно найти её решение геометрически (рис. 3).

Рис. 3

Множество R — пятиугольник OABCD. Строим линии уровня целевой функции

g(y)=3y₁+7y₂ = const

и перемещаем их в направлении вектора grad g(y)=(3;7). Оптимальной вершиной является точка С, координаты которой определим из решения

системы уравнений:

→ C (5;2).

Итак, y^*₁=5; y^*₂=2; max g (y) = g(y^*) = 3·5+7·2 = 29.

Зная оптимальный план двойственной задачи, найдём оптимальный план исходной задачи x^*, используя теоремы двойственности.

По теореме 5 можно утверждать, что прямая задача (4.15) – (4.16) имеет оптимальный план x^*, на котором целевая функция принимает значение f(x^*)=g(y^*)=29. Сам оптимальный план x^* получим из условия (4.14) теоремы 6. Так как y^*=(5;2) имеет две положительных компоненты, то соответствующие им ограничения прямой задачи (4.16) на оптимальном плане x^*=(x^*₁, x^*₂, x^*₃, x^*₄) обращаются в равенства:

(4.18)

При этом x^*₁=0 и x^*₄=0, так как первое и четвёртое ограничения системы (4.17) на плане y^* обращаются в строгие неравенства.

Система уравнений

имеет решение х^*₂ =18/7, х^*₃ =1/7. Следовательно, оптимальный план исходной задачи х^* = (0; 18/7; 1/7; 0); на нём целевая функция принимает значение

f(x^*)= g(y^*).

Решим теперь задачу (4.17) симплекс-методом. Для этого запишем её в канонической форме, введя дополнительные переменные :

g (y)=3y₁+7y₂ →max,

Составим с.-т.: Симплекс – таблица 3.1


	y₁	y₂
y₃	-3 -1	-5 -3	=
y₄	=
y₅	=
y₆	=
	-3	-7

Первый опорный план у¹ = (0; 0; 6; 11; 5; 1), g (y¹) = 0. По стандартной схеме (см. пример 1) выбираем разрешающий столбец первый, разрешающую строку – третью, разрешающий элемент и проводим один шаг жордановых преобразований.

Симплекс – таблица 3.2


		y₅	y₂
	y₃		-1	=
	y₄			=
	y₁			=
y₆			=
			-12	=

Второй опорный план y²=( ;0;11; ;0; ), g(y²)=5. План не оптимальный, так как имеется отрицательный коэффициент в строке . Второй столбец — разрешающий, вторая строка — разрешающая.

Третий опорный план у³ = (5; 2; 13; 0; 0; 12) является оптимальным, коэффициенты -строки положительны. Отбрасывая дополнительные переменные, получаем оптимальный план задачи

y^* = (5;2), max g(y) = g(y^*) = 29.

Симплекс – таблица 3.3


		y₅	y₄
	y₃			=
	y₂			=
	y₁			=
y₆			=
				=

Оптимальный план х^* задачи (4.15)–(4.16) определим, используя последнюю с.-т. 3.3. Воспользуемся формулой для вычисления относительных оценок через оптимальный план двойственной задачи, вытекающей из теоремы 6:

. (4.20)

При этом, если y^*_j — базисная переменная, т.е. y^*_j > 0, то , иначе находится в -строке табл. 3.3. Матрица ограничений задачи (4.19) содержит четыре единичных столбца A₃, A₄, A₅, A₆, поэтому

Условия (4.20) примут вид: , .

Имеем