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

 

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

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

Найти максимум (минимум) функции

 

 

 

при условиях

 

 

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

Симплекс – метод – это алгебраический метод решения задач линейного программирования. В процессе вычислений производиться последовательный обход вершин многогранника решений (ОДР) с проверкой в каждой вершине условий оптимальности. При этом каждый переход в смежную вершину сопровождается улучшением целевой функции.

Вычислительные процедуры симплекс – метода

 

При графическом методе решения задачи линейного программирования (ЗЛП) оптимальному решению соответствует всегда одна из угловых (экстремальных) точек пространства решений. Это результат положен в основу построения симплекс-метода. Симплекс-метод не обладает наглядностью геометрического представления пространства решений.

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

Обозначим: N– общее количество переменных в ЗЛП, представленной в канонической форме; n- количество исходных переменных; m - количество ограничений, n_q - количество дополнительных переменных, тогда N=n+n_q. Каждая вершина многогранника решений имеет m - ненулевых переменных и

(N-m) - нулевых переменных. Ненулевые переменные называются базисными, нулевые переменные – небазисными. Дополним систему равенств равенством целевой функции, при этом будем считать, что z является m+1 базисной переменной, которая всегда присутствует в базисе для любой вершины.

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

При выборе начального допустимого базиса для составления симплекс-таблицы на первом шаге исходные x₁, x₂ переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные x₃, x₄, x₅ в равенствах (2) - (4) являются базисными и в z - строку входят с коэффициентами, равными 0. Для заполнения симплекс-таблицы необходимо целевую функцию преобразовать к виду

 

.

Таким образом, окончательно получаем:

(1)

(2)

(3)

(4)

 

При составлении симплекс-таблицы придерживаются следующих правил:

1. в крайнем левом столбце располагаются базисные переменные и z;

2. в крайнем правом столбце располагаются правые части ограничений;

3. в первой строке располагаются переменные в определённом порядке: сначала z, потом небазисные переменные, базисные переменные располагаются в последних m столбцах перед правой частью.

 

	св.	z	x1	x2	x3	x4	x5
z	0	1	-C1	-C2	0	0	0
X3	b1	0	a11	a12	1	0	0
X4	b2	0	a21	a22	0	1	0
X5	b3	0	a31	a32	0	0	1

 

Идею рассмотрим на примере:

7x₁+5x₂→ max

2x₁+3x₂≤ 19

2x₁+x₂≤ 13

3x₂≤ 15

3x₁≤ 18

x₁≥ 0, x₂≥ 0

Запишем задачу в каноническом виде. При необходимости предварительно неравенство преобразовать так чтобы все свободные члены были неотрицательными.

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

 

7x₁+5x₂→ max

2x₁+3x₂+x₃ =19

2x₁+x₂ +x₄ =13

 3x₂ +x₅ =15

3x₁ +x₆ =18

x_i≥ 0, (i=1, …n)

 

В нашем случае базисными переменными являются x₃, x₄, x₅, x₆. Остальные переменные являются свободными (x₁, x₂). Придавая произвольные значения свободным переменным мы будем получать различные значения базисных. Любое решение системы ограничений задачи называется допустимым. Опорным называется решение задачи, записанное в каноническом виде в котором свободные переменные равны 0.

Теорема 1:

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

7x₁+5x₂→ max

x₃=19-2x₁-3x₂ (0; 0; 19; 13; 15; 18)

x₄ =13-2x₁-x₂ первоначальный опорный план

x₅ =15-3x₂        

x₆ =18-3x₁ F(x₁, x₂ )=7*0+5*0=0     

x_i≥ 0, (i=1, …n)

 

На интуитивном уровне понятно, что естественным будет увеличение x₁, так как коэффициент при нем больше чем при x₂. Оставляя x₂=0, мы можем увеличивать до тех пор, пока x₃, x₄, x₅, x₆ будут оставаться неотрицательными.

 

x₁=min {19/2; 13/2; ∞; 18/3}=6

 

Это означает что при x₁=6, x₆=0, то есть x₁-переходит в число базисных, а x₆-в число свободных.

 

x₁=6-1/3 x₆

 

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

 

x₃=19-2(6-1/3 x₆)-3 x₂=19-12+2/3 x₆-3 x₂=7+2/3 x₆-3 x₂

x₄=13-2(6-1/3 x₆)- x₂=1+2/3 x₆- x₂

x₅= x₅=15

F(x₂; x₆) =42-7/3 x₆+5 x₂

 

При данном опорном плане (6; 0; 7; 1; 15; 0) x₂ переводиться из свободных в базисные переменные:

x₂=min{∞; 7/3; 1/11; 15/3}=1

 

Выражаем x₂ через x₄

 

x₂=1+2/3 x₆- x₄

 

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

 

x₃=7+2/3 x₆-3(1+2/3x₆ –x₄)= 7+2/3 x₆-3-2x₆+3x₄=4-4/3x₆+3 x₄

x₅= 12-2x₆+3x₄-

F=42-7/3 x₆+5(1+2/3x₂- x₄) =47-7/3x₆ +10/3x₆-5x₄=47+x₆-5x₄

 

x₆ положительное, следовательно можно увеличивать

 

x₆=min{18; ∞; 3; 6}=1

x₄=4/3-4/9 x₆- 1/3x₃

F=47+x₆-5(4/3-4/9-1/3x₃)

 

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

Теорема 2:

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

 

⇐ Предыдущая123

Поделиться: