1.3.2.1 Закрытая транспортная задача Минимизация стоимости перевозок кирпича

Постановка задачи

Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготавливать 100, 150 и 50 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 70, 80, 60 и 90 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого из заводов к каждому из строящихся объектов, они заданы матрицей С следующего вида:

. (***)

Составить такой план перевозок кирпича от заводов к стоящимся объектам, при котором общая стоимость перевозок будет минимальной.

Представим данные задачи в виде следующей таблицы:

Таблица 10

	Стоимость перевозки 1 усл. ед. кирпича с завода к строящемуся объекту				Возможности заводов
Объекты Заводы	1	2	3	4
I	6	7	3	5	100
II	1	2	5	6	150
III	8	10	20	1	50
Потребность объектов в кирпиче	70	80	60	90

В данной задаче потребность всех объектов в кирпиче равна запасам всех заводов (70+80+60+90=100+150+50), т.е. она является закрытой, а следовательно разрешима.

Решение

I этап: Составление математической модели

Элементы модели

1. Переменные (неизвестные) задачи

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

Ведем следующие переменные:

–количество усл.ед. кирпича, перевозимого с i – ого завода на j – ый строящийся объект, i=1,2,3, j = 1,2,3,4.

В итоге мы имеем 12 неизвестных.

Примечание: Например, x12 – количество усл. ед. кирпичей, которые необходимо перевезти с 1 – ого завода ко 2 - ому строящемуся объекту.

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

Цель задачи – минимизировать стоимость перевозок. Т.к. стоимость перевозки 1 усл. ед. от каждого завода к каждому объекту нам известна (см.*) т.о. S будет иметь вид:

S=6*x11+7*x12+3*x13+5*x14+1*x21+2*x22+5*x23+6*x24+

+8*x31+10*x32+20*x33+1*x34 (руб.)

3. Ограничения

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

Ограничения «на производство» кирпича:

x11+x12+x13+x14=100, (13)

x21+x22+x23+x24=150, (14)

x31+x32+x33+x34=50, (15)

Ограничения «на потребности» в кирпиче:

x11+x21+x31=70, (16)

x12+x22+x32=80, (17)

x13+x23+x33=60, (18)

x14+x24+x34=90, (19)

xi0, i=1,2,3,4, (20)

xi – целые числа (21)

Примечание: Ограничения (20) и (21) представляют собой следующие естественные условия: количество перевозимых кирпичей должно быть не отрицательным и целым.

Таблица 11

Неизвестные
– количество усл.ед. кирпичей, перевозимых сi – ого завода наj – ый строящийся объект,i=1,2,3,j= 1,2,3,4.
Целевая функция	Ограничения
S=6*x11+7*x12+3*x13+5*x14+ +1*x21+2*x22+5*x23+6*x24+ +8*x31+10*x32+20*x33+1*x34 (руб.)	x11+x12+x13+x14=100, x21+x22+x23+x24=150, x31+x32+x33+x34=50, x11+x21+x31=70, x12+x22+x32=80, x13+x23+x33=60, x14+x24+x34=90 xi0, i=1,2,3,4, xi – целые числа