a_i1x₁ +…+a_inx_n b_i, i = i,k,

a_i1x₁ +…+a_inx_n b_i, i = i,k,

a_i1x₁ +…+a_inx_n b_i, i = i,k.

Cреди ограничений часто встречаются условия не отрицательности всех или части переменных

x_j 0, j=1, 2, …,S.

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

В более компактной записи общая задача линейного программирования имеет вид: при ограничениях

где a_ij, b_i, c_j - заданные постоянные величины.

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

Различаются еще две основные формы задач линейного программирования в зависимости от наличия ограничений разного типа:

стандартная форма ЗЛП

при ограничениях

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

каноническая форма ЗЛП

при ограничениях

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

Стандартная форма ЗЛП интересна тем, что большое число прикладных задач естественным образом сводится к этому виду моделей. Каноническая форма ЗЛП важна ввиду того, что основные вычислительные методы решения ЗЛП разработаны именно для этой формы. Указанные выше три формы ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть приведена к любой из двух остальных. Транспортная задача является одной из самых распространённых ЗЛП специального вида.

Нелинейное программирование:

i=1…k

i=k+1…m

j=1…S

В отличие от линейного программирования, в нелинейном есть локальный max

60. Модификации метода Ньютона

Значительные трудности, возникающие при практической реализации метода Ньютона, связаны с необходимостью вычислить матрицу f ''(x). Мы рассмотрим две модификации метода Ньютона, которые используют не точные значения, а некоторые приближённые аналоги матрицы вторых производных. В результате уменьшается трудоёмкость методов, но, конечно, ухудшается их сходимость.

В качестве первой модификации метода Ньютона рассмотрим следующий алгоритм: x_k+1 = x_k - _k(f ''(x_k)) ^-1·f '(x_k), _k ? 0.(8) здесь для построения направления спуска используется один раз вычисленная и обращённая матрица вторых производных f ''(x₀).

Схема модификации I метода Ньютона.

Шаг 1. При k = 0, вводятся x₀, е₃. Вычисляются f '(x₀) и f ''(x₀).

Шаг 2. Определение обратной матрицы (f ''(x₀))-¹.

Шаг 3. Определение направления спуска p_k:

p_k = - f '(x_k)·(f ''(x₀))-¹.

Шаг 4. Определение следующей точки: x_k+1 = x_k + ·p_k,

где - решение задачи одномерной минимизации функции: ц() = f(x_k + ·p_k), при ? 0.

Шаг 5. Вычисление в точке x_k+1.градиента f '(x_k+1).

Шаг 6. Если ||f '(x_k+1)|| е₃, то поиск заканчивается и полагается и .

Иначе k = k + 1 и переход к шагу 3.

В рассмотренной схеме для выбора шага _k используется способ аналогичный исп-му в методе наискорейшего спуска. Но можно было бы воспользоваться и способом аналогичным используемому в градиентном методе с дроблением шага.

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

Другая модификация метода Ньютона связана с обновлением матрицы вторых производных через определённое количество шагов. Формула вычисления очередной точки x_k+1, в этом случае, будет выглядеть следующим образом:

X_jm+i+1 = x_jm+i - _jm+i· (f ''(x_jm)) ^-1·f '(x_jm+i),

_jm+i ? 0, k = jm + i, j = 0, 1, 2, …, i = 0, 1, …, m -1.

Здесь m > 0 - целое число, определяющее количество шагов через которое происходит обновление матрицы вторых производных f ''(x). Этот метод занимает промежуточное положение между методом Ньютона и его модификацией I.

Схема модификации II метода Ньютона.

Шаг 1. Вводятся x₀, е₃, m. Присваиваются j = 0 и k = 0. Вычисляется градиент f '(x₀).

Шаг 2. Вычисляется (обновляется) матрица f ''(x_jm) и обратная матрица (f ''(x_jm))-¹.

Шаг 3. Определение направления спуска p_jm+1:

p_jm+1 = - f '(x_jm+1)·(f ''(x_jm))-¹.

Шаг 4. Определение очередной точки x_jm+i+1:

x_jm+i+1 = x_jm+i + ·p_jm+i, где - решение задачи одномерной минимизации функции:

ц() = f(x_jm+i + ·p_jm+i), при ? 0.

Шаг 5. Вычисление в очередной точке x_jm+i+1.градиента f '(x_jm+i+1).

Шаг 6. Если ||f '(x_jm+i+1)|| е₃, то поиск заканчивается и полагается и .

Иначе k = k + 1 и переход к шагу 7.

Шаг 7. Определяется i = i + 1.

Если i = m, то j = j + 1, i = 0 и переход к шагу 2 (т.е. будем обновлять матрицу f ''(x)).

Иначе переход к шагу 3 (т.е. используется матрица

f ''(x), вычисленная на одном из предыдущих шагов).

62. Переход от общей ЗЛП к стандартной и канонической

Общий вид:

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

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

a_i1x₁ +a_i2x₂+…+a_inx_n b_i

можно заменить следующим:

(-a_i1) x₁ +(-a_i2)+…+(-a_in)x_n (-b_i)

Переход от от общей к канонической. Любое ограничение в форме неравенства введением дополнительной неотрицательной переменной может превратиться в ограничение - равенство. Так, к примеру, условие

a_i1x₁ +a_i2x₂+…+a_inx_n b_i

эквивалентно двум ограничениям

a_i1x₁ +a_i2x₂+…+a_inx_n+x_n+1= b_i, x_n+10.

Переменные типа x_n+1 называют фиктивными или дополнительными

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

x_j = x^'_j - x^"_j, x^'_j 0, x^"_j 0.

63. Переход от стандартной форме к канонической и обратно каноническая:

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

j=1..n

стандартная:

Любое ограничение в форме неравенства введением дополнительной неотрицательной переменной может превратиться в ограничение - равенство. Так, к примеру, условие a_i1x₁ +a_i2x₂+…+a_inx_n b_i эквивалентно двум ограничениям a_i1x₁ +a_i2x₂+…+a_inx_n+x_n+1= b_i, x_n+10.

Переменные типа x_n+1 называют фиктивными или дополнительными.

Обратно:

Ограничение a_i1x₁ +a_i2x₂+…+a_inx_n = b_i

можно представить парой ограничений a_i1x₁ +a_i2x₂+…+a_inx_n b_i

(-a_i1) x₁ +(-a_i2)+…+(-a_in)x_n (-b_i)

64. Геометрическое решение ЗЛП в стандартной форме

Если задача линейного программирования в стандартной форме содержит всего лишь две переменные x₁ и x₂ (т.е. n=2), то ее можно решить следующим способом, основанным на ее геометрической интерпретации.

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

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

Для решения задачи линия уровня сдвигается в пределах области допустимых решений (многогранника допустимых решений) в направлении вектора-градиента

grad z = f(x) = до самой крайней точки области для задачи максимизации, и в направлении антиградиента

- grad z= для задачи минимизации. Координаты этой точки и определяют решение ЗЛП (оптимальный план задачи).

Рис1. Геометрическая интерпретация ЗЛП в стандартной форме



Рис.2 Пример пустой области допустимых решений (X)

Рис.3 Пример ЗЛП, имеющий бесконечное множество решений (ребро АВ многогранника допустимых решений ABCDE)

65. Теорема о выпуклости множества допустимых решений ЗЛП(стандартной и канонической форм)

Д-во: 1) для канон-й формы: Есть точки x⁽¹⁾, x⁽²⁾. x⁽¹⁾ОДР, x⁽²⁾ОДР. Возьмем точку, принадлежащую отрезку: x[ x⁽¹⁾, x⁽⁰⁾]ОДР. Существуют два таких числа, что x выр-ся через значения концов этих отрезков =. . . (по всем координатам). x0(доказали, что x явл допустимым решением). AX=A()===()B=B. Ax=B(x-явл-ся решением)

2) для стандартной формы

A x⁽¹⁾?B, A x⁽²⁾?B. Ax= A()=?=()B=B. Ax?B

66. Теорема о глобальности экстремума ЗЛП

67. Теорема о том, что экстремум ЗЛП может находиться только на границе множества допустимых решений.

Т-ма: если существует экстремум целевой функции задачи линейного прогр-я, тогда: 1) этот экстремум всегда является глобальным. Док (док-во относит min) Пусть в точке x^* достигается локальный min. Сущ-т окр-ть т. x^* U_е (x^*)ОДР. f(x)?f(x^*). Д.б. точка x⁽⁰⁾, в которой f(x⁽⁰⁾)<f(x^*). В силу 1 Th все точки окр-ти? явл-ся допустимым реш-м.

2)экстремум достигается в граничной точке. Док: Докажем, что экстремум задачи, если он есть, достигается в граничной точке. , что . Градиент целевой функции: (частные произв-е по всем переменным): ; z^/={c₁, c₂…c_n }

во внутр-х точках экстремума нету(т.к. по теореме градиент д.б. =0)

x[ x⁽²⁾, x^(*)]; x=; . .

Значение целевой функции в этой точке: = ==, где ) f(x)<f(x^*).

Это противоречиенаше предположение неверно.

68. Угловая точка множества

x^*-угловая точка множества А(крайняя точка). Не сущ-т таких 2-х точек, чтобы на отрезке их соединяющем нах-сь вершина. и и ,

69. Т-ма о наличии среди оптимальных решений ЗЛП угловых точек множества допустимых решений

Множество оптимальных решений ЗЛП (если оно не пусто) всегда содержит угл-ю точку. Частный сл: если решение единственно, то это и есть угл-я точка. Док: x^*-реш-е задачи, нужно доказать, что она угловая. Предположим, что она не угловая. Т.е. x⁽¹⁾, x⁽²⁾ОДР и x^* нах-ся на отрезке, их соединяющем. x^* [ x⁽¹⁾, x⁽⁰⁾] (это означает, что x^* не явл-ся угл точкой). f(x⁽¹⁾)>f(x^*).

f(x⁽⁰⁾>f(x^*). (знак > т.к. решение единственно). x^* =; (существуют такие что точка нах-ся на отрезке).

. .

>

=

нет такого отрезка, концы которого ОДР и эта точка лежит на этом отрезке. ). x^*-явл-ся угловой точкой ОДР.

70. Общее представление допустимых решений ЗЛП канонической формы

Идея симплекс-метода относительно проста. Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n - m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных x₁, x₂, … x_k, а остальные m выражены через них:

x_k+1 = a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,kx_k + b_k+1

x_k+2 = a_k+2,1x₁ + a_k+2,2x₂ + … + a_k+2,kx_k + b_k+2

… (1)

x_n = a_n,1x₁ + a_n,2x₂ + … + a_n,kx_k + b_n

Если положить все свободные переменные x₁, x₂, … x_k равными нулю, то мы получим решение:

x₁ = 0, x₂ = 0, … x_k = 0, x_k+1 = b_k+1, x_k+2 = b_k+2, …, x_n = b_n,

которое называется базисным. Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены b_k+1, b_k+2, …, b_n неотрицательны. Если это условие выполняется, то полученное решение называется допустимым базисным решением или опорным решением. Допустимое базисное решение соответствует одной из угловых точек ОДР (вершин ОДР).

71. Базисное решение ЗЛП

Идея симплекс-метода относительно проста. Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n - m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных x₁, x₂, … x_k, а остальные m выражены через них:

x_k+1 = a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,kx_k + b_k+1

x_k+2 = a_k+2,1x₁ + a_k+2,2x₂ + … + a_k+2,kx_k + b_k+2

… (1)

x_n = a_n,1x₁ + a_n,2x₂ + … + a_n,kx_k + b_n

Если положить все свободные переменные x₁, x₂, … x_k равными нулю, то мы получим решение:

x₁ = 0, x₂ = 0, … x_k = 0, x_k+1 = b_k+1, x_k+2 = b_k+2, …, x_n = b_n,

которое называется базисным. Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены b_k+1, b_k+2, …, b_n неотрицательны. Если это условие выполняется, то полученное решение называется допустимым базисным решением или опорным решением.

72. Связь базисных точек с угловыми точками множества допустимых решений

76. Поиск исходного допустимого базисного решения

78. Вырожденное допустимое базисное решение и проблемы, связанные с ним

Идея симплекс-метода относительно проста. Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n - m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных x₁, x₂, … x_k, а остальные m выражены через них:

x_k+1 = a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,kx_k + b_k+1

x_k+2 = a_k+2,1x₁ + a_k+2,2x₂ + … + a_k+2,kx_k + b_k+2

… (1)

x_n = a_n,1x₁ + a_n,2x₂ + … + a_n,kx_k + b_n

Если положить все свободные переменные x₁, x₂, … x_k равными нулю, то мы получим решение:

x₁ = 0, x₂ = 0, … x_k = 0, x_k+1 = b_k+1, x_k+2 = b_k+2, …, x_n = b_n,

которое называется базисным. Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены b_k+1, b_k+2, …, b_n неотрицательны. Если это условие выполняется, то полученное решение называется допустимым базисным решением или опорным решением. Допустимое базисное решение соответствует одной из угловых точек ОДР (вершин ОДР).

73. Выражение целевой функции через свободные переменные

74. Критерий оптимальности

Выразим целевую функцию z = c1x1 + c2x2 + … + cnxn, (2), которую требуется минимизировать, через свободные переменные x1, x2, … xk: z = d0 + d1x1 + … + dkxk, (3)

Для этого надо в (2) подставить (1), выражение базисных переменных через свободные и привести подобные члены. Очевидно, что при x₁ = 0, x₂ = 0, … x_k = 0 z = d₀, т.е. d₀ - это значение целевой функции при допустимом базисном решении. Посмотрим, не можем ли мы улучшить решение, т.е. уменьшить целевую функцию z, увеличивая какие-нибудь из переменных x₁, x₂, … x_k (уменьшать их мы не можем, т.к. все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты d₁, d₂, … d_k в формуле (3) положительны, то, увеличивая какие-то из переменных x₁, x₂, … x_k сверх нуля, мы не сможем уменьшить целевую функцию z; следовательно, найденное нами допустимое базисное решение является оптимальным. Если же среди коэффициентов d₁, d₂, … d_k в формуле (3) есть отрицательные, то, увеличивая некоторые из переменных x₁, x₂, … x_k, а именно - те, коэффициенты при которых отрицательны, мы можем улучшить решение, т.е. уменьшить z.

Пусть, например, коэффициент d₁ в формуле (3) отрицателен. Значит, есть смысл увеличить х₁, т.е. перейти от данного допустимого базисного решения (опорного решения) к другому, где переменная х₁ не равна нулю, а вместо нее равна нулю какая-то другая, т.е. перейти от одной вершины ОДР к другой вершине. Увеличение х₁ “полезно” для целевой функции z, делает меньше. Однако увеличивать х₁ надо осторожно, так чтобы не стали отрицательными другие переменные x_k+1, x_k+2, …, x_n, выраженные через свободные переменные, в частности, через х₁ формулами (1). Так как остальные свободные переменные x₂, … x_k остаются равными нулю, то изменения базисных переменных x_k+1, x_k+2, …, x_n от увеличения х₁ выражаются формулами:

x_k+1 = a_k+1,1x₁ + b₁

x_k+2 = a_k+2,1x₁ + b₂

… (4)

x_n = a_n,1 x₁ + b_n

75. Симплекс-алгоритм

Схема алгоритма

Шаг 1. Построение начального симплекса.

Для этого задаются начальная точка х₀(0) и длина ребра симплекса l. Формируются остальные вершины симплекса: x_i(0) = x₀(0) + l*e_i (i=1,2,…,n), где e_i - единичные векторы.

Шаг 2. Определение направления улучшения решения.

Для этого на к-й итерации вычисляются значения целевой функции в каждой точке симплекса. Пусть для всех i: f(x_min(k))f(x_i(k))f(x_max(k)), где min, max, i - номера соответствующих вершин симплекса. Опр-м центр тяжести всех точек, исключая точку x_max(k), C_k=(x_i(k))/n. Тогда направление улучшения решения опр-ся вектором C_k-x_max(k).

Шаг 3. Построение отраженной точки.

Замена вершины x_max(k) с максимальным значением целевой функции на новую точку с помощью операции отражения, результатом которой является новая точка:

u_k=c_k+(c_k-x_max(k))=2c_k-x_max(k)

Шаг 4. Построение нового симплекса.

Вычисляем f(u_k). При этом возможен один из двух случаев:

а) f(u_k)<f(x_max(k); б) f(u_k)f(x_max(k).

Случай а): вершина x_max заменяется на u_k, чем определяется набор вершин к+1-й итерации и к-я итерация заканчивается.

Случай б): в результате отражения получается новая точка u_k, значение функции в которой еще хуже, чем в точке x_max, то есть отражать симплекс некуда. Поэтому в этом случае производится пропорциональное уменьшение симплекса (например, в 2 раза) в сторону вершины x_min(k): x_i(k+1)=x^{^}_i=(x_i(k)+x_min(k))/2, где i=0,1,…,n. На этом к-я итерация заканчивается.

Шаг 5. Проверка сходимости.

Если то поиск минимума заканчивается и полагается

В противном случае к=к+1 и происходит переход к шагу 2.

77. Симлекс-метод

Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n - m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных x₁, x₂, … x_k, а остальные m выражены через них:

x_k+1 = a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,kx_k + b_k+1

x_k+2 = a_k+2,1x₁ + a_k+2,2x₂ + … + a_k+2,kx_k + b_k+2

… (1)

x_n = a_n,1x₁ + a_n,2x₂ + … + a_n,kx_k + b_n

Если положить все свободные переменные x₁, x₂, … x_k равными нулю, то мы получим решение:

x₁ = 0, x₂ = 0, … x_k = 0, x_k+1 = b_k+1, x_k+2 = b_k+2, …, x_n = b_n,

которое называется базисным. Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены b_k+1, b_k+2, …, b_n неотрицательны. Если это условие выполняется, то полученное решение называется допустимым базисным решением или опорным решением. Допустимое базисное решение соответствует одной из угловых точек ОДР (вершин ОДР). Предположим, что условие не отрицательности свободных членов выполнено. Тогда мы имеем допустимое базисное решение, но является ли оно оптимальным?

Чтобы проверить это, выразим целевую функцию

z = c₁x₁ + c₂x₂ + … + c_nx_n, (2)

которую требуется минимизировать, через свободные переменные x₁, x₂, … x_k:

z = d₀ + d₁x₁ + … + d_kx_k, (3)

Для этого надо в (2) подставить (1), выражение базисных переменных через свободные и привести подобные члены. Очевидно, что при x₁ = 0, x₂ = 0, … x_k = 0 z = d₀, т.е. d₀ - это значение целевой функции при допустимом базисном решении. Посмотрим, не можем ли мы улучшить решение, т.е. уменьшить целевую функцию z, увеличивая какие-нибудь из переменных x₁, x₂, … x_k (уменьшать их мы не можем, т.к. все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты d₁, d₂, … d_k в формуле (3) положительны, то, увеличивая какие-то из переменных x₁, x₂, … x_k сверх нуля, мы не сможем уменьшить целевую функцию z; следовательно, найденное нами допустимое базисное решение является оптимальным. Если же среди коэффициентов d₁, d₂, … d_k в формуле (3) есть отрицательные, то, увеличивая некоторые из переменных x₁, x₂, … x_k, а именно - те, коэффициенты при которых отрицательны, мы можем улучшить решение, т.е. уменьшить z.

Пусть, например, коэффициент d₁ в формуле (3) отрицателен. Значит, есть смысл увеличить х₁, т.е. перейти от данного допустимого базисного решения (опорного решения) к другому, где переменная х₁ не равна нулю, а вместо нее равна нулю какая-то другая, т.е. перейти от одной вершины ОДР к другой вершине. Увеличение х₁ “полезно” для целевой функции z, делает меньше.

Однако увеличивать х₁ надо осторожно, так чтобы не стали отрицательными другие переменные x_k+1, x_k+2, …, x_n, выраженные через свободные переменные, в частности, через х₁ формулами (1). Так как остальные свободные переменные x₂, … x_k остаются равными нулю, то изменения базисных переменных x_k+1, x_k+2, …, x_n от увеличения х₁ выражаются формулами:

x_k+1 = a_k+1,1x₁ + b₁

x_k+2 = a_k+2,1x₁ + b₂

… (4)

x_n = a_n,1 x₁ + b_n

Посмотрим, опасно ли для переменных xk+1, xk+2, …, xn увеличение х1, т.е. может ли оно делать их отрицательными? Да, опасно, если коэффициент при х1 в соответствующем уравнении отрицателен. Если среди уравнений (4) нет уравнения с отрицательным коэффициентом при х1, то величину х1 можно увеличивать беспредельно, а, значит, целевая функция z не ограничена снизу и оптимального решения задачи ЛП не существует.

Допустим, что это не так и что среди уравнений (4) есть такие, в которых коэффициент при х1 отрицателен. Для переменных, стоящих в левых частях уравнений, увеличение х1 опасно - оно может сделать их отрицательными. Возьмем одну из таких переменных хl и посмотрим, до какой степени можно все же увеличить х1, пока переменная хl не станет отрицательной? Выпишем l-ое уравнение из системы (4) xl = al,1x1 + bl

Здесь свободный член b_l >= 0, а коэффициент a_l,1 отрицателен. Легко понять, что мы можем увеличивать х₁ только до значения, равного - b_l / a_l,1, а при дальнейшем увеличении х₁ переменная х_l станет отрицательной.

Выберем ту из переменных x_k+1, x_k+2, …, x_n, которая раньше всех обратиться в нуль при увеличении х₁, т.е. ту, для которой величина - b_l / a_l,1 меньше всего. Пусть этой переменной будет х_r. Тогда имеет смысл “пере разрешить” систему уравнений (1) относительно базисных переменных, выведя из числа свободных переменных х₁ и переведя вместо нее в группу свободных переменных х_r. Действительно, мы хотим перейти от допустимого базисного решения, задаваемого равенствами x₁ = 0, x₂ = 0, … x_k = 0, к допустимому базисному решению, в котором уже x₁ <> 0, а x₂ = 0, … x_k = 0,х_r = 0. Первое допустимое базисное решение мы получили, если обратим в нуль все новые свободные переменные x₁, x₂, … x_k ; второе мы получим, если обратим в нуль прежние переменные x₂, … x_k, х_r. Базисными переменными при этом будут x₁,x_k+1, …,х_r-1, х_r+1, …, х_n.

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

79. Взаимно-двойственные ЗЛП

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

max

x_j0_, i=1...m; j=1..n

Двойственная:

min

y_j0_, i=1...m

постановка 1-й задачи в матричном виде:

z=(c, x) max

Ax A^тYc

x Y0

a₁₁y₁+a₂₁y₂+…a_m1y_mc₁

a₁₂y₁+a₂₂y₂+…a_m2y_mc₂ a_1my₁+a_2ny₂+…a_mny_mc_n

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

допустимые решения первой и второй задачи:

;

=

Следствие 1 Th1: если x^*-{ x₁^*.. x_n^* }, y^*-{ y₁^*.. y_n^* } ( допустимые решения первой и второй задачи), z^*=f₁(x^*)=f₂(y^*)= (если имеется такое второе допустимое решение, что целевые функции совпадают, то эти решения оптимальные). Док-во: в силу Th1 выполняется: x ; x

Следствие 2 Th1: если одна из взаимно-двойственных задач является неограниченной функцией, тогда двойственная к ней задача допустимых решений не имеет. Докажем, что 1-я задача имеет неограниченную функцию, а во 2-й нет доп-х решений. Док-во: пусть f₁(x) неограниченна. Y -допустимых решений. Тогда x целевая функция ограниченна сверху f₁(Y) не существует такого Y.

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

1)допустимые решения первой и второй задачи:

Если одна из этих пар имеет оптимальное решение, тогда 2-я задача также имеет оптимальное решение. ; f₁()=f₂()

2)Если одна из этих задач не имеет решения в силу неограниченности целевой функции, то 2-я задача тоже не имеет решения в силу пустоты ее ОДР.

Следствие 1 Th2: Обе задачи одновременно имеют решение или не имеют.

82. 3-я теорема двойственности(формулировка) (т-ма равновесия)

; j=1..n

; i=1..m

83. Экономическая интерпретация решения двойственной задачи

Двойственные ЗЛП.

Т. -решение прямой задачи

-решение двойственной задачи

Т. Если обе взаимодвойственные задачи имеют ДБР, то у обеих задач есть оптимальное решение и maxZ=min

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

Т.

Т. Экономический смысл

84. Двойственная задача к ЗЛП в канонической форме

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

max x_j0_, i=1...m; j=1..n

Двойственная: min

y_j0_, i=1...m

постановка 1-й задачи в матричном виде:

z=(c, x) max

Ax A^тYc

x Y0

a₁₁y₁+a₂₁y₂+…a_m1y_mc₁

a₁₂y₁+a₂₂y₂+…a_m2y_mc₂ a_1my₁+a_2ny₂+…a_mny_mc_n

85. Формулирование задачи нелинейного программирования

Нелинейное программирование:

i=1…k

i=k+1…m

j=1…S

В отличие от линейного программирования, в нелинейном есть локальный max

87. Метод множителей Лагранжа

f(x₁..x_n) max(min)

i=1..m

где f, g_i-непрерывно дифференцируемые функции

L(x₁..x_n, y₁...y_m)= f(x₁..x_n)+

Где y_i-множители Лагранжа

Задача условной оптимизациизадача безусл оптимизации

//(n+m)

1 шаг: Составление функции Лагранжа

2: вычисление частных производных по всем (n+m) переменным и приравнивание их к 0.

3: Найти решение системы уравнений(в общем случае нелин)

4: Исследование полученных решений

88. Выпуклые функции

f(x)= f(x₁..x_n) наз выпуклой, если для любых двух точек x₁, x₂ выполняется соотношение:

89. Выпуклое программирование

f(x)= f(x₁..x_n) наз выпуклой, если для любых двух точек x₁, x₂ выполняется соотношение:

Задача выпуклого программирования: f(x₁..x_n)

min

i=1..m, j=1..n

где f, y_i-выпуклые функции

90. Теорема о множестве допустимых решений задачи ВП

Т-ма: Область допустимых решений задачи ВП- выпуклое множество. Док-во: x⁽¹⁾, x⁽²⁾ ОДР

[ОДР

где

91. Теорема о глобальности экстремума в задаче

Т-ма: У задачи выпуклого программирования существуют только глобальные минимумы

Док-во: Пусть x^* ОДР точка min

f(x^*)f(x^*)

будет находится в заштрихованной области, т.е. f(x^*)f(x^*)=

f(x⁽⁰⁾)-f(x^(*))

f(x⁽⁰⁾) f(x^(*))-для всех точек ОДР, т. е. x^* не просто локальный min, а глобальный.

92. Функция Лагранжа в задаче ВП

Функция Лагранжа для задачи выпуклого программирования имеет вид:

L(x₁, x_n, y_1, y_n)=f(x₁..x_n)+

93. Седловая точка функции Лагранжа

(x⁽⁰⁾, y⁽⁰⁾)=()

L(x₁, y⁽⁰⁾) L(x⁽⁰⁾, y⁽⁰⁾) L(x⁽⁰⁾, y)

94. Теорема Куна-Таккера(формулировка)

Если задача выпуклого программирования удовлетворяет условию регулярности, тогда некая точка x⁽⁰⁾= (будет решением задачи ВП. Только тогда (необх-е и дост-е усл-е), если , тогда (x⁽⁰⁾, y⁽⁰⁾)-седловая точка функции Лагранжа.

Условие регулярности: если , что для всех ограничений вып-ся: g_i(x)<b_i

95. Критерий силовой точки для гладких функций Лагранжа(формулировка)

(x⁽⁰⁾, y⁽⁰⁾)- седловая точка, когда выполняется система уравнений:

(j=1..n)

(j=1...n)

x_j (j=1...n)

(i=1...m)

(i=1...m)

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

?

общее число ограничений m*n

-могут быть любые по знаку

96. Транспортная задача в матричной постановке

97. Сбалансированная и несбалансированная транспортные задачи.

Является частным случаем общей задачи линейного программирования.

Транспортная задача является одной из самых распространённых ЗЛП специального вида. Предположим, что имеется m складов, где хранится некоторый продукт в количествах a₁,.., a_m, и n пункт в реализации этого продукта, потребности которых равны b₁,.. b_n. Требуется найти наиболее экономичный способ перевозки продукта со складов к потребителям, если затраты на перевозку единицы продукта с i-го склада в j-ый пункт потребления равны c_ij.

Пусть x_ij количество продукта, перевозимое с i-го склада в j-ый пункт потребления.

Тогда целевая функция транспортных расходов, которую требуется минимизировать, выглядит так:

Ограничения имеют вид

x₁₁ + x₁₂…+x_1n b₁

x₂₁ + x₂₂…+x_2n b₂

x_m1 + x_m2…+x_mn b_m

x₁₁ + x₁₂…+x_1n =a₁

x₂₁ + x₂₂…+x_2n =a₂

x_m1 + x_m2…+x_mn = a_m

x_ij0

Первое неравенство означает, что количество продукта, вывезенного со склада, не должно превышать запаса, второе - что потребности каждого пункта должны быть удовлетворены. Третье условие обеспечивает неотрицательность планируемых объёмов перевозок.

Особенностью полученной общей ЗЛП является двойная индексация переменных.

(+для 97: сбалансированная задача- когда запасы есть в точно необходимом количестве)

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