Сталеплавильная компания располагает тремя заводами P1, P2, P3, способными произвести в неделю 50, 30

Сталеплавильная компания располагает тремя заводами P1, P2, P3, способными произвести в неделю 50, 30 и 30 тысяч тонн стали соответственно. Свою продукцию компания поставляет трем потребителям M1, M2 и M3, потребности которых составляют соответственно 45, 25 и 40 тысяч тонн стали. Стоимости производства и транспортировки 1 тысячи тонн стали с различных заводов различным потребителям приведены в таблице: Заводы Потребители M1 M2 M3 P1 15 10 14 P2 19 18 16 P3 12 15 20 Требуется найти план перевозок стали от производителей потребителям, минимизирующий общую стоимость.

Имеем дело с транспортной задачей.
Наличие груза у поставщиков (заводов) равно:
i=13Pi=50+30+30=110 тысяч тонн.
Общая потребность в грузе в пунктах назначения равна:
j=13Mj=45+25+40=110 тысяч тонн.
i=13Pi=j=13Mj, следовалеотно
модель транспортной задачи является закрытой. Задача разрешима.
Найдем опорный план задачи методом минимального элемента. Минимальный тариф равный 10 находится в клетке P1,M2. Поэтому заполняем эту клетку. P1>M2. Следовательно, в клетку P1,M2 помещаем 25 тысяч тонн стали. Потребности пункта M2 полностью удовлетворены. Поэтому исключаем из рассмотрения второй столбец, и будем считать запасы завода P1 равными 50−25=25 тысяч тонн стали.
Следующий минимальный тариф равный 12 находится в клетке P3,M1. Поэтому заполняем эту клетку. Так как P3<M1 в клетку P3,M1 помещаем 30 тысяч тонн стали. Запасы завода P3 полностью исчерпаны. Поэтому исключаем из рассмотрения третью строку, и будем считать потребности пункта M1 равными 45−30=15 тысяч тонн стали.
Минимальный тариф равный 14 находится в клетке P1,M3. Поэтому заполняем эту клетку. Так как P1<M3, в данную клетку помещаем 25 тысяч тонн стали. Запасы завода P1 полностью исчерпаны. Поэтому исключаем из рассмотрения первую строку, а потребности пункта M3 равны 40−25=15 тысяч тонн стали.
Следующую заполняем клетку P2,M3 с минимальным из оставшихся тарифов равным 16 денежных единиц

. P2>M3. Следовательно, в клетку P2,M3 помещаем 15 тысяч тонн стали. Потребности пункта тысяч тонн стали полностью удовлетворены. Поэтому исключаем из рассмотрения третий столбец, а запасы завода P2 равны 30−15=15 тысяч тонн стали.
Осталось заполнить клетку P2,M1, в которую помещаем 15 тысяч тонн стали. Запасы завода P2 полностью исчерпаны и потребности пунктаM1 полностью удовлетворены.
Таблица 1. Начальный опорный план
Заводы Потребители
Запасы
M1
M2
M3
P1
15
10
25 14
25 50
P2
19
15 18 16
15 30
P3
12
30 15 20 30
Потребности 45 25 40
При этом плане стоимость перевозок вычисляется так:
S0=25∙10+25∙14+15∙19+15∙16+30∙12=1485 (денежных единиц)
Опорный план имеет следующий вид:
02525150153000.
Проверим опорный план на оптимальность методом потенциалов. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем и решаем систему из 5 уравнений с 6 неизвестными, предположив, что один из потенциалов равен 0:
c12=u1+v2, пусть u1=0⇒v2=c12-u1=10-0=10;
c13=u1+v3 ⇒v3=c13-u1=14-0=14;
c23=u2+v3 ⇒u2=c23-v3=16-14=2;
c21=u2+v1 ⇒v1=c21-u2=19-2=17;
c31=u3+v1 ⇒u3=c31-v1=12-17=-5.
Для каждой свободной клетки проверим выполнение условия:
cij≤ui+vj.
c11=15>u1+v1=0+17=17-не выполняется;
c22=18<u2+v2=2+10=12-выполняется;
c32=15<u3+v2=-5+10=5-выполняется;
c33=20<u3+v3=-5+14=9-выполняется.
Полученные числа записываем в соответствующие клетки таблицы 2