Каноническая задача линейного программирования (кзлп)

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

В канонической форме

1. все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

2. все переменные неотрицательны;

3. целевая функция подлежит максимизации

Таким образом, КЗЛП имеет вид

(2.12)

, (2.13)

(2.14)

или в векторно-матричной форме

(2.15)

(2.16)

(2.17)

или

(2.18)

КЗЛП является частным случаем общей ЗЛП при m₁=0, p=n

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

• минимизация целевой функции = c₁x₁+…+c_nx_n равносильна максимизации целевой функции - = -c₁x₁ -…-c_nx_n;

• ограничение в виде неравенства, например, 3x₁+2x₂-x₃6, может быть приведено к стандартной форме 3x₁+2x₂-x₃+x₄=6, где новая переменная x₄ неотрицательна. Ограничение x₁ - x₂ + 3x₃10 может быть приведено к стандартной форме x₁ - x₂ + 3x₃ - x₅=10, где новая переменная x₅ неотрицательна;

• если некоторая переменная x_k может принимать любые значения, то ее можно представить в виде , где 0 и 0.

Для общей ЗЛП соответствующая каноническая форма имеет вид:

Для основной ЗЛП в векторно-матричной форме соответствующая КЗЛП имеет вид:

Пример 2.1.

Пусть ЗЛП имеет вид:

- не ограничена в знаке,

Для приведения данной задачи к виду КЗЛП, выполним следующие шаги: 1. Представим свободную переменную в виде

2. Введем дополнительные переменные («избыточная» переменная) и («остаточная» переменная) в первое и второе ограничения

3. Умножим первое ограничение на -1

4. Изменим знак на противоположный

В результате получим следующую КЗЛП, равносильную исходной

Теорема 2.1 (об эквивалентности КЗЛП и ОЗЛП).

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

1. если разрешима КЗЛП, то разрешима и ОЗЛП, и наоборот;

2. если множество планов КЗЛП пусто, то и множество планов ОЗЛП пусто, и наоборот;

3. если целевая функция КЗЛП не ограничена сверху на множестве планов КЗЛП, то и целевая функция ОЗЛП не ограничена сверху на множестве планов ОЗЛП, и наоборот.

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

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

Пусть множество .

0Пределение 2.4.

Пусть , тогда выражение

(2.19)

называется выпуклой линейной комбинацией точек и .

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

(2.20)

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

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

Например, круг, треугольник являются выпуклыми множествами, а кольцо – не является выпуклым множеством.

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

Определение 2.7.

Множество

(2.21)

где ; b-действительное число, называется гиперплоскостью.

Теорема 2.2. Множество является выпуклым множеством.

Доказательство. Пусть ,т.е. и

Рассмотрим выпуклую линейную комбинацию точек т.е.

Чтобы доказать выпуклость множества Г достаточно доказать, что

Действительно , , т.к. - выпуклое множество и .

Итак, и ,т.е. при

Определение 2.8. Множества

и называются полупространствами пространства .

Теорема 2.3. Множества и являются выпуклыми множествами.

Теорема 2.3 доказывается аналогично теореме 2.2.

Теорема 2.4. Множество P планов ЗЛП (в любой постановке) является выпуклым.

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

Докажем теорему для случая КЗЛП (для остальных постановок доказательство аналогично).

Итак, Пусть т.е.

Рассмотрим выпуклую линейную комбинацию точек и , т.е.

Для доказательства выпуклости P достаточно показать, что .

Действительно:

, т.к. -выпуклое множество;

,т.е. , следовательно, P-выпуклое множество.

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

Доказательство. Пусть , где – выпуклые множества для всех . Тогда для всех и в силу их выпуклости точка для всех и , следовательно, , т.е. – выпуклое множество.

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

Нетрудно доказать, что если и – выпуклые множества, то множества , , ( – действительное число) выпуклы.

Пользуясь теоремой 2.4., можно, например, доказать, что множество планов Р основной ЗЛП является выпуклым множеством. Действительно,

является выпуклым как пересечение m+n полупространств:

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

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

Доказательство. Необходимость. Пусть P – выпуклое множество. Тогда по определению 1 содержит выпуклые комбинации любых двух своих точек. Предположим, что множество содержит выпуклые комбинации любых своих точек. Рассмотрим выпуклую комбинацию произвольных точек из . Можем считать, что , и так как , , .

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

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

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

Теорема 2.7. Если – выпуклое множество, то также выпукло.

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

Действительно, поскольку

,

,

, .

Из определения и имеем

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

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

Замечание. Таким образом, множество состоит из точек трех типов: изолированные точки множества , предельные точки множества , принадлежащие , предельные точки множества , не принадлежащие . Выпуклое множество не может иметь изолированных точек, следовательно, замыкание выпуклого множества состоит только из предельных точек множества .

Теорема 2.8. Если – выпуклое множество, то также выпукло.

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

Большую роль в построении теории линейного программирования играет понятие крайней точки.

Определение 2.12. Точка выпуклого множества P является крайней, если в P не существует таких точек и , ≠ , что

, при некотором .

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

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

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

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

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

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

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

Легко видеть, что Х = (1- )Х₁ + Х₄ , 0  1

и Х₄ = (1- ₁)Х₂ + ₁Х₃ , 0 ₁ 1 ,

откуда Х = (1- )Х₁ +  (1-₁)Х₂ +  ₁Х₃ , 0  1, 0 ₁ 1 ,

причём 1 -   0, (1- ₁)  0 , ₁  0 и (1- ) + (1- ₁) + ₁ = 1.