Выбор плана снабжения участков нефтедобычи, наносящего минимальный ущерб окружающей среде, страница 3

Рис.1 Последовательные стадии заполнения таблицы перевозок

Таким образом, мы обеспечили участок В₁. В оставшейся незаполненной части таблицы находим варианты с минимальным ущербом, - (1,1), (3,2) и (2,3). Намечаем перевозку по трассе (3,2) – 20 ед. Получаем рис. 1б. Аналогично направляем 30 ед. оборудования по трассе (1,2) и остается единственный вариант – направить 40 ед. по трассе (1,3) – рис. 1в.

Подсчитаем теперь оценку ущерба, наносимого природе данным планом.

Но является ли составленный план оптимальным?

Для проверки этого служит прием, называемый «циклом ячейки».

Для этого следует провести оценку каждой свободной ячейки на рис. 1в, составив для нее цикл, - а по нему – знакочередующуюся сумму потерь ячеек, входящих в этот цикл (рис.2а). Если эта сумма окажется для проверяемой ячейки положительной, то ее не нужно включать в новый план, если же отрицательной – то составленный план не оптимален и эту ячейку следует включить в более оптимальный план.

Как только в составленном плане все свободные ячейки будут иметь положительные оценки, - данный план является оптимальным.

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

Возьмем ячейку (1,1) на рис. 1в. Ближайшая заполненная ячейка (1,2). Проводим стрелку (1,1)→(1,2). Здесь меняем направление движения вниз. Доходим до ячейки (3,2). Здесь снова меняем направление движения влево, - до ячейки (3,1). Последний поворот – в сторону проверяемой ячейки (1,1), - рис.2а.

По этому циклу подсчитываем знакопеременную сумму потерь по тем ячейкам, где изменялось направление движения:

(1,1) +2; (1,2) -3; (3,2) +2; (3,1) -1; Сумма S=+2-3+2-1=0

Цикл (2,1) – (2,2) – (3,2) – (3,1): S=+3-1+2-1=3>0

Цикл (2,3) – (1,3) – (1,2) – (2,2): S=+2-4+3-1=0

Цикл (3,3) – (1,3) – (1,2) – (3,2): S=+3-4+3-2=0

2	3
1	2

а)

3	1
1	2

б)

	3	4
	1	2

в)

	3	4
	2	3

г)