Вырождение в задачах линейного программирования

Решение или распределение является вырожденным, если в нем имеется менее m + n - 1 заполненных клеток, поскольку из-за недостатка заполненных клеток нельзя построить циклы пересчета для части свободных клеток. Для устранения вырождения необходимо количество заполненных клеток довести до m + n - 1. Для этого среди свободных клеток выбирается ровно столько, сколько не хватает заполненных клеток до m + n - 1 и в них помещают нулевые загрузки.

Таблица 12

Грузообразующие точки	Потенциалы	Грузопоглощающие точки						Итого по вывозу, т
		B1		B2		B3	B4
		0		-4		6	4
A1	0	16		6		10	4400	400
A2	6	8		2 400		12200	14	600
A3	2	2 200		18		8600	6200	1000
Итого по ввозу, т	200	400		800		600	2000

6. Способы составления первого допустимого плана перевозок

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

Таблица 13

Cуточное производство и потребность в кирпиче, т

Расстояние от перевозки, км

Завод

Объём производства

Строительные площадки

Потребность в кирпиче

Завод

B1

B2

B3

B4

B5

A1 A2 A3 A4

100 300 75 125

B1 B2 B3 B4 B5

25 150 100 175 150

A1 A2 A3 A4

15 15 10 6

12 22 5 13

16 22 17 18

21 14 6 22

18 12 10 18

Первоначальное распределение перевозок может быть получено несколькими способами. Рассмотрим на конкретном примере сущность и эффективность некоторых из них. От четырех кирпичных заводов кирпич автомобильным транспортом доставляется на пять строительных площадок. Необходимо определить план перевозок кирпича, при котором объем транспортной работы будет минимальной. Исходные данные задачи приведены в табл. 13.

Способ северо-западного угла

Построение допустимого плана этим способом начинается с верхней левой клетки и заканчивается в нижней правой клетке матрицы. В клетки заносят максимально возможную поставку, учитывая соотношение ресурсов поставщика и спрос потребителя. Груз первого поставщика распределяется так, что вначале удовлетворяются потребности первого потребителя, затем второго и так до полного распределения всего объема грузов данного поставщика. Затем переходят к распределению грузов второго поставщика и так до полного распределения объема грузов всех поставщиков. Если спрос какого-либо потребителя превышает количество груза у поставщика, то недостающий спрос удовлетворяется за счет следующего поставщика, т.е. расчет в этом случае ведется по столбцу. Допустимый план перевозки кирпича на строительные площадки, составленный способом северо-западного угла, приведен в табл. 14. В плане полностью соблюдается условие по ввозу и вывозу кирпича, количество заполненных клеток соответствует m + n - 1. Суммарная транспортная работа по плану распределения, составленному способом северо-западного угла, будет

L(x) = 15 * 25 +12 * 75 +22 * 75 +22 * 100+14 * 125+ 6 * 50 + 10 * 25+ 18* 125 = 9675т* км.

Таблица 14

Завод	Строительная площадка							Объём производства, т
	B1		B2		B3	B4	B5
A1	15 25		12 75		16	21	18	100
A2	15		22 75		22100	14125	12	300
A3	10		5		17	650	1025	75
A4	6		13		18	22	18125	125
Потребность в кирпиче, т	25		150		100	175	150	600

Этот способ прост, однако первоначально допустимое решение, как правило, далеко от оптимального, поскольку заполнение клеток матрицы производится механически без учета расстояния или стоимости перевозки.