52 Понятие двойственной пары злп

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

«Прямая» ЗЛП:

f(x)=c^tx→max

Ax=b

x≥0

с,хЄRⁿ

bЄR^m

«Двойственная» ЗЛП:

g(y) = b^тy → min

A^тy ≥ c

y≥ 0

b, yЄ R^m, c Є Rⁿ

Эти задачи образуют двойственную пару ЗЛП. Задачи двойственной пары дополняют друг друга и часто решение одной из них можно получить, анализируя решение другой.

53 Двойственная лемма. Понятие прямых и двойственных оценок

Двойственная лемма:

Для любого плана х прямой задачи, и любого плана у двойственной задачи справедливо:

двойственной задачи справедливо:

f(х) ≤ g(у)

Следствие:

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

Говорят,что компоненты оптимального плана х* прямой задачи наз.прямыми оценками

Компоненты y*_i , i = 1, m оптим. плана двойственной задачи называются двойственными оценками.

54 Первая, вторая теорема двойственнрсти

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

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

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

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

(Σ_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

Следствие:

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

67-68 Методы поиска опрного плана ТЗ: метод северо-западного угла, метод минимального элемента

Для получения оптимального плана, необходимо сначала найти опорный план (вершину). Рассм 2 метода: МСЗУ и ММЭ.

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

В первом сл-е дальше считается недопустимыми клетки столбца, а во втором- строки, на пресечении кот-ых нах-ся заполненная клетка. При этом в МСЗУ на каждом шаге заполняется левая верхняя клетка из числа доступных, а ММЭ - та клетка из доступных, кот-ая соотв-ет мин-ым тарифам.