Пименение Метода Штифеля в дробно-линейном программировании
Морозов Ю.Г., Уксусов С.Н.
Метод Штифеля при решении общих задач линейного программирования описан в [1].
Общей задачей дробно-линейного программирования называется задача нахождения экстремума (максимума или минимума) функции
,
определенной на некотором выпуклом подмножестве n -мерного пространства, которое задается системой линейных неравенств и уравнений:
a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n xn £ a 1,
…………………………………………
ai 1 x 1 + ai 2 x 2 + ai 3 x 3 + … + ainxn £ ai,
…………………………………………
am 1 x 1 + am 2 x 2 + am 3 x 3 + … + amnxn £ am,
x 1, x 2, x 3, … xn ³ 0.
Предполагается, что на множестве опорных планов задачи (т.е. на множестве решений системы ограничений) нет точек, в которых знаменатель целевой функции равен нулю. Без ограничения общности полагают, что 
.
В задаче дробно-линейного программирования экстремум или асимптотический экстремум целевой функции достигаются в вершине многогранника решений. Это сходство с линейным программированием позволяет решать дробно-линейные задачи методом Штифеля. Приведем соответствующий алгоритм.
Вычисления так же, как и раньше, будем оформлять в виде жордановых таблиц. При этом для функционала две нижние строки: в первую из них записываем коэффициенты числителя, а во вторую – знаменателя. Исходной задаче соответствует таблица 1:
| – x 1 | – x 2 | … | – xj | … | – xn | |
y 1 | a 11 | a 12 | … | a 1 j | … | a 1 n | a 1 |
… | …………………………………………… | … | |||||
yi | ai 1 | ai 2 | … | aij | … | ain | ai |
… | …………………………………………… | … | |||||
ym | am 1 | am 2 | … | amj | … | amn | am |
z 1 | – p 1 | – p 2 | … | – pj | … | – pn | |
z 2 | – q 1 | – q 2 | … | – qj | … | – qn |
Табл. 1.
Через yi обозначаются разности между правыми и левыми частями системы ограничений:
yi = ai – ai 1 x 1 – ai 2 x 2 – ai 3 x 3 – … – ainxn ³ 0.
Свободными переменными мы, как и прежде (см. [1]), будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. Придавая свободным переменным различные значения, мы каждый раз будем получать различные значения зависимых (базисных) переменных yi. Исходным базисным решением является вектор с координатами 
. Данный вектор не может являться опорным планом, т.к. знаменатель целевого функционала на нем равен нулю (z 2 = 0).
Базисное решение системы ограничений не является опорным планом, если среди свободных членов системы ограничений, т.е. среди чисел a 1,…, am есть отрицательные числа. Шагами модифицированных жордановых исключений, точно так же, как при решении задачи линейного программирования (см. [1]), отыскиваем первоначальный план задачи. В результате k шагов мы приходим к таблице 2:
| – y 1 | … | – xj | … | – xn | |
x 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
.… | ……………………………………….… | |||||
yi | bi 1 | … | bij | … | bin | bi |
…. | …………………………………………. | |||||
ym | bm 1 | … | bmj | … | bmn | bm |
z 1 | f 1 | … | fj | … | fn | F |
z 2 | g 1 | … | gj | … | gn | G |
Табл. 2.
В таблице 2 все свободные члены bi неотрицательны, что обеспечивает не отрицательность базисных переменных x 1,…, ym. Кроме того 
(в силу положительности знаменателя целевой функции z 2 на множестве опорных планов). Первоначальным опорным планом является вектор 
с координатами 
. Значение целевой функции на первоначальном опорном плане равно 
.
Заметим, что если на одном из шагов жордановых исключений какой-либо из свободных членов b i окажется отрицательным, а все остальные элементы i -й строки будут неотрицательными, то задача не будет иметь решения из-за отсутствия планов (в этом случае, ни при каком выборе свободных переменных, базисная переменная yi не может стать неотрицательной).
Проследим за тем, как меняется целевая функция при переходе от первоначального опорного плана задачи к другому опорному плану. Если значение целевой функции возрастет, то мы приблизимся к ее максимуму, а если уменьшится, то к минимуму. Предположим, что в j -м столбце, в соответствии с принципом минимального симплексного отношения ([1]), выбран разрешающий элемент 
. После шага модифицированных жордановых исключений мы приходим к таблице:
| – y 1 | … | – yi | … | – xn | |
x 1 |
| … |
| … |
|
|
.… | ……………………………………….… | |||||
xj |
| … |
| … |
|
|
…. | …………………………………………. | |||||
ym |
| … |
| … |
|
|
z 1 |
| … |
| … |
|
|
z 2 |
| … |
| … |
|
|
Табл. 3.
Напомним, что новые коэффициенты системы, в соответствие с методом Штифеля, находятся по следующим правилам:
1. Разрешающий элемент заменяется обратным числом: 
2. Остальные элементы разрешающей строки делятся на разрешающий элемент: 
3. Остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный: 
4. Элементы, не попавшие в разрешающую строку и разрешающий столбец, пересчитываются по формулам: 
В частности, 
.
Оценим разность между новым и старым значениями целевой функции:
.
Очевидно, что коэффициент 
строго больше нуля (
как симплексное отношение, а 
и 
по предположению о знаменателе целевого функционала на множестве опорных планов).
Следовательно, знак разности 
совпадает со знаком определителя 
. Если 
, то значение целевой функции при переходе к новому опорному плану увеличивается, а если 
, то – уменьшается. В дальнейшем 
мы будем называть оценками свободных переменных.
Предположим, что исходная задача дробно-линейного программирования являлась задачей на максимум. Если все определители , вычисленные по таблице 2, неотрицательны, то при переходе к любому другому опорному плану функция цели может только уменьшится. Следовательно, оптимальным является опорный план и 
.
Если среди оценок свободных переменных есть отрицательные числа, например, (для некоторого j), то план не является оптимальным. Его можно улучшить, выбрав в качестве разрешающего столбца j -й столбец и перейти к плану 
, соответствующему таблице 3. При этом целевая функция возрастет на величину 
. Т.к. многогранник решений содержит лишь конечное число опорных планов, то за конечное число шагов мы придем к оптимальному опорному плану.
Этому процессу может помешать только неограниченность многогранника решений. В этом случае целевая функция может иметь так называемый асимптотический экстремум (в данном случае – максимум). Асимптотическим максимумом задачи дробно-линейного программирования называется точная верхняя грань целевой функции на множестве планов, которая не достигается ни на одном из планов. В том случае, когда задача имеет асимптотический максимум, в области планов всегда можно найти такой план (не опорный), на котором целевая функция принимает значение сколь угодно близкое к асимптотическому максимуму.
Метод Штифеля позволяет находить не только максимум, но и асимптотический максимум задачи дробно-линейного программирования. Рассмотрим более подробно переход от плана к плану и выясним – всегда ли такой переход возможен? Выбирая разрешающий элемент в j -м столбце, мы должны руководствоваться принципом минимального симплексного отношения. Т.е. разрешающий элемент в j -м столбце должен попасть в ту строку, для которой симплексное отношение 
положительно и минимально.
Т.к. после нахождения первоначального опорного плана все правые части bi стали неотрицательными, то разрешающим элементом j -го столбца может быть один из его положительных элементов (
). Если на каждом шаге этапа поиска оптимального опорного плана в выбранном разрешающем столбце присутствует (хотя бы один) положительный элемент , то такая задача имеет максимум (возможно, что не один). Этот максимум можно найти за конечное число шагов.
Однако, если на одном из шагов только одна оценка меньше нуля, т.е. разрешающим столбцом может быть только j -й столбец. Пусть при этом все элементы j -го столбца 
. Тогда в данном столбце, руководствуясь принципом минимального симплексного отношения, разрешающий элемент выбирать нельзя. Увеличивая значения свободной переменной xj от 0 и до 
(см. Табл. 2), мы все время остаемся в области планов. Это связано с тем, что увеличение переменной xj не вызывает изменения знака на минус ни у одной из базисных переменных.
Обозначим через М предел, к которому, монотонно возрастая, стремится целевая функция при 
: 
. Если 
, задача имеет асимптотический максимум, и этот максимум равен 
. Если же 
, то задача имеет обычный максимум и он равен 
.
Рассмотрим разность 
. По предположению 
и, следовательно, знак выражения 
противоположен знаку 
. Если 
, то , и задача имеет обычный максимум . Если 
, то , и задача имеет асимптотический экстремум. Выбирая значение xj сколь угодно большим, значение функции цели можно сделать сколь угодно близким к числу .
ЛИТЕРАТУРА
1. Зуховицкий С. И. Линейное и нелинейное программирование / С. И. Зуховицкий, Л.И. Авдеева. – М.: Наука, 1967. – 352 с.
2. Полунин И.Ф. Курс математического программирования / И.Ф. Полунин. – Минск: Вышэйш. шк., 1968. – 253 с.
Дата добавления: 2015-08-28; просмотров: 191 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| Комитет здравоохранения | | | Применение определенного интеграла |
