Линейное программирование

1.1. Свойства задачи линейного программирования.

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

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

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

Теорема 1. Любая внутренняя точка выпуклого множества представляет собой выпуклую линейную комбинацию угловых точек этого множе-

ства. Т. е. справедливо равенство в n-мерном векторном пространстве:

i 1

Для простейшего выпуклого множества, представленного отрезком, это очевидно. Действительно, пусть х1 – начало отрезка, х2 – конец отрезка, а х – внутренняя точка отрезка, тогда справедливо равенство:

Если внутреннюю точку х совместить с концом отрезка х2, то число λ будет равно нулю, если совместить с х1, то λ равно единице. Для всякой внутренней точки х λ принадлежит интервалу от нуля до единицы. Из (2) внутренняя тока х = λх1 + (1 – λ)х2. Обозначим λ = α1 (0;1) и 1 – λ = α2 (0;1). Справедливо равенство α1 + α2=1. Для отрезка получим равенство аналогичное равенству (1):

i 1

Стой лишь разницей, что здесь х, х1, х2 одномерные векторы (числа, а не наборы n действительных чисел).

1

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

В одномерном пространстве выпуклое множество – это отрезок. Граница этого множества состоит из двух точек. Они же угловые точки. Линейная функция, заданная над этим множеством, принимает экстремальные (минимальное или максимальное) значения в угловой точке (начало или конец отрезка). Этот очевидный факт подтверждается с алгебраической точки зрения для выпуклых множеств. Действительно, пусть, например, отыскивается максимум линейной функции F(x) = cx равный числу М, который достигается в некоторой точке х отрезка [x1; x2]. Но всякая точка выпуклого множества, в данном случае представляется равенством (3). Подставляя это равенство в линейную функ-

цию, получим: F(x) = cx = c(α1х1 + α2х2) = α1(cх1) + α2(cх2) = α1F(x1) + α2F(x2) ≤ |

какое-то из чисел F(x1) или F(x2) большее и равное числу М. Заменим оба значения F(x1) и F(x2) числом М. Далее получим неравенство. | ≤ α1М + α2М = (α1 + α2)

М = М. Из полученного неравенства мы видим, что максимум достигается в угловой точке х1 или х2. Если значения линейной функции в точках х1 и х2 одинаковые, то максимум достигается в выпуклой линейной комбинации этих точек (график линейной функции – прямая линия параллельная отрезку [x1; x2]). Приводя алгебраические доводы для очевидного факта, мы, вместе с тем, привели схему доказательства, пригодную для n-мерного пространства следующего свойства.

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

В двумерном пространстве (на плоскости) выпуклое не замкнутое (не имеющее всех своих граничных точек) не ограниченное (не помещающееся в круг конечного радиуса) множество в виде полуплоскости задается неравенством: a∙х1 + b∙x2≤ d или неравенством противоположного смысла. Неравенство

2

a∙х1 + b∙x2≤ d эквивалентно пересечению двух множеств, а именно, множеству a∙х1 + b∙x2 = d, представляющему уравнение прямой и строгому неравенству a∙х1 + b∙x2 < d, задающему одну из двух полуплоскостей на которые прямая a∙х1 + b∙x2 = d делит всю плоскость.

Теорема 3. Непустое пересечение выпуклых множеств образует выпуклое множество.

Система нескольких неравенств вида а∙х1 + b∙x2≤ d с различными числами a, b и d задает ограниченное замкнутое выпуклое множество. Для того, чтобы можно было оперировать с выпуклыми множествами в алгебраической форме, опираясь на их свойство (Теорема. 1.), необходимо потребовать неотрицательные значения для х1 и х2. Это требование достигается введением дополнительных неравенств х1 ≥ 0 и х2 ≥ 0. Далее х1 и х2 будут называться допустимыми значениями.

Пусть над выпуклым многоугольником допустимых значений задана линейная функция, например, F(x1,x2) = c1x1 + c2x2. С геометрической точки зрения равенство F(x1,x2) = c1x1 + c2x2 представляет собой уравнение плоскости в системе координат (х1; х2; F). Предположим, что значение функции F равно константе С, т. е. F = С, тогда равенство c1x1 + c2x2 = С является уравнением прямой на плоскости (х1, х2). На этой прямой значение функции не меняется. По этой причине прямая называется линией уровня функции F. Коэффициенты c1, c2 прямой c1x1 + c2x2 = С играют роль координат нормального (перпендикулярного) вектора ē(c1; c2) этой прямой. Если прямую c1x1 + c2x2 = С перемещать в направлении вектора нормали ē(c1; c2), оставляя её параллельной самой себе, то значение функции F будет испытывать наибольшее изменение в сторону увеличения (если перемещать в противоположном направлении, то значение функции F будет иметь наибольшее изменение в сторону уменьшения).

Для того чтобы решить задачу линейного программирования на плоскости (говорят решить задачу графически) строят множества решений всех неравенств вида a∙х1 + b∙x2≤ d задающих выпуклый многогранник. В этой же системе координат (х1, х2) строят нормальный вектор ē(c1; c2) исходящий, например, из начала координат. Через начало координат проводят линию нулевого уровня функции F перпендикулярно нормальному вектору ē(c1; c2). Перемещая линию уровня параллельно самой себе в направлении вектора нормали до первой угловой точки многоугольника допустимых решений, получим минимум линей-

3

ной функции, достигаемый в этой угловой точке. Дальнейшее перемещение линии уровня приведет к обнаружению максимума линейной функции в угловой точке многоугольника допустимых решений, после которой линия уровня выходит из многоугольника. Если среди множества нормальных векторов ū(а;b) прямых вида a∙х1 + b∙x2 = d, ограничивающих выпуклый многоугольник, найдется коллинеарный вектор вектору ē(c1; c2), то линия уровня на входе или на выходе (там, где расположена прямая с коллинеарным вектором нормали) может совпасть не с угловой точкой, а со стороной выпуклого многоугольника, и оптимальное решение будет достигаться во всех точках этой стороны многоугольника.

П р и м е р 1. Найти минимальное и максимальное значения линейной функции F(x1,x2) = х1 + 2х2 заданной над выпуклым многоугольником: х1 + х2 ≤ 3; х1 + х2 ≥ 1; х2 ≤ 2; 2х1 – х2 ≤ 4; х1 ≥ 0; х2 ≥ 0. Говорят решить задачу линейного программирования (ЗЛП). См. рис. 1.

Неравенство х1 + х2 ≤ 3 эквивалентно пересечению двух множеств: множества х1 + х2 = 3, представляющего собой уравнение прямой, и строгого неравенства х1 + х2 < 3, задающего полуплоскость. Аналогично рассматриваются остальные неравенства. Линия уровня функции F впервые встречается с многоугольником допустимых решений в угловой точке А(1;0). Следова-

тельно, минимальное значение линейной функции Fmin(1;0) = 1 + 2∙0 = 1. Линия уровня покидает многоугольник в угловой точке В(1;2). Это значит, что максимальное значение целевой функции Fmax(1;2) = 1 + 2∙2 = 5.

В общем случае задачу линейного программирования можно записать в стандартной форме:

Если в системе ограничений есть неравенства противоположного смысла, то, умножая обе части такого неравенства на минус единицу, получим неравенство

4

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

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

Если уравнения в системе ограничений (5) линейно независимы (каждое уравнение имеет информацию, отличающуюся от информации заключенной в других уравнениях) и система совместна, то ранг задачи равен m (числу уравнений). Число базисных столбцов матрицы системы (5) также равно m. Переменные, являющиеся множителями базисных столбцов, называют базисными пе-

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

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

Действительно, пусть вектор х(х1, х2, …, хm, 0, 0, …, 0) представляет собой допустимое базисное решение системы ограничений (5). Существует две возможности. Первая возможность – вектор соответствует угловой точке многогранника допустимых решений (4), тогда первое предложение теоремы доказано. Но существует вторая возможность – вектор не соответствует внутренней точке многогранника допустимых решений (4). Иных возможностей нет. Рассмотрим вторую возможность. Внутренняя точка может быть представлена

5

точкой некоторого отрезка, так что справедлива выпуклая линейная комбинация вектора х = α1х' + α2х". Поскольку х внутри отрезка [х'; х"], то α1>0 и α2>0. Запишем векторное равенство х = α1х' + α2х" по их координатам, получим:

Все «иксы» в (6) неотрицательные числа, α1 и α2 строго положительные, справедливы последние n равенств и справедлива теорема о том, что свободные переменные однозначно определяют базисные (в данном случае, если равенства верны для свободных переменных, то они верны и для базисных). Следовательно, равенства (6) эквивалентны равенствам:

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

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

(5) запишем в форме:

6

где I1, I2, …, In+m – столбцы коэффициентов системы (5), В – столбец свободных членов.

Пусть х(х1, х2, …, хm, 0, …, 0) – угловая точка многогранника допустимых решений. Возникают вновь две возможности, а именно, если столбцы I1, I2, …, Im, стоящие перед переменными х1, х2, …, хm в (8) линейно независимы, то точка х(х1, х2, …, хm, 0, …, 0) представляет собой базисное решение системы (8):

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

Вторая возможность допускает линейно зависящие столбцы I1, I2, …, Im, стоящие перед переменными х1, х2, …, хm в (8). В случае второй возможности, существуют не все равные нулю числа β1, β2, …, βm такие, что справедливо равенство:

Умножая равенство (10) на число μ и добавляя его к равенству (9), а также вычитая из равенства (9), получим:

Подбирая достаточно малое число μ все числа в скобках равенства (11) можно сделать неотрицательными.

Из (11) следует, что точка х(х1, х2, …, хm, 0, …, 0) не является угловой точкой, поскольку представима выпуклой линейной комбинацией:

где векторы х'((х1+μβ1), (х2+μβ2), …, (хm+μβm)) и х"((х1–μβ1), (х2–μβ2), …, (хm–

μβm)) определяют некоторые две точки многогранника допустимых решений. Полученное противоречие определению угловой точки заставляет за-

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

1.2. Симплексный метод.

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

7

решению системы ограничений (5). Следовательно, достаточно подсчитать значение линейной функции на всех допустимых базисных решениях и из полученного множества чисел выбрать наименьшее и наибольшее числа они и будут соответственно минимальным и максимальным значениями линейной функции. Однако с увеличением чисел m и n количество базисных решений становится экспоненциально большим.

Число рассматриваемых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущее, по значениям линейной функции (увеличение её при отыскании максимума F → max, уменьшение – при отыскании минимума F → min).

Для применения симплексного метода – последовательного улучшения решения – удобно освоить три элемента:

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

◊правило перехода к не худшему решению;

◊критерий проверки оптимальности найденного решения.

П р и м е р 2. Решить симплексным методом задачу:

Р е ш е н и е. С помощью дополнительных неотрицательных переменных перейдём к канонической задаче вида (5). Все дополнительные переменные вводятся со знаком «плюс», так как все неравенства имеют вид «≤».

Получим систему ограничений:

8

Для первоначального базисного решения в качестве базисных переменных можно взять переменные х3, х4, х5, х6. Каждое из этих переменных входит только в одно уравнение, и нет ни одного уравнения, в которое не входила бы указанная переменная (определитель, составленный из коэффициентов перед этими переменными, отличен от нуля). Свободные переменные – х1, х2.

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

x3 18 x1 x2 , x4 16 2x1 x2 ,

x6 21 3x1,

F 0; 0; 18; 16; 5; 21 2x1 3x2.

В скобках перед функцией F записано допустимое базисное решение (0; 0; 18; 16; 5; 21). Значение функции при этом допустимом решении равно нулю F(0; 0; 18; 16; 5; 21) = 2x1 + 3x2 = 2∙0 +3∙0 = 0. Функцию F можно увеличить за счет увеличения любой из свободных переменных х1 или х2, переводя её в базисную переменную. Коэффициенты перед свободными переменными положительные числа. Для определенности выберем переменную с наибольшим коэффициентом в надежде получить наибольшее приращение линейной функции. Увеличение переменной х2 означает перевод её из свободной переменной в базисные, где она примет некоторое неотрицательное значение. При этом линейная функция получит приращение ∆F = 3х2б, где х2б – значение переменной х2 в будущем базисном решении.

Далее необходимо решить, какую из базисных переменных необходимо отправить в свободные переменные так, чтобы не появилось ни одной недопустимой переменной. Система (15) накладывает ограничения на рост х2. Полагая в (15) свободную переменную х1 равной нулю, получим эти ограничения в явном виде:

9

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

икоэффициент при переменной в уравнении имеют одинаковые знаки, так как

ив этом случае нет ограничений на рост переменной.

Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение).

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х2 определяется как х2 = min {18/3; 16/1; 5/1; ∞} = 5. При х2 = 5 переменная х5 обращается в нуль и переходит в свободные.

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

Далее. Базисные переменные: х2, х3, х4, х6. Свободные переменные: х1, х5. Выразим новые базисные переменные через новые свободные, начиная с разрешающего уравнения (его используем при записи выражения для х2):

10