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

Приведение к канонической форме

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

,

,

,

.

Приведение к канонической форме:

1. Если , то соответствующее ограничение умножается на (-1). При этом, если соответствующее ограничение – неравенство, то знак неравенства меняется на противоположный.

2. Если , то функция заменяется на следующую .

3. Если имеется неравенство , то оно заменяется на уравнение , при и .

Если имеется неравенство , то оно заменяется на уравнение , при и .

Переменная называется дополнительной переменной и показывает, на сколько левая часть неравенства отличается от правой.

Пример 1.6. Привести ЗЛП к каноническому виду.

,

,

,

,

.

1.Устранение неотрицательных чисел в правой части:

,

,

,

,

.

2. Изменение целевой функции:

,

,

,

,

.

3,4. Замена неравенств в ограничениях равенствами:

,

,

,

,

,

.

Это окончательный вид ЗЛП.

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

В дальнейшем почти всегда ЗЛП будут рассматриваться только в канонической форме.

Геометрический смысл ЗЛП

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

Аналитическое определение: Множество G называется выпуклым, если для любых и , где .

Пример выпуклого множества рис. 1.7.1, 1.7.2.

Рис. 1.7.1 Рис. 1.7.2 Рис. 1.7.3

Пример невыпуклого множества рис. 1.7.3.

Из всех приведенных выше примеров множеств следует, что допустимое множество ЗЛП выпукло.

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

Аналитическое определение: Точка называется крайней точкой, если из того, что , и , где .

Как следует из определения, если множество является многогранником, то крайними точками являются вершины этого многогранника (см. рис. 1.7.1). Здесь множество крайних точек ограничено. Заметим, что число крайних точек может быть и бесконечным, если множество не является многогранником. Из рис. 1.7.2 видно, что крайними точками являются все точки окружности.

Рассмотрим ЗЛП в каноническом виде.

(1.7.1)

.

Утверждение 1. Допустимое множество G ЗЛП выпуклое.

Доказательство: Пусть и - это означает, что , и , . Возьмем , где . Так как , , и , то . Теперь подставим в левую часть уравнения (7), получим , то есть . Таким образом , что и требовалось доказать.

Из рис. 1.4.1, 1.4.3 следует, что, если ЗЛП имеет решение, то всегда существует оптимальная крайняя точка. Таким образом, если задача имеет решение, то для его поиска достаточно перебрать только крайние точки.

Вновь рассмотрим ЗЛП в канонической форме

(1.7.2)

, где , .

Будем считать, что , то есть матрица А имеет m линейно независимых столбцов. Допустимое решение , , называется базисным решением или опорным планом, если положительным значениям , соответствуют линейно независимые столбцы матрицы А.

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

Сформулируем без доказательства.

Утверждение 2: Каждому базисному решению ЗЛП соответствует крайняя точка выпуклого множества G. Каждой крайней точке выпуклого множества G соответствует базисное решение ЗЛП. Таким образом, если ЗЛП – разрешима, то для нахождения оптимального решения достаточно перебрать только базисные решения, число которых конечно и не превосходит .

Рассмотрим сначала способ перестроения базисного решения системы без условия неотрицательности.

Пусть матрица А имеет вид

,

где Е – единичная матрица.

Обозначим через множество номеров единичных столбцов матрицы А и через множество остальных номеров столбцов. Вектор X представим в виде , где и Вектор представим в виде . Тогда система примет вид

.

Если положить , то получим базисное решение .

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

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

· Шаг 1: l-строка делится на направляющий элемент.

· В новой итерации эта строка будет иметь номер k.

· ,

· ,

· .

Шаг 2: Для

,

.

Шаг 3: ,

.