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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 852. 67
И.Ю. ГРИШИН, канд. техн. наук, РВУЗ & quot-КГУ"- (г. Ялта)
ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ОПРЕДЕЛЕНИЯ ГЛАВНЫХ
ГРАНЕЙ ПРИ РЕШЕНИИ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Рассмотрен алгоритм определения внутреннего многогранника из множества вложенных выпуклых многогранников, заданных системой линейных неравенств. Такой алгоритм может эффективно использоваться при решении задачи линейного программирования методом главных граней, являющего реальной альтернативой симплекс-методу. Приведен пример применения алгоритма, показана его вычислительная эффективность.
Ключевые слова: алгоритм, многогранник, система линейных неравенств, задача линейного программирования, симплекс-метод.
Постановка проблемы. Известен метод решения задачи линейного программирования [1, 2], позволяющий находить гипергрань многогранника, на которой находится точка оптимума. После замены одного из линейных ограничений-неравенств равенством осуществляется снижение размерности исходной задачи и определяется следующая гипергрань, содержащая оптимальное решение. Эта гипергрань является смежной с ранее найденной. Однако при снижении размерности задачи часть из исходных ограничений-неравенств может стать несовместными, что приводит к неправильному определению очередной главной грани и, как следствие, к неверному нахождению оптимальной точки. В общей постановке задача нахождения граней, смежных с заданной гранью (или задача определения внутреннего многогранника из множества вложенных выпуклых многогранников, заданных системой линейных неравенств) в настоящее время не решена [3]. Поэтому имеет смысл использовать достаточно простые эвристические алгоритмы последовательного определения главных граней.
Анализ литературы. Широко известен метод определения совместности системы линейных уравнений [4], состоящий в вычислении ранга матрицы системы и сравнении его с количеством переменных. Данный метод может быть применен и для решения задачи линейного программирования после приведения имеющихся ограничений-неравенств к ограничениям-равенствам. Однако с вычислительной точки зрения этот метод неэффективен, поскольку количество операций, необходимых для его реализации, зависит экспоненциально от размерности задачи и количества ограничений. В работе [5] изложен метод и алгоритм определения совместности систем линейных неравенств, однако он тоже малоприменим для систем большой размерности вследствие своей высокой вычислительной трудоемкости.
Цель статьи — предложить практически реализуемый алгоритм определения совместности систем линейных неравенств для нахождения смежных гиперграней с целью его применения в методе главных граней решения задачи линейного программирования.
Основы эвристического алгоритма. Главная грань и грани смежные с ней [6] показаны на рисунке. При проекции на координатные плоскости смежные грани выбираемой главной грани образуют грани внутреннего многогранника. Прямая, проведенная через внутреннюю точку Р этого многогранника параллельно оси координат, пересекает его грани в точках, имеющих минимальное (по модулю) расстояние по оси координат до точки Р.
Рис. Главная и смежные с ней грани
Поиск оптимальных (квазиоптимальных) решений предложенным способом рассмотрим на примере. В качестве внутренних точек на следующей итерации целесообразно брать точки пересечения этих прямых с выбираемой гиперплоскостью Ьк и проецировать их на координатную плоскость, нормаль которой наиболее близка к нормали грани Ьк, то есть коэффициент при
соответствующем х}- в уравнении гиперплоскости Ц должен быть
наибольшим по модулю.
Для наглядности коэффициенты целевой функции и неравенств записаны в виде таблиц коэффициентов (табл. 1, 2, 4, 5). В таблицах расстояний (табл. 3) в строках даны значения координат х}- точек пересечения прямой Х'-^,
параллельной оси X^, с соответствующими гиперплоскостями. Координаты
смежных граней, имеющих наименьшую удаленность по прямым от точки Р, подчеркнуты.
Пример. Решить задачу распределения ресурсов (предполагается, что исходная система неравенств совместна и не содержит лишних ограничений).
Найти тах г = 3×1 + 4×2 + 8×3 + 5×4 +12×5 + 2×6, п =(3, 4, 8, 5, 12, 2) при ограничениях
Ц: 3х + 2×2 — х + 6×4 + х + х — 24, п = (3, 2, — 1, 6, 1, 1) —
Ц: х + 6×2 + х + 2×6 -18, п2 = (1, 6, 1, 0, 0, 2) —
Ц: х4 + 2×5 -12, п = (0, 0, 0, 1, 2, 0) —
Ц: 3×4 + х5 -12, п4 = (0, 0, 0, 3, 1, 0) —
Ц: 2х + X + х — 24, п5 = (2, 1, 1, 0, 0, 0) —
Ц: 2х + х + 3×6 — 36, п6 = (0, 0, 2, 0, 1, 3) —
Ц6+]: — х] - 0 ] =1,6 •
В табл. 1 представлена запись исходной задачи.
Таблица 1
Исходная задача
х1×2×3×4×5 х6
г 3 4 8 5 12 2
А 3 2 -1 6 1 1 24
Ц2 1 6 1 0 0 2 18
4 0 0 0 1 2 0 12
Ц4 0 0 0 3 1 0 12
Ц5 2 1 1 0 0 0 24
4 0 0 2 0 1 3 36
Ь: х4 = 12 — 2х5
Ью: х5 — 6
На первой итерации находится первая главная грань. Вычисляется проекция по формуле рг^ п = _п. Максимальное значение имеет
_ 5 + 24 29, «_
ргщП = = -^=, то есть первая главная гипергрань 13: х4 + 2×5 = 12.
Исключается переменная х4 = 12 — 2×5. В результате получена табл. 2.
Таблица 2
Исключена переменная х4
х1×2×3×5 хб
2 3 4 8 2 2
3 2 -1 -11 1 -48
Ц2 1 6 1 0 2 18
Ц.0 0 0 0 1 0 6
Ц4 0 0 0 -5 0 -24
Ц5 2 1 1 0 0 24
Цб 0 0 2 1 3 36
2: 6×2 = 18 — х1 — х3 — 2х6
8: -18 + х1 + х3 + 2хб ^ 0
На второй итерации через внутреннюю точку Р (1, 1, 1, 5, 2) проводятся
прямые Х^, параллельные осям Хг, Х2, Х3, Х5, Хб. Подставляя
координаты точки Р, находятся координаты точек пересечения этих прямых с
гиперплоскостями /.,… /, б И координатными ПЛОСКОСТЯМИ /, 7… /, 2. По
координатам точек определяются ближайшие, то есть смежные грани.
Например, для определения точек пересечения прямой Х '-6 с гиперплоскостями подставляются в уравнения табл. 2 значения
Х1 = х2 = X = 1, X = 5 •
Тогда для гиперплоскостей Ц, Ь2, Ь6:
Ц: 3−1 + 2−1 -1−1-11−5 + 1- х6 = 48 ^ х6 = 3 —
Ц?: 1−1 + 6 -1 + 1−1 + 2 — Хб = 18 Хб = 5 —
Ц: 2 -1 + 1- 5 + 3- х = 36 ^ хб =
29
3
Решая аналогичные уравнения для Ц, Ь5, Ц0 получаем хб =
Расстояние от точки Р до гиперплоскости по прямой X- равно Sj = |х- - х°|, где х0 — значение координаты точки Р. Минимальное расстояние Sj соответствует минимальному значению х- при х ¦ & gt- х° и максимальному значению х- при х- & lt- х°. Каждая прямая X'-- пересекается только с одной координатной плоскостью Ь6± (х- = 0), поэтому координата
точки пересечения х- = 0, Sj = |х- - х0| = х'-0.
Для прямой X- значение х° = 2 и минимальные расстояния до точки Р по прямой X6 имеют гиперплоскости Ц (х6 = 3, S6 = |3 — 2 = 1) и Ц (х6 = 0, S6 = |0 — 2 = 2). Аналогично могут быть вычислены расстояния до гиперплоскостей по прямым X-, X-, X-, X-. Результаты вычислений приведены в табл. 3.
Таблица 3
Расстояния до гиперплоскостей на второй итерации
Ц X — 4 4 40 4 4 4 4±
X- 1,33 7 да да 11 да 0
X 2 15 2 да да 21 да 0
X 3 0 7 да да 21 12,5 0
X 5 4,3 да 6 4,8 да 28 0
X 6 3 5 да да да 29/3 0
Из табл. 3 следует, что с гранью Ц являются смежными грани Ц, Ц,
/, 7… /,|0. /,|2. Из смежных граней максимальную в

Статистика по статье
  • 42
    читатели
  • 7
    скачивания
  • 0
    в избранном
  • 0
    соц. сети

Ключевые слова
  • АЛГОРИТМ,
  • МНОГОГРАННИК,
  • СИСТЕМА ЛИНЕЙНЫХ НЕРАВЕНСТВ,
  • ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ,
  • СИМПЛЕКС-МЕТОД,
  • СИСТЕМА ЛіНіЙНИХ НЕРіВНОСТЕЙ,
  • ЗАДАЧА ЛіНіЙНОГО ПРОГРАМУВАННЯ,
  • ALGORITHM,
  • POLYHEDRON,
  • SET OF LINEAR INEQUALITIES,
  • THE LINEAR PROGRAMMING TASK,
  • SIMPLEX-METHOD

Аннотация
научной статьи
по математике, автор научной работы & mdash- Гришин И. Ю.

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

ПоказатьСвернуть
Заполнить форму текущей работой