Транспортная задача

Постановка:

Пусть имеется m поставщиков однотипного товара А1, А2….Аm и n потребителей В1, В2…Вn

Известны запасы каждого поставщика а1, а2…аm

И потребности каждого потребителя  в1, в2…вn

Известна стоимость перевозки  единицы товаров от каждого поставщика к каждому потребителю. Эти данные можно записать в виде матрицы mxn

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

Если это равенство не выполняется, то транспортную задачу нужно сбалансировать. Если сумма запасов больше суммы  потребностей, то мы вводим фиктивного потребителя, которому отдаём запасы.

Полагаем  стоимость перевозки от всех поставщиков  к каждому потребителю =0

Если сумма потребностей больше суммы запасов, то мы вводим фиктивного поставщика и ему присваиваем  запасы.

И стоимость перевозки так же полагаем =0

Математическая модель

Пусть Xij – количество товаров перевозимого от i поставщика к j потребителю (i=1….m; j=1….n)

Транспортная задача размерности 2х3

Даже при небольшой трансп задаче матрица получается большой размерности  и с малым заполнением, то есть с большим числом 0, поэтому несмотря на то, что транспортная задача лин программирования использование симплекс метода при её решении нерационально.

На этом примере напишем двойственную задачу для транспортной задачи.

Прежде чем заполнять таблицу следует убедиться, что задача сбалансирована. (Сумма ресурсов=Сумме потребностей)

Если же это требование не выполняется, то вы должны ввести фиктивного потребителя, если запасы больше  потребностей или  фиктивного поставщика, если потребности больше запасов.

Cij – стоимость перевозки товаров от I поставщика к j потребителю.

Если есть фиктивный поставщик  или потребитель, то стоимость перевозок  соот-х ему =0.