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

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

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 неизвестных. Чтобы найти частное решение одну любую переменную приравнивают к любому произвольному числу. Тогдазначение остальных переменных определяется однозначно.

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

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

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

Алгоритм:

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

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

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

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

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

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

40. Усложненные постановки тз. Задачи транспортного типа.

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

Нередко целесообразно минимиз-ть суммарные затраты на пр-во и транспортировку прод-ции. В таких задачах критерием оптимальности служит сумма затрат на пр-во ед.груза и на его перевозку.

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

Иногда следует учитывать ограничения по пропускной способности некоторых маршрутов. Если, например, по маршруту можно провести не более d ед.груза, то столбец матрицы перевозок разбивается на два: . В первом спрос принимается равным разности между действительным спросом и ограничением d, во втором – равным ограничению d. Тарифы сij в обоих столбцах одинаковы и равны данным, но в первой клетке, соответствующей ограничению, вместо истинного тарифа cks ставится искусственно завышенный тариф M (клетка блокируется) затем задача решается обычным способом.зклетка блокируется). завышенный данным, но в первой клетке, соответствующей ограничению-рыми их придется сравнивать в процесс

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

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