Решение задач транспортного типа

Метод северо-запдного угла. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного х₁₁ (северо западный угол) и заканчивается клеткой для неизвестного х_min то есть идет как бы по диагонали таблицы с севера запада.

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

Метод принципов.

Теорема: Решение транспортной задачи будет оптимальным, если наидутся такие числа u_i и v_j называемые соответственно потенциалами поставщиков и потребителей, отвечающие условиям: u_i + v_j = c_ij, для x_ij >0

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

Алгоритм решения транспортной задачи на основе метода потенциалов.

1. Находится первый опорный план по одному из рассмотренных методов

2. Проверяется опорный план на оптимальность для чего:

Находят потенциалы поставщиков Ui и потребителей Vi по формуле Ui + Vl = Cij .

Проверяется выполнено ли условие Sij = Сij – (Ui + vj) ≥ 0

Дата добавления: 2015-07-26; просмотров: 153; Нарушение авторских прав

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