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

Анализируется вся матрица, и все метки матрицы нумеруются в порядке возрастания с и, начиная с минимального. Если в процессе расчета оказываются две или более метки с одинаковыми значениями C_ij, то они нумеруются произвольно .

Далее в той же последовательности загружаются' базисные клетки из условия (6), исключая те столбцы и строки, ресурсы которых исчерпаны.

В таблице 3 нумерация меток дана в правом верхнем углу каждой клетки.

Таблица 3

Начальный план 1

Пункт отправ- ления	Gi	αi	Пункт назначения
			B1		B2		B3		B4		B5
			Gi
			100		100		80		70		70
		βj	4		12		14		37		1000
A1	200	0	5 15		7 22		80	4 14	70		50	13 1000
A2	100	-1	8 24		100	2 11	11 40		6 19		14 1000
A3	120	0	100	1 4	0	3 12	9 32		12 61		20	15 1000

Ресурсы первого столбца исчерпаны полностью. Следующей будет загружаться клетка (2-2)

Одновременно исключаем 2-ю строку и 2-ой столбец из дальнейших расчетов. Следующей будет загружаться клетка (1-3)

Далее аналогично - до получения  окончательной матрицы. Проверяются ограничения задачи (2), (3), (4).

Значение целевой функции:

F = 80 * 14 + 70 * 38 + 50 * 1000 + 100 * 11 + 100 * 4 +  20 * 1000 = 72,27 т.руб.

Для проверки на оптимальность выбирается начальный план составленный методом минимального элемента. Проверяем план на невырожденность.

        (7)

где     L_Н - необходимое число базисных клеток в матрице;

m - количество строк в матрице;

n - количество столбцов в матрице.

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

План вырожденный, для устранения вырожденности вводиться дополнительная  базисная метка (табл. 3).

План считается оптимальным, если выполняется условие для базисных клеток

        (8)

для  свободных клеток

        (9)

где  соответственно потенциалы строк и столбцов.

Принимаем   =0

Далее рассчитываются остальные потенциалы. Потенциалы рассчитываются только по загруженным клеткам (табл.3).

  и т.д.

Рассчитываются характеристики свободных клеток

  и т.д.

План, представленный в табл.3 оптимален, т.к. удовлетворяет условию (9).

Полученный оптимальный план взаимной увязки поставщиков и потребителей оформляется в виде корреспонденции перевозок местных грузов (табл.4)

Таблица 4

Корреспонденция перевозок местных грузов

Пункты		Масса перевозок тыс.т	Удельные транспортные затраты по пе -ревозке, руб./т	Затраты тыс.руб.
отправления	назначения
А1	В1	80	14	1120
А2	В2	70	37	2590
А3	В3	100	11	1100
А4	В4	100	4	400
Итого:		350		5210

Грузопотоки, в которых один из корреспондирующих пунктов «фиктивный» в таблицу 4 вводится и к расчету не принимаются.

2. Распределительная задача

Содержание: расстановка имеющейся перегрузочной техники по пунктам обработки флота.

2.1. Исходные данные.

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