Проверка плана на оптимальность. Теорема об оптимальности плана или теорема о потенциальности плана.

Для док-ва составим двойственную к прямой задаче.

Z = Cijxij->min

х11+х12+…+х1n =a1 ¦ -u1

x21+x22+…+x2n =a2 ¦ -u2

xm1+xm2+…+xmn = am ¦ -um

x11+ x21 +xm1 = b1 ¦ V1

x12+ x22+ xm2 = b2 ¦ V2

x1n+ x2n+ +xmn=bn ¦ Vn

xij>=0

V1-u1<=c11 Vm-Un<=C1n

Формулировка : Для того чтобы решения Х состоящее Х=¦xij¦ (i=1,m) (j=1,n) б было оптимальным для Т.З. необходимо и достаточно что бы существовала система из m+n чисел таки что бы выполнялось условия Vj-Ui<=Cij (для свободных клеток) Vj-Ui=Cij (для занятых)

Необходимость Х* - оптим. решение Т.З. Док-ть 1) и 2) условие

Если Х* оптим. решение прямой задачи то по 1-ой т. двойственности существует и решение двойственной задачи , т.е. существуют такие числа Vj & Ui такие что Vj-Ui<=Cij, - 1 условие

Хij(Vj-Ui-Cij)=0 но если клетка занятая то xij>=0 => Vj-Ui=Cij

Достаточность : Дано : Xij>=0 Vj-Ui=Cij

Доктть : Х* оптим решен.

2. -> перенеся Сij в левую часть и * Xij получим 0, это первое условие оптимальности плана поп второй т. двойственности. xij=ai ¦ -ui => (суммаXij –ai) ui =0 и (сумма Хij –bi)Vj=0 => второе условие оптимальности. => Х* оптимальное решение.

Алгоритм потенциалов.

Проверяем Vj-Ui=Cij и Vj-Ui<=Cij

Совместный учет производственных и

транспортных издержек.

Предположим что имеется m-производителей и n-покупателей.

A_i = (i = 1,m ) B_j = (j = 1.n )

Известны производственные затраты d_i (i = 1,n )

Спланировать перевозки так чтобы суммарные (производственные и транспортные) затраты были минимальными.

Нужно решить обычную транспортную задачу, затраты которой Cij = Cij + d

Блокирование перевозки или запрещение

перевозок.

Очень часто на практике при решение Т.З либо какой-то производитель или потребитель закладывает “запрет“ на продукцию.

Если это производитель – то он может запретить перевозку своего товара любому потребителю своей продукции.

Если это потребитель – то он может запретить перевозку товара к себе любому производителю с которым нехочет иметь дело.

В этом случае клетка с номером i , j должна быть заблокирована. И осуществляется это следующим образом. В клетку с номером i , j место Cij записываем число m (очень большое положительное число).

Задачи о назначении.

Пусть имеются m исполнителей которые должны быть назначены на выполнение n работ.

Известна матрица C. С – затраты при назначении i – исполнителя на выполнение j – вида работ C = Cij

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

Возможные постановки:

Ai – Экономисты. (i = 1,m) Bj – Работа. (j = 1,n) Cij – Затраты.

Ai – Строительные механизмы. Bj –Площади. Cij – производительность.