29. Потенциалы поставщиков и потр-лей, их вычисление и экон. Смысл.

Пусть дана модель ТЗ закрытого типа. Построим модель двойственной к ней задачи.

f= (i=от1 до m)Σ(j=от 1 до n)Σcij xij →min

(j=от 1 до n)Σ xij = ai i=от1 до m ui

(i=от1 до m) Σxij = bj j=от1 до n vj

xij>=0 i=от1 до m ; j=от1 до n

Двойственная задача

F=(i=от1 до m)Σ ai ui + (j=от1 до n) Σbj vj → max

ui – произвольное, i=от1 до m

vj – произвольное, j=от1 до n

ui+vj <= cij

Каждому пост-ку ставится в соответствие ui. Каждому потребителю ставится в соответствие vj. Эти потенциалы характ-т возможность пост-ков и потребителей изменять величину общих зат-т, меняя величину запасов и спрос. Из второй теоремы двойственности следует, что каждому xij*>0 соотв-ет равенство ui+vj=cij (1). Таким образом чтобы определить значение потенциалов, необходимо для каждой загруж-й клетки составить уравнение типа (1). В полученной таким образом системе будет m+n-1 уравнений и m+n неизвестных. Чтобы найти частное решение одну любую переменную приравнивают к любому произвольному числу. Тогда значение остальных переменных определяется однозначно.

30.Связь между оценками св клеток и потенциалами.

Разность

- наз-ся оценкой свободной клетки Если в опт плане есть своб клетки с отриц оценками, то из них выбирается клетка с макс по модулю оценкой(перспективная) и загружается макс возможной поставкой. Чтобы загрузить перспективную клетку, нужно составить для нее цикл. Он существует, причем единственный. Вершины его отмечаются знаками + и – поочередно, начиная с перспективной клетки. Далее выбирается наименьшая загрузка клетки, отмеченной минусом. Это число(λ) добавляется к загрузке клеток, отмеченных +, и вычитается от тех, что отмечены -. Эта процедура называется сдвиг λ по циклу. В рез-те загружается 1 клетка, и должна освободиться 1 клетка. Если освобождается больше чем 1 клетка, то свободной нужно оставить только одну, ту, у которой тариф наибольший. В остальные освобождающиеся вписать нулевую загрузку.

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

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

2. Условие задачи записывается в форме транспорт.таблицы

3. Строится начальный опорный план

4. Определяются потенциалы пост-ков и потреб-лей

5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т.е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след.

6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.

32.Основное неравенство теории двойственности: для любых допустимых планов x и y пары взаимнодвойственных задач справедливо неравенство z(x)<=f(y). Его экономическое содержание состоит в том, что для любого допустимого плана производства x и любого допустимого вектора оценок y общая созданная стоимость не превосходит суммарной оценки ресурсов.

Критерий оптимальности Канторовича (достаточный признак оптимальности): если для некоторых допустимых планов x* и y* являются оптимальными планами соответствующих задач. Экономический смысл критерия следующий: план проихводства X и вектор оценок ресурсов Y являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.

33.Теорема существования оптимальных планов пары двойственных задач: для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существования допустимого плана для каждой из них.