Задача,двойственная к транспортной задаче.
Пусть дана закрытая транспортная задача,математическая модель которой имеет вид (1.2)-(1.5).Составим двойственную задачу.Обозначим переменные двойственной задачи,соответствующие уравнениям (1.3) через Pi (i=1,...,m),а переменные, соответствующие уравнениям (1.4)-через Qj(j+1,…,n). Тогда задача,двойственная к задаче (1.2)-(1.5), примет вид
(1,6);(1,7)
Задача (1.6),(1.7)содержит(mn) неравенств (1.7) относительно (m+n) неизвестных Pi и Qj ,которые могут принимать значения любого знака.
Из второй основной теоремы двойственности получаем,что допустимое решение Хij (i=1,…,m; j=1,…,n) задачи (1.2)-(1.5) и допустим решение Pi(i=1,…,m) и Qj (j=1,…,n) задачи (1.6)-(1.7) будут оптимальными решениями соответствующих задач тогда и только тогда,когда они будут удовлетворять следующим условиям:
n
pi(∑xij-ai)=0,i=1,…,m
j=1
m
qj(∑xij-bj)=0,j=1,…,n
i=1
xij(pi+qj-cij)=0, i=1,..,m; j=1,..,n
Правила расчета потенциалов поставщиков и потребителей в транспортной задаче. Расчет оценочных коэффициентов для свободных клеток транспортной задачи. Условие оптимальности базисного решения.
Ui+Vj=Cij
Задается начальный потенциал,потом по кружкам вычисляют.
|
|
Условие: Базисное решение в транспортной задаче- определ вариант распределенных базисных поставок,число кружков=m+n-1.Кружки должны образовывать вычеркиваемую комбинацию.
Условие-хар-ки свободных клеток должны быть положительными.
Записать определение цикла пересчета в транспортной таблице. Использование цикла пересчета для получения нового (улучшенного) базисного решения.
Циклом пересчета, соответствующим данной свободной клетке транспортной задачи, называется замкнутая ломаная линия, одна вершина которой лежит в этой свободной клетке, а остальные вершины - в занятых базисных клетках транспортной таблицы. Полученная ломаная должна удовлетворять следующим условиям:
а) ее звенья параллельны строкам или столбцам таблицы;
б) в каждой вершине ломаной под прямым углом сходятся два ее звена.
Доказано, что для любой свободной клетки транспортной таблицы существует единственный цикл пересчета, который может быть представлен и самопересекающейся ломаной, но точки ее самопересечения по определению цикла пересчета не являются его вершинами.
Теорема. Если в транспортной таблице построено базисное реш-е, то для каждой свободной клетки этой табл сущ единственный цикл пересчёта.
|
|
Построим цикл пересчета для выделенной нами свободной клетки ( ).
Запишем в клетку с номером ( ) знак “+”, в соседнюю клетку с номером ( ) - знак “-“.Так, двигаясь вдоль цикла пересчета, будем в вершинах цикла поочередно ставить знаки “+” или знаки “-”.Очевидно, что число вершин цикла пересчета всегда четно. Поэтому не имеет значения, в какую из двух соседних клеток был осуществлен переход из клетки с номером ( ). Изменим теперь поставки в вершинах цикла пересчета в соответствии со знаками, находящимися в этих вершинах, на величину w. Тогда поставки примут значение
+w, 1-w, -w, …, -w, -w.
В вершинах цикла пересчёта, помеченных знаком «-» находим min поставку из старого базисного плана . Присвоим величине w значение, равное , и по вершинам цикла пересчёта согласно последовательности перераспред-ем поставки. При этом поставка - w окажется равной 0. Соответствующую неизвестную переводим в разряд свободных, а клетка с номером ( ) остается пустой. Если после пересчёта в нес-ких вершинах цикла поставки примут нулевые значения, то в разряд свободных переводим только 1-ну из соответствующих неизвестных, сохраняя остальные в базисном наборе с нулевыми знач-ями перевозок. В итоге будет получено новое базисное решение, в кот будет занято (m+n-1) клеток и кот исследуется на оптимальность тем же методом. Процесс продолж до получения оптимальн реш-ия.
|
|
Дата добавления: 2018-06-01; просмотров: 688; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!