11 Формы представления злп

ЗЛП называется задача вида f (x)→ max (min) xєDcRⁿ

Где f(x) – линейная целевая ф-ия,а область ограничений Д – выпуклый многогранник.

Ф-ия f(x) наз линейной,если она представлена в виде: f(x)=c₁x₁+c₂x₂+…c_nx_n+β

Формы представления:

1. ЗЛП в канонической форме

f(x)=с^Тх → max (min)

Ax=b

x≥0

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

f(x)=с^Тх → max (min)

Ax≤b

x≥0

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

f(x)=с^Тх → max (min)

A₁x=b₁

A₂x≤b₂

x≥0

Вне зависимости от форм представления ЗЛП все они эквивалентны. Это следует из теоремы об эквивалентности форм представления:

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

12 Графический метод решения злп

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

Описание графич. метода:

Шаг 1: графич. способом строится обл. огр. D исходной задачи.

Шаг 2: строится направляющий вектор с”=f(x”)

Шаг3:ч/з любую точку обл D проводится пл-ть(прямая), ортогональная вектору с”.

Шаг 4: построенная пл-ть перемещ-ся в направ-и вектора c” параллельно самой себе до точки последнего соприкосн-я перемещаемой пл-ти (прямой) с обл-тью D.Точка отрыва опред-т оптим план задачи.

Шаг 5: устан-ся точные знач-я компонент оптим плана,для чего реш-ся с-ма ур-ий тех пл-тей(прямых), в рез-те пересеч-я к-ых появл т оптим плана.

13 Двойств злп. Двойств лемма.

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

Прямая ЗЛП: Двойственная ЗЛП:

f(x) = c^тx → max(1) g(y) = b^тy → min(3)

{Ax ≤ b (2) {A^тy ≥ c(4)

{x≥ 0 {y ≥ 0

Эти задачи образуют двойственную пару ЗЛП.

Для любого плана х прямой задачи и любого плана У двойственной задачи справедливо: f(x) ≤ g(y)

Следствие: Если для некоторых планов x* и y* двойственной пары выполняется f(x*) = g(y*), то эти планы являются оптим-ми планами своих задач.

Компоненты x*j, j=1,n оптим-го плана х* прямой задачи назыв. прямыми. оценками, а компоненты y*_i , i = 1, n оптим-го плана у* двойственной задачи называются двойственными оценками.

14. 1-я т. двойств-ти: 1-я теорема двойственности:

Если одна задача двойств. пары имеет решение, то и вторая тоже имеет решение, причём значения целевых ф-ций этих задач на оптим-ых планах равны между собой. Если целевая ф-ция одной из задач двойствен. пары не ограничена, то мн-во допустимых решений второй задачи пусто, и наоборот.

2-я теорема двойственности:

План x* двойствен. задачи f(x) = c^тx → max { Ax ≤ b, x ≥ 0 и y* прямой задачи g(y) = b^тy → min

{A^тy ≥ c

{y ≥ 0

являются оптим. планами своих задач тогда и только тогда, когда выполняется соотношение:

{(Σ_j=1ⁿa_ijx^*_j - b_j)y*_i = 0, i = 1, m

{(Σ_i=1^ma_ijy*_i – c_j)x*_j = 0, j = 1, n

Где a_{ij –} эл-т матрицы А в ограниченниях Ax ≤ b

b_j- компоненты правой части b ограничений.

c_{j –} коэф-ты при х_j в выражении целевой ф-ии c^тx

Следствие: Если как-либо компонента оптим. плана одной из задач двойств. пары отлична от 0, то соотв. ограничение др.задачи этой пары должно выполнятся как точное равенство. Если же как-либо ограничение одной из задач выполняется как строгое неравенство, то соотв. компонента оптим. плана другой задачи этой пары равны 0.