18 Теорема о разделяющей гиперплоскости. Теорема о выпуклости полупространства. Понятие выпуклого многогранника

Теорема о разделяющей гиперплоскости

Любая гиперплоскость c^Tx= разделяет всё пространство Rⁿ на 2 непересекающихся множества p₁ и p₂, наз полупространствами: p₁={xRⁿ:c^Tx}, p₂={xRⁿ:c^Tx>}

Теорема о выпуклости полупространства

Любое полупространство явл выпуклым множеством.

Пересечение конечного числа полупространств явл выпуклым множеством и наз выпуклым многогранником

19 Понятие системы линейных неравенств. Графический метод решения ситемы линейных неравенств

СЛН наз-ся сис-ма:

с^т₁х<=₁

с^т₂х<=₂

_… (1)

с^т_mх<=_m,

где с₁, с₂,…,с_mRⁿ- заданные веткора, а _1, _2,…, _mRⁿ - заданные числа.

Решением системы (1) наз-ся множестов хRⁿ, удовл=щих всем нер-вамодновременно.

В сл-е малой размерности, когда n<=3 можно применить гарфический способ решения системы (1).

Схема реализации гарф-го метода:

1) Для каждого нер-ва находится и строится «критическая» гиперплоскость, полученная заменой знака нер-ва на знак рав-ва. Эта гиперпл-ть разделяет все пр-во на два полупр-ва. При этом все точки одного из полупр-в удовл-ют нер-ву, а другого - нет. Тип полупр-ва опр-ся простой подстановкой координат точки в текущее нер-во.

2) После выявления всех «хороших» полупр-в, содержащих удовл-щие текущим нер-вам точки, делается их пересечение, которое и определяет решение исходной сис-мы.

20Общая постановка змп

ЗМП или оптимизационной задачей наз задача вида: f(x)max(min) (1) xДRⁿ, где f(x) – целевая функция, ДRⁿ – область допустимых значений

Решить ЗМП означает:

а) либо найти все такие yД:f(y)f(x), при поиске макс-мА;f(у)f(x), при поиске мин-ма xД (2)

б) установить неразрешимость поставленной задачи.

xД наз допустимым решением или планом ЗМП (1)

у в п. а) формулы (2) наз оптимальным решением или оптимальным планом задачи. В качестве целевой функции f(x) могут выступать функции, выражающие прибыль, объём производства, затраты, потери и т.д. В качестве области допустимых решений Д может служить множество решений системы уравнений ил неравенств.

Разновидности ЗМП

В случае когда целевая функция f(x) явл линейной функцией т.е. представима в виде: f(x)=c^Tx=c₁x₁+c₂x₂+…+c_nx_n, а обл Д есть выпуклый многогранник, то ЗМП (1) наз задачей линейного программирования. В противном случае она наз задачей нелинейного программирования. В зависимости от способа задания обл ограничений Д выделяют следующие виды ЗМП

1.ЗМП без ограничений (классическая оптимизационная задача)

f(x)max(min) (3) xRⁿ

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

f(x)max(min) (4)

g_i(х)=b_i, i=1,m

В этом сл-е обл-ть огран-ний Д образуют такие хRⁿ, которые являются решениями сис-мы ур-ний - огр-ний:

g_i(х)=b_i, i=1,m ЗМП-(4)

3. ЗМП в симметр-ной форме (с огр-ми - нер-ми)

f(x)max(min) (5)

g_i(х)<=b_i, i=1,m

В этом сл-е обл-ть огр-ний Д представл-ся мн-вом решений сис-мы огр-ний ЗМП-(5).

4. ЗМП в общей форме (со смешанными огр-ми)

f(x)max(min) (6)

g_i(х)=b_i, i=1,m

g_к(х)<=b_к, к=m+1,p

В этом сл-е обл-ть огр-ний Д представляет собой мн-во решений сис-мы нер-в и ур-ний ЗМП-(6)