Проверка опорного плана на оптимальность. Начальный опорный план - в левом нижнем углу клеток

Начальный опорный план - в левом нижнем углу клеток.

Используется метод минимальной стоимости.

Нахождение начального опорного плана (угловой точки).

Его суть:

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

Табл. 2

Потребители						ЗАПАСЫ
Поставшики
СПРОС

(1,3),(2,4),(2,2),(1,5)

б) правило: “там, где 0 вычеркиваем”

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

г) контроль: общее число занятых клеток должно быть равно m + n – 1. У нас 3+ 5- 1= 7.

д) расчитываем значение целевой функции

F = 20*7 + 80*2+ 100*4 + 30*6 + 70*4 + 150*2 + 50*5= 1710

Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице. (табл. 3) Табл. 3

Потребители						U
Поставщики
	7 -	4 +
	+ 6	-				-1
						-2
V

ПРАВИЛО 1: для всех занятых клеток должно быть:

u _i + v _j = c _{i j} (1)

(сумма потенциалов равна стоимости). Это правило- для заполнения столбцов U, V.

ПРАВИЛО 2: для всех свободных клеток должно быть:

u _i + v _j ≤ c _{i j} (2)

Это правило проверки оптимальности. Условие оптимальности нарушено в клетке (1, 2)!

Итак, полученный опорный план не оптимален!

Экономический смысл потенциалов:

Потенциалы u и v можно рассматривать как платежи поставщиков и потребителей некоторому третьему лицу - назовем его “ перевозчиком”.

Дата добавления: 2015-06-04