Курсовая работа: Решение транспортной задачи методом потенциалов

5

20

2

5

3

1

8

Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт а₁ подал заявку на 20 единиц груза. Удовлетворим эту заявку за счёт запаса 15, имеющегося в пункте b ₁ , и запишем перевозку 15 в клетке (1,1). После этого дополним заявку за счет заявка пункта b ₂ , и запишем 5 в клетке (1,2), теперь заявка удовлетворена, но в пункте b ₂ осталось ещё 10 единиц груза. Удовлетворим за счёт них заявку пунктов а₂ (5 единиц клетка 2,2) и а₃ (5 единиц клетка 2,3). На складе b ₃ есть запас в 20 единиц, за счет его мы удовлетворим оставшиеся заявки а₃ (оставшиеся 5 единиц клетка 3,3), а₃ (10 единиц клетка 3,4) и а₅ (5 единиц клетка 3,5).

5
6	4	7
		3	1	8

На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок С _ij .

1.2 Метод потенциалов

Пусть имеется транспортная таблица, соответствующая начальному решению, х _il = для базисного решения переменных, х _il = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными p_ij .

Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u ₁ ,…, u_m , в нижнюю строку – значения неизвестных v ₁ ,…, v_n ,. Эти m + n неизвестных для всех ( i , j ) , соответствующих базисным переменным, должны удовлетворять линейной системе уравнений u_i + v_j = p_ij .

pll		plj		pln	ul
	. … .		. … .		. « 2 3 4 5 6 7 8 9 10 11 » К-во Просмотров: 311 Бесплатно скачать Курсовая работа: Решение транспортной задачи методом потенциалов >>> Скачать <<< Меню Поиск