Пример. Необходимо разработать корпус ЭВС в форме параллелепипеда с объемом не менее 1000 см3 и минимальной площадью поверхности стенок. Толщину стенок рассматривать не будем. Обозначим через xi

размеры параллелепипеда.

F 2x1x2 2x2 x3 2x1x3 min x1x2 x3 1000см3

Многокритериальные задачи оптимизации.

Метод главного критерия.

min F1(X), при ограничениях F2(X) F2д(X), F3(X) F3д(X),

…… Fn(X) Fnд(X), где

Fiд(X) - максимально допустимое значение i-го частного критерия.

Метод взвешивания критериев оптимизации.

F ( X ) i Fi ( X )

i 1

i – весовой коэффициент.

Постановка задачи линейного программирования

		n
max(min)
	F c0 cj xj
n		j 1

aij x j bi		(i		)
			1,m
j 1	x j	0

Каноническая форма (канонический вид) записи ЗЛП

n	n
max cj x j ;	aij x j bi	;	x j 0 ,
j 1	j 1

(i		) ,	j		.
				1,n
	1,m

Cij

адача о назначениях. Пусть имеется n мест на плате для азмещения n элементов, причем на каждом месте может быть азмещена только одна микросхема. Эффективность размещени

й микросхемы на j-м месте C(например суммарная длина

вязей).

На основании этих данных можно построить квадратную

матрицу	Cij	n n
матрицу	Cij

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

Определим некоторую матрицу X			xij	, в которой
Определим некоторую матрицу X			xij	, в которой
				n n
				n n
x		1, если j-е место занимает i-я микросхема,
x	ij
	ij	0 в противном слу ае .

Математическая модель задачи оптимизации

n	n
max cij xij
i 1	j 1
n
xij 1	j
xij 1	j		1,n
i 1
n
xij 1	i	1, n

j 1

Вобщем случае задача оптимизации решается в K-мерном

пространстве. При этом мерность пространства зависит как от числа переменных n, так и от вида ограничений. В случае, если все m ограничений имеют вид неравенств, то K=n.

Если все m ограничений имеют вид уравнений, то K=n-m.

Вслучае, если m ограничений - в виде уравнений, а l - в виде неравенств, то K=n+l-m.