Алгоритм перебора неотрицательных базисных решений систем линейных уравнений

Метод перебора базисных решений

Лабораторная работа №6

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

Цель работы и задачи работы

Закрепить теоретические сведения о методах решения канонической задачи линейного программирования. Освоить приемы их применения в среде MathCAD.

Теоретические сведения, необходимые для выполнения лабораторной работы

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

Задачей линейного программирования (ЗЛП) называются задачи, в векторно-матричном виде записываемые следующим образом:

(1)

Конструкция в выражении (1) означает, что на ее месте может стоять один из знаков , или =.

n – размерность вектора переменных задачи (число переменных x_i), m – число уравнений и/или неравенств ограничений.

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

Среди различных вариантов постановки ЗЛП выделяют две формы, отличающиеся способом задания ограничений:

1) каноническая (КЗЛП);

2) стандартная (СЗЛР).

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

В стандартной форме все ограничения заданы в виде неравенств, причем число неравенств больше размерности вектора переменных системы (m ³ n+1).

Указанные формы постановки ЗЛП приведены в таблице 2.1.

Формы постановки ЗЛП

Каноническая	Стандартная

Любая форма постановки ЗЛП может быть сведена к указанным двум с помощью следующих преобразований:

1. если в условии задачи ЛП требуется определить максимум функции f(x) , то это эквивалентно нахождению минимума -f(x).

2. В ограничениях типа неревенств возможна замена знака неравенства на противоположный, т.е. неравенство

3. Ограничения в виде неравенства можно заменить ограничением в виде равенства. Пусть ограничение имеет вид:

Вводим дополнительную переменную x_n+1 ³ 0 , тогда

Если знак неравенства противоположный, т,е,

При этом, естественно, увеличивается размерность вектора x.

4. От ограничений в виде равенств можно перейти к ограничениям в виде неравенств следующим образом. Систему из m уравнений с n переменными (m

Методы решения КЗЛП

Определим основные термины, используемые при решении КЗЛП.

Точка, удовлетворяющая ограничениям задачи называется допустимым решением или планом.

Допустимое решение, при котором целевая функция f(x) приобретает минимальное значение называется оптимальнымрешением (оптимальнымпланом),

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

Оставшиеся (n-m) переменных называются свободными переменными.

Решение системы из m уравнений с m базисными переменными при условии равенства нулю свободных (n-m) переменных называется базиснымрешением.

Если базисное решение дает отрицательные значения некоторых переменных, то оно называется недопустимым, а базисное решение с неотрицательными значениями переменных называется допустимымбазиснымрешением.

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

Метод перебора базисных решений

В методе перебора определяются все базисные решения задачи. Для этого необходимо рассмотреть всевозможные случаи сочетания базисных (m штук) переменных. Количество перебираемых вариантов определяется по формуле:

(2)

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

Перебрав все сочетания базисных переменных и, соответственно, определив все базисные решения, среди них выбираются допустимые базисные решения (с неотрицательными переменными).

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

Пример.

Решим методом перебора следующую КЗЛП:

В данной задаче размерность вектора переменных n=4, число уравнений m=2.

Методом перебора необходимо перебрать базисных решений.

В таблице 2.2 представлены сочетания базисных переменных, системы уравнений и базисные решения

К решению примера

№	Сочетание	Система уравнений	Базисное решение	Значение целевой функции
x₁x₂			—
x₁x₃			0.5
x₁x₄			—
x₂x₃			0.25
x₂x₄			—
x₃x₄

Жирным шрифтом выделены допустимые базисные решения.

Среди допустимых базисных решений минимальное значение целевая функция имеет для сочетания 6.

Таким образом, Оптимальное решение:

На рисунке 2.1 приведен фрагмент документа MathCAD, в котором решена рассмотренная задача. Как видно из рисунка методом перебора получено правильное решение.

Алгоритм нахождения неотрицательного решения системы линейных уравнений Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Севостьянов Егор Николаевич, Лепчинский Михаил Германович

В статье рассматривается новый алгоритм для отыскания точного решения задачи линейного программирования. Метод основан на сведении задачи линейного программирования к задаче решения системы линейных уравнений неполного ранга в неотрицательных числах, которая решается через последовательные приближения в специально построенных подпространствах. Доказана сходимость метода за конечное число шагов. Приводятся результаты тестирования алгоритма на данных задачи Кли Минти и на группе случайных тестов.

Algorithm for finding of a non-negative solution for linear system of equations

The new algorithm for finding of the exact solution for the linear programming problem is constructed. The method is based on the converting of the linear programming problem to the problem of solving in nonnegative numbers for a system of linear equations with an incomplete rank. This problem is solved by successive approximations in specially constructed subspaces. The convergence of the algorithm for a finite number of the steps is proved. The algorithm has been tested on the data of the Klee Minty problem and on a set of random tests.

Текст научной работы на тему «Алгоритм нахождения неотрицательного решения системы линейных уравнений»

Челябинский физико-математический журнал. 2016. Т. 1, вып. 2. С. 68-77.

АЛГОРИТМ НАХОЖДЕНИЯ НЕОТРИЦАТЕЛЬНОГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Е. Н. Севостьянов1′», М. Г. Лепчинский2’6

1ЗАО «Диджитал Айрон Пайп», Челябинск, Россия 2 Челябинский государственный университет, Челябинск, Россия «y384@mail.ru; ъшу1Н@сзи.ти

В статье рассматривается новый алгоритм для отыскания точного решения задачи линейного программирования. Метод основан на сведении задачи линейного программирования к задаче решения системы линейных уравнений неполного ранга в неотрицательных числах, которая решается через последовательные приближения в специально построенных подпространствах. Доказана сходимость метода за конечное число шагов. Приводятся результаты тестирования алгоритма на данных задачи Кли — Минти и на группе случайных тестов.

Ключевые слова: алгоритм линейного программирования, неотрицательное ‘решение системы линейных уравнений, линейное неравенство.

Первоначально исследования в области численных методов линейного программирования (ЛП) концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статьи [1] внимание многих исследователей переключилось на методы внутренних точек.

В связи с тем, что не найден сильно полиномиальный алгоритм для задачи ЛП [2, с. 194-205], интерес вызывает изучение иных подходов к построению алгоритмов ЛП. Данная работа посвящена описанию и изучению алгоритма линейного программирования, отличного от алгоритмов метода внутренних точек и симплекс-метода. Отличительной особенностью алгоритма является то, что задача линейного программирования в стандартной форме с помощью комбинирования прямой и двойственной задачи сводится к задаче нахождения неотрицательного решения системы линейных уравнений, которая, в свою очередь, решается через последовательные приближения по направлениям вдоль гиперплоскостей, ограничивающих неотрицательную область пространства Кп. Доказана сходимость алгоритма к точному решению не более чем за 2пи шагов. Предложенный алгоритм можно считать обобщением и развитием идей, высказанных в работе [3].

1. Обозначения и начальный вид решаемой задачи

Договоримся обозначать множество матриц размером т на и над полем К как 1т’п. Единичную матрицу будем обозначать как Е. Под вектором (точкой) условимся понимать вектор-строку, чертой над вектором будем делать различие в обозначении между вектором и скаляром. Векторы из нулей и одной единицы на позиции г будем обозначать как е^. Линейную оболочку множества X будем обозначать как

Задача линейного программирования в стандартной форме имеет следующий

Покажем, как задачу (1) свести к задаче более простого вида:

Ax* = b*, где A G Rm’n и m 0.

По сути, в (2) надо решить систему линейных уравнений неполного ранга в неотрицательных числах.

Ш!аг 1. Комбинация прямой и двойственной задачи. Рассмотрим задачу

Ax* 0>, ограниченный гиперплоскостями Е = £(<ё1. ёп>\<ё>). В дальнейшем нас будут интересовать линейные подпространства данных гиперплоскостей, порождённые векторами из <е>, которые мы будем называть граничными К-плоскостями. Для каждой граничной К-плоскости введём квадратную диагональную матрицу Zi С Кга’га, составленную из единичных и нулевых векторов-строк, причём на главной диагонали матрицы Zi будет стоять единица, если данная единичная вектор-строка принадлежит граничной К-плоскости, и ноль в противном случае. Следовательно, ранг матрицы Zi совпадает с размерностью граничной К-плоскости и равен К. Будем обозначать граничную К-плоскость, порождённую матрицей Zi, как подразумевая, что

граничная К-плоскость является линейной оболочкой строк матрицы Множество решений системы линейных уравнений Аж* = Ь* обозначим как П.

Алгоритм решения системы линейных уравнений неполного ранга Ах1 = Ъ: в неотрицательных числах будет представлять из себя движение точки внутри конуса К к неотрицательному решению системы. Для этого будем последовательно уменьшать расстояние между множеством решений системы линейных уравнений П и рассматриваемой на данном этапе точкой х1-1, не выходя за пределы неотрицательной области К. Нам потребуется известная формула [5, с. 92] ортогональной проекции точки Х0 на множество решений системы линейных уравнений

Хр = Х0 — А'(АА’)-1АХ0 + А*(АА*)-1Ъ*. (5)

Подойдя к какой-либо граничной К-плоскости положительной области К,

будем изменять направление движения вдоль в сторону уменьшения рассто-

яния между и П. Ниже покажем, что для сходимости алгоритма достаточ-

но брать в качестве направления движения наиближайшую к х1-1 точку рассматриваемой граничной К-плоскости расстояние от которой до П минимально на L(Zi). При достижении минимума расстояния от какой-нибудь граничной К-плоскости до П будем искать новое приближение к решению, уходя от данной граничной К-плоскости.

Соответственно, квадрат расстояния от точки Х Е до множества решений

системы линейных уравнений Ахt = Ъ будет определяться формулой

р2^гх*, П) = р2^гх*, Zгxt — At(AAt)-1AZгxt + А1(АА1)-Щ =

= (At(AAt)-1AZгХt — А:(АА:)-1Ъ:)2. (6)

Очевидно, что квадратичная форма (6) является неотрицательной полуопределённой, а значит, выпуклой. Таким образом, для любых двух точек Х,у Е Кга и скаляра а Е [0,1] выполняется неравенство Йенсена

р2(ах + (1 — а)у, П) г. Если мы покажем, что р(х1-1, П) > р(Хк-1, П), то мы покажем, что в ходе работы алгоритма происходит постепенное приближение к П. Если для итерации ] Е <г, г + 1. к - 1>точка Хз = х1-1, то мы совершили движение в сторону уменьшения расстояния, а значит, р(х1-1, П) > р(Хд-1, П). Следовательно, нам надо показать, что существует ] Е <г, г + 1. к - 1>, для которого х1-1 = Хз.

В лемме 2 покажем, что для индекса ] Е <г, г + 1. к - 1>, при котором Х^-1 = х1-1, вектор у — х1-1 не ортогонален пространству £^+1). Отсюда следует, что если мы обозначим проекцию точки уд на множество 2(Zj+1) как к, то мы получим невырожденный прямоугольный треугольник Ау1Нх1-1, а значит, р(Х1-1, П) = р(в, П). Так как р(Х^1, П) = шт^е^—) р(в, П), то ^ 2^^). Отсюда следует, что существует ] Е <г,г + 1. к - 1>, такое, что х1-1 = Хз, а значит, х1-1 = Хк-1.

Покажем теперь, что алгоритм закончит работу за конечное число итераций. Действительно, для любого г Е Л выполняется соотношение р(х1-1, П) = шт^ея^- 1) р(в, П). Но так как мы постепенно уменьшаем расстояние до П, то за конечное число шагов мы найдём минимум на всех К-плоскостях, а значит, доберёмся и до положительного решения за конечное число шагов. □

Лемма 1. Пусть на итерации г матрица Zi = Е. Если неотрицательное решение существует, то 2^+) не ортогональна вектору к = уд — х1-1.

Доказательство. Предположим, что к ортогонален 2^+). Через П проведём гиперплоскость Ф, ортогональную вектору к . Через 2(Zi+1) проведём гиперплоскость Ф, ортогональную вектору к . В силу построений Ф П Ф = 0. Рассмотрим конус неотрицательной области К = <Х | Х = а1(в1 + . + апеп, где а >0>. В дальнейшем покажем, что Ф и К лежат по разные стороны от гиперплоскости Ф (причём К и Ф могут иметь общие точки). Отсюда будет следовать, что П ПК = 0. Тем самым мы покажем, что если существует неотрицательное решение, принадлежащее конусу К, то 2(Zi+1) не ортогональна вектору к . Геометрические построения при доказательстве леммы 1 можно отследить по рисунку на с. 73.

Рассмотрим множество Г’ тех индексов, для координат которых мы обнуляли строки матрицы Zi+1 на шаге (д) алгоритма. Исключим из Г’ все индексы, единичные векторы которых лежат в Ф, и обозначим данное множество как Г. Фиксируем какой-нибудь индекс Г Е Г. Пусть V = Ф П Аёгк, где А Е К. Заметим, что V существует, так как иначе ёгк Е Ф, а мы исключили этот случай.

Произведём перенос точки х1-1 в точку 0 Е Ф. Точка уд Е Ф тогда перейдёт в новую точку и Е Ф, которая является проекцией точки 0 на Ф. Так как Ф || Ф, то для любой точки д из Ф её проекция на Ф будет вычисляться как д +(у1 -Х1-1). Покажем, что знак Гд-й координаты точки уд и знак Гд-й координаты точки и совпадают. Если это не так, то существует точка в Е \у%,и] С Ф, у которой Г-я координата равна нулю. Пусть й — это проекция в на 2(Zi+1). Точка с1 принадлежит области (х1-1, 0) в силу того, что 0 Е 2^+) С Ф и х1-1 Е 2^+) С Ф. Заметим, что Гк-я координата вектора ( в — с1) нулевая, а Гд-я координата вектора (у1 — х1-1) отрицательная, но этого не может быть, так как Ф || Ф. Следовательно, знак Гд-й координаты точки и совпадает со знаком Г-й координаты точки уд и отрицателен.

Покажем, что и Гд-я координата точки V = Ф П АГгк также отрицательна. В силу того, что Ф П Ф = 0, точка V = 0. Пусть Гд-я координата точки V положительна, тогда среди внутренних точек отрезка [й,г>] существует точка I с нулевой Гк-й координатой. Рассмотрим треугольники Д0иР, Д0м/ и ДО/ V. Угол 0м/ прямой, следовательно, угол О/ V тупой. Так как Гд-я координата точки / нулевая, то (О — / , егк) = 0. В силу этого угол Ш / прямой. Отсюда следует, что сумма углов треугольника 0/Р больше 180°. Пришли к противоречию.

Так как Г/г-я координата точки у отрицательна, то луч АгГк, где А ^ 0, лежит на противоположной П стороне относительно гиперплоскости Ф (возможны общие точки Ф и Аегк, где А ^ 0). Данное утверждение справедливо для всех лучей, образованных единичными векторами с индексами из Г. Обозначим выпуклый конус, порождённый единичными векторами с индексами из Г’, как Ф. Очевидно, что К С <х | X = Г + д, / Е £(^+1), д Е Ф>. Отсюда следует, что К Р| П =

существует неотрицательное решение, принадлежащее конусу К, то £(^+1) не ортогонально вектору к .

Графическое построение леммы 1

Лемма 2. Пусть на итерации i матрица Z = E. Тогда если неотрицательное решение существует, то для итерации j ^ i, на которой Xj = Xi-1, граничная К-плоскость £(Zj+1) не ортогональна вектору h = y — Xi-1.

Доказательство. Доказательство проведём по индукции. Базой индукции послужит случай j = i, доказанный в лемме 1. Пусть верно для j = k — 1. Покажем для j = k. Отметим, что точки y и y не совпадают по построению, точка y Е П.

Обозначим проекцию точки y на L(Zj) как yL. Из формулы (5) следует, что такая проекция строится обнулением тех координат, которые обнулены в матрице Zj. Из предположения индукции следует, что p(Xi-1, П) > П) как отношение

длины катета и гипотенузы. Следовательно, Xi-1 = y¡L. Заметим, что отрезок [y, yL] лежит в L(Zj), а для функции (6) на линейном пространстве выполняются следующие неравенства p(Xi-1, П) > p(yj, П).

Далее покажем, что на К-плоскости L(Zj+1) лежит точка, расстояние от которой до П меньше, чем p(Xi-1, П). Отсюда сразу же будет следовать, что граничная К-плоскость £(Zj+1) не ортогональна вектору h = y — Xi-1.

Пусть множество в — это множество тех индексов единичных векторов e¿, которые входят в строки матрицы Zj, но отсутствуют среди строк матрицы Zj+1. Заметим, что координаты с индексами из в точки y неположительны по условиям работы алгоритма. Векторное подпространство L(Zj) С L(Zi+1), проекция вектора y на £(Zi+1) строится обнулением соответствующих координат, а координаты с индексами из в проекции y на L(Zi+1) неотрицательны в силу построений леммы 1, следовательно, координаты с индексами из в точки yL неотрицательны.

Так как Zj = Zj+1, то мощность в больше нуля. Проведём процедуру, уменьшающую мощность в так, чтобы построить точку из £(Zj+1), в которой значение

функции (6) меньше, чем в точке х1-1. Для этого введём следующие обозначения: щ = уз, и1 = у^ = ^.

После переобозначений получим следующие необходимые для проведения процедуры уменьшения мощности в условия: отрезок [у^и^ С 2(^), расстояние р(х1-1, П) > р(у1, П), расстояние р(х1-1, П) > р(и1, П), координаты с индексами из в точки ;и1 неположительны, а координаты с индексами из в точки и1 неотрицательны.

Процедура, уменьшающая мощность в: найдём точку у2 отрезка [У1,и1>, которая первой при движении от точки у1 в сторону точки и1 обнуляет хотя бы одну координату, соответствующую индексам из в. Удалим из множества в индексы, которые обнулились в точке у1. Обозначим матрицу ^^ как матрицу, совпадающую с матрицей Zj+1. Добавим ^^ единичные векторы-строки, индексы которых присутствуют в в. Далее обозначим проекцию точки у на 2^2) как и2.

Покажем, что у нас выполнены все условия, чтобы повторить процедуру для отрезка [у2,и2] С 2(Z,2). Действительно, так как выполняется неравенство Йенсе-на, то р(х1-1, П) > р(у2, П). Отсюда следует, что на 2^2) есть точка минимума функции (6), не совпадающая с х1-1, следовательно, р(х1-1, П) > р(и2, П), а значит, х1-1 = и2. Координаты с индексами из в точки у2 неположительны по построению. Векторное подпространство 2(Z2) С 2^+), проекция вектора у на 2^+) строится обнулением соответствующих координат, а координаты с индексами из в проекции у1 на 2(Zi+1) неотрицательны в силу построений леммы 1, следовательно, координаты с индексами из в точки и2 неотрицательны.

Пусть на повторе процедуры под номером в мы пришли к ситуации, когда мощность в равна нулю. Очевидно, что в конечна, так как конечна мощность в и на каждом повторе процедуры гарантированно происходит уменьшение мощности в. Заметим, что на повторе в матрица = Zj+1, следовательно, У3+1 Е [у8,й8] С 2(Zj+1). По построению р(х1-1 , П) > р(у3+1, П), поэтому граничная К-плоскость 2^з+1) не ортогональна вектору к = у1 — х1-1. □

5. Численные эксперименты

Целью численных экспериментов ставились поиск задач, на которых алгоритм показал бы время работы, наиболее близкое к полученной оценке, и проверка алгоритма на устойчивость. Для этих целей алгоритм был проверен на задаче Кли — Минти [6], на данных которой симплекс-метод Данцига совершает обход по всем вершинам симплекса за 2п шагов, а также и на группе случайных тестов.

Реализация алгоритма была осуществлена без потери точности в классе рациональных чисел библиотеки ОМР [7]. Для проверки численной устойчивости в тестах отслеживались два параметра — в и 7, где в — это минимальное количество бит, необходимых для кодирования любой переменной матрицы входных данных Аг(ААг)-1А, а 7 — это максимальное количество бит, которое потребовалось для кодирования любой промежуточной координаты вектора х1, вектора уд или коэффициента а из шага (б) алгоритма.

Результаты практической проверки для задачи Кли — Минти сведены в табл. 1. Первая строка п таблицы содержит размерность задачи Кли — Минти, во второй строке Б приводится экспериментальное число шагов предложенного алгоритма для данной размерности. Данные третьей и четвёртой строк соответствуют экспериментальным данным по параметрам в и 7, а пятая строка является отношением в, которое позволяет определить соотношение количества бит, необходимых для кодирования промежуточных и входных данных.

Проверка на данных задачи Кли — Минти

n 9 10 11 12 13 14 15 16 17 18 19 20

S 54 63 72 82 92 103 114 126 138 151 164 178

в 120 134 158 170 200 220 236 262 276 303 330 348

Y 224 270 302 346 390 436 468 522 563 604 655 697

Y в 1.86 2.01 1.91 2.03 1.95 1.98 1.98 1.99 2.03 1.99 1.98 2.00

Для инициализации случайных тестов квадратная матрица размерами п на п, отвечающая системе линейных неравенств, и вектор целевой функции заполнялись случайными знаковыми 32-битными целыми. Сгенерированная таблица симплекс-методом Данцига проверялась на наличие решения и в случае существования оптимума отдавалась на проверку предложенному в работе алгоритму. Для каждого рассматриваемого размера проводилось по тысяче случайных тестов. Результаты тестов сведены в табл. 2. Первая строка п таблицы содержит размерность случайной задачи. Во второй строке Б приводится максимальное экспериментальное число шагов алгоритма для данной размерности, которое было обнаружено при тестировании. Данные третьей и четвёртой строк соответствуют экспериментальным данным по параметрам в и 7, которые отвечают максимальному обнаруженному значению дроби 7/в для данной размерности, значение которой занесено в пятую строку.

Проверка на случайных тестах

n 7 8 9 10 11 12 13 14 15

S 45 50 54 63 61 72 77 82 89

в 768 912 1028 1136 1256 1368 1504 1624 1736

Y 2822 3227 3837 4027 4527 4418 4630 5424 5879

Y в 3.67 3.53 3.73 3.54 3.60 3.22 3.07 3.34 3.38

Низкое значение дроби 7/в и отсутствие роста её значения при увеличении размерности задачи на случайных экспериментальных данных свидетельствуют о хорошей численной устойчивости предлагаемого алгоритма.

Из табл. 1 видно, что на данных задачи Кли — Минти предложенный алгоритм показывает преимущество по количеству шагов над алгоритмом симплекс-метода Данцига. Из данных табл. 2 видно, что набору случайных тестов не удалось найти задачу, которая по числу итераций приближалась бы к значению 2nn. Однако результаты данных тестов нельзя интерпретировать в пользу полиномиальности предлагаемого алгоритма, так как и симплекс-метод Данцига, являющийся полиномиальным в среднем алгоритмом [2, с. 142-147], тоже не показал на этих тестах «плохих» результатов. Поэтому вопрос о наличии примеров, подтверждающих экс-поненциальность предложенного алгоритма, остаётся открытым.

1. Дикин, И. И. Итеративное решение задач линейного и квадратичного программирования / И. И. Дикин // Докл. АН СССР. — 1967. — Т. 174, № 4. — С. 745-747.

2. Schrijver, A. Theory of Linear and Integer Programming / A. Schrijver. — Wiley-Interscience series in discrete mathematics. — Chichester : John Wiley & Sons, 1986. — xi+471 p.

3. Моллаверди, Н. Методы решения задач линейной оптимизации большой размерности : дис. канд. физ.-мат. наук / Н. Моллаверди. — М. , 2005. — 96 с.

4. Karmarkar, N. A new polynomial-time algorithm for linear programming / N. Karmarkar // Combinatorica. — 1984. — № 4. — Р. 373-395.

5. Розенфельд, Б. А. Многомерные пространства / Б. А. Розенфельд. — М. : Наука, 1966. — 648 с.

6. Klee, V. How good is the Simplex algorithm? / V. Klee, G. J. Minty // Inequalities: III, ed. O. Shisha. — New York : Academic Press, 1972. — P. 158-175.

7. Nikolaevskaya, E. Programming with Multiple Precision / E. Nikolaevskaya, A. Khimich, T. Chistyakova. — Studies in Computational Intelligence. — Vol. 397. — Richmond, USA : Springer, 2012. — 234 p.

Поступила в ‘редакцию 08.04-2016 После переработки 21.05.2016

Сведения об авторах

Севостьянов Егор Николаевич, ведущий инженер-программист (руководитель группы математического моделирования), ЗАО «Диджитал Айрон Пайп», Челябинск, Россия; e-mail: y384@mail.ru.

Лепчинский Михаил Германович, кандидат физико-математических наук, доцент кафедры вычислительной математики, Челябинский государственный университет, Челябинск, Россия; e-mail: myth@csu.ru.

Chelyabinsk Physical and Mathematical Journal. 2016. Vol. 1, iss. 2. P. 68-77.

ALGORITHM FOR FINDING OF A NON-NEGATIVE SOLUTION FOR LINEAR SYSTEM OF EQUATIONS

E.N. Sevostyanov1″, M.G. Leptchinski26

1ZAO «Digital Iron Pipe», Chelyabinsk, Russia 2 Chelyabinsk State University, Chelyabinsk, Russia ay384@mail.ru; bmyth@csu.ru

Keywords: algorithm of linear programming, non-negative solution of linear system of equations, linear inequality.

1. Dikin I.I. Iterativnoe reshenie zadach lineynogo i kvadratichnogo programmirovaniya [Iterative solving of linear and quadratic programming problems]. Doklady Akademii Nauk SSSR [USSR Academy of Science Reports], 1967, vol. 174, no. 4, pp. 745-747. (In Russ.).

2. Schrijver A. Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics. Chichester, John Wiley & Sons, 1986. xi+471 p.

3. Mollaverdi N. Metody resheniya zadach lineynoy optimizatsii bol’shoy razmernosti [Methods for solving of linear optimization problems with large dimension. Thesis]. Moscow, 2005. 96 p. (In Russ.).

4. Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984, no. 4, pp. 373-395.

5. Rozenfel’d B.A. Mnogomernye prostranstva [Multidimensional spaces]. Moscow, Nauka Publ., 1966. 648 p. (In Russ.).

6. Klee V, Minty G.J. How good is the Simplex algorithm? Inequalities: III. New York, Academic Press, 1972. Pp. 158-175.

7. Nikolaevskaya E., Khimich A., Chistyakova T. Programming with Multiple Precision. Studies in Computational Intelligence, vol. 397. Richmond, USA, Springer, 2012. 234 p.

Accepted article received 08.04.2016 Corrections received 21.05.2016

Подробный разбор симплекс-метода

Пролог

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

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

§1. Постановка задачи линейного программирования

Определение: Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n- мерного пространства, задаваемых системами линейными уравнений и неравенств.

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

Неравенства с отрицательными умножаем на (-1).
Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
Делаем замену переменных:

Если , то
Если — любой, то , где

Замечание: Будем нумеровать по номеру неравенства, в которое мы его добавили.

Замечание: ≥0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

Определение: Точка называется угловой точкой, если представление возможно только при .

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит (т.е. – не внутренняя точка).

Графический способ решения задачи ЛП показывает, что нахождение оптимального решения ассоциируется с угловой точкой. Это является основной концепцией при разработке симплекс-метода.

Определение: Пусть есть система m уравнений и n неизвестных (m

источники:

http://cyberleninka.ru/article/n/algoritm-nahozhdeniya-neotritsatelnogo-resheniya-sistemy-lineynyh-uravneniy

http://habr.com/ru/post/474286/