х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
– производительность.
Математическая модель.
Предположим m=n. Введем целочисленное обозначение пусть Xij 1- i-ый на j—ю , 0 в
противном случае. Получим матрицу из элементов 0 и 1. Так как исполнитель может быть
назначен на одну работу и одна работа может быть выполнена только одним исполнителем в
каждой строке и столбце только одна 1. Система ограничение все = 1 (по строкам и столбцам)