41 Общая постановка злп и формы её представления. Теорема о эквивалентности форм представления злп

ЗЛП называется оптимиз. задача f(x) → max (min) (xЄDcRⁿ), где

f(x)=c^tx=Σ_j=1ⁿ c_jx_j – линейная целевая функция, а D выпуклый многогранник. Формы представления:

1. ЗЛП в канонической форме (с ограничениями равенствами)

f(x) → max (min)

x≥0

Ax=b

2. ЗЛП в симметрич. форме (с ограничениями неравенствами)

f(x) → max (min)

Ax≤b

x≥0

3. ЗЛП в общей форме ( со смешан. ограничениями)

f(x) → max (min)

A₁x=b₁

A₂x≤b₂

Замечание: 1-я и 2-я формы задач ЗЛП содержат требование неотрицательности инструм. переменных x≥0. Общая форма задачи этого не требует.

Теорема:

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

42 Понятие угловой точки (вершины) выпуклого многогранника, опорного плана злп. Понятие оптимального плана злп. Понятия вырожденного и невырожденного опорного плана

Пусть ДcRⁿ- выпуклый многогранник, точка х D области ограничения ЗЛП называется угловой точкой(вершиной), если не существует отрезка, целиком принадлежащего D для которого. эта точка является внутренней.

Любая вершина области Д з-чи: f(x) → max (min) (xЄDcRⁿ) наз-ся опорным планом.

Опорный план наз-ся невырожденным, если он содержит ровно m, где m- число Ур-ний - огр-ний канонической формы представления данной ЗЛП, пол-ных компонент, в противном сл-е , когда число пол-ных компонент опoрного плана <m, опорный план наз-ся вырожденным.

43 Теорема Каратеодори. Теорема о решении злп. Теорема о вершине

Теорема Каратеодори:

Пусть у₁, у₂,…,у_n – вершины выпуклого многогранника D, тогда любая т. хЄD этого многогранника может быть представлена в виде выпуклой линейной комбинации его вершин:

х=Σ_i=1^N λ_iyi, где Σ_i=1^N λ_i=1; λ_i≥0, i=1,N

Теорема о решении ЗЛП:

Пусть D есть обл. ограничений ЗЛП, тогда справедливо следующее:

1. Максимум(минимум) целевой функции достигается в вершине области D.

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

Теорема о вершине:

Для того, чтобы т. x была вершиной обл. ограничений задачи 1-2, необходимо и достаточно чтобы она была решением СЛУ Ax=b, заданной в (2), в кот. все свободные переменные =0, а базисные неотрицательны.

Следствие:

Число положит. компонент вершины обл. ограничений задачи 1-2 не может быть >m, где m число уравнений в системе Ax=b.

44 Назначение и обоснование графического метода решения злп

Метод применяется для реш-я ЗЛП малой размерности, когда число пер-ных з-чи не превышает 3-х. В основе метода лежит теорема о реш-ии ЗЛП и то факт, что градиент цел-ой ф-ии ЗЛП, указывающий направление наискорейшего роста этой ф-ии, во всех точках одинаков. Причем f(x)=с, если f(x)=с^тх. Деств-но рассм-м гиперпл-ть Р_β, предсавл-ую собой мн-во ур-ня β цел-ой ф-ии f(x)=с^тх исходной ЗЛП. Р_β={ xЄRⁿ: f(x)=с^тх=β=конст}

Пусть точки х и у принадлежат этой гиперплоскости Р_β.

Тогда напр-ный отрезок z=у-х целиком принадлежит гиперпл-ти Р_β.

Рассм-м скаларное произ-е градиента f(x) целевой ф-ии f (x)=с^тх и вектора z. Имеем: (f(x),z)=(c,z)= с^тz=с^т(y-x)= с^тy- с^тx=0/

След-но градиент ортогонален любой гиперпл-ти, в точках кот-ой цел-ая ф-ия принимает одинаковые знач-я.