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

Классическая постановка транспортной задачи общего вида такова.  Имеется 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 обозначает объем перевозок из пункта A_i в пункт В_j. Набор переменных X = {x_ij} и будет планом, который необходимо найти, исходя из постановки задачи.

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

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

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

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

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

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

Транспортные задачи с неправильным балансом

В рассмотренной модели транспортной задачи мы предполагали, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. 

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

в рассмотрение вводится фиктивный потребитель с потребностью    и тарифами на перевозку c_{i ( k +1)} =0. Если же то вводится фиктивный поставщик, запасы которого равны

с тарифами на перевозку c _{( n +1)j}=0.  Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0).

Сведение транспортной постановки к задаче линейного программирования.

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА И ФОРМАЛЬНАЯ МОДЕЛЬ ТЗЛП

Пусть имеется m пунктов производства однородной или взаимозаменяемой продукции. Каждый из пунктов производства обозначим через , где i= 1,...,m. Через  будем обозначать  объем продукции, производимой в пункте . И пусть имеется n пунктов потребления (назначения) данной продукции, каждый из которых будем обозначать , где  j=1,...,n , а через  будем обозначать объем потребления (спроса) продукции в пункте  .  Стоимость перевозки единицы продукции от i-го  производителя к  j-му  потребителю составляет  (i=1,...,m, j=1,...,n). Предполагается, что транспортные расходы на перевозки между любой парой пунктов пропорциональны объему перевозимого продукта. Требуется установить такие объемы перевозок  от каждого производителя к каждому потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены (если только объем возможных поставок покрывает общий объем потребления). Представим транспортную модель в виде сети. В ней: вершины соответствуют пунктам производства и потребления, дуги, соединяющие вершины, представляют собой маршруты, по которым перевозится продукция, вес дуги – расстояние между соотв. пунктами.