Тема 2. Решение транспортной задачи.

Транспортная задачка (ТЗ) является одной из более узнаваемых ЗЛП. Разглядим её постановку по аспекту цены. Пусть в m пт отправления А1,...,Аm сосредоточен груз в количествах а1,...,аm единиц. Этот груз нужно доставить к потребителям В1,...,Вn, спрос которых b1,…,bn единиц соответственно. Известна цена cij перевозок единицы груза из пт Тема 2. Решение транспортной задачи. Ai в пункт Bj. Требуется составить план перевозок, который стопроцентно удовлетворяет спрос потребителя в грузе и при всем этом минимизируют суммарные транспортные издержки.

Пусть xij – количество единиц груза, которое нужно доставить из пт Ai в пункт Bj, тогда план перевозок имеет вид

X=

Для наглядности ТЗ комфортно представить в Тема 2. Решение транспортной задачи. виде распределительной таблицы:

поставщик Потребитель Припас груза ai
B1 B2 Bn
A1 c11 x11 c12 x12 c1n x1n a1
A2 c21 x21 c22 x22 c2n x2n a2
Am cm1 xm1 cm2 xm2 cmn xm2n am
Потребноть в грузе bj b1 b22 bn

и как ЗЛП Тема 2. Решение транспортной задачи. :

f(X) = f(x11, x12…..xmn)=

План Х, удовлетворяющий условиям (2.1), именуется допустимым планом, а план Х, минимизирующий мотивированную функцию b(x), именуется хорошим ланом.

Допустимый план Х считается базовым, если посреди его частей xij равно

(m+n-1) ненулевых.

Способ нахождения рационального плана именуется способом потенциалов. Он носит итерационный нрав Тема 2. Решение транспортной задачи. и состоит из нескольких стадий:

Построение исходного базового плана;

Проверка базового плана на оптимальность;

Улучшение базового плана.

Исходный базовый план удобнее выстроить, к примеру, по правилу малого элемента. В данном случае просматриваются тарифы распределительной таблицы и сначала заполняется клеточка с наименьшим тарифом. При всем этом в клеточку записывается очень вероятное значение Тема 2. Решение транспортной задачи. поставки. После чего все другие клеточки строчки, соответственной этому поставщику, считается свободными, если его припас на сто процентов исчерпан, либо все другие клеточки столбца, соответственного потребителю, числятся свободными, спрос которого вполне удовлетворён. Дальше из оставшихся клеток опять выбирают клеточку с наименьшим тарифом и т.д. Для Тема 2. Решение транспортной задачи. избранного исходного базового плана ( он содержит m+n-1 базовых заполненных клеток) определяют потенциалы Ui и Vj для тех клеток, где xij из критерий vj-4i=cij . Этих критерий m+n-1, а неведомых m+n, потому одному из потенциалов присваивают случайное ( к примеру нулевое) значение, а другие неведомые потом определяются совершенно Тема 2. Решение транспортной задачи. точно.

Дальше, для свободных ( пустых) клеточки проверяются условия vj-uj именуются разностями потенциалов.

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

(

«+» «-»

«-» «+»

(l,

Рис. 2.1

В рассматриваемой цепочке ставятся знаки«+» и «-» попеременно. Из клеток со знаком «-» выбирается та, для которой объём перевозок мал, обозначим его через ( к примеру, ), после этого происходит перерасчет в рамках данной цепочки: в клеточке с «+» добавляется , в клеточках с «-» вычитается . Таким макаром, клеточка ( ) становится свободной. В конечном итоге Тема 2. Решение транспортной задачи. выходит новый базовый план, для которого вновь определяются потенциалы, после этого он проверяется на оптимальность и т.д.

Пример 2.1.

На 3-х складах A1, A2, A3 хранится единиц 1-го и такого же груза. Этот груз требуется доставить четырём потребителям B1, B2, B3, B4, заказы которых составляют единиц груза соответственно Тема 2. Решение транспортной задачи.. Цены j перевозкой единиц груза с i-го склада j-ому потребителю указана в правых верхних углах соответственных клеток распределительной таблицы:

ai
4 2 3 1
6 3 5 6
3 2 6 3
bj

Используя способ потенциалов, составить лучший план , обеспечивающий наименьшую цена перевозок fmin=f(X*) и отыскать эту цена.

Решение.

Имеем m=3, n=4, откуда m+n- 1=6. Как следует Тема 2. Решение транспортной задачи. для получения исходного базового плана X0 нужно заполнить 6 клеток распределительно таблицы:

ai
4 2 10 3 1 70
6 10 3 40 5 50 6
3 70 2 6 3
bj

Таким макаром, исходный базовый план

X0 =

Проверим этот план на оптимальность. Для этого найдем потенциалы vj и ui надлежащие заполненным клеточкам (1,2), (1,4), (2,1), (2,2), (2,3) и (3,1). Пусть v1=0, тогда имеем

(2.2)

Решив систему уравнений (2,2), получим u1=-5, u2=-6, u3=-3, v1=0, v2=-3, v3=-1, v Тема 2. Решение транспортной задачи.4=-4

Дальше для незаполненных клеток (1,1), (1,3), (2,4), (3,2), (3,3) и (3,4) вычислим разности потенциалов:

Откуда следует что для клеток (1,1) и (1.3) , а означает, план X0 не является хорошим.

Так как то в качестве свободной клеточки, которая на последующей стадии решения задачки будет заполнена, разумно избрать клеточку (1.3). Эта клеточка является верхушкой квадрата, другие верхушки которого (1,2), (2,2) и (2,3) представляют собой Тема 2. Решение транспортной задачи. заполненные клеточки, потому перерасчет следует сделать в рамках этой цепочки (см. рис. 2.2):

«-» «+»

(1,2) (1,3)

«+» «-»

(2,2

Рис. 2.2

Для клеток со знаком «-» имеем x12=10,x23=50откуда . Таким макаром, в клеточке со знаком «+» прибавится 10 единиц груза, а в клеточках со знаком «-» такое же количество груз а отнимается. В конечном итоге получим новейшую распределительную таблицу:

ai
4 2 3 10 1 70
6 10 3 50 5 40 6
3 70 2 6 3
bj Тема 2. Решение транспортной задачи.

и новый базовый план

X1=

Проведя рассуждения, аналогично рассуждениям для плана Х0 найдем потенциалы vj и ui для базовых клеток и разности потенциалов для свободных клеток плана X1 .

Расчеты проявили, что все а означает, план X1 оптимален, другими словами X1=X*. Малая цена перевозок груза .fmin =f(X Тема 2. Решение транспортной задачи.*)= 3


tema-2-marketingovie-issledovaniya-turistskogo-rinka.html
tema-2-mesto-cheloveka-v-zhivotnom-mire.html
tema-2-metodi-sociologii-mnsterstvo-osvti-ta-nauki-ukrani.html