Для данной транспортной задачи требуется составить соответствующую ей задачу линейного программирования

1) Когда спрос j=1nbj равен предложению i=1mai, формулировку транспортной задачи можно записать в виде: найти переменные xij, для которых
f=i=1mj=1ncij∙xij→min
и удовлетворяющие ограничениям:
j=1nxij=ai, i=1,2,…,m
i=1mxij=bj, j=1,2,…,n
xij≥0, i=1,2,…,m; j=1,2,…,n.
Конкретно, в нашем случае имеем задачу:
f=2x11+x21+8x31+7x12+9x22+6x32+8x13+3x23+4x33+
+5x14+x24+2x34+2x11+7x12+8x13+5x14+x21+9x22+
+3x23+x24+8x31+6x32+4x33+2x34→min
x11+x21+x31=20
x12+x22 +x32=30
x13+x23+x33=10
x14+x24+x34=20
x11+x12+x13+x14=35
x21+x22+x23+x24=25
x31+x32+x33+x34=20
xij≥0, i=1,2,3; j=1,2,3,4.
2) В общем случае для прямой транспортной задачи, сформулированной выше, двойственная задача имеет вид:
F=i=1maiui+j=1nbjvj→max
ui+vj≤cij
i=1,2,…,m;j=1,2,…,n.
Строим двойственную задачу для заданной задачи. Имеем:
F=35u1+25u2+20u3+20v1+30v2+10v3+20v4→max
u1+v1≤2
u1+v2≤7
u1+v3≤8
u1+v4≤5
u2+v1≤1
u2+v2≤9
u2+v3≤3
u2+v4≤1
u3+v1≤8
u3+v2≤6
u3+v3≤4
u3+v4≤2.
3) Построим исходный опорный план перевозок методом северо-западного угла . Т.е. начинаем заполнять таблицу перевозок, начиная с левой верхней клетки таблицы. При заполнении анализируем величину потребности (оставшейся) с величиной потребностей (не удовлетворенной) и заполняем клетку минимальным значением этих величин. Затем «двигаемся» по строке или столбцу неудовлетворенной потребности или ресурса в соседнюю клетку. Это повторяем, пока не составим план перевозок, выбирающий все ресурсы и удовлетворяющий все потребности. Число занятых клеток при этом должно быть равно m+n-1, где m - число поставщиков, n число потребителей. В нашем случае это значение равно 3+4-1=6.
Решение, построенное по правилу северо-западного угла, имеет вид:

20 30 10 20
35 2
20 7
15 8 5
25 1 9
15 3
10 1
0
20 8 6 4 2
20
Здесь мы имеем «базисный нуль».
4) Оценим построенное решение. Для этого выписываем матрицу затрат и в ней подчеркиваем элементы, соответствующие занятым клеткам.
2 7 8 5 +0
1 9 3 1 -2
8 6 4 2 -3
-2 -7 -1 +1
Справа и снизу подобраны числа - потенциалы, прибавление которых к строкам и столбцам матрицы затрат приводит к получению матрицы оценок