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

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

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

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

Итак, требуется найти максимальное (минимальное) значение целевой функции

L = ® max (min)

при ограничениях

(1)

x₁ ³ 0, x₂ ³ 0, ... , x_r ³ 0. Здесь k£m£n.

Если все переменные неотрицательны x_j ³ 0 (j=1,2,…,n), система ограничений (1) состоит лишь из неравенств, т.е. k=m – такая ЗЛП называется стандартная (симметричная) задача линейного программирования: необходимо максимизировать (минимизировать) линейную функцию от нескольких переменных L= ® max (min) при ограничениях: , i=1, 2, ... ,m.

x₁ ³ 0, x₂ ³ 0, ... , x_n ³ 0,

Векторная форма записи: L=CX® max (min) при ограничениях A₁x₁+A₂x₂+…+A_nx_n£ B, X³ 0,

где С=(C₁,C₂,...,C_n) - вектор коэффициентов целевой функции, Х=( x₁,x₂,…,x_n),

СХ – скалярное произведение,

А₁= , А₂= ,…,А_n= , В= - векторы, состоящие соответственно из коэффициентов при неизвестных и свободных членов.

Матричная форма записи.

Элементы таблицы a_ij образуют матрицу А размером m х n; b_i выразим вектором ограничений B=(b₁,b₂,...,b_m), x_i - вектором X=(x₁,x₂,...,x_n), коэффициенты целевой функции - вектор C=(C₁,C₂,...,C_n).

В соответствии с правилом умножения матрицы на вектор каждое из m выражений, стоящих в левой части неравенств, представляет собой координату вектора AX. Систему неравенств можно переписать следующим образом: A×X £ B.

Выражение C₁x₁+C₂x₂+××××+C_nx_n запишем в виде скалярного произведения двух векторов CX.

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

найти L=C X® max (min) при ограничениях A×X £ B, X ³ 0 .

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

Если система ограничений (1) состоит лишь из равенств, т.е. k=0 – такая ЗЛП называется каноническая (основная) задача линейного программирования:

найти максимум (минимум) линейной функции от нескольких переменных:

L= ® max (min) при ограничениях

, i=1, 2, ... ,m, x₁ ³ 0, x₂ ³ 0, ... , x_n ³ 0,

В матричной записи: L=CX® max (min) при ограничениях A×X = B, X ³ 0 .

В векторной записи: L=CX® max (min) при ограничениях A₁x₁+A₂x₂+…+A_nx_n= B, X³ 0.

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

Покажем, например, как привести стандартную задачу к канонической форме. Рассмотрим линейное неравенство с n неизвестными

. (1)

Для приведения неравенства к равенству необходимо к его левой части прибавить неотрицательную величину . (2)

В результате получаем линейное уравнение, содержащее n+1 переменную:

. (3)

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

Теорема. Каждому решению =(b₁,b₂,…,b_n) неравенства (1) соответствует единственное решение =(b₁,b₂,…,b_n, b_n+1) уравнения (3) и неравенства (2), и, наоборот, каждому решению уравнения (3) и неравенства (2) соответствует единственное решение неравенства(1).

Доказательство. Пусть - решение неравенства (1), тогда а₁b₁+a₂b₂+…+a_nb_n £b.

Перенося левую часть этого неравенства в правую и обозначая выражение в правой части через b_n+1, т.е. 0£b-( а₁b₁+a₂b₂+…+a_nb_n )= b_n+1,

получаем, что решение =(b₁,b₂,…,b_n, b_n+1) удовлетворяет уравнению (3) и неравенству (2). Действительно, и

а₁b₁+a₂b₂+…+a_nb_n + b_n+1= а₁b₁+a₂b₂+…+a_nb_n +[ b-( а₁b₁+a₂b₂+…+a_nb_n )]=b.

Пусть удовлетворяет уравнению (3) и неравенству (2), т.е.

а₁b₁+a₂b₂+…+a_nb_n + b_n+1=b и .

Тогда, отбрасывая в левой части равенства неотрицательную величину b_n+1, получаем неравенство а₁b₁+a₂b₂+…+a_nb_n £b.

Отсюда следует, что - решение неравенства (1).

¨

В каждое из m неравенств системы ограничений стандартной задачи ведем новые неотрицательные переменные x_n+1, x_n+2,..., x_n+m, и рассмотрим следующую каноническую задачу: найти максимальное значение целевой функции

L = C₁x₁+C₂x₂+ ... + C_nx_n +0×x_n+1 + 0×x_n+2 + ××× +0×x_n+m ® max

при ограничениях:

x₁ ³ 0, x₂ ³ 0, ... , x_n, x_n+1, x_n+2, ... , x_n+m ³ 0.

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

Еще проще процесс сведения канонической задачи к стандартной - надо лишь каждое уравнение из системы ограничений заменить двумя неравенствами:

a_i1x₁ + a_i2x₂ + ××× + a_inx_n = b_i Û a_i1x₁ + a_i2x₂ + ××× + a_inx_n £ b_i,

a_i1x₁ + a_i2x₂ + ××× + a_inx_n ³ b_i.

Если на переменную x_j общей ЗЛП не накладывается условие неотрицательности, то для того, чтобы общую задачу свести к стандартной, нужно положить x_j = u_j - v_j, где u_j, v_j - новые переменные, и наложить условия u_j ³ 0, v_j ³ 0. Это возможно, т.к. любое число может быть записано как разность двух положительных чисел.

Тот случай, когда в задаче требуется минимизировать линейную форму C₁x₁+C₂x₂+ ... + C_nx_n, легко свести к задаче максимизации: следует рассмотреть задачу нахождения максимума функции -С₁x₁-C₂x₂- ... -C_nx_n.

Терминология задач линейного программирования.

Линейная функция L=CX = C₁x₁+C₂x₂+ ... + C_nx_n, подлежащая максимизации (или минимизации), называется целевой функцией.

Вектор X=(x₁, x₂, ... , x_n), удовлетворяющий всем ограничениям задачи линейного программирования, называется допустимым вектором (решением) или планом.

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

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

Максимальное значение d=CX^* целевой функции называется значением задачи.

План X=(x₁, x₂, ... , x_n) называется опорным, если векторы A_i (i=1,2, ... , m), входящие в разложение A₁x₁+A₂x₂+…+A_nx_n = B с положительными коэффициентами x_i, являются линейно независимыми.

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

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

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

Решение ЗЛП связано с понятием выпуклого множества.

Выпуклые множества

Пусть на плоскости х₁Ох₂ заданы две точки А₁(x₁⁽¹⁾,x₂⁽¹⁾) и А₂(x₁⁽²⁾,x₂⁽²⁾), определяющие прямолинейный направленный отрезок . Определим координаты произвольной внутренней точки А(x₁, x₂) данного отрезка, выразив их через координаты конечных точек отрезка A₁ и A₂. Заметим, что векторы
=(x₁-x₁⁽¹⁾, x₂-x₂⁽¹⁾) и =(x₁⁽²⁾-x₁⁽¹⁾,x₂⁽²⁾-x₂⁽¹⁾) параллельны и одинаково направлены, поэтому =t( ), где 0 £ t £ 1, или x₁-x₁⁽¹⁾=t(x₁⁽²⁾-x₁⁽¹⁾), x₂- x₂⁽¹⁾=t(x₂⁽²⁾-x₂⁽¹⁾).

Отсюда получаем систему уравнений

Раскрыв скобки в уравнениях системы, сгруппировав члены относительно координат точек, получаем

Обозначив 1-t = l₁, а t = l₂, получим

.

Заметим, что l₁ ³ 0, l₂³0 и l₁+l₂=1, так как 0 £ t £ 1. Таким образом координаты точки А являются суммами одноимённых координат точек А₁ и А₂, умноженными на числа l₁ и l₂. Такое представление координат точки называется выпуклой линейной комбинацией точек А₁ и А₂ и может быть записано в следующем виде:

А=l₁А₁+l₂А₂;

l₁³0, l₂³0, l₁+l₂=1.

При l₁=1 и l₂=0 точка А совпадает с концом отрезка А₁, при l₁=0 и l₂=1 - с концом отрезка А₂. Таким образом, если t пробегает все значения от 0 до 1, то точка А описывает отрезок .

Точки А₁ и А₂ называются угловыми ( крайними ) токами отрезка .

Пусть имеется n точек А_1, А_2,…А_n. Точка А - выпуклая линейная комбинация, если выполняются условия

А=l₁А₁+l₂А₂+…+l_nА_n; l_j³0, (j=1,2,…,n) , l₁+l₂+…+l_n=1.

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

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

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

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

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

Замкнутым называется множество, содержащее все свои граничные точки.

Замкнутое множество может быть ограниченным и неограниченным.

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

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

Теорема 1. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.

Доказательство.

Для доказательства ограничимся случаем двух множеств.

Пусть F - пересечение выпуклых множеств F₁ и F₂ (см. рис.). Возьмем в F две произвольные точки A₁ , A₂ и соединим их прямолинейным отрезком. Отрезок принадлежит F₁ и F₂ , так как они - выпуклые множества; этот же отрезок принадлежит и множеству F, так как оно является общей частью F₁ и F₂. Следовательно, F - выпуклое множество.¨

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

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

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

Выпуклым многогранником называется замкнутое ограниченное выпуклое множество n-мерного пространства с конечным числом угловых точек.

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

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

Рассмотрим теорему о представлении выпуклого многогранника.

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

Доказательство.

Рассмотрим многогранник, имеющий n вершин. Пусть для простоты n=3, т.е. в качестве многогранника возьмем треугольник А₁А₂А₃. Сначала докажем, что любая точка треугольника удовлетворяет теореме. В треугольнике А₁А₂А₃ возьмем произвольную точку А и через нее проведем отрезок (см. рисунок).

А₂

А₄

А₁ А₃

Т. к. точка А принадлежит отрезку , то она – выпуклая линейная комбинация его концов, т.е. А=l₁А₁+l₄А₄; l₁³0, l₄³0, l₁+l₄=1. (*)

Точка А₄ принадлежит отрезку , следовательно, является выпуклой линейной комбинацией, т.е. А₄=l₂А₂+l₃А₃; l₂³0, l₃³0, l₂+l₃=1. (**)

Подставляя (**) в (*), получаем

А=l₁А₁+l₄(l₂А₂+l₃А₃)= l₁А₁+l₂l₄А₂+l₃l₄А₃.

Полагая l₁= t₁, l₂l₄=t₂, l₃l₄=t₃, окончательно получим

А= t₁А₁+t₂А₂+t₃А₃, t₁³0, t₂³0, t₃³0, t₁+t₂+t₃=1,

т.е. точка А - выпуклая линейная комбинация вершин А₁, А₂, А₃. Если положить, например, t₁=0, то это означает, что точка А совпадает с точкой А₄ и лежит на стороне . В этом случае выпуклая линейная комбинация для точки имеет вид

А=0^.А₁+t₂А₂+t₃А₃=t₂А₂+t₃А₃, t₁=0,t₂³0, t₃³0, t₂+t₃=1. ¨