13.Построение первоначального опорного плана по правилу наименьшей стоимости

Построение плана по правилу наименьшей стоимости заключается в следующем. Рассматриваем матрицу (таблицу) транспортных расходов, стоимостей, данную изначально в качестве условия задачи. Выбираем клетку с минимальной ценой перевозки (клетка с номером i, j) и помещаем в эту клетку наименьшее из чисел {ai, bj}. Затем исключаем из рассмотрения строку, соответствующую поставщику (если аi меньшее), или столбец, соответствующий потребителю (если в j меньшее). Исключение строки означает, что запасы i-го потребителя удовлетворены. Из оставшейся таблицы снова выбираем наименьшую стоимость, и т.д. продолжаем до тех пор, пока все запасы не исчерпаны, а потребности не удовлетворены. Проверьте, что сумма чисел в каждой строке получившейся таблицы равна а i, а сумма чисел в каждом столбце равна вj, что и требовалось. Число занятых клеток должно равняться m + n – 1, в противном случае, если занятых клеток меньше, чем m + n – 1, дополним таблицу необходимым количеством нулей (нулевых перевозок) и будем считать эти клетки с нулями занятыми так, чтобы общее количество занятых клеток равнялось равноm + n – 1. Нули поставим в клетки, соответствующие минимальной стоимости..

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

Решение транспортной задачи методом северо-западного угла

Имеются три пункта отправления А1, А2, А3 однородного груза и пять пунктов В1, В2, В3, В4, В5 его назначения. На пунктах А1, А2, А3 груз находится в количестве а1, а2, а3 тонн соответственно. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Расстояние в сотнях километров между пунктами отправления и назначения приведены в матрице D.

Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными. Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах; 2) для решения задачи использовать методы северо-западного угла и потенциалов

14.Метод потенциалов

При построении плана мы ставим задачу найти хоть какой-нибудь, не обязательно лучший, оптимальный план, удовлетворяющий ограничениям задачи. Теперь нам хотелось бы уметь отвечать на вопрос: является ли найденный опорный план оптимальным, и если нет, то «улучшать» его. Эту задачу решает метод потенциалов, предложенный в 1949 г. советскими учеными Л.В. Канторовичем и М.К. Гавуриным. теоретической основой метода является теорема.

Теорема. Если для некоторого опорного плана Х = { xij} транспортной задачи можно подобрать систему из m + n чисел u1, u2, …, um, v1, v2, … vn, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия: для всех xij > 0 (1)

для всех i = 1,m, j = 1,n

где (cij) – матрица стоимостей перевозок.

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

I шаг (вычисление потенциалов).

Условие (1) представляет собой систему из ( m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.

II шаг (проверка плана на оптимальность).

Для проверки плана на оптимальность необходимо проверить условие (2). Для занятых клеток это условие выполняется, именно на них достигается равенство. Остается посчитать суммы ui + vj для свободных клеток. Если ui + vj ≤ сij, то, по теореме, план является оптимальным и задача решена.

III шаг (улучшение плана).

Для проведения операции улучшения плана нам понадобится понятие цикла.

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

Графически нетрудно представить цикл в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену.

Примеры:

С понятием цикла связаны важные свойства планов:

допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла;

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

Улучшение плана производится по следующей схеме. В подчеркнутых клетках табл. 2 находим клетку с наибольшей разностью ui + vj – cij, т.е. где условие (2) нарушается максимально.

Затем для этой клетки, согласно утверждению 2, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке.

Начиная с клетки (1, 1), где условие (2) нарушено максимально, строим цикл. Клетку (1, 1) помечаем знаком «+». Цикл единственен, у нас все занятые клетки вошли в цикл, но это необязательно. Строим новый план хn по правилу:

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

http://conf.sfu-kras.ru/sites/mn2012/thesis/s011/s011-001.pdf

метод гомори

http://vtit.kuzstu.ru/books/shelf/65/doc/glava_2.html