Экономико-математические методы: Учебно-практическое пособие по дисциплине «Математика». Часть 3

Таблица 9.7

Матрица планирования	220		280		200		100
240		6,5		9,5		8,5		0	u1 = 0
	220				20
360		6		6		7		0	u2  = –1,5
			280		80
100		8		11		10		0	u3  = 0
							100
100		10		11		8		0	u4  = 0,5
					100
	v1  = 6,5		v2  = 7,5		v3  = 8,5		v4  = 0		4640

Из таблицы 9.7 оптимального плана получаем, что оптимальным вариантом прироста мощности является вариант строительства нового предприятия, так как вариант реконструкции приходится на «фиктивного» потребителя.

Полученное оптимальное решение является целочисленным, т.е. все мощности предприятий не дробятся между реальными и фиктивными потребителями.

10. Сетевые модели

10.1. Некоторые понятия теории графов

Совокупность G двух множеств: А – множества вершин и С – множества дуг, называется графом. Т.е. G = (А, С).

А – множество объектов произвольной природы, С – множество формализованных связей между ними.

Геометрически вершины графа обозначаются:      , а связи между ними – линиями, соединяющими вершины.

Так как физические свойства объектов множества А нас интересовать не будут, то вершины будем обозначать числами. Связи или дуги будем обозначать линиями. Если существует дуга, соединяющая вершины i и j, то эти вершины называются связанными, в противном случае, несвязанными.

Довольно часто графы представляются в виде матрицы смежности вершин, в которой элементы с номерами i и j, соответствующие связанным вершинам, отмечаются единицей (1) или точкой (·), а соответствующие несвязанным вершинам – нулем (0)

или просто оставляется пустая клетка. Для графа (рис 10.1) матицы смежности вершин будут иметь вид:

Часто в матрице смежности вершинам проставляются значения, которые характеризуют дуги. Например, если C_ij – расстояние между вершинами, то матрица смежности превращается в матрицу расстояний. Если C_ij – пропускная способность дуги, то C будет называться матрицей пропускных способностей. Если C_ij – стоимость перевозки единицы груза из i в j, то С – матрица стоимостей.

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

Если любые две вершины графа можно соединить цепью, то он называется связанным, в противном случае – несвязанным. Связанный граф без циклов называется деревом-остовом или просто деревом.

Если существует связь между вершиной i и вершиной j, но нет обратной связи, то соответствующая дуга, соединяющая эти вершины, называется ориентированной. Поэтому граф, в котором все дуги ориентированы, называется ориентированным. В нём геометрически дуги изображаются стрелками (рис. 10.2).

10.2. Примеры и постановка задач

Транспортная задача (и ее варианты) – лишь одна из многочисленных задач, которые можно сформулировать и решить с помощью сетевых моделей.

Рассмотрим конкретные примеры:

а) проектирование нефтепровода, соединяющего буровые скважины в Каспийском море с находящейся на берегу приемной станцией. Следует выбрать проект, в котором строительство нефтепровода имеет минимальную стоимость (наименьшую протяженность);

б) определение кратчайшего пути между двумя городами, проходящего по существующей сети шоссейных дорог;

в) определение максимальной пропускной способности (тонна/год) газопровода для транспортировки газа с мест добычи к месту переработки (потребления);

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