Транспортная задача

  • 18 марта 2012 г.
  • 2027 Слова
ЧАСТНОЕ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«МИНСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ»

Кафедра информационных технологий и высшей математики











Контролируемая самостоятельная работа

по дисциплине «Теория вероятностей»

на тему: «Транспортная задача в сетевой постановке»

























Минск, 2011



Содержание:

1. Постановка транспортной задачина сети

2. Постановка задачи о максимальном потоке и ее математической модели

3. Алгоритм Форда нахождения максимального потока

4. Постановка и математическая модель задачи нахождения потока минимальной стоимостиПостановка транспортной задачи на сети
Если условия транспортной задачи заданы в виде картосхемы, на которой условно изображены поставщики, потребители и связывающие их дороги, указаны величины запасов груза и потребностей в нем, а также числа cij являющиеся
[pic] 
Рис.1
показателями принятого в задаче критерияоптимальности (тарифы, расстояния и т.п.), то говорят, что транспортная задача поставлена в сетевой форме (рис. 1, 2).
Описанную картосхему будем называть транспортной сетью. Пункты расположения поставщиков и потребителей будем изображать кружками и называть вершинами (узлами) сети, запасы груза будем записывать в кружках положительными, а потребности - отрицательными числами. Дороги, связывающие пунктырасположения и потребления груза и другие пункты, будем изображать линиями и называть ребрами (дугами, звеньями) сети. При изображении транспортной сети реальный масштаб не соблюдается. На сети могут быть изображены вершины, в которых нет ни поставщиков, ни потребителей. Наличие таких вершин не повлияет на способ решения, если считать, что запасы (потребности) груза в них равны нулю.
[pic] 
Рис.2
Такиевершины называют нулевыми (см. вершину II на рис. 2). Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях. Далее мы будем использовать уже известный метод потенциалов.
Решение задачи на сети начинается с построения начального опорного плана. Поставки груза из вершины в вершину будем обозначать стрелками суказанием величин поставок.
Решение задачи на сети начинается с построения начального опорного плана.
Опорный план должен удовлетворять следующим требованиям:
1) все запасы должны быть распределены, а потребности удовлетворены;
2) к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;
3) общее количество стрелок должно быть на единицу меньше числа вершин;
4) стрелки недолжны образовывать замкнутый контур
Далее следует проверить план на оптимальность.
Для этого вычисляют потенциалы. Одной из вершин (например, вершине I) присвоим некоторое значение потенциала (например, равное 0). (Для большей наглядности потенциалы заключают в рамки.) После этого, двигаясь по стрелкам, определяют потенциалы остальных вершин, руководствуясь правилом: если стрелка выходит из вершины, ток потенциалу этой вершины прибавляем показатель Cij критерия оптимальности, если же направление стрелки противоположно, то Cij вычитаем.
После вычисления потенциалов находят характеристики ребер без стрелок по правилу: из большего потенциала вычитается меньший, а разность вычитается из показателя Cij, отвечающего данному ребру; если все ребра без стрелок имеют неотрицательные характеристики, тосоставленный план является оптимальным.
Если план не оптимален.
Для улучшения плана надо "загрузить" то ребро без стрелки, которому соответствует отрицательная характеристика. Если таких ребер несколько, то выбирается ребро с наибольшей по абсолютной величине отрицательной характеристикой и к нему подрисовывается новая стрелка. При этом образуется замкнутый контур из...
tracking img