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

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

1.все ограничения имеют вид равенства, «=»;

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

3.находится минимум целевой функции, Z min.

Иногда третье условие пишут в виде Z max.

Рассмотрим правило сведения общей ЗЛП к КЗЛП. Если в задаче Z max, то делается замена

Чтобы из неравенства сделать равенство, надо в его левую часть прибавить дополнительную (балансовую) неотрицательную переменную, если ограничение типа « », или отнять, если ограничение типа « ». При этом в каждое неравенство вводится своя (n+i)-я дополнительная переменная. Если , то делают замену , если некоторая переменная может иметь произвольный знак, то делают замену . Любую ЗЛП можно привести к каноническому виду.

17. Значение неизвестны переменных, удовлетворяющие всем ограничениям ЗЛП, называются допустимыми значениями переменных, а составленный из них вектор – планом. Множество всех планок ЗЛП называется ОДЗ. План ЗЛП, при котором функция принимает максимальное (минимальное) значение на ОДЗ, называется оптимальным.

18. Свернутая

Z= →min;

Xj≥0, j=1,n

Матричная

Z=C*X→min

AX=A0,

X≥0,

Где C=(c1,c2,…,cn), A=

X= A0=

Векторная

Z= * →min

A1X1+A2X2+…+AnXn=A0

X≥0

=(c1,c2,…,cn), X= A1= A2= A0=

19. 1)Преобразование переменных. Если какая то переменная Х_к неположительная, то вводим новую переменную Х_к`, такую, что Х<sub>к</sub>`=- Х_к. Очевидно, что Х_к`≤0. После этого в каждом ограничении и целевой ф-ии переменную Х<sub>к</sub> заменяют на (- Х<sub>к</sub>`). Если какая то переменная X_t может принимать любые значения, то ее заменяют разностью 2 неотриц переменных X_t` и X<sub>t</sub>``, т е полагают, что X<sub>t</sub>= X<sub>t</sub>`- X_t``, где X<sub>t</sub>` и X<sub>t</sub>``≥0.

2) Если какое либо из ограничений в модели имеет вид неравенства, то оно преобразуется в уравнение прибавления (неравенство имеет смысл ≤) к его левой части некоторой дополнительной не отрицательной переменной, или вычитанием такой переменной из его левой части (если неравенство имеет смысл ≥). Эти переменные называются балансовыми. Балансовые переменные входят в целевую функцию с нулевым коэффициентом. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая Х7 и т.д.

3) преобразование целевой функции. Если в модели задана целевая функция для нахождения максимального значения то вместо задачи z→max, будем рассматривать задачу z’=-z→min. В окончательном ответе необходимо опять поменять знак на противоположный т.е. min z = -max z’.

20.Пусть ЗЛП задана в канонической форме:

Z= →max;

(j=1,m)

Xj≥0, j=1,n

Предположим, в системе ограничений:

(j=1,m),

канонической формы модели m и все m уравнений линейно независимы (ранг системы r=m). В этом случае система имеет бесчисленное множество решений. Ее можно разрешить относительно m переменных x1, X2,..,Xm, например методом Жордана–Гаусса, если векторы-столбцы коэффициентов при этих неизвестных линейно независимы:

(j=1,m)

В этом случае x1, X2,..,Xm являются базисными переменными, а свободные переменные.

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

В результате преобразования получим:

,

так как , то из равенств имеем:

(j=1,m)

Стандартная форма модели ЗЛП примет вид:

,

(j=1,m)

Xj≥0 (j=m+1,n)

21. Гиперплоскость

Гиперповерхность в евклидовом n-мерном пространстве, которая задается линейным уравнением

или

.

Размерность гиперплоскости на единицу меньше размерности пространства E_n, в котором она расположена. Так, в трехмерном пространстве гиперплоскость — это просто плоскость, а в двухмерном — прямая на плоскости.

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

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

Полупростра́нство, ограниченное гиперплоскостью α — это геометрическая фигура в пространстве, для которой выполняется следующее:

Эта фигура включает в себя плоскость α, но не сводится к ней.

Любой отрезок, ограниченный произвольными точками этой фигуры A и B, не принадлежащими α, не имеет пересечений с плоскостью α.

Любой отрезок, ограниченный произвольными точками этой фигуры A и B, где А принадлежит α, а B — нет, имеет пересечение с плоскостью α.

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

Если неравенство строгое, то полупространство

называется открытым.

ОПОРНАЯ ГИПЕРПЛОСКОСТЬ множества М в n- мерном векторном пространстве - (n - 1)-мерная плоскость, которая содержит точки замыкания М и оставляет М в одном замкнутом пространстве. При n=З Опорная гиперплоскость наз. опорной плоскостью, а при n=2 - опорной прямой. Граничную точку множества М, через которую проходит хотя бы одна Опорная гиперплоскость, наз. опорной точкой М. У выпуклого множества М все его граничные точки – опорные. Граничные точки выпуклого множества M, через которые проходит единственная Опорная гиперплоскость, наз. гладкими. В общих векторных пространствах, где гиперплоскость определяется как область постоянства значений линейного функционала, также вводится понятие О. г. как гиперплоскости, экстремальной по значению этого функционала среди гиперплоскостей, оставляющих М в одном полупространстве.

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

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

(3)

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

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

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

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

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

2. Выбрать произвольное значение (например ) и построить соответствующую линию уровня целевой функции .

3. Построить вектор градиента целевой функции, т.е. вектор , указывающий направление наискорейшего возрастания целевой функции;

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

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

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

При решении задачи линейного программирования возможны следующие случаи:

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

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

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

4. Задача не имеет решения: целевая функция не ограничена, линия уровня, сколько бы ее ни перемещали, не имеет предельного положения;

5. Область допустимых решений — пустое множество (т.е. система ограничений задачи несовместна), задача не имеет решения.

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