Составление сметы на весь комплекс проектно-изыскательских работ по форме 2П. Модель транспортной задачи в аналитическом виде, страница 6

Исходные данные транспортной задачи удобно представить в таблице. Если ресурсы обозначим через a_i, а потребности - через b_j, элементы матрицы коэффициентов производительности труда - через С_ij, а искомые количества ресурсов исполнителей по видам работ - через x_ij, то в общем виде получим следующую таблицу:

Таблица 3.5

	b1	b2	…	bi	…	bm	Ui
a1	C11   X11	C12   X12	…	C1j   X1j	…	C1n   X1n	U1
a2	C21   X21	C22   X22	…	C2j   X2j	…	C2n   X2n	U2
…	…	…	…	…	…	…	…
ai	Ci1   Xi1	Ci2   Xi2	…	Cij   Xij	…	Cin   Xin	Ui
…	…	…	…	…	…	…	…
am	Cm1   Xm1	Cm2   Xm2	…	Cmj   Xmj	…	Cmn   Xmn	Um
vj	V1	V2	…	vj	…	Vn

Пользуясь данными табл.3.5, запишем экономико-математическую модель задачи. При этом будем иметь в виду, что в конечном итоге необходимо обеспечить максимальную производительность труда и что методом потенциалов можно решить только закрытую транспортную задачу, в которой общее количество ресурсов в точности соответствует потребности в них. (В случае неравенства этих значений необходимо введение фиктивного ресурса или фиктивных потребностей с тем, чтобы свести открытую транспортную задачу к закрытой).

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

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

	m    n

 

i=1  j=1

                       F = S  S C_ij x_ij       max                    

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

	m				m

 

i=1

j=1

i=1

j=1

x_ij >=0; S a_i = S b_j; S x_ij = a_i; S x_ij = b_j

ограничения 3) и 4) вызваны тем, что в каждом случае необходимо распределить равно Q_i ресурсов и соответственно удовлетворить потребности в количестве равно b_j ресурсов. Полученная система ограничений содержит mn неизвестных при числе уравнений m+n. Последнее указывает на то, что система уравнений совместна и неопределенна, т.е. Имеет множество решений.

При отыскании исходного опорного решения в данном случае используем метод северо-западного угла. Он состоит в следующем:

Выбираем клетку (1,1), находящуюся в северо-западном углу таб. 3.5, и назначаем в эту клетку наибольшее возможное значение x₁₁. Это будет очевидно минимальное из a₁ и b₁. Затем переходим к соседней клетке (1,2), если x₁₁ = b₁, или к соседней клетке (2,1), если x₁₁ = a₁, и вписываем в нее наибольшее из возможных значений ресурсов. Последовательно перемещаясь таким образом и достигнув юго-восточного угла таблицы, получим исходный базисный план (см. пример ниже). В базисном плане число заполненных (базисных) клеток таблицы должно быть не более чем m+n–1 (m – число строк таблицы, n - число столбцов).

Составив допустимый базисный план и убедившись в несовпадении заданных ограничений, следует проверить полученный план на оптимальность. Для этой цели рассчитываем систему потенциалов U_i,V_j, таких, чтобы для всех заполненных (базисных) клеток, т.е. клеток, в которых x_ij > 0, удовлетворялось бы равенство