Содержание к диссертации
Введение
1. Метод решения прямой задачи линейного программирования с больпіим числом неотрицательных переменных 13
1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования 13
1.2. Итерационный метод нахождения решений прямой и двойственной задач (метод ПД) 23
1.3. Конечная сходимость итерационного метода 26
1.4. Обобщенный метод Ньютона 28
1.5. Нахождение проекции точки на множество решений систем линейных уравнений 29
2. Метод решения двойственной задачи линейного программирования с больпіим числом переменных 31
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования 31
2.2. Итерационный метод нахождения решений двойственной и прямой задач (метод ДП) 38
3. Программная реализация и вычислительные эксперименты 40
3.1. Генераторы тестовых задач 40
3.2. Программная реализация метода ПД в системе MATLAB 44
3.3. Результаты численных экспериментов с программой EGM1 46
3.4. Программная реализация метода ДП в системе MATLAB 62
3.5. Результаты численных экспериментов с программой EGM2 63
3.6. Результаты численных экспериментов с помощью программ нахождения нормальных решений линейных систем 69
Выводы 74
Приложение 75
Цитированная литература 91
- Итерационный метод нахождения решений прямой и двойственной задач (метод ПД)
- Нахождение проекции точки на множество решений систем линейных уравнений
- Итерационный метод нахождения решений двойственной и прямой задач (метод ДП)
- Результаты численных экспериментов с программой EGM1
Введение к работе
Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. Укажем лишь несколько опубликованных на русском языке мо-нографий [2], [4], [5], [13], [18] - [22], [26], [29], [30], [33], [36], [42], [43]. Огромный интерес к задачам ЛП определяется прежде всего их экономической содержательностью, многочисленными практическими приложениями и применением в качестве вспомогательных процедур во многих численных методах нелинейной оптимизации. Несмотря на продолжающееся повышение производительности вычислительной техники, всегда актуальным остается возможность решения задач линейного программирования очень большой размерности.
Первоначально исследования в области численных методов ЛП концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статей [24], [14], [15], [16], [52] внимание многих исследователей переключилось на методы внутренних точек. При этом возникли новые формулировки задач ЛП и появились новые формы задания необходимых и достаточных условий оптимальности (см. например, [60], [17], [49]). Укажем на специальный выпуск журнала Optimization Methods & Software [61], целиком посвященный методу внутренней точки, а также обзор [50].
В работах советских математиков в 70-х годах активно разрабатывался подход к задачам ЛП, основанный на использовании метода внешних штрафных функций (квадратичная функция штрафа). Хорошо известны работы в этом направлении, которые проводились А.С. Антипиным, Ф.П. Васильевым, Е.Г. Гольштейном, И.И. Ереминым, Б.Т. Поляком, Б.С. Разумихиным, Н.В. Третьяковым и другими исследователями из МГУ, ИПУ, ЦЭМИ, ИММ УрО РАН, ВЦ РАН [3], [13], [51], [32]-[35], [42], [44]. Примерно в это же время в США близкие исследования проводились О.Мангасарьяном и его сотрудниками. В их работах [53]-[55] основное внимание уделялось нахождению нормальных решений в задачах ЛП,
т.е. решений, обладающих минимальной евклидовой нормой. Широкое распространение этот подход в то время не получил. Только в последнее время появились свидетельства о его перспективности с вычислительной точки зрения [57], [58]. Связано это с использованием быстро сходящегося обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной непрерывно дифференцируемой штрафной функции. У нее не существует матрица Гессе. Однако для такой штрафной функции можно построить обобщенный метод Ньютона, введя обобщенную матрицу Гессе. В работах [57], [58], [51] доказана конечная глобальная сходимость обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной функции. Минимизация этой штрафной функции, примененной к двойственной задаче ЛП, дает возможность получить точное нормальное (с минимальной евклидовой нормой) решение прямой задачи, начиная с некоторого конечного значения коэффициента штрафа.
Заметим, что, как правило, большие задачи ЛП имеют не единственное решение. Указанные методы представляют ценность тем, что дают различные решения в случае неединственности. Так, симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод квадратичной штрафной функции, будучи примененным к двойственной задаче, дает возможность получить нормальное решение прямой задачи при конечном значении коэффициента штрафа.
Весьма актуальным является обобщение метода квадратичной штрафной функции для получения проекции произвольной точки на множество решений прямой или двойственной задач ЛП. Задача нахождения проекции заданной точки на множество решений часто может иметь важный содержательный смысл для приложений. Так, пусть известен некоторый оптимальный план, который из-за изменившихся условий уже не только не оптимальный, но может даже оказаться и недопустимым. Желательно найти такой новый оптимальный план, который
был бы ближайшим к первоначальному плану.
Работа посвящена созданию методов нахождения проекции заданной точки на множество решений задачи ЛП с большим числом переменных, программной реализации, проведению вычислительных экспериментов (в том числе и на практической задаче).
В главе 1 предлагается метод решения прямой задачи ЛП с большим числом (до нескольких десятков миллионов) неотрицательных переменных и средним числом ограничений-равенств (несколько тысяч). В 1.1 рассматривается задача нахождения проекции заданной точки на множество решений прямой задачи. Вместо обычно применяемой кусочно квадратичной штрафной функции предлагается использовать вспомогательную функцию, сходную с модифицированной функцией Лагранжа (см., например [31], [1]), зависящую от некоторого параметра /?. Этот подход характеризуется следующим: начиная с некоторого фиксированного значения параметра (3* после однократной безусловной максимизации вспомогательной функции при всех /3 > /3* по простой формуле вычисляется точная проекция заданной точки на множество решений прямой задачи ЛП (теорема 1.1). В этой теореме при определенных предположе-нях получена формула для порогового значения /3*. Эта величина может быть отрицательна. В этом случае расстояние от заданной проектируемой точки до множества решений прямой задачи совпадает с расстоянием от этой точки до допустимого множества прямой задачи. Показана связь предложенной вспомогательной функции с методами регуляризации и квадратичным штрафом, примененным к двойственной задаче. Подставляя найденную проекцию во вспомогательную функцию и, максимизируя ее, находим некоторое точное решение двойственной задачи ЛП (теорема 1.2).
В 1.2 приводится итерационный метод нахождения решений прямой и двойственной задач ЛП. Этот метод является прямым-двойственным методом (ПД-метод). В процессе итераций метод дает допустимые прямые точки и недопустимые двойственные. Формально в нем не требуется
знания порогового значения параметра (3*. Но, если выбранное значение /3 меньше порогового значения, то метод решает задачу ЛП более, чем за две итерации. Метод за конечное число шагов находит некоторое решение прямой задачи, но не проекцию начальной точки на множество решений прямой задачи.
При некоторых дополнительных предположениях доказана сходимость метода и в 1.3. Доказана конечная сходимость.
В 1.4 приводятся сведения об обобщенном методе Ньютона ([57], [58], [51]), который рекомендуется применять для безусловной максимизации вспомогательной функции, если прямая задача ЛП имеет среднее число ограничений (до 4 тыс.). Обобщенный метод Ньютона для данной задачи глобально сходится за конечное число шагов.
В 1.5 предложенный метод переносится на задачу нахождения проекции заданной точки на множество решений систем линейных уравнений с неотрицательными переменными.
Во второй главе рассматривается аналогичный подход для решения двойственных задач ЛП с большим числом переменных (до нескольких десятков миллионов) и средним числом ограничений-неравенств (до 4 тыс.). Здесь модифицированная функция Лагранжа зависит от параметра а. В 2.1 приводится оценка для порогового значения параметра а*, начиная с которого, в результате однократной максимизации вспомогательной функции на положительном ортанте, находится точная проекция заданной точки на множество решений двойственной задачи. В 2.2 приводится итерационный метод решения двойственной и прямой задач (метод ДП). В процессе итераций получаются допустимые двойственные точки и недопустимые прямые. Как и в первой главе, этот метод может быть использован со значением параметра а, меньшим, чем пороговое значение. Однако расчеты при этом не дают проекцию начальной точки на множество решений двойственной задачи. В этом методе максимизация производится на положительном ортанте. Для снятия ограничений на знак переменных применялась квадратичная штрафная функция. Это
позволило здесь так же применить обобщенный метод Ньютона.
Итерационный метод нахождения решений прямой и двойственной задач (метод ПД)
Вместо отыскания проекции ж на X поставим задачу нахождения какой-нибудь точки х из множества решений X . Ниже покажем, что, благодаря такому упрощению, в предлагаемом ниже итеративном процессе не требуется знать пороговое значение параметра /? . Функция (1.10) может рассматриваться как модифицированная функция Лагранжа для двойственной задачи (D). Введем следующий итерационный процесс где параметр /3 фиксирован, а вектор pk+i определяется из решения следующей задачи безусловной максимизации Этот итерационный процесс является конечным и дает точное решение прямой задачи (Р) и точное решение двойственной задачи (D). Теорема 1.3. Пусть множество решений X прямой задачи (Р) непусто. Тогда при любом /3 0 и при любой начальной точке XQ итерационный процесс (1.34) сходится к х X за конечное число шазов ш. Формула « = рш+\/(3 дает точное решение двойственной задачи (D). Заметим, что хш = х Є X является проекцией точки хи-\ на множество решений X задачи (Р). После того, как с помощью метода (1.34), (1.35) найдено некоторое решение і Є It) можно решить исходную задачу (1.3) об определении проекции точки х на множество X . Для этого определим / = сТх и решим задачу безусловной минимизации (1.8). В результате по (1.7) найдем проекцию х точки х на множество X решений прямой задачи (Р). Если в (1.34), (1.35) сделать замену переменных р = (Зи, то приходим к методу модифицированной функции Лагранжа для решения задачи ЛП, предложенному в [31], [1] Доказательство конечной сходимости метода (1.36), (1.37) дано в [1], [31]. Здесь приведем более простое доказательство конечной сходимости метода (1.36), (1.37) при некоторых дополнительных предположениях. Теорема 1.4. Если множество решений U задачи (D) непусто, то процесс (1.36) при дополнительном условии ограниченности последовательности ик из (1.37) сходится монотонно по норме к одному из решений прямой задачи (Р), т.е. хк — х при к — со для всеххо R\. Доказательство. В (1.36) хк+\ может рассматриваться как решение задачи проектирования точки хк + /3(АТик+і — с) на положительный ортант, т.е. как решение следующей задачи Из необходимых и достаточных условий минимума этой задачи получаем, что минимум по х достигается в точке хк+ъ задаваемой формулой(І.Зб). В точке и — ик+і выполняется следующее необходимое условие минимума для задачи (1.37) Учитывая (1.36), это условие, запишем в виде Применяя принцип линеаризации к задаче (1.38), получим, что в точке х = хк+і имеет место вариационное неравенство Взяв здесь х в качестве х, получим неравенство Выпишем функцию Лагранжа для задач (JP) и (D) Прямое и двойственное решения ж , и задач (Р) и (D) являются седло-вой точкой функции Лагранжа, т.е. справедливы неравенства Система неравенств (1.42) может быть переписана в следующей эквивалентной форме необходимых и достаточных условий оптимальности задач (Р) и (D) Умножим векторное равенство — Ь+Ахк+і = 0m из (1.39) скалярно на вектор и — U&+1 и —6 + Ac = 0т - на вектор ик+\ — гг . После сложения полученных результатов и элементарных преобразований приходим к выражению Сопоставляя (1.41), (1.46) и (1.45), получим
Положим х\ = Xk, Х2 = х , х$ = #&+i- Тогда из (1.48) с учетом (1.47) имеем следует, что с ростом к величина \\хк — х \\2 монотонно убывает. Просуммируем это неравенство от к = 0 до к = К, получим \\хк+і - 2 + 2 Iki+i - ХІ\\2 Ижо - ж 2. Из найденного неравенства следует ограниченность траектории ж.кч-і — # 2 #о — # 2 а также сходимость ряда: ]Г!І О ІІ ї+і — хг\\2 и» следовательно, стремление к нулю величины \\xk+i — Xk\\2 — 0, Jb — со. Так как последовательность хк ограничена по доказанному, а ик ограничена по условиям теоремы, то существует элемент х , и , такой, что хкі —їх икі — w при / — со, и при этом Цж +і — xh\\2 0. Рассматривая выражения (1.39), (1.40) для всех к{ — со и переходя к пределу, получим: Так как эти выражения совпадают с (1.43), (1.44), то ж = ж Є Я", т.е. любая предельная точка последовательности хк является решением задачи. Условие монотонности убывания величины \\хк — х \\ обеспечивает единственность предельной точки, т.е. сходимость хк — х при к — со. В отличие от хк, последовательность ик может иметь много предельных точек и все они являются решениями исходной задачи. Теорема доказана. Используя систему неравенств (1.42) и следуя [30], введем понятие острого минимума. Для этого достаточно усилить правое неравенство системы (1.42). Введем следующее определение. Решение х прямой задачи ЛП (Р) назовем острым минимумом, если это решение подчинено условию где 7 0. Условие (1.49) можно рассматривать как усиление (1.44). Покажем, что при дополнительном условии остроты минимума прямой задачи (Р) последовательность хк, порождаемая методом (1.36), имеет конечное число элементов, т.е. метод сходится за конечное число итераций. Теорема 1.5. Если решение прямой задачи (Р) представляет собой острый минимум (1.49), то процесс (1.36), (1.37) сходится к решению прямой задачи (Р) за конечное число итераций. Доказательство. Учитывая (1.46) и условие острого минимума (1.49) при х = Xk+i, из неравенства (1.41) получаем Предполагая, что \\хк+і — х \\ ф 0 для всех х, из (1.50) получаем Эта оценка противоречит ранее доказанному утверждению \\хк+і — хк\\ — 0, к — оо. Выход из противоречия состоит в том, чтобы признать, что утверждение \\хк+\ — ж+ ф 0 для всех к неверно. Последнее означает, что существует такой номер к/, что хк} - решение задачи (Р). Теорема доказана. Безусловная максимизация в (1.9) и (1.35) может выполняться любым методом, например, методом сопряженного градиента. Но, как показал О.Мангасарьян, для безусловной максимизации вогнутой дифференцируемой кусочно квадратичной функции особенно эффективен обобщенный метод Ньютона [57], [58]. Приведем краткое описание этого метода. Задачи (1.9) и (1.35) запишем в виде Здесь S является вогнутой кусочно-квадратичной дифференцируемой функцией вектора р. У этой функции обычная матрица Гессе не существует. Действительно, градиент функции S(p, р, х) не дифференцируем. Но для этой функции можно определить обобщенную матрицу Гессе, которая является m х тп симметричной, отрицательно полуопределенной матрицей следующего вида где через D$(z) обозначена пхп диагональная матрица с г-м диагональным элементом z\ равным 1, если (х-\- Атр — /Зс)г 0, и равным 0, если [х + Атр — @с)г 0, г = 1,... ,п. Так как обобщенная матрица Гессе может быть вырожденной, используется следующее модифицированное ньютоновское направление где 5 - есть малая положительная величина (обычно при расчетах полагалось 6 = Ю-4) и Im - единичная матрица порядка т. В этом случае модифицированный метод Ньютона имеет вид Критерий окончания его работы полагался следующим Разумеется, что при численной реализации метода Ньютона не обращалась матрица. Вместо этого решалась следующая система линейных уравнений О.Мангасарьян исследовал сходимость обобщенного метода Ньютона для безусловной минимизации аналогичной выпуклой кусочно квадратичной дифференцируемой функции с выбором шага по правилу Арми-хо. Доказательство конечной глобальной сходимости обобщенного метода Ньютона можно найти в [57], [58], [51]. Многочисленные результаты расчетов с использованием этого варианта метода Ньютона будут приведены в третьей главе.
Нахождение проекции точки на множество решений систем линейных уравнений
Будем искать проекцию заданной точки на множество решений двойственной задачи ЛП аналогично тому, как это делалось в параграфе 1.1. Из множества решений У двойственной задачи (D) выделим решение й , ближайшее в евклидовой норме к некоторому заданному вектору й, т.е. найдем единственное решение и задачи строго выпуклого квадратичного программирования Здесь / - оптимальное значение целевой функции задачи (D). Для задачи (2.1) введем функцию Лагранжа Здесь у Є R+ и а Є R1 — множители Лагранжа, а й рассматривается как фиксированный вектор. Двойственная к (2.1) задача имеет вид max max min L(u,y,a,u). (2.2) Приведем условия Куна-Таккера для задачи (2.1) Из (2.3) получаем решение внутренней задачи минимизации в (2.2) Подставляя (2.4) в функцию Лагранжа Ь(и,у,а,й), получаем двойственную функцию Функция L(y,a, и) вогнута, квадратична и дважды непрерывно дифференцируема по своим аргументам. Двойственная задача (2.2) сводится к решению внешней задачи максимизации max max L(y,a,it). (2.5) Решив задачу (2.5), найдем оптимальные ума. После их подстановки в (2.4) получаем проекцию й , т.е. решение задачи (2.1). Приведем необходимые и достаточные условия оптимальности для задачи (2.5) Здесь вектор и определяется по формуле (2.4). Эти условия оптимальности выполнены тогда и только тогда, когда и Є / и и = й . Как и в случае задачи (1.8), задача максимизации (2.5) содержит неизвестную априори величину / - оптимальное значение целевой функции задачи ЛП. Однако, задачу (2.5) так же можно упростить, избавившись от этого недостатка, и решать следующую упрощенную задачу максимизации на положительном ортанте где вектор й и скаляр а фиксированы, а функция S(y, а, й) определена следующим образом Будем считать, что прямая задача (Р) имеет единственное, быть может, вырожденное решение х . В этом решении х+ 0/ - совокупность положительных компонент, I т. В случае невырожденного решения I = т. Обозначим индексное множество, соответствующее положительным компонентам вектора ж , через I+. Если ж - вырожденное решение, то двойственная задача (D) имеет неединственное решение, и в точке [ж , к ] выполнены условия Куна-Таккера для задачи (Р), которые в подробной записи имеют вид: BLxi = b. Здесь матрица A = [ В \ N ] представлена в соответствии с разбиением вектора невязок г; = с — АТй ограничений двойственной задачи (D) на нулевые [v , vf ] = vf = 0 и положительные г Od компоненты, где k = l + s m, d n — к. Используя это разбиение, представим вектор ж в виде: xj = [xf ,х+ ]. В свою очередь, матрица В представлена в соответствии с разбиением вектора rcf на положительные х% и нулевые жf компоненты, т.е. В = [ BL Bg ]. В силу единственности ре единственное, быть может, вырожденное решение х . В этом решении х+ 0/ - совокупность положительных компонент, I т. В случае невырожденного решения I = т. Обозначим индексное множество, соответствующее положительным компонентам вектора ж , через I+.
Если ж - вырожденное решение, то двойственная задача (D) имеет неединственное решение, и в точке [ж , к ] выполнены условия Куна-Таккера для задачи (Р), которые в подробной записи имеют вид: BLxi = b. Здесь матрица A = [ В \ N ] представлена в соответствии с разбиением вектора невязок г; = с — АТй ограничений двойственной задачи (D) на нулевые [v , vf ] = vf = 0 и положительные г Od компоненты, где k = l + s m, d n — к. Используя это разбиение, представим вектор ж в виде: xj = [xf ,х+ ]. В свою очередь, матрица В представлена в соответствии с разбиением вектора rcf на положительные х% и нулевые жf компоненты, т.е. В = [ BL Bg ]. В силу единственности решения ж матрица В состоит из к m линейно независимых столбцов, т.е. ее ранг равен к. Для дальнейшего потребуется вектор г) Є Rk, определенный следующим образом: rj = (ВтВ) 1(св — Втй). Заметим, что если к = т, то вектор rj легко приводится к виду rj = .В-1 (и — и). Кроме того, определим следующую величину { Теорема 2.1. Пусть множество решений / задачи D непусто, ранг матрицы В, соответствующей нулевым компонентам вектора-невязок двойственных ограничений v , вычисленных в решении w , равен к т. Решение й задачи (2.1) шения ж матрица В состоит из к m линейно независимых столбцов, т.е. ее ранг равен к. Для дальнейшего потребуется вектор г) Є Rk, определенный следующим образом: rj = (ВтВ) 1(св — Втй). Заметим, что если к = т, то вектор rj легко приводится к виду rj = .В-1 (и — и). Кроме того, определим следующую величину { Теорема 2.1. Пусть множество решений / задачи D непусто, ранг матрицы В, соответствующей нулевым компонентам вектора-невязок двойственных ограничений v , вычисленных в решении w , равен к т. Решение й задачи (2.1) представимо в виде
Итерационный метод нахождения решений двойственной и прямой задач (метод ДП)
Излагаемый в данном параграфе метод (1.10) нахождения решений двойственной и прямой задач ЛП аналогичен методу из параграфа (1.2). Теперь, вместо отыскания проекции й на множество решений Z7 двойственной задачи (D), поставим задачу нахождения произвольной точки w Є / . Благодаря такому упрощению, не требуется, чтобы параметр а превышал априори неизвестное пороговое значение см . Функция S(y, а, и) может рассматриваться как модифицированная функция Лагранжа для задачи (D). Введем следующий итерационный процесс Здесь параметр а фиксирован, а вектор Ук+і определяется из решения следующей задачи минимизации на положительном ортанте Этот итерационный процесс является конечным и дает точное решение прямой задачи (Р) и точное решение двойственной задачи (D). Теорема 2.4. Пусть множество решений / двойственной задачи (D) непусто. Тогда при любых а 0 и начальной точке щ итерационный процесс (2.26) сходится к и Є U за конечное число шагов v. Формула х = уи+\/а дает точное решение прямой задачи (Р). Заметим, что uv = и Є / является проекцией точки uv-\ на множество решений / задачи (D). Если в (2.26),(2.27) сделать замену переменных у = ах, то приходим к методу модифицированной функции Лагранжа для решения задачи ЛП Доказательство конечной сходимости метода (2.28), (2.29) дано в [31], [1]. Перенос доказательства этого свойства для метода (2.26), (2.27) очевиден. Заметим, что для решения задачи минимизации квадратичной функции на положительном ортанте непосредственно использовать метод Ньютона затруднительно. Поэтому при решении задачи минимизации (2.27) условие неотрицательности снималось с помощью квадратичного штрафа и обобщенный метод Ньютона применялся к следующей задаче безусловной минимизации Здесь г - положительный коэффициент штрафа. Как известно, точное решение задачи (2.27) получается из (2.30) только в пределе при г — +0О. Но, как показали численные эксперименты, решение задач ЛП получалось с достаточной точностью за приемлемое время, если задача (2.30) решалась один раз при достаточно большом значении коэффициента штрафа г. Для проведения вычислительных экспериментов с разработанными методами были созданы генераторы тестовых задач. Для тестирования метода из первой главы решались сгенерированные случайным образом разрешимые прямые задачи (Р) с большим числом неотрицательных переменных (до 50 млн.) и средним числом ограничений типа равенств (до четырех тысяч), т.е. имело место условие п » т. Этот же генератор порождал разрешимые двойственные задачи (D) с большим числом переменных (до 50 млн.) и средним числом ограничений типа неравенств (до нескольких тысяч), т.е. имело место т» п. Генератор задач ЛП работал следующим образом. Задавались числа тип, определяющие количество строк и столбцов матрицы А, и р -плотность заполнения матрицы
А ненулевыми элементами. В частности, значение р — 1 означает, что случайным образом генерировались все элементы матрицы А, а значение р = 0.01 указывает, что в матрице А генерировались только 1% элементов, а остальные полагались равными нулю. Элементы матрицы А задавались случайным образом из интервала [-50 , 50]. Решение ж прямой задачи (Р) и решение и двойственной задачи (D) генерировались следующим образом. Полагалось, что в векторе ж содержится п — Зт нулевых компонент, а остальные компоненты выбирались случайным образом из интервала [0,10]. Половина компонент вектора и полагалась равными нулю, а остальные выбирались случайным образом из интервала [-10,10]. Решения ж и и использовались для вычисления коэффициентов целевой функции с и правых частей Ъ задачи (Р). Векторы бис определялись по формулам случайным образом из интервала 0 у г 9г. В приведенных ниже результатах расчетов считалось, что все 7г — 1 и в1 = 10. Заметим, что при 7 близких к нулю, величина г = (с— Ати )г = Тогда условия Куна-Таккера (3.4), (3.5) позволяют сгенерировать задачу (3.1) с известным нормальным решением хдеп. Генератор задач работал следующим образом. Задавались числа m и п, определяющие количество строк и столбцов матрицы А, и р - плотность заполнения матрицы А ненулевыми элементами. Элементы матрицы А задавались случайным образом из интервала [-50 , 50]. Компоненты оптимального вектора множителей Лагранжа и выбирались случайным образом из интервала [1,100]. Тогда нормальное решение хдеп вычислялось по формуле (3.5), а вектор Ъ вычислялся по формуле b = Ахдеп. Генератор представлен в виде следующей программы: Code 3. Генератор линейных систем уравнений с неотрицательными переменными Этот же генератор с небольшими очевидными изменениями использовался для построения систем линейных уравнений с известным нормальным решением хдеп. При этом вместо формулы (3.5) применялась формула Генератор представлен в виде следующей программы: Предлагаемый метод решения прямой и двойственной задач ЛП сочетает итерационный процесс (1.34) и обобщенный метод Ньютона, примененный для решения задачи (1.35). Метод реализован в системе MATLAB 6.5. в виде программы EGM1. Критерием окончания итераций (1.34) было условие Критерием окончания процесса безусловной максимизации по методу Ньютона (1.54) было следующее условие
Обычно бралось toll = 10 12 , Ш2 = Ю-7. В конце расчетов вычислялись чебышевские нормы векторов невязок Если х 0п, то равенство нулю невязок является необходимым и достаточным условием оптимальности в задачах (Р) и (D). Условия х 0П автоматически обеспечиваются формулой (1.34). Ниже приводится текст программы EG Ml, реализующей метод (1.34). Метод (1.34) реализован в виде программы EGM1. Для вычислений использовался в основном компьютер с процессором Pentium-4, тактовой частотой 2.6 ГГц, оперативной памятью 1 Гб. Результаты вычислений случайным образом сгенерированных 16 задач ЛП приведены в таблице 3.1. В таблице указаны размерности т , п и р — плотность ненулевых элементов матрицы А, Т - время решения задачи ЛП в секундах, / -количество шагов, сделанных обобщенным методом Ньютона на первой итерации (при к = 0). В пятом, шестом и седьмом столбцах приведены чебышевские нормы невязок и разность оптимальных значений целевых функций прямой и двойственной задач ( см. формулы (3.9) ). При вычислении произведения матриц AD (z)AT для ускорения расчетов, а также в случае задач особо высокой размерности, из-за нехватки оперативной памяти матрица А разбивалась на В блоков и умножение производилось поблочно. Соответствующее количество блоков В приведено в последнем столбце таблицы. Всюду полагалось /3 = l,toll = 10 12 (точность расчетов обобщенного метода Ньютона). Оказалось, что во всех примерах выполнялось условие Р ft - Таким образом, нормальное решение прямой задачи (Р) = х\ было получено из процесса (1.34) за одну итерацию. Но для проверки условия (3.7) делалась ещё одна дополнительная итерация. На второй итерации при к = 1 из (1.34) найдена близкая точка Х2, что обеспечивало выполнение условия (3.7).
Результаты численных экспериментов с программой EGM1
Ориентировочные значения нормативной эффективности всех ограниченных ресурсов принимаются в соответствии с рекомендациями государственных плановых органов или плановых органов корпорации. Для каждого модельного хозяйства необходимо отобрать из исходного перечня сельскохозяйственной техники тракторы и машины, обеспечивающие своевременное выполнение и необходимое взаимное согласование всех работ в течение года при наименьших затратах. Таким образом определятся общегосударственный (общекорпоративный) оптимальный перспективный парк тракторов и машин, его зональные составные части и оптимальные парки тракторов и машин для сельскохозяйственных предприятий. Решался вариант модели, ориентированный на модельное хозяйство из некоторой природно - климатической зоны государства или корпорации с целью определения оптимального перспективного парка тракторов и машин. Пусть календарный год разбит на Т периодов с номерами t = 1, Т. Выполнению подлежат / различных г-работ (г = 1, J) в объеме А{. Каждая г -работа должна осуществляться в пределах части или всего допустимого агросрока, охватывающего -периоды в количестве ТЇ, принадлежащие множеству ТІ (t ТІ). Для модельного хозяйства заданы множества J; jf-агрегатов, которые потенциально могут выполнять в нем различные г-работы (j Є «/,), причем число j-агрегатов, предназначенных для г-работы, равно Ji. Каждый j-агрегат имеет определенный состав, который может быть качественно охарактеризован известной номенклатурой fc-средств механизации и сельскохозяйственных рабочих, образующих множество Kj (к Є Kj). В данном j-агрегате насчитывается Kj различных /г-средств механизации и сельскохозяйственных рабочих разных специальностей. Общий список -средств механизации и сельскохозяйственных рабочих в количестве К также задан (к = 1, К). Количественный состав агрегата характеризуется числами bijj , каждое из которых показывает, сколько средств механизации (или рабочих) &-вида заняты в j-агрегате при выполнении г-работы. Для каждого -периода (t Є TJ) может быть записан баланс использования одноименных /:-средств механизации (или рабочих) в модельном хозяйстве: общее искомое количество Xk -средств механизации, определяемое по наиболее напряженному периоду, для любого і-периода равно сумме простаивающих х\ (из-за отсутствия работы) и работающих в со ставе различных j-агрегатов на разных г-работах bijkxjj, где x\j i=1jeJi — искомое количество j-агрегатов, занятых в -периоде на г-работе. Таким образом, балансы использования одноименных средств механизации (или рабочих) имеют вид: Один j-агрегат (j Є «Л) способен выполнить в течение -периода (t Є ТІ) в модельном хозяйстве определенный объем г-работы, равный а -.
Следовательно, искомое количество х\ агрегатов сможет выполнить за f-период объем г-работы, равный a\jx\j. Сумма таких объемов по всем -периодам {t Є Т{), составляющим допустимый агросрок выполнения г-работы всеми возможными j-агрегатами (j Є Ji), должна быть равна Д-объему г-работы в модельном хозяйстве. Это составляет обязательное условие выполнения заданных объемов работ в допустимые агросроки: Многие работы в модельном хозяйстве необходимо согласовывать между собой по срокам и объемам выполнения. Возможно взаимное согласование двух работ, работы с некоторой группой работ и двух различных групп работ. Последний случай наиболее общий. Ему соответствует наличие группы г о-работ, принадлежащих множеству IQ («о Є /о) которая должна согласовываться с группой г о-работ, принадлежащих множеству /J (г0 JJ). Согласование работ может быть полным или частичным, синхронным или асинхронным. При полном асинхронном согласовании работ, принадлежащих множествам IQ И Г0, выполнение определенного суммарного объема работ г о Є IQ В некотором -периоде должно непременно сопровождаться выполнением соответствующего (с учетом коэффициента приведения размерностей ді0і 0) суммарного объема работ г0 Є IQ В периоде (t + ТІ0І О), где ТІ0І — число целых периодов, определяющее относительный сдвиг во времени согласуемых работ (предполагается, что продолжительность всех периодов выполнения согласуемых работ одинакова). При синхронном согласовании работ т,-0 = 0, т.е. это частный случай асинхронного согласования. Если работы г о Є IQ проводятся в периоды t Є TJ0, условие полного их согласования с работами г 0 Є IQ, выполняемыми в периоды t Є Т (со сдвигом ТІ0І О относительно работ г о), можно для каждого -периода записать в следующем виде: При частичном согласовании работ, принадлежащих множествам IQ И IQ, необходимо, чтобы объем работ г о Є IQ, выполненный за -период и все периоды, ему предшествовавшие, был не менее объема работ г0 Є IQ, выполненного за то же число периодов (с соответствующим сдвигом или без него, поскольку очевидно, что к частично согласованным работам также применимы понятия асинхронности и синхронности). Обозначив начальные периоды выполнения работ г о Є Jo и г 0 Є IQ соответственно через to и 0) условие частичного согласования работ для каждого t-периода можно записать в следующем виде:
