Математическое моделирование

§ 4.  Геометрия задачи линейного программирования.

4.1.  Выпуклое множество  точек.

      В школьном курсе математики выпуклым назывались многоугольники,

целиком расположенные по одну сторону от прямых, на которых лежат их стороны.

    

                               а)                б)

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

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

      Согласно  определению, рисунок а) – является выпуклым, а рисунок б) – нет.

      Среди точек множества выделяют внутренние, граничные и угловые.

      Df. Точка множества называется внутренней, если в некоторой её окрестности содержатся только точки данного множества (т. М).

      Df. Точка множества называется граничной, если в любой её окрестности содержатся точки, принадлежащие данному множеству и не принадлежащие ему (т. N).

      Df. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству (т. В).

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

      !!! Если фигура ограничена только прямыми или отрезками, то число её угловых точек конечно. !!!

      В случае криволинейных границ фигура содержит бесконечное множество  угловых точек. Отсюда определение:

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

      Замечание.

     Df. Множество точек называется замкнутым, если оно включает все граничные точки.

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

  Мы рассмотрели выпуклое множество точек на плоскости и в пространстве. Аналитически такие точки изображаются упорядоченной парой (тройкой) чисел (х₁, х₂) (или (х₁, х₂, х₃)).  Понятие точки можно обобщить, если подразумевать под точкой (или вектором) упорядоченный набор n чисел (х₁, х₂, …, х_n), в котором числа х₁, х₂, …, х_n называются координатами (компонентами) точки (или вектора). Множество всех точек Х = (х₁, х₂, …, х_n) – {X} образует n-мерное пространство (Rⁿ). При n больше 3, точки и фигуры n-мерного пространства не имеют реального геометрического смысла, и все исследования объектов этого пространства необходимо  проводить в аналитической форме. Однако и в этом случае используются геометрические понятия для облегчения представления об объектах n-мерного пространства.

      Df. Пусть имеем две точки в Rⁿ :

Х⁽¹⁾ = (х₁⁽¹⁾, х₂⁽¹⁾, …, х_n⁽¹⁾) и Х⁽²⁾ = (х₁⁽²⁾, х₂⁽²⁾, …, х_n⁽²⁾). 

Отрезком [Х⁽¹⁾ Х⁽²⁾] в Rⁿ называется множество точек Х = (х₁, х₂, …, х_n), удовлетворяющих условию: X = aX⁽¹⁾ + (1-a)X⁽²⁾, где a – некоторое действительное число, причём  0 £ a £ 1.

      Обобщением  понятия отрезка для нескольких (m) точек является их выпуклая комбинация.

      Df. Точка Х в Rⁿ называется выпуклой линейной комбинацией нескольких (m) точек Х⁽¹⁾, Х⁽²⁾, …, Х^(m) если выполняется следующее условие :

                                                                                         _m

X = a₁X⁽¹⁾ + a₂X⁽²⁾ +…+ a_mХ^(m) и a_j ³ 0, j = 1,. . m,    åa_j = 1.

Например:

X = 1/6X⁽¹⁾ + 1/3X⁽²⁾ + 1/2X⁽³⁾ – выпуклая линейная комбинация точек X⁽¹⁾,X⁽²⁾,X⁽³⁾.

X = 1/6X⁽¹⁾ - 1/3X⁽²⁾ - 1/2X⁽³⁾ – линейная комбинация, но невыпуклая.

X = 1/6X⁽¹⁾ + 1/3X⁽²⁾ + 1/3X⁽³⁾ – линейная комбинация, но невыпуклая.

      Очевидно, что при m = 2, отрезок является выпуклой линейной комбинацией двух точек - его концов.

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

      Имеет место следующая теорема:

Теорема. Выпуклый m-мерный многогранник является выпуклой линейной комбинацией своих угловых точек (вершин).

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

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

4.2.  Основные теоремы  линейного программирования.

      В ЗЛП представляет интерес система  m линейных уравнений с n неизвестными, у которой число независимых уравнений m (или, что тоже самое ранг матрицы системы r) меньше числа неизвестных n:       m < n (или r < n). В этом случае система имеет бесчисленное множество решений.

      Любые m переменных системы называются базисными (основными), если определитель матрицы их коэффициентов (минор, состоящий из коэффициентов при этих переменных) отличен от нуля. Тогда остальные      (n - m) переменных называются свободными (или не основными).

      Выразив базисные переменные через свободные, получим общее решение системы.

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

     Замечание. Число базисных решений конечно, так как оно равно числу групп базисных  переменных не превосходящих число сочетаний C_n^m.

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

      Теорема 1. (Геометрия системы ограничений ЗЛП).

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

      Теорема 2. (Фундаментальная).

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

     Теорема 3. (Геометрическая интерпретация допустимого базисного решения).

     Каждому допустимому базисному решению  ЗЛП соответствует вершина многогранника решений и наоборот: каждой вершине многогранника решений соответствует допустимое базисное решение. 

      Следствие из теорем 2 и 3. Если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из допустимых базисных решений. 

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

4.3.  Геометрическое изображение  системы ограничений. Линии уровня целевой функции.

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

      Рассмотрим  ЗЛП на плоскости:

      Пусть имеем ЗЛП в стандартной форме  с двумя переменными (n=2):

найти решение Х^*=(х₁^*, х₂^*), которое удовлетворяет следующим условиям:

      a₁₁x₁ + a₁₂x₂ £ b₁,

     a₁₂x₁ + a₂₂x₂ £ b₂,

     ……………………

     a_m1x₁ + a₂₁x₂ £ b_m

  (2)     x₁ ³ 0, x₂ ³ 0

и которое  доставляет оптимальное значение  функции (3) F = с₁х₁ + с₂х₂ ® max (min).

      С геометрической точки зрения система  неравенств (1) – это пересечение  полуплоскостей вида a_i1x₁ + a_i2x₂ £ b_i i = 1, m, границами которых являются прямые a_i1x₁ + a_i2x₂ = b_i. Неравенства (2) также соответствует полуплоскостям, одна из которых расположена справа от оси ординат, другая - над осью абсцисс.

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

      Пусть геометрическим изображением системы  ограничений (1), (2) является многоугольник  ABCDE (Рис.1). Геометрически решение задачи (1) – (3) заключается в том, что среди точек этого многоугольника необходимо найти такую точку, в которой линейная функция (3) принимала бы максимальное (минимальное) значение.