Решение: Подставляя в неравенство координаты точек, будем иметь

АЛГЕБРАИЧЕСКОЕ И ГЕОМЕТРИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

 

Великий новгород – 2015

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

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

 

I. ПОЛУПЛОСКОСТИ И ПОЛУПРОСТРАНСТВА

 

Из аналитической геометрии известно, что каждому линейному уравнению (первой степени) а₁х₁+а₂х₂=b в двумерном векторном пространстве (на плоскости) соответствует прямая (рис.1), перпендикулярная вектору (а₁,а₂), и каждому линейному уравнению а₁х₁+а₂х₂+а₃х₃=b в трехмерном пространстве соответствует плоскость, перпендикулярная вектору (а₁, а₂, а₃) (рис. 2).

По аналогии будем называть плоскостью в n –мерном пространстве совокупность всех точек (х ₁, х ₂, …, х _n), удовлетворяющих уравнению

а₁х₁ + а₂х₂ + …+ а_nх_n = b    (1)

Плоскость (1) называют гиперплоскостью в n- мерном пространстве. Эта плоскость перпендикулярна к вектору (а₁,а₂,…,а_n).

Прямая на плоскости делит последнюю на две части, называемые полуплоскостями. Плоскость в пространстве делит все пространство на две части, называемые полупространствами. На рис.1 заштрихована одна полуплоскость. На рис.2 – одно полупространство. Полуплоскости и полупространства определяются соответственно неравенствами

а₁х₁ + а₂х₂ < b          или         а₁х₁ + b₂х₂ > b;

а₁х₁ + а₂х₂ + а₃х₃ < b      или        а₁х₁ + а₂х₂ + а₃х₃ > b.

 

Пример 1. Рассмотрим полупространство, определяемое неравенством

х₁ + 5х₂ + 2х₃ < 10.

Определить, принадлежит ли ему начало координат О(0,0,0) и точка М (4, 2, 10).

Решение: Подставляя в неравенство координаты точек, будем иметь

0 + 5* 0 + 2* 0 < 10,       4 + 5* 2 + 2* 10 > 10

(выполняется)                    (не выполняется)

Следовательно, начало координат принадлежит рассматриваемому полупространству, а точка М не принадлежит указанному полупространству (рис. 3)

 

Плоскость х₁+5х₂+2х₃=10, отсекающая на осях координат соответственно отрезками 10, 2 и 5, перпендикулярна вектору {1, 5, 2}.

Замечание. Сама плоскость а₁х₁+а₂х₂+…+а_nх_п=b может быть присоединена к одному из полупространств. Тогда вся совокупность точек п- мерного пространства будет разделена на два вида: точки, для которых а₁х₁+а₂х₂+…+а_пх_п<=b и точки, для которых а₁х₁+а₂х₂+…+а_пх_п>b.

II. ВЫПУКЛЫЕ ТЕЛА

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

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

 

 

Рис. 4

 

Рассмотрим на плоскости многоугольник, лежащий по одну сторону от каждой прямой, с помощью которой он образован.

Рис. 5

 

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

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

 

Рис. 6

 

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

На рис.7 прямые АВ, СD, EF для заштрихованного многоугольника будут опорными.

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

 

Рис. 7

 

III. СИСТЕМА ЛИНЕЙНЫХ НЕРАВЕНСТВ

 

 

Рассмотрим линейную систему m  неравенств с двумя переменными:

a_i1x₁ + a_i2x₂ ≤ b_i, i = 1,2,…,m (1),

где a_i1, a_i2, b_i – заданные числа.

Каждое из этих неравенств определяет одну из двух полуплоскостей с граничной прямой a_i1x₁+a_i2x₂=b_i,, которая перпендикулярна вектору (a_i1, a_i2).

Каждая пара чисел (x₁,x₂), удовлетворяющая всем неравенствам этой системы, называется решением данной системы.

Пример 1. Неравенство 2х₁ + х₂ ≤ 120 определяет полуплоскость (рис. 8). Этому неравенству удовлетворяют координаты каждой точки, лежащей в заштрихованной части полуплоскости. Граничная прямая 2х₁ + х₂=120 перпендикулярна к вектору =(2, 1)

Пример 2. Четыре неравенства  

х₁ ≥ 0;       x₂ ≥ 0;

 2x₁ + x₂ < 120;        x₁ + 1,5x₂ < 120

определяют часть плоскости, образующую многоугольник (рис. 9).

 

 

 

Пример 3. Шести неравенствам

- х₁  ≤ 0; - x₂ ≤ 0;           -x₁ ≤ 10; x₁ - x₂ ≤ 60

x₁ + x₂ < 120;                     x₁ + 1,5x₂ < 120

соответствует тоже множество точек, что и в примере 2. Третье и четвертое неравенство могут быть исключены без изменения множества решений. Прямая x₁ - x₂=60 имеет одну общую точку с четырехугольником и является опорной.

Пусть задана система с п – переменными

a_i1x₁ + a_i2x₂ + … + a_inx_n ≤ b_i;   i = 1,2 … m; m <n (3).

По аналогии можно сказать, что каждое из этих неравенств определяет в п – мерном пространстве полупространство с граничной плоскостью:

 

a_i1x₁ + a_i2x₂ + … + a_inx_n = b_i;    i = 1,2,…,n

Совокупность точек в п- мерном пространстве, удовлетворяющих одновременно всем неравенствам, будем называть «многогранником решений».

Замечание: Если данной системе не удовлетворяет ни одна точка п – мерного пространства, то система неравенств называется несовместной.

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