Читать реферат по статистике: "Решение задач транспортного типа методом потенциалов" Страница 5


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

освобождают одну из базисных клеток. При этом общее число базисных клеток остаётся неизменным и равным m + n - 1 . Этот метод удобен тем, что для него легче находить подходящие циклы. Можно доказать, что для любой свободной клетке транспортной таблице всегда существует цикл и притом единственный, одна из вершин которого лежит в этой свободной клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза k, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Применённый выше метод отыскания оптимального решения транспортной задачи называется распределённым; он состоит в непосредственном отыскании свободных клеток с отрицательной ценой цикла и в перемещении перевозок по этому циклу. Распределительный метод решения транспортной задачи, с которым мы познакомились, обладает одним недостатком: нужно отыскивать циклы длявсех свободных клеток и находить их цены. От этой трудоёмкой работы нас избавляет специальный метод решения транспортной задачи, который называется методом потенциалов.

5. Решение транспортной задачи методом потенциалов.

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.Пусть имеется транспортная задача с балансовыми условиямиСтоимость перевозки единицы груза из Ai в Bj равна C ij ; таблица стоимостей задана. Требуется найти план перевозок xij, который удовлетворял быбалансовым условиям и при этом стоимость всех перевозок бала минимальна.Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму i ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму j . Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим i + j =ij ( i=1..m ;j=1..n) и будем называть величинуij “псевдостоимостью” перевозки единицы груза из Ai в Bj. Заметим, что платежиi и j не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (i и j ) одна и та же и от плана к плану не меняется. До сих пор мы никак не связывали платежи (i и j) и псевдостоимостиij с истинными стоимостями перевозок C ij. Теперь мы установим между ними связь. Предположим, что план xij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клеток xij >0. Определим платежи (i и j) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:ij = i + j = сij , при xij >0.Что касается свободных клеток (где xij = 0), то в них соотношение между



Интересная статья: Быстрое написание курсовой работы