Классическая транспортная задача. (КТЗ)

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

1.1 Постановка задачи. Имеются пункты производства некоторой однородной продукции. В каждом пункте объем производства составляет . Эта продукция поставляется в пункты потребления , причем потребность пункта равна . Перевозка продукции возможна из любого пункта в любой пункт , при этом стоимость перевозки единицы продукции определяется величиной . Требуется найти такой план перевозки продукции, при котором запросы всех пунктов потребления будут полностью удовлетворяться, запасы продукции из всех пунктов производства полностью вывозиться, а суммарная стоимость перевозки была бы минимальной.

Замечание. Очевидно, что при такой постановке решение задачи будет существовать только если выполняется условие баланса: . Такая КТЗ называется закрытой.. Графическая интерпретация задачи представлена на рис.1.

1.2Математическая модель КТЗ.

Пусть - количество продукции, перевезенной из пункта А_i в B_j. Тогда ММ КТЗ запишется в виде:

(1)

(2)

(3)

(4)

Здесь целевая функция (1) отражает суммарные транспортные расходы. Ограничения (2) требуют, чтобы вся продукция была вывезена, а ограничения (3) – чтобы потребности всех пунктов потребления были удовлетворены. Условие (4) вытекает из физического смысла введенных переменных.

Ограничения (2)-(4) задают планы перевозок (х_ij)_mxn. Т.О., ММ КТЗ относится к классу ЗЛП. В этой задаче - активные средства, - определенные (фиксированные) неконтролируемые факторы, а матрица плана перевозок - стратегии оперирующей стороны. Цель операции задается целевой функцией (1). Если некоторая матрица является решением ЗЛП (1)-(4), то она является оптимальной (наилучшей) стратегией оперирующей стороны. Т.к. КТЗ относится к классу ЗЛП, то она может быть решена стандартными методами ЛП. Однако, учитывая особенности КТЗ, можно модифицировать общие алгоритмы решения ЗЛП таким образом, чтобы получить более эффективные алгоритмы. Для решения КТЗ используется алгоритм, разработанный в соответствии с методом потенциалов.

Решение КТЗ методом потенциалов.

Метод потенциалов является модификацией метода последовательного улучшения плана в ЗЛП. Решение задачи включает в себя следующие этапы:

1. Построение начального опорного плана.

2. Проверка опорного плана на оптимальность.

3. Переход в случае необходимости к лучшему опорному плану.

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

Затем необходимо построить начальный опорный план.

1.Построение начального опорного плана.

Всего существует три метода отыскания начального ОП:

1) Метод северо-западного угла,

2) Метод минимального элемента,

3) Метод Фогеля.

Рассмотрим 2 первых метода.