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

Рассмотрим каноническую задачу линейного программирования. Перепишем её в векторной форме: найти минимум функции L=CX при условиях

A 1 x 1 +A 2 x 2 +…+Anxn=B,

(5.4)

где C=(с ₁ ;с ₂ ;…;с_n), X=(х ₁ ;х ₂ ;…;х_n); CX – скалярное произведение векторов; А ₁ ,…,А_n и В – m -мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

.

Определение 5.1. План X=(х ₁ ;х ₂ ;…х_n) называется опорным планом канонической задачи линейного программирования, если система векторов A_j, входящих в разложение (5.4) с положительными коэффициентами, линейно независима.

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

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

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

Теорема 5.1. Множество планов канонической задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов канонической задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

Теорема 5.3. Если система векторов А ₁ ,А ₂ ,…,А_k (k ≤ n) в разложении (5.4) линейно независима и такова, что А ₁ х ₁ +А ₂ х ₂ +…+А_kx_k = B, где все x_j ≥0, то точка X=(х ₁ ;х ₂ ;…;х_k; 0;…;0 ) является вершиной многогранника решений.

Теорема 5.4. Если X = (х ₁ ;х ₂ ;…х_n) – вершина многогранника решений, то вектора A_j, соответствующие положительным x_j в разложении (5.4), линейно независимы.

Сформулированные теоремы позволяют сделать следующие выводы.

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

Вершину многогранника решений, в которой целевая функция принимает экстремальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более 2-х переменных или задача, записанная в форме канонической, содержит не более 2-х свободных переменных, т.е. n-r ≤2, где n – число переменных, r – ранг матрицы, составленной из коэффициентов в системе ограничений задачи.

5.7 Нахождение решения задачи линейного программирования на основе её геометрической интерпретации

Найдём решение задачи (записанной в форме стандартной), состоящей в определении максимального значения функции L=c ₁ x ₁ +c ₂ x ₂ при условиях

a_{i 1} x ₁ + +a_{i 2} x ₂ ≤b_i (i= 1 ,…,k),

x_j≥ 0 (j= 1,2 ).

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость с граничными прямыми a_{i 1} x ₁ +a_{i 2} x ₂ =b_i (i= 1, …,k), х ₁ = 0 и х ₂=0. В том случае, если система неравенств совместна, область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений (многогранником, когда n ≥3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция L принимает максимальное значение (для стандартной задачи линейного программирования). Эта точка существует тогда, когда многоугольник решений не пуст, и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня с ₁ х ₁ +с ₂ х₂=h (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать её в направлении вектора =(с ₁ ;с ₂ ) до тех пор, пока она не пройдёт через последнюю её общую точку с многоугольником решений. Координаты указанной точки и определят оптимальный план данной задачи.

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

Из рисунка 5.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка AB. На рисунке 5.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рисунке 5.4 – случай, когда система ограничений задачи несовместна. Последние 3 случая – это особые случаи.

Рисунок 5.4 – Случай 4

Рисунок 5.3 – Случай 3

Рисунок 5.2 – Случай 2

Рисунок 5.1 – Случай 1

Отметим, что нахождение минимального значения линейной целевой функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня с ₁ х ₁ +с ₂ х ₂ =h передвигается не в направлении вектора =(с ₁ ;с ₂ ), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении её минимального значения.

Итак, нахождение решения задачи линейного программирования на основе её геометрической интерпретации включает следующие этапы:

1. Строят прямые, уравнения которых получают в результате замены в ограничениях знаков неравенств на знаки точных равенств.

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

3. Находят многоугольник решений.

4. Строят вектор =(с₁;с₂).

5. Строят прямую с₁х₁+с₂х₂=h, проходящую через многоугольник решений.

6. Передвигают прямую с₁х₁+с₂х₂=h в направлении вектора, в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Рассмотрим пример.

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

Таблица 5.3 – Условия задачи оптимального использования сырья

Вид сырья	Нормы расхода сырья (кг) на одно изделие	Общее количество
	A	B	сырья (кг)
I II III
Прибыль от реализации одного изделия (руб.)

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

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

Общая прибыль от реализации изделий вида А и изделий вида В составит F =30 + 40.

Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.

Решим сформулированную задачу геометрическим способом. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдём соответствующие прямые:

Эти прямые изображены на рисунке 5.5. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли её координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенством 12 +4 <300. Для этого, построив прямую 12 +4 =300 (пр. I), возьмём какую-нибудь точку, принадлежащую одной из полученных полуплоскостей, например, точку O(0;0). Координаты этой точки удовлетворяют неравенству: 12, значит, полуплоскость, которой принадлежит точка O(0;0), определится неравенством 12.

Это и показано стрелками на рисунке 5.5.

Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи.

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

Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение. Чтобы найти указанную точку, построим вектор и прямую 30, где h – некоторая постоянная такая, что прямая 30имеет общие точки с многоугольником решений. Положим, например, h =480 и построим прямую 30 (рисунок 5.5). Точки пересечения с осями.

А

BBBBBBВDD

С

D

C

X2

(V

(IV)

(II)

12х1 + 4х2 = 300 (I)

4x1 + 4x2 = 120 (II)

30x1 + 40x2 = 480

30x1 + 40x2 = 1080

3x1 + 12x2 =252 (III)

X1

Рисунок 5.5 – Геометрический метод решения примера 5.1

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

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

Найдем координаты точки В как точки пересечения прямых II и III. Следовательно, её координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений, получим =12, =18. Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную = руб.

Вообще, с помощью графического метода может быть решена такая задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если n и m связаны соотношением n-m =2.

Действительно, пусть поставлена каноническая задача линейного программирования: найти минимальное значение линейной функции Z = при ограничениях

где все уравнения линейно независимы и выполняется соотношение n-m= 2.

Используя метод Гаусса, производим m исключений, в результате которых базисными неизвестными оказались, например, m первых неизвестных, а свободными – два последних и, т.е. система ограничений приняла вид:

(4.6)

(j= 1,2,…, n).

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные переменные - неотрицательные (, j= 1,2,…, n),отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу:

Найти минимальное значение линейной функции Z= при ограничениях

Преобразованная задача содержит две неизвестных; решая её геометрическим способом, находим оптимальные значения и, а затем, подставляя их в (5.4), находим оптимальные значения.