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

Постановка транспортной задачи: некоторый однородный продукт, сосредоточенный у М поставщиков в количестве a_i (i = 1,…,M) единиц соответственно, необходимо доставить N потребителям в количестве b_j (j=1,…,N). Известна стоимость С_ij перевозки единицы груза от i–го поставщика к j–ому потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

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

X_ij – управляемые переменные, количество единиц груза.

Целевая функция:

Система ограничений:

• все грузы вывезены
• все потребности удовлетворены .

Граничные  условия X_ij ³ 0.

Прежде чем решать транспортную задачу, необходимо сначала  определить, к какому типу она принадлежит.

 

 

Типы моделей:

1. Модель закрытая:
2. Модель открытая:

• суммарные запасы превышают суммарные потребности: .

Для преобразования открытой модели данного вида к закрытой необходимо ввести фиктивного потребителя, потребности которого равны:  

• суммарные потребности превышают суммарные запасы: .

Для преобразования открытой модели данного вида к закрытой необходимо ввести фиктивного поставщика, объем производства которого равен:

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

Рассмотрим несколько  примеров.

Пример 1: суммарный объем потребностей больше суммарного объема производства.  Потребности некоторых потребителей обязательно должны быть удовлетворены полностью.

Решение:

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

Пример 2: суммарный объем  производства больше суммарного объема потребностей. От некоторых поставщиков  нужно вывести всю продукцию.

Решение:

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

Пример 3: груз от поставщика, по каким – то причинам не может  быть направлен одному из потребителей.

Решение: заблокировать клетки.

Частным случаем транспортной задачи является задача оптимального назначения.

Постановка задачи: пусть, имеются М лиц a_i (i=1,…,M), которые могут выполнять b_j (j=1,…,M) видов различных работ. Известна производительность i–го лица при выполнении j–ой работы С_ij. Необходимо определить, кого и на какую работу следует назначить, что бы добиться максимальной суммарной производительности при условии, что каждое лицо может быть назначено только на одну работу.

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

X_ij – управляемые переменные, назначение i–го лица на j-ую работу.

X_ij принимает значение “0” или “1”. (“0” – не назначен; “1” – назначен).

Целевая функция: .

Система ограничений:

Граничные условия X_ij ³0

 

Составить план перевозки  песка из пунктов отправления: песчаный карьер №1, железнодорожная товарная станция, речной грузовой порт, песчаный карьер №2, в пункты назначения ЖБИ №1, ЖБИ №2, ДСК, при котором затраты на перевозку будут минимальными. Затраты на перевозку 1 т песка  между пунктами отправления и назначения указаны в таблице исходных данных в км. Потребности ДСК должны быть удовлетворены полностью.

 

Таблица 8 – Таблица  исходных данных

Поставщик	Потребитель			Запас
	ЖБИ №1	ЖБИ №2	ДСК
Песчаный карьер №1	11    x11	15   x12	7     x13	120
Ж/д станция	12   x21	16   x22	14   x23	200
Речной порт	13   x31	10   x32	9     x33	80
Песчаный карьер №1	14    x41	9     x42	11   x43	100
Фиктивный поставщик	0      x51	0     x52		50
Заявки	160	170	220

 

Определим тип модели:

Следовательно, модель открытого  типа. Для решения задачи необходимо ввести фиктивного поставщика, а также  учесть, что потребности ДСК должны быть удовлетворены полностью, запретив перевозку Фиктивный поставщик  – ДСК.

Целевая функция:

W = 11·X₁₁+15·X₁₂+ 17·X₁₃+ 12·X₂₁+ 16·X₂₂+ 14·X₂₃+ 13·X₃₁ +10·X₃₂ +       +9·X₃₃+ 14·X₄₁+ 9·X₄₂ + 11·X₄₃ + 0·X₅₁ + 0·X₅₂ ® max

Система ограничений:

• все потребности удовлетворены

x₁₁+x₂₁+x₃₁+x₄₁+x₅₁=160

x₁₂+x₂₂+x₃₂+x₄₂+x₅₂=170

x₁₃+x₂₃+x₃₃+x₄₃        =220

• все запасы вывезены

x₁₁+x₁₂+x₁₃=120

x₂₁+x₂₂+x₂₃=200

x₃₁+x₃₂+x₃₃=80

x₄₁+x₄₂+x₄₃=100

x₅₁+x₅₂       =50

Граничные условия X_ij ³0