Курсовая работа: Решение транспортной задачи

Общая сумма производимой продукции больше или равна спросу:

Следовательно c_{i , j} тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i – запасы груза в i-м пункте отправления, черезb_j – потребности в грузе в j-м пункте назначения, а через х_{i , j} – количество единиц груза, переводимого из i-го пункта определений в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции.

2. Формулировка задачи

Число производителей

k=3

а₁ =38

Объем производимой продукции

а₂ =45

а₃ =97

Число потребителей

m=4

b₁ =42

b₂ =35

Потребности потребителей:

b₃ =63

B₄ =15

Производители	Потребители
	j=1	j=2	j=3	j=4
i=1	10	11	18	32
i=2	16	14	20	25
i=3	26	28	22	30

Рис. 1

На рисунке 1 представлен исходный граф, который иллюстрирует транспортную задачу. Для решения данной задачи требуется использовать стандартную форму фиксированного источника и стока. Каждый производитель связан с каждым потребителем. Источник не может иметь связи с потребителем, но зато каждый потребитель, в свою очередь, связан с фиктивным стоком. В обозначении дуги присутствует два параметра. Первый параметр указывает пропускную способность дуги, второй параметр показывает стоимость пересылки единицы потока на дуге. Так, например, из источника выходят дуги содержащие ограничения по пропускной способности, т.к. данная величина характеризует производительную возможность каждого поставщика, стоимость данной дуги равна нулю, т.к. источник – фиксированный элемент нашего графа. Такая же ситуация обстоит с дугами, которые втекают в сток. Дуги, которые выходят из i-ых вершин (производители) и входят j-ые вершины (потребители), т.е. соединяющие поставщика со складок, характеризуются тоже двумя параметрами. Только в этом случае, для данных дуг, в качестве первого параметра берется пропускная способность дуги равная бесконечности, а второй показатель – стоимость пересылки единицы потока.

3. Теоретическое обоснование. Общие вопросы

Сеть (транспортная сеть) – частный случай ориентированного графа. Транспортная сеть G=( V,E) – ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность. Выделяются две вершины: источник v и сток u такие, что любая другая вершина сети лежит на пути из v в u. v – это единственная вершина (v – источник ), которая не содержит входящих дуг , а содержит только выходящие дуги. u – это единственная вершина (u - сток), которая не содержит выходящих дуг. Все остальные вершины – промежуточные вершины. Для любой промежуточной вершины существует путь из источника в сток. Сеть не содержит контуров. Если для сети указаны пропускные способности, то такая сеть называется транспортной сетью.

Поток – это определенная величина на дуге е. Поток в сети G=( V,E) – это функция f, заданная на дугах сети, значение на дуге е – это величина на дуге е. Для всех промежуточных вершин соответствует сумма величин потоков на дугах входящих в вершину w, которая равна выходящему из вершины потоку.

Величина потока в сети.

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