Задача,двойственная к транспортной задаче.

Пусть дана закрытая транспортная задача,математическая модель которой имеет вид (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

                                     p_i(∑x_ij-a_i)=0,i=1,…,m

                                        j=1

                                          m

                                     q_j(∑x_ij-b_j)=0,j=1,…,n

                                         i=1

                                     x_ij(p_i+q_j-c_ij)=0, i=1,..,m; j=1,..,n

 

Правила расчета потенциалов поставщиков и потребителей в транспортной задаче. Расчет оценочных коэффициентов для свободных клеток транспортной задачи. Условие оптимальности базисного решения.

 

Ui+Vj=Cij

Задается начальный потенциал,потом по кружкам вычисляют.

Условие: Базисное решение в транспортной задаче- определ вариант распределенных базисных поставок,число кружков=m+n-1.Кружки должны образовывать вычеркиваемую комбинацию.

Условие-хар-ки свободных клеток должны быть положительными.

 

 

Записать определение цикла пересчета в транспортной таблице. Использование цикла пересчета для получения нового (улучшенного) базисного решения.

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

а) ее звенья параллельны строкам или столбцам таблицы;

б) в каждой вершине ломаной под прямым углом сходятся два ее звена.

Доказано, что для любой свободной клетки транспортной таблицы существует единственный цикл пересчета, который может быть представлен и самопересекающейся ломаной, но точки ее самопересечения по определению цикла пересчета не являются его вершинами.

Теорема. Если в транспортной таблице построено базисное реш-е, то для каждой свободной клетки этой табл сущ единственный цикл пересчёта.

 Построим цикл пересчета для выделенной нами свободной клетки ( ).

Запишем в клетку с номером ( ) знак “+”, в соседнюю клетку с номером ( ) - знак “-“.Так, двигаясь вдоль цикла пересчета, будем в вершинах цикла поочередно ставить знаки “+” или знаки “-”.Очевидно, что число вершин цикла пересчета всегда четно. Поэтому не имеет значения, в какую из двух соседних клеток был осуществлен переход из клетки с номером ( ). Изменим теперь поставки в вершинах цикла пересчета в соответствии со знаками, находящимися в этих вершинах, на величину w. Тогда поставки примут значение

+w, ₁-w, -w, …, -w, -w.

В вершинах цикла пересчёта, помеченных знаком «-» находим min поставку из старого базисного плана . Присвоим величине w значение, равное , и по вершинам цикла пересчёта согласно последовательности перераспред-ем поставки. При этом поставка  - w окажется равной 0. Соответствующую неизвестную  переводим в разряд свободных, а клетка с номером ( ) остается пустой. Если после пересчёта в нес-ких вершинах цикла поставки примут нулевые значения, то в разряд свободных переводим только 1-ну из соответствующих неизвестных, сохраняя остальные в базисном наборе с нулевыми знач-ями перевозок. В итоге будет получено новое базисное решение, в кот будет занято (m+n-1) клеток и кот исследуется на оптимальность тем же методом. Процесс продолж до получения оптимальн реш-ия.

 

---

Дата добавления: 2018-06-01; просмотров: 688; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!