Как видно, пришлось ввести две искусственные клетки (2,5) и (4,4), в которых помещены перевозки, необходимые для баланса плана. Клетка (4,5) вспомогательная, она необходима для нахождения циклов, с помощью которых мы будем избавляться от вспомогательных искусственных клеток.

Ход, с которого можно начать эту работу: по циклу (2,5)→(2,2)→(3,2)→(3,4)→(4,4)→(4,5)→(2,5) можно перебросить две единицы продукции.

	B1		B2		B3		B4						ai
A1	7	5	14	7	15	3	7	5						30
			8		15		7
A2	17	3	10	7	12	8	5	5		∞		M		28
	17		6	[+]			5			0		[-]
A3	15	5	8	4	12	6	∞	7						27
	8		6	[-]	10		3	[+]
							∞	M		∞		M
							0	[-]		M		[+]
bj	25		20		25		15						85

---

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

	B1		B2		B3		B4			ai
A1	7	5	14	7	15	3	7	5	30
			8		15		7
A2	17	3	10	7	12	8	5	5	28
	17		6				5
A3	15	5	8	4	12	6	∞	7	27
	8		6		10		3
bj	25		20		25		15			85

---

Целевая функция: Lф = 7*8 + 3*15 + 5*7 + 3*17 + 7*6 + 5*5 + 5*8 + 4*6 + 6*10 + 7*3 = 399. Это больше, если сравнивать с целевой функцией этой же транспортной задачи, но без ограничений (там было Lф = 319).

---

6. Процесс оптимизации полученного опорного плана методом потенциалов.

Проверим оптимальность опорного плана.

В таблице, максимальное количество перевозок опорного плана – во втором столбце. Назначаем второму столбцу нулевую псевдоцену, v2  0. Поскольку в этом столбце все клетки включены в опорный план, можно составить систему, в которой найдем псевдостоимость u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij.

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	7
			8		15		7
A2 28	17	3	10	7	12	8	5	5	7
	17		6				5
A3 27	15	5	8	4	12	6	∞	7	4
	8		6		10		3
v	4		0		4		3

---

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

	B1 25		B2 20		B3 25		B4 15			u
A1 30	7	5	14	7	15	3	7	5	7
		11	8		15		7
A2 28	17	3	10	7	12	8	5	5	7
	17		6			11	5
A3 27	15	5	8	4	12	6	∞	7	4
	8		6		10		3
v	4		0		4		3

---

Смотрите также файлы

• Z9411_КафкаРС_ПМО_пр.docx

• Малімні атыжні Умбетова Меруерт ПнСынып.docx

• Выполните упражнения после текста.docx

• Программы верстки 2 Форматирование символов 5.docx

• Интелектуалды ойын химбион зерде білгірдер сайысы ойлан тап ребус шешу.pptx