Постановка транспортной задачи общего вида

Постановка транспортной задачи общего вида

Классическая постановка транспортной задачи общего вида такова.

Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

a_i – объемы производства i -го поставщика, i = 1, …, m;

в_j – спрос j-го потребителя, j= 1,…,n;

с_ij – стоимость перевозки одной единицы продукции из пункта A_i – i-го поставщика, в пункт В_j – j-го потребителя.

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

Потребители Поставщики	В1	В2	…	Вn	запасы
А1	С11	C12	C1n	а 1
А2	С21	C22	C2n	а2
…
Am	Cm1	Cm2	Cmn	а m
Потребности	в1	в2	в n

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

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных х_ij , i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {x_ij } и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

– условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

В силу ограничений нетрудно увидеть, что ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику, а именно: каждая переменная х _ij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути, является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности. Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (2). Заметим, что это система линейных уравнений, состоящая из m + n уравнений с m*n неизвестными. Можно доказать, что линейно независимых уравнений в системе (2) m + n – 1, ввиду условия сбалансированности, т.е. базисных переменных должно быть m + n– 1. Итак, в качестве плана будем представлять себе таблицу размера m ∙ n, в которой должно быть занято m + n – 1 клеток, отвечающих базисным переменным x_ij .

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

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

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

При построении плана мы ставим задачу найти хоть какой-нибуд

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать