Реферат: Математические методы в экономике 3

Классическая транспортная задача формулируется следующим образом:

Имеется m пунктов отправления (производства) A₁ , A₂ , ... ,A_m , в которых расположены запасы некоторого однородного продукта (груза). Объём этого продукта в пункте A_i составляет a_i единиц. Кроме того, имеется n пунктов потребления B₁ , B₂ , ... ,B_n . Объём потребления в пункте B_j составляет b_j единиц. Предполагается, что из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления. Известна также стоимость c_ij перевозки единицы продукта из пункта A_i в пункт B_j .

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

При такой постановке данную задачу называют транспортной задачей по критерию стоимости.

В общем виде исходные данные представлены в таблице 9.

Таблица 9

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

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой .

П.1 Алгоритм метода минимального элемента.

1. Из распределительной таблицы 9 выбирают наименьшую стоимость и в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j (если таких клеток несколько, то выбирают любую);

2. Из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и то и другое;

3. Из оставшейся части таблицы снова выбирают наименьшую стоимость и процесс продолжается до тех пор, пока все запасы не будут вывезены, а потребности удовлетворены;

4. Рассчитывают транспортные расходы: сумма произведений количества перевезенной продукции на стоимость для занятых клеток.

П. 2 Алгоритм метода Фогеля.

1. В каждой строке находят разность между двумя наименьшими стоимостями и записывают ее около соответствующей строки справа;

2. В каждом столбце находят разность между двумя наименьшими стоимостями и записывают ее под соответствующим столбцом;

3. Среди всех полученных разностей находят максимальную и распределяют объем перевозки в клетку строки или столбца с наименьшей стоимостью;

4. Исключают из рассмотрения строку или столбец с распределенными поставками и возвращаются к пункту 1. Процесс продолжается до тех пор, пока все запасы не будут вывезены, а потребности удовлетворены;

5. Когда план построен, рассчитываются транспортные расходы.

П.3 Алгоритм метода двойного предпочтения.

1. В таблице 9 в каждом столбце отмечают галочкой клетку с наименьшей стоимостью и в каждой строке отмечают галочкой клетку с наименьшей стоимостью;

2. В клетки с двумя галочками записывают максимально возможные объемы перевозок, каждый раз, исключая соответствующий столбец или строку;

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

4. В оставшейся части таблицы перевозки распределяют в клетки с наименьшей стоимостью.

5. Когда план построен, рассчитываются транспортные расходы.

П.4. Алгоритм метода северо-западного угла.

1. Пользуясь таблицей 9 распределяют груз, начиная с левой верхней, условно называемой северо-западной, клетки (1,1). Необходимо удовлетворить потребности В₁ за счет поставщика А₁ ;

2. а). Если b₁ >a₁ , в клетку (1,1) записывают a₁ и строку 1 вычеркивают из рассмотрения;

b). Если a₁ >b₁ , в клетку (1,1) записывают b₁ и столбец 1 вычеркивают из рассмотрения;

3. а). Если b₁ >a₁ , ∆= b₁ - a₁ – неудовлетворенные потребности. Спускаются на клетку вниз и сравнивают ∆ с a₂ ;

b). Если a₁ >b₁ , ∆=a₁ - b₁ – не вывезенные запасы. Двигаются по строке вправо и сравнивают ∆ с b₂ ;