На трех базах A1, A2, A3 имеется однородный груз в количестве: a1 т –

На трех базах A1, A2, A3 имеется однородный груз в количестве: a1 т – на базе A1, a2 т – на базе A2, a3 т – на базе A3. Полученный груз требуется перевезти в пять пунктов: b1 т – в пункт B1, b2 т – в пункт B2, b3 т – в пункт B3, b4 т – в пункт B4, b5 т – в пункт B5. Затраты на перевозку груза между пунктами поставок и потребления заданы матрице тарифов C=(cij), где cij – стоимость перевозки 1 т груза от поставщика с номером i (i=1,2,3) к потребителю под номером j (j=1,2,3,4,5), в тыс. руб. Составить математическую модель задачи. Спланировать перевозки так, чтобы их общая стоимость была минимальной. При нахождении оптимального плана использовать метод потенциалов. a1=250, a2=200,a3=150 b1=180, b2=120, b3=90, b4=105, b5=105 C=1282110151341513211916261720

Математическая модель задачи
Обозначим: xij – объем перевозки с i-го поставщика j-му потребителю (i=1,3, j=1,5).
Тогда суммарная стоимость перевозок равна (целевая функция):
ZX=i=13j=15cijxij=12x11+8x12+21x13+10x14+15x15+13x21+4x22++15x23+13x24+21x25+19x31+16x32+26x33+17x34+20x35
Ограничения:
Запасы груза у поставщиков:
j=15x1j=x11+x12+x13+x14+x15=250
j=15x2j=x21+x22+x23+x24+x25=200
j=15x3j=x31+x32+x33+x34+x35=150
Потребности потребителей
i=13xi1=x11+x21+x31=180
i=13xi2=x12+x22+x32=120
i=13xi3=x13+x23+x33=90
i=13xi4=x14+x24+x34=105
i=13xi5=x15+x25+x35=105
Объем перевозок не может быть отрицательным числом
xij≥0 (i=1,3, j=1,5)
Таким образом, получена математическая модель задачи:
Найти минимальное значение функции
ZX=i=13j=15cijxij=12x11+8x12+21x13+10x14+15x15+13x21+4x22++15x23+13x24+21x25+19x31+16x32+26x33+17x34+20x35→min
при ограничениях
x11+x12+x13+x14+x15=250x21+x22+x23+x24+x25=200x31+x32+x33+x34+x35=150x11+x21+x31=180x12+x22+x32=120x13+x23+x33=90x14+x24+x34=105x15+x25+x35=105
xij≥0 (i=1,3, j=1,5
Решение транспортной задачи
Проверка сбалансированности транспортной задачи
Общий объем груза у поставщиков:
i=13ai=250+200+150=600
Объем груза, необходимый потребителям:
j=15bj=180+120+90+105+105=600
Т.к. суммарные запасы равны суммарным потребностям, то имеем сбалансированную транспортную задачу.
Сведем исходные данные в таблицу 1.
Таблица 1
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
12
8
21
10
15 250
A2
13
4
15
13
21 200
A3
19
16
26
17
20 150
Потребности 180 120 90 105 105 =600
Найдем опорный план методом наименьших тарифов.
Определяем клетку с наименьшим тарифом – это клетка (2,2). Помещаем в нее максимально возможную перевозку 120. При этом потребности второго потребителя полностью удовлетворены, поэтому остальные клетки второго столбца вычеркиваем из рассмотрения. Запасы второго поставщика уменьшились и стали равны 200–120=80.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом

. Это клетка (1,4). Помещаем в нее максимально возможную перевозку 105, а в остальные клетки четвертого столбца вычеркиваем из рассмотрения, т.к. потребности четвертого потребителя удовлетворены. Запасы первого поставщика уменьшились и стали равны 250–105=145.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (1,1). Помещаем в нее максимально возможную перевозку: 145. Запасы первого поставщика исчерпаны, поэтому остальные клетки первой строки вычеркиваем из рассмотрения. Потребности первого потребителя уменьшились и стали равны: 180–145=35.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (2,1). Помещаем в нее максимально возможную перевозку: 35. Запасы второго поставщика уменьшились и стали равны: 80–35=45. Потребности первого потребителя полностью удовлетворены, поэтому остальные клетки первого столбца вычеркиваем из рассмотрения.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (2,3). Помещаем в нее максимально возможную перевозку: 45. Запасы второго поставщика исчерпаны, поэтому оставшиеся клетки второй строки вычеркиваем из рассмотрения. Потребности третьего потребителя уменьшились и стали равны: 90–45=45.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (3,5). Помещаем в нее максимально возможную перевозку: 105. Потребности пятого потребителя удовлетворены. Запасы третьего поставщика уменьшились и стали равны: 150–105=45.
Последнюю пустую клетку (3,3) заполняем нераспределенной перевозкой: 45.
Количество заполненных клеток равно 7=3+5-1, поэтому опорный план невырожденный.
Полученный опорный план представлен в таблице 2.
Таблица 2
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
12
8
21
10
15 250
145
105
A2
13
4
15
13
21 200
35
120
45
A3
19
16
26
17
20 150
45
105
Потребности 180 120 90 105 105
Проверка опорного плана (таблица 2) на оптимальность методом потенциалов
Определим потенциалы каждого поставщика Ai и каждого потребителя Bj.
Для этого поставим в соответствие:
поставщику A1 – потенциал p1;
поставщику A2 – потенциал p2
поставщику A3 - потенциал p3;
потребителю B1 – потенциал q1;
потребителю B2 – потенциал q2;
потребителю B3 – потенциал q3;
потребителю B4 – потенциал q4;
потребителю B5 – потенциал q5.
Для каждой заполненной клетки составим уравнение qj-pi=cij