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

Симплекс - метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

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

Запишем ограничения задачи ЛП в таком виде:

A₁x₁ + A₂x₂ +... + A_nx_n + A_n+1x_n+1 +... + A_n+mx_n+m = A₀.

Пусть A₁,..., A_m - множество линейно независимых векторов.

Тогда уравнение

( 4.1)

определяет базисное решение ,

Предположим, что это решение допустимо, то есть . Базис {A₁,., A_m} образует m -мерное пространство, а потому каждый из векторов A_m+1,., A_m+n единственным образом выражается через этот базис. Если A_r не входит в базис, то

( 4.2)

где x_ir - соответствующие коэффициенты (i = 1, 2, ..., m).

Предположим, что хотя бы одна из величин x_ir больше нуля.

Решение уравнения

( 4.3)

обозначим как

Тогда, очевидно:

( 4.4)

Умножив уравнение (4.2) на x_r и вычтя полученное уравнение из уравнения (4.1), получим

( 4.5)

Сравнив уравнения (4.5) и (4.4), находим связь нового решения со старым базисным решением :

( 4.6)

Решение (4.6), во-первых, не будет базисным, так как содержит m + 1 переменную, а во-вторых, будет допустимым не для всех значений x_r.

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

( 4.7)

где x_ir > 0.

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

Для этого выбираем значения в соответствии с (4.7). Тогда новое базисное решение имеет вид

, а новый базис - (A₁, A₂, ., A_j-1, A_j+1, ., A_m, A_r).

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

Новому ДБР соответствует следующее значение целевой функции

( 4.8)

, где z₀ - значение целевой функции для начального ДБР;

с_r-с₁x_1r - с₂x_2r -... - с_mx_mr - симплекс-разность для переменной х_r.

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

Таким образом, алгоритм симплекс-метода состоит из следующих этапов:

1. находят начальный базис и связанное с ним допустимое базисное решение;

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

3. вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплекс-разностью; ее значение определяют из соотношения

для всех x_ir > 0;

4. выводят из базисного решения переменную x_j, соответствующую

а из базиса - вектор A_j;

5. переходят к этапу 2 новой итерации.

Этапы 2 - 4 повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.

Это и есть признак оптимальности текущего базисного решения.

 

 

Метод полного исключения

Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана - Гаусса.

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

В матричной форме данная система имеет следующий вид:

Ax=A₀.

Матрица A_p=[A, A₀] называется расширенной матрицей. Метод полного исключения Жордана - Гаусса состоит из конечного числа однотипных итераций и заключается в сведении матрицы к единичному виду. Метод основывается на двух операциях:

1. одну из строк расширенной матрицы умножают на множитель, отличный от нуля;

2. из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.

Каждое из таких элементарных преобразований (называемых преобразованием Гаусса) приводит к новой системе линейных уравнений, которая эквивалентна начальной системе.

Первая итерация метода полного исключения.

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

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

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

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

Если после k -й итерации главная часть матрицы A_p^{(k)} не содержит ни одного элемента или содержит только нули, то процесс заканчивается.

Пусть процесс оборвался после итерации 1. Предположим вначале, что среди строк матрицы A^(l) есть такие, которые не были направляющими ни в одной из предыдущих итераций, например, строка с номером i. Тогда очевидно,

a_ij=0; j = 1, 2, ., n.

Поскольку для любой строки справедливо

( 1.1)

то уравнение для i -й строки имеет вид

( 1.2)

Если , то уравнение (1.2) противоречиво, и данная система уравнений неразрешима.

Если , то уравнение (1.2) представляет собой тождество и i -я строка может быть отброшена.

Перебрав одну за другой все строки матрицы A^(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.

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

( 1.3)

Пусть i -й направляющей строке соответствует i -й направляющий столбец вследствие соответствующего выбора направляющего элемента. Тогда

( 1.4)

Следовательно, (1.3) можно записать в виде:

( 1.5)

причем переменные x_i (i=1, ., l) являются базисными, а переменные x_j (j=l+1, ., n) - небазисными.

При x_j = 0 (j=l+1, ., n) получим одно из базисных решений системы уравнений .

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

Если x_i - i -я компонента этого решения, то

( 1.6)

Обозначим

Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (1.6):

( 1.7)

где x₀ - базисное решение начальной системы уравнений; - полное решение соответствующей однородной системы уравнений (то есть при A₀=0 ).

Обозначим расширенную матрицу системы уравнений после k -й итерации через

Пусть - направляющий элемент преобразования на (k+1) -й итерации. Тогда в результате (k+1) -й итерации метода полного исключения Гаусса получим матрицу , элементы которой определяются следующими соотношениями:

1. для всех элементов направляющей строки

( 1.8)

2. для элементов направляющего столбца

( 1.9)

3. для всех остальных элементов матрицы

( 1.10)

Табличный симплекс - метод

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

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

A₁x₁+...+A_nx_n+e₁x_n+e₁x_n+1+...+e_mx_n+m=A₀=[a_i0],

где

для всех i = 1, 2,., n.

Применим одну итерацию метода полного исключения к расширенной матрице ограничений A_p=[A₁, ..., A_n, e₁, ..., e_m, A₀].

Пусть a_ij - направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (1.10) получим новые значения свободных членов:

( 2.1)

Исследуем выражения (2.1) и выясним условия, при которых для всех l, то есть новое базисное решение будет также допустимым.

По предположению , тогда

Если , тогда , поскольку .

Если , то

будет больше нуля при всех l=1, 2, ..., m тогда и только тогда, когда

( 2.2)

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

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

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что a_ij> 0.

При таком преобразовании в базис вводится вектор A_j и выводится вектор А_i. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов :

( 2.3)

где - множество индексов базисных векторов; x_ij - определяют из условия

( 2.4)

Величины равны симплекс-разницам для переменных {x_j} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец А_j с наибольшей по модулю отрицательной оценкой, то есть

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.1.

 

Таблица 2.1.
c			c1	c2	c3	.	cj	.	cn
	Bx	a00	A1	A2	A3	.		.	An
c1	x1	a10	a11	a12	a13	.	a1j	.	a1n
c2	x2	a20	a21	a22	a23	.	a2j	.	a2n
.	.	.	.	.	.	.	.	.	.
	xi	ai0	ai1	ai2	ai3	.	aij	.	ain
.	.	.	.	.	.	.	.	.	.
cm	xm	am0	am1	am2	am3	.	amj	.	amn
						.		.

 

Последняя строка таблицы - индексная - служит для определения направляющего столбца. Ее элементы определяют по формуле (2.3). Очевидно, для всех базисных векторов {A_i} i=1,., m оценки .

Значение целевой функции a₀₀ определяется из соотношения

В столбце B_x записываем базисные переменные {x_i} i= 1, ..., m. Их значения определяются столбиком свободных членов a_i0, то есть

X_i=a_i0, i=1, 2,., m.

Направляющие строка A_i и столбец A_j указываются стрелками. Если в качестве направляющего элемента выбран a_ij, то переход от данной симплекс-таблицы к следующей определяется соотношениями (1.8) - (1.10).

Итак, алгоритм решения задачи ЛП табличным симплекс-методом состоит из этапов.

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

2. В качестве направляющего столбца выбирают A_j, для которого

3. Направляющая строка A_і выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом a_ij, для чего используют соотношения (1.8) - (1.10). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

Правильность вычислений контролируют по формулам непосредственного счета:

	(2.5)
	( 2.5)

В столбце B_x новой таблицы заменяют x_i на x_j, а в столбце С c_i на c_j.

5. Если все , то новое базисное решение - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

а) все . Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;

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

Назовем некоторые особенности применения табличного симплекс-метода.

Если в качестве начального базиса выбирают базис из свободных переменных, для которых c_i=0, то оценки для всех небазисных переменных равны , а соответствующее значение целевой функции

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

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

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

 

 

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. А теперь мое решение проблемы
5. А теперь мое решение проблемы
6. Алгоритм решения задач линейного программирования с помощью Excel
7. Алгоритм решения задач ЛП графическим методом
8. Алгоритм решения транспортной задачи
9. Анализ подходов и методов решения задачи
10. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
11. Анализ состава задач по проектированию трудовых процессов и нормированию труда и возможностей их автоматизации.
12. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви