Дробно – линейного программирования

Поиск с помощью метода Штифеля асимптотических решений задачи

Дана задача: найти максимум функционала (1)

При выполнении ограничений:

(2)

Решение задачи выполняется в такой последовательности.

1.Составим жорданову таблицу. При этом для функционала предусмотрены две строки: в верхнюю записываем коэффициенты числителя, а в нижнюю – знаменателя (таб.1).

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

В результате шагов придем к следующей таблице.

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

Как и в случае линейного программирования, решение, записанное в таблице, получаем, приравнивая все верхние переменные нулю, а боковые – свободным членам. Так находится вершина многогранника. При этом значение функционала на k -м шаге

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

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

Приведем подобные члены, вынесем в числители общий множитель со знаком минус за скобку, а знаменатели заменим выражение в скобках на . Получим:

Обозначим числитель первой дроби символом :

(3)

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

(4)

Исследуем выражение (4).

1.Чтобы не оторваться от многогранника решений, симплексное отношение должно быть положительным и минимальным из всех возможных:

(отсюда должно быть , так как по условию допустимости плана ). Следовательно, скобка в выражении (4) всегда будет отрицательной: .

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

Если этот определитель положителен: , то вся правая часть выражения (4) окажется отрицательной, т.е. будем иметь ; отсюда .

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

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

Если будет , то , , т.е. значение функционала останется без изменения.

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

Имея такие результаты, для отыскания оптимального плана можно сформулировать следующие пункты алгоритма.

3.После нахождения опорного плана вычисляем для каждого столбца значение определителя (3):

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

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

5. Разрешающий элемент в выбранном столбце отыскивается по наименьшему симплексному отношению.

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

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

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

9.При решении задачи на минимум функционала за разрешающий принимается столбец с положительным значением определителя . Разрешающая строка устанавливается пол минимальному симплексному отношению. Критерием оптимальности служит положительность определителей .

Вместо того чтобы менять алгоритм, можно изменить знак в числители функционала и решать задачу на максимум.

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

Док - во:

Пусть и все элементы , отрицательны.

Выпишем базисные переменные , которые равны соответственно .

Переменную увеличиваем, тогда переменные начинают расти.

Выясним, к чему стремится определитель . Из таблицы видно что , при чем продолжает увеличиваться это следует из того, что (так как ).

Ч.т.д.

Рассмотрим конкретный пример:

Найдем максимум функционала:

При выполнении ограничений:

Составим жорданову таблицу.

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

шаг модифицированных жордановых исключений

Продолжаем искать опорный план. За разрешающий элемент берем .

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

Определим угловой коэффициент, обозначим . Выпишем :

Угловой коэффициент

Конечный или бесконечный максимум, для этого определим к чему стремится z.

Получили конечный максимум.

Об ускорении поиска оптимального опорного плана задачи

Поиск по сайту: