РЕФЕРАТ

по дисциплине МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ

на тему: «Метод потенциалов для решения транспортной задачи»

Москва, 2010

1. Решение транспортной задачи

Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут такими:

Iэтап. Нахождение начального допустимого решения.

IIэтап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае — перейти к III этапу.

IIIэтап. Выбор выводимой из базиса переменной (используя условия допустимости) из числа переменных текущего базиса; затем нахождение нового базисного решения и возвращение ко II этапу.

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

I этап. Определение начального допустимого решения

Для сбалансированной транспортной задачи существует только m + n - 1 независимых уравнений. Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных.

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

1. Правило "северо-западного угла"

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х11 приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина сij). Более совершенным правилом является правило "минимального элемента".

2.Правило "минимального элемента"

В методе "северо-западного угла" на каждом шаге потребность первого из оставшихся пунктов назначения удовлетворяется за счет запасов первого из оставшихся пунктов отправления. Очевидно, что выбор пунктов назначения и отправления целесообразно производить, ориентируясь на стоимость перевозок, а именно на каждом шаге следует выбирать какую-либо клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассматривать пункты назначения и отправления, соответствующие выбранной клетке.

Правило "минимального элемента" заключается в том, чтобы перевозить максимально возможные объемы из пунктов отправления маршрутами минимальной стоимости. Заполнение таблицы начинаем с клетки, которой соответствует наименьшая стоимость перевозки (элемент cij) из всей таблицы. ............