Пересечение замкнутых множеств, множество нетривиальных ограничений

1.    Пересечение замкнутых множеств, множество нетривиальных ограничений.

2.    Множество решений системы линейных нестрогих неравенств и уравнений является замкнутым.

αX=(αx₁,x₂,…, αx_n)

X+Y=(x₁+y₁, x₂+y₂,… x_n+y_n)

Линейные координаты X₁,X₂,…X_n называется точка P=λ₁x₁+ λ₂x₂+…+ λ_kx_k

Теорема 3:

Множество P={λ₁x₁+ λ₂x₂+…+ λ_kx_k} 0≤ h_i≤1 для i= 1,…k_n åR_i=1, 1≤ i ≤k выпуклая линейная комбинация точек x₁,x₂,…x_n. Если k=2, то это множество называется отрезком. X₁,X₂ – концы отрезка. Угловой точкой замкнутого множества называется точка, которая не является нетривиальной линейной комбинацией точек множества (угловая точка).

Нетривиальность означает, что хотя бы одна из λ отлична от 0 или 1.

Теорема 4:

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

Теорема 5:

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

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

Переход к новому опорному плану

F₁=F(x₁); F₂=F(x₂) F₂-F₁=-υ_kΔ_k=F₂ можно доказать, где υ_kрассмотренный выше минимум, который определяется при введении k-ой переменной в базис, а Δ_k=åс_jx_j⁽¹⁾-С_k, где n ≤ j ≤1, X₁=(x₁⁽¹⁾;x₂⁽¹⁾ ;…x_n⁽¹⁾)- оценка k-ой переменной, поэтому если решается задача на максимум, то величина ΔF₂ положительной должна быть, Δk – отрицательная. При решении задач на минимум ΔF₂-отрицательная, Δ_k - положительная. Эти величины вычисляются и если среди ΔF₂ все значения не положительны, то при решении задач на минимум наоборот. Если при решении на максимум среди ΔF₂ несколько положительных, то вводим в базис тот вектор, при котором эта величина достигает максимум, а если задача решается на минимум и среди ΔF₂ несколько отрицательных, то в число базисных включается вектор с наименьшим значением ΔF₂, то есть с наибольшим по абсолютной величине. При выполнении этих условий гарантируется наибольшее возможное изменении значения функции.

Решение задачи будет единственным, если для любых векторов x_k не входящих в базис, оценки Δ_k≠0, если хотя бы одно из таких Δ_k=0, то решение не является единственным, для нахождения другого решения переходим к другому опорному плану, включая в базис x_k, где Δ_k=0. Перебор все такие опорные решений составляют их в линейную комбинацию, которая и будет решением задачи.

Если для любого некоторого Δ_k противоречащих условию оптимальности коэффициенты при переменной x_k≤ 0, то система ограничений не ограничена, то есть оптимального плана не существует.

Двойственная задача

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

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

1.  m переменных, соответствующих числу ограничений прямой задачи;

2.  n ограничений, соответствующих числу переменных прямой задачи.

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

·   Каждому ограничению b_iПЗ соответствует переменная y_i ДЗ;

·   Каждой переменной x_j ПЗ соответствует ограничение C_j ДЗ;

·   Коэффициенты при x_j в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

·   Коэффициенты C_j при x_j в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

·   Постоянные ограничений b_iПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим следующие две задачи:

F = С₁х₁+С₂х₂+... +С_nx_n→max

(5)

a₁₁x₁ + a₂₂x₂ + ... + a_1mx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2mx_n ≤b₂

. . . . . . . . . . . . . . . . . . . . . . .

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤b_m

x_j≥0 j=1,…,n

Z = b₁х₁+b₂х₂+... +b_nx_n→min

(6)

a₁₁y₁ + a₂₁y₂ + ... + a_m1y₁ ≤ C₁

a₁₂y₁ + a₂₂y₂ + ... + a_m2y₂ ≤C₂

. . . . . . . . . . . . . . . . . . . . . . .

a_1ny_n + a_2my_n + ... + a_nmy_n ≤C_n

y_i≥0 i=1,…,m

Теорема 1 (первая теорема двойственности)

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

Fmax=Zmin

Теорема 2(вторая теорема двойственности)

Если (5) и (6) пара симметричных двойственных задач, то (x⁰₁, x⁰₂, ... , x⁰_n) и (y⁰₁, y⁰₂, ... , y⁰_n) являются их оптимальными решениями, то компоненты оптимальных решений удовлетворяются системе.

x₁⁰(a₁₁y₁⁰+a₂₁y₂⁰+…+a_m1y_n⁰-c₁)=0

x₂⁰(a₁₂y₁⁰+a₂₂y₂⁰+…+a_m2y_n⁰-c₂)=0

. . . . . . . . . . . . . . . . . . . . . . . . . . .

x_n⁰(a_1ny₁⁰+a_2my₂⁰+…+a_m1y_n⁰-c₁)=0

y₁⁰(a₁₁x⁰₁+a₂₂x⁰₂+...+a_1mx⁰_n -b₁)=0

y₂⁰(a₂₁x⁰₁+a₂₂x⁰₂+... +a_2mx⁰_n-b₂)=0

. . . . . . . . . . . . . . . . . . . . . . . . . . .

y_n⁰(a_m1x⁰₁+a_m2x⁰₂+...+a_mnx⁰_n-b_m)=0

Заключение

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

1.         Основы математических методов и их применение;

2.         Решение задач с помощью симплекс – метода.