Файл: Математическое программирование и производственные задачи..pdf

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

Для решения поставленных задач можно было применять

эффективные алгоритмы их решения. Эти алгоритмы основа­ ны на идеях параметрического линейного программирования.

2°. Алгоритм решения. Идея предлагаемого алгоритма

параметры. При некотором фиксированном наборе значений этих параметров данная задача является задачей линейного программирования сравнительно небольших размеров и ре­ шается одним из конечных методов.

Далее, пользуясь идеями параметрического программи­

ои (/=i y-i i 1

где область D определяется условиями (1.1), (1.2) и неот­ рицательности переменных % . Области же изменения па­ раметров определяются следующим образом: компоненты вектора Q принимают натуральные значения, а а-неотрица- телькые значения, удовлетворяющие ограничению (1.3).

Задача 1.3 является частным видом параметрической задачи линейного программирования. В этой задаче от век­ торного параметра линейно зависит вектор ограничений (а и Q в системе условий (1.1) переносятся в правые части).

54

Тогда вместо дискретной параметрической задачи 1.3 будем иметь непрерывную параметрическую задачу. Для единооб­

рической задачи.

Определение 2.2. Если в точке допустимости линейная

называется точкой определения функции FQ-).

Обозначим через G множество точек определения

нейная функция (2.2) не ограничена снизу на соответствую­ щем множестве А , то 0 = 0 ; иными словами, если в не­ которой допустимой точке функция (2.2) не ограничена снизу, то и во всех точках допустимости она будет неог­ раниченной снизу на соответствующих множествах.

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

55

ния двойственной задачи. Но условия двойственной задачи не содержат параметра X (он участвует только в выражении це­ левой функции). Следовательно, при всех X двойственная задача будет неразрешимой. Отсюда вытекает и неразреши­ мость прямой задачи во всех допустимых точках. Значит, во

56

функция F(k) является выпуклой („выпуклостью вниз") функцией. Элементарными рассуждениями можно показать, что множество G разбивается на конечное число выпук­ лых подмножеств, на которых функция FQ.) является ли­ нейной и определяется с помощью одного и того же бази­

са.

На основе приведенных рассуждений можно разрабо­ тать алгоритм построения функции FQ.) на множестве G.

Из свойства выпуклости функции F (l) следует, что множество точек, минимизирующих эту функцию, выпукло. Значит, за конечное число переходов от одного подмно­ жества к другому можно найти минимальное значение /7(л) на множестве G.

Приведем краткое описание алгоритма построения функ­

ние задачи в данной точке. Легко заметить, что это решение одновременно является и оптимальным. Базис, соответствую­ щий указанному решению, можно определить при помощи метода построения исходного решения обычной транспортной задачи. Применяя затем процедуру, аналогичную обобщен­ ному методу потенциалов, получим оптимальный базис. Так как каждый базисный компонент решения является некото­ рой линейной функцией векторного параметра то множе­ ство точек допустимости данного базисного решения будет оп­ ределяться как пересечение конечного числа полупространств, т. е. это 'множество является выпуклым многогранным множеством. Обозначим его через Oj. На этом множестве функция FQ.) является линейной, значит, направление наи­ скорейшего убывания этой функции определяется непосред­ ственно по коэффициентам при .компонентах *. Двигаясь по выбранному направлению, попадем в точку, являющуюся общей для смежных подмножеств. Отметим, что в общих точ­ ках смежных подмножеств функция F(l) является непрерыв­ ной и недифференцируемой. Поэтому обычные градиентные

* Отметим, что на направление s обязательно должно быть наложе­ но ограничение нормализации (относительно различных способов норма­

лизации см., например, 137]).

57

J

методы не применимы для переходов через граничные точки. Здесь решается задача выбора направления, которая заклю­ чается в следующем. Пусть s/{ —направление, выбранное для

подмножества 0^. Выбираем направление s так, чтобы ска­ лярное произведение (sk ,s) было максимальным. Ясно, что при движении по направлению s имеющийся базис перестает быть допустимым. С другой стороны, по направлению 5 вместо многопараметрической задачи имеем однопараметрическую простейшую задачу, для которой известны правила переходов через граничные (критические) точки. Для этого реализуется одна итерация двойственного симплексного метода (вернее, двойственный аналог обобщенного метода потенциалов). Из­ вестно, что через конечное число итераций либо найдем смеж­ ное подмножество G^+1, на котором возможно убывание функции F0-), либо обнаружим, что в текущей точке F (l) принимает наименьшее значение. Последнее имеет место, ког­ да любое направление s, позволяющее движение по допусти­ мым точкам, с вектором sk образует тупой угол. Чтобы выя­ вить такие возможности, каждый раз в задаче выбора на­

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

ния. В силу конечности количества базисов, через конечное число переходов по подмножествам 0/? найдется точка, опти­ мизирующая функцию /г(/).

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

Таким образом, за конечное число итераций получим ре­ шение задачи 1.1.

Процесс решения задачи 1.2 отличается от описанного только тем, что после выбора начальных значений параме­ тров <*.j и Qi реализуются алгоритмы построения начального базисного решения и дальнейшей оптимизации имеющегося решения обычной распределительной задачи

58