Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Морозов Ю.Г., Уксусов С.Н.
Пименение Метода Штифеля в дробно-линейном программировании
Метод Штифеля при решении общих задач линейного программирования описан в [1].
Общей задачей дробно-линейного программирования называется задача нахождения экстремума (максимума или минимума) функции
,
определенной на некотором выпуклом подмножестве n-мерного пространства, которое задается системой линейных неравенств и уравнений:
a11x1 + a12x2 + a13x3 + … + a1nxn a1,
…………………………………………
ai1x1 + ai2x2 + ai3x3 + … + ainxn ai,
…………………………………………
am1x1 + am2x2 + am3x3 + … + amnxn am,
x1, x2, x3, … xn 0.
Предполагается, что на множестве опорных планов задачи (т.е. на множестве решений системы ограничений) нет точек, в которых знаменатель целевой функции равен нулю. Без ограничения общности полагают, что .
В задаче дробно-линейного программирования экстремум или асимптотический экстремум целевой функции достигаются в вершине многогранника решений. Это сходство с линейным программированием позволяет решать дробно-линейные задачи методом Штифеля. Приведем соответствующий алгоритм.
Вычисления так же, как и раньше, будем оформлять в виде жордановых таблиц. При этом для функционала две нижние строки: в первую из них записываем коэффициенты числителя, а во вторую – знаменателя. Исходной задаче соответствует таблица 1:
|
–x1 |
–x2 |
… |
–xj |
… |
–xn |
1 |
|
|
y1 |
a11 |
a12 |
… |
a1j |
… |
a1n |
a1 |
|
… |
…………………………………………… |
… |
|||||
|
yi |
ai1 |
ai2 |
… |
aij |
… |
ain |
ai |
|
… |
…………………………………………… |
… |
|||||
|
ym |
am1 |
am2 |
… |
amj |
… |
amn |
am |
|
z1 |
–p1 |
–p2 |
… |
–pj |
… |
–pn |
0 |
|
z2 |
–q1 |
–q2 |
… |
–qj |
… |
–qn |
0 |
Табл. 1.
Через yi обозначаются разности между правыми и левыми частями системы ограничений:
yi = ai – ai1x1 – ai2x2 – ai3x3 – … – ainxn 0.
Свободными переменными мы, как и прежде (см. [1]), будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. Придавая свободным переменным различные значения, мы каждый раз будем получать различные значения зависимых (базисных) переменных yi. Исходным базисным решением является вектор с координатами . Данный вектор не может являться опорным планом, т.к. знаменатель целевого функционала на нем равен нулю (z2 = 0).
Базисное решение системы ограничений не является опорным планом, если среди свободных членов системы ограничений, т.е. среди чисел a1,…, am есть отрицательные числа. Шагами модифицированных жордановых исключений, точно так же, как при решении задачи линейного программирования (см. [1]), отыскиваем первоначальный план задачи. В результате k шагов мы приходим к таблице 2:
|
–y1 |
… |
–xj |
… |
–xn |
1 |
|
|
x1 |
b11 |
… |
b1j |
… |
b1n |
b1 |
|
.… |
……………………………………….… |
|||||
|
yi |
bi1 |
… |
bij |
… |
bin |
bi |
|
…. |
…………………………………………. |
|||||
|
ym |
bm1 |
… |
bmj |
… |
bmn |
bm |
|
z1 |
f1 |
… |
fj |
… |
fn |
F |
|
z2 |
g1 |
… |
gj |
… |
gn |
G |
Табл. 2.
В таблице 2 все свободные члены bi неотрицательны, что обеспечивает не отрицательность базисных переменных x1,…, ym. Кроме того (в силу положительности знаменателя целевой функции z2 на множестве опорных планов). Первоначальным опорным планом является вектор с координатами . Значение целевой функции на первоначальном опорном плане равно .
Заметим, что если на одном из шагов жордановых исключений какой-либо из свободных членов bi окажется отрицательным, а все остальные элементы i-й строки будут неотрицательными, то задача не будет иметь решения из-за отсутствия планов (в этом случае, ни при каком выборе свободных переменных, базисная переменная yi не может стать неотрицательной).
Проследим за тем, как меняется целевая функция при переходе от первоначального опорного плана задачи к другому опорному плану. Если значение целевой функции возрастет, то мы приблизимся к ее максимуму, а если уменьшится, то к минимуму. Предположим, что в j-м столбце, в соответствии с принципом минимального симплексного отношения ([1]), выбран разрешающий элемент . После шага модифицированных жордановых исключений мы приходим к таблице:
|
–y1 |
… |
–yi |
… |
–xn |
1 |
|
|
x1 |
… |
… |
||||
|
.… |
……………………………………….… |
|||||
|
xj |
… |
… |
||||
|
…. |
…………………………………………. |
|||||
|
ym |
… |
… |
||||
|
z1 |
… |
… |
||||
|
z2 |
… |
… |
Табл. 3.
Напомним, что новые коэффициенты системы, в соответствие с методом Штифеля, находятся по следующим правилам:
В частности, .
Оценим разность между новым и старым значениями целевой функции:
.
Очевидно, что коэффициент строго больше нуля ( как симплексное отношение, а и по предположению о знаменателе целевого функционала на множестве опорных планов).
Следовательно, знак разности совпадает со знаком определителя . Если , то значение целевой функции при переходе к новому опорному плану увеличивается, а если , то – уменьшается. В дальнейшем мы будем называть оценками свободных переменных.
Предположим, что исходная задача дробно-линейного программирования являлась задачей на максимум. Если все определители , вычисленные по таблице 2, неотрицательны, то при переходе к любому другому опорному плану функция цели может только уменьшится. Следовательно, оптимальным является опорный план и .
Если среди оценок свободных переменных есть отрицательные числа, например, (для некоторого j), то план не является оптимальным. Его можно улучшить, выбрав в качестве разрешающего столбца j-й столбец и перейти к плану , соответствующему таблице 3. При этом целевая функция возрастет на величину . Т.к. многогранник решений содержит лишь конечное число опорных планов, то за конечное число шагов мы придем к оптимальному опорному плану.
Этому процессу может помешать только неограниченность многогранника решений. В этом случае целевая функция может иметь так называемый асимптотический экстремум (в данном случае – максимум). Асимптотическим максимумом задачи дробно-линейного программирования называется точная верхняя грань целевой функции на множестве планов, которая не достигается ни на одном из планов. В том случае, когда задача имеет асимптотический максимум, в области планов всегда можно найти такой план (не опорный), на котором целевая функция принимает значение сколь угодно близкое к асимптотическому максимуму.
Метод Штифеля позволяет находить не только максимум, но и асимптотический максимум задачи дробно-линейного программирования. Рассмотрим более подробно переход от плана к плану и выясним – всегда ли такой переход возможен? Выбирая разрешающий элемент в j-м столбце, мы должны руководствоваться принципом минимального симплексного отношения. Т.е. разрешающий элемент в j-м столбце должен попасть в ту строку, для которой симплексное отношение положительно и минимально.
Т.к. после нахождения первоначального опорного плана все правые части bi стали неотрицательными, то разрешающим элементом j-го столбца может быть один из его положительных элементов (). Если на каждом шаге этапа поиска оптимального опорного плана в выбранном разрешающем столбце присутствует (хотя бы один) положительный элемент , то такая задача имеет максимум (возможно, что не один). Этот максимум можно найти за конечное число шагов.
Однако, если на одном из шагов только одна оценка меньше нуля, т.е. разрешающим столбцом может быть только j-й столбец. Пусть при этом все элементы j-го столбца . Тогда в данном столбце, руководствуясь принципом минимального симплексного отношения, разрешающий элемент выбирать нельзя. Увеличивая значения свободной переменной xj от 0 и до (см. Табл. 2), мы все время остаемся в области планов. Это связано с тем, что увеличение переменной xj не вызывает изменения знака на минус ни у одной из базисных переменных.
Обозначим через М предел, к которому, монотонно возрастая, стремится целевая функция при : . Если , задача имеет асимптотический максимум, и этот максимум равен . Если же , то задача имеет обычный максимум и он равен .
Рассмотрим разность . По предположению и, следовательно, знак выражения противоположен знаку . Если , то , и задача имеет обычный максимум . Если , то , и задача имеет асимптотический экстремум. Выбирая значение xj сколь угодно большим, значение функции цели можно сделать сколь угодно близким к числу .
При решении общей задачи линейного программирования методом Штифеля мы должны проделать следующие шаги:
Причем первый и второй этапы желательно проделать одновременно.
Зафиксируем j-й столбец жордановой таблицы (3.1). Для тех элементов aij данного столбца, знак которых совпадает со знаком свободного члена bi, расположенного в той же строке, что и aij, определим отношение:
.
Числа называются симплексными отношениями. Из определения следует, что все симплексные отношения строго больше нуля.
Решение задачи линейного программирования основывается на следующей основной теореме:
Пример. Найти максимум функции цели
z(X) = - 8x1 + x2 + 6x3 + x4 + 7x5 max
при условии, что
– 2x1 + x2 + 2x3 - x4 + x5 – 4,
x1 + 4x2 + x3 – 2x4 – 2x5 = – 8,
– 3x1 – x2 + 2x3 + x4 + 3x5 – 2,
x1, x3, x4, x5 0.
Решение. Перепишем систему ограничений в виде:
2x1 – x2 – 2x3 + x4 – x5 – 4 = y1,
– x1 – 4x2 – x3 + 2x4 + 2x5 – 8 = 0,
3x1 + x2 – 2x3 – x4 – 3x5 – 2 = y2,
x1, x3, x4, x5, y1, y2 0.
Решим данную задачу методом Штифеля:
|
–x1 |
–x2 |
–x3 |
–x4 |
–x5 |
1 |
–x1 |
–x2 |
–x3 |
–x4 |
1 |
|||
|
y1 |
–2 |
1 |
2 |
–1 |
1 |
–4 |
y1 |
–3/2 |
3 |
5/2 |
–2 |
–8 |
|
|
0 |
1 |
4 |
1 |
–2 |
–2 |
–8 |
x5 |
–1/2 |
–2 |
–1/2 |
1 |
4 |
|
|
y2 |
–3 |
–1 |
2 |
1 |
3 |
–2 |
y2 |
–3/2 |
5 |
7/2 |
–2 |
–14 |
|
|
z |
8 |
–1 |
–6 |
–1 |
–7 |
0 |
z |
9/2 |
–15 |
–19/2 |
6 |
28 |
Табл. 4. Табл. 5.
На первом шаге (при переходе от табл. 4. к табл. 5) свободная переменная x5 меняется на базисную переменную 0. При попадании нуля на верх, соответствующий столбец можно исключить из таблицы.
На втором шаге (при переходе от табл. 5 к табл. 6) свободная переменная x2 меняется на базисную переменную y2. После этого строку, соответствующую переменной x2, можно, предварительно запомнив, исключить из таблицы 6. Таким образом, мы приходим к таблице 7:
|
–x1 |
–y2 |
–x3 |
–x4 |
1 |
||||||||
|
y1 |
–0,6 |
–0,6 |
0,4 |
–0,8 |
0,4 |
–x1 |
–y2 |
–x3 |
–x4 |
1 |
||
|
x5 |
–1,1 |
0,4 |
0,9 |
0,2 |
–1,6 |
y1 |
–0,6 |
–0,6 |
0,4 |
–0,8 |
0,4 |
|
|
x2 |
–0,3 |
0,2 |
0,7 |
–0,4 |
–2,8 |
x5 |
–1,1 |
0,4 |
0,9 |
0,2 |
–1,6 |
|
|
z |
0 |
3 |
1 |
0 |
–14 |
z |
0 |
3 |
1 |
0 |
–14 |
Табл. 6. Табл. 7.
На данном этапе завершается упрощение задачи. Заметим, что упрощение задачи можно было сделать иначе. На первом же шаге можно было базисную переменную 0 заменить на свободную переменную x2. Тем самым, мы могли сэкономить один шаг.
До сих пор мы не следили за значениями функции цели и за оценками свободных и базисных переменных. На втором этапе обратим внимание на оценки базисных переменных y1 и x5, то есть на числа 0,4 и – 1,6 из последнего столбца таблицы 4. Среди этих чисел есть отрицательное
(–1,6). Просматривая другие элементы строки, соответствующей базисной переменной x5, находим среди них еще одно отрицательное –1.1 (если бы такого отрицательного числа не нашлось, то задача не имела бы решения из-за отсутствия планов). Вычислим минимальное симплексное отношение для первого столбца, в котором находится отрицательное число –1,1. В данном случае оно, очевидно, равно (–1,6):(–1,1) = 16/11, и разрешающим элементом является число –1,1. После очередного пересчета приходим к таблице:
|
–x5 |
–y2 |
–x3 |
–x4 |
1 |
|
|
y1 |
–6/11 |
–9/11 |
–1/11 |
–1/11 |
14/11 |
|
x1 |
–10/11 |
–4/11 |
–9/11 |
–2/11 |
16/11 |
|
z |
0 |
3 |
1 |
0 |
–14 |
Табл. 8.
Теперь обе оценки базисных переменных положительны и, следовательно, мы вышли в область планов. Так как все оценки свободных переменных неотрицательны, то данный план является оптимальным. Причем он является единственным оптимальным планом данной задачи, несмотря на наличие нулевых оценок. Действительно, при попытке заменить любую из свободных переменных x5 или x4, имеющую нулевую оценку на любую из базисных переменных, нам пришлось бы в качестве разрешающего элемента выбрать отрицательное число, и тем самым выйти из области планов задачи. Таким образом, оптимальным планом задачи (4.6) является план с компонентами:
То есть, . При этом .
ЛИТЕРАТУРА