Контрольная работа: Метод потенциалов для решения транспортной задачи

1. Каждой строке i и столбцу j транспортной таблицы ставится в соответствие числа u_i и v_j , называемые потенциалами. Они должны для каждой базисной переменной х_ij текущего решения удовлетворять условию u_i + v_j = с_ij . Эти условия приводят к системе, состоящей из m + n - 1 уравнений (так как имеется всего m + n - 1 базис-переменных), в которых фигурируют m + n неизвестных. Значение потенциалов определяют из этой системы уравнений, придавая одному из них произвольное значение (например, u_i = 0).

2. Определяются оценки c_ij для небазисных переменных в соответствии с соотношением:

с_ij = u_i + v_j – с_ij

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

4. Вводимой в базис переменной является небазисная переменная, имеющая самую большую положительную оценку с_ij .

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

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

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

После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшим к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают jзаполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице, была записана промежуточная рента.

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

После конечного числа описанных выше итераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.

III этап. Определение переменной, выводимой из базиса (построение цикла).

Процедура построения цикла эквивалентна использованию условия допустимости в симплекс-методе.

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

2. Нечетным вершинам цикла (начиная с вводимой в базис переменной) присваивается знак "+", четным – "-" (будем называть эти клетки плюсовыми и минусовыми).

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

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

Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным и равным (n + m - 1).

Однако при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать зацикливания, следует соответствующие нулевые элементы опорного плана заменить сколь угодно малым числом ε и решать задачу как невырожденную. В оптимальном плане такой задачи необходимо считать ε= 0.

транспортный задача алгоритм фогель цикл

2. Пример практического решения задачи оптимального планирования

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

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

Пример: Три поставщика некоторого товара располагают следующими запасами: первый – 120 единиц, второй – 100 единиц, третий – 80 единиц. Товар должен быть перевезен трем потребителям: спрос первого – 90 единиц; спрос второго – 90 единиц; спрос третьего – 120 единиц. Известны также показатели затрат (c_ij ) на перевозку единицы товара от каждого поставщика к каждому потребителю.

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

Под планом перевозок понимается матрица

X11	X12	X13
X21	X22	X23
X31	X32	X33

в которой х_ij количество единиц товара, планируемого к перевозке от поставщика с номером i к потребителю с номером j.

Для решения задачи исходные данные удобно свести в таблицу:

Поставщики	Возможности поставщиков	Потребители и их спрос
		1	2	3
		90	90	120
1	120	7	6	4
2	100	3	8	5
3	80	2	3	7