mu_po_oformleniyu_mat_razdela_k_i_dp

11

3.1. Математическая модель выпуклой оболочки набора точек на плоскости

Выпуклая оболочка набора точек S (обозначается CH(S)) – выпуклый полигон минимальной площади, содержащий все точки набора S [3].

CH(S)

S

Рис. 3.1. Выпуклая оболочка набора точек S

Основные свойства выпуклой оболочки (рис. 3.1):

1.Прямая, проходящая через любое ребро выпуклой оболочки отделяет все точки набора точек S от внешней полуплоскости. Другими словами, все точки набора S лежат по одну сторону от прямой, проходящей через ребро выпуклой оболочки.

2.Хорда выпуклой оболочки – отрезок, соединяющий пару точек набора S. Любая хорда, лежит внутри выпуклой оболочки. Отрезки, ограничивающие полигон тоже являются хордами. Эти отрезки считаются принадлежащими полигону.

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

3.2. Задача построения выпуклой оболочки набора точек

Входные данные: Дан набор S точек плоскости (рис. 3.2).

Выходные данные: Построить выпуклую оболочку CH(S) набора точек

(рис. 3.3).

CH(S)

S S

Рис. 3.2. Набор точек S на входе	Рис. 3.3. Выпуклая оболочка CH(S)
	на выходе

Алгоритм Джарвиса построения выпуклой оболочки набора точек

Алгоритм Джарвиса так же известен как «алгоритм заворачивания подарка» [4].

12

Пошаговое описание алгоритма Джарвиса:

1. Найти экстремальную точку q набора точек S.

Экстремальная точка набора точек – точка с какой-либо экстремаль-

ной координатой относительно других точек набора. Таких точек 4. Алгоритм Джарвиса инвариантен к выбору экстремальной точки. Обычно берут самую нижнюю точку.

2.Найти отрезок с минимальным углом поворота к соответствующей оси

( min). Для нижней экстремальной точки необходимо искать точку с минимальным углом поворота к оси OX.

3.Цикл пока не придем в исходную точку q.

3.1.Перейти на найденную точку

3.2.Найти точку с минимальным углом поворота относительно предыдущего ребра (рис. 3.4).

	min 2
S	min1
	min 0
q	X

Рис. 3.4. Поиск минимального угла поворота

Угол между отрезками можно рассчитать по формуле:

arccos			v1 v2					,
			v1		v2

где v1, v2 – вектора отрезков.

1. Вычислительная сложность метода Джарвиса

Оценим временную сложность алгоритма Джарвиса. Для начала оценим временную сложность каждого шага алгоритма Джарвиса.

Шаг 1. Поиск экстремальной точки простым последовательным перебором точек занимает за линейное время – O(n).

Шаг 2. Поиск точки с минимальным углом поворота последовательным перебором занимает линейное время – O(n).

Шаг 3. Число итераций в цикле «пока не придем в исходную точку» равно h – числу точек-вершин выпуклой оболочки.

Шаг 3.1. Тело цикла занимает постоянное время – O(c).

Шаг 3.2. Тело цикла аналогично шагу 2 занимает линейное время – O(n).

Запишем итоговую функцию временной сложности для всего алгоритма с учетом его структуры:T(n) O(n n h (c n)) O(h n).

Рассмотрим влияние неопределенного фактора h на вычислительную сложность алгоритма Джарвиса (рис. 3.5., 3.6).

13

Наихудший случай

Наилучший случай

Рис. 3.5. Нет внутренних точек	Рис. 3.6. Треугольная оболочка
2	h<<n, в этом случае T(n) O(n)
h=n, тогда T(n) O(n )

Сильная зависимость времени работы от входных данных считается недостатком алгоритма Джарвиса.

4. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ "ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ ОПРЕДЕЛЕННОСТИ"

Классическими задачами принятия решений в условиях определенности считаются:

1.Задача планирования производства. Выбрать план производства, т.е.

определить, какие виды продукции и в каких количествах следует производить, чтобы обеспечить получение максимальной прибыли. Известны расходы всех видов ресурсов на производство единицы продукции всех типов и прибыль, получаемая при производстве единицы продукции. Предприятие располагает ограниченным количеством производств ресурсов.

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

3.План снабжения предприятий. Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями путями сообщения со своими тарифами. Требуется разработать план снабжения предприятий сырьем при минимальных расходах на перевозки.

4.Постройка участка магистрали. Сооружается участок железнодорожной магистрали. В нашем распоряжении определенное количество средств: людей, строительных машин, ремонтных мастерских, грузовых автомобилей и т.д. Требуется спланировать строительство (т.е. назначить очередность работ, распределить машины и людей по участкам пути, обеспечить ремонтные работы) так, чтобы оно было завершено в минимально возможный срок.

14

5. Выборочный контроль продукции. Завод выпускает определенного вида изделия. Для обеспечения их высокого качества организуется система выборочного контроля. Требуется разумно организовать контроль (т.е. выбрать размер контрольной партии, набор тестов, правила браковки и т.д.) так, чтобы обеспечить заданный уровень качества при минимальных расходах на контроль.

Под задачей принятия решений в условиях определенности понимает-

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

Входные данные:

CX	max (или CX min) – исходная целевая функция.
AX	B, x 0 – система ограничений,
где: С = (с1, с2, …, сn) – вектор коэффициентов целевой функции,
A = (	ij), i = [1..m], j = [1..n] – матрица коэффициентов ограничений, i –

количество уравнений в системе ограничений, j – количество переменных.

X = (x1, x2, … , xn)T – вектор-столбец решения.

B = (b1, b2, … , bm)T – вектор-столбец правых частей ограничений.

Выходные данные:

x1

Вектор X	x2	, максимизирующий (минимизирующий) линейную це-
	...
	xn

левую функцию CX.

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

1. Проверка правых частей ограничений на неотрицательность:

Если правая часть какого-либо ограничения bi < 0, то умножаем это ограничение на -1.

2. Приведение задачи к канонической форме:

Анализируются знаки неравенств системы ограничений, после чего добавляются балансовые и искусственные переменные в ограничения:

15

mi Ai X bi

Ai X yi

bi

Ai X bi

Ai X yi zi

bi

i 1

Ai X bi

Ai X zi

bi

,

где: m – количество ограничений системы ограничений;

Ai – i-тая строка матрицы А;

X – вектор-столбец решения;

bi – правая часть i-ограничения;

yi – балансовая переменная

yi

0,

i

1,m ;

zi – искусственная переменная

zi

0,

i 1,m .

Целевая функция принимает следующий вид:

max F X

CX 0 Y

,если задача максимизации

MZ ,

M

C,

min

,если задача минимизации

где: Y = (y1, y2, … , ym)T – вектор-столбец балансовых переменных;

Z = (z1, z2, … , zm)T – вектор-столбец искусственных переменных; М – коэффициент при искусственных переменных.

В качестве М принимается значение, на много превышающее модуль любого коэффициента целевой функции С.

3. Определение базисных переменных:

Если в ограничении-неравенстве присутствует только балансовая переменная, то она добавляется в первоначальный базис, иначе если есть искусственная переменная, то в базис добавляется искусственная переменная:

mi Ai X	yi	bi	xn i	БАЗИС yi	,
i 1
Ai X yi	zi	bi	Ai X	zi bi xn i БАЗИС zi

где БАЗИС x – функция, определяющая переменную x как базисную.

4. Расчет первой крайней точки:

X1 0, ,0,b1,b2, ,bm

n

и вычисление F X1 .

5. Построение симплексной таблицы:

В столбец "Базис" записываем переменные, вошедшие в базис. Таблица имеет следующий вид:

16

	Базис	Cб	C	c1	c2	…	cn	cn 1	…	cn m
			B	A1	A2	…	An	An+1	…	An+m
	xn+1	Cn 1	b1	a11	a12	…	a1n	1	…	0
	xn+2	Cn 2	b2	a21	a22	…	a2n	0	…	0
	.	.	.	.	.	.	.	.	.	.
	.	.	.	.	.	.	.	.	.	.
	.	.	.	.	.	.	.	.	.	.
	xn+m	C	bm	am1	am2	…	amn	0	…	1
		n m

	1	2 … n n+1 … n+m
F
k	AkCб	ck , k 1,n m,

где: k – симплексные разности в j-ой крайней точке;

Ak – вектор-столбец, составленный из коэффициентов при xk;

Cб – вектор, составленный из коэффициентов целевой функции, соответствующих базисным переменным;

С – вектор коэффициентов целевой функции.

6. Проверка оптимальности решения для j-крайней точки. Если для j-ой

крайней точки все симплексные разности k 0, k 1,n					m, то эта точка опти-
мальная. Конец решения.
Если есть столбец, в котором симплексная разность						k	0, а все элемен-
					0
ты столбца aik	0, i 1,m, то задача линейного программирования решения не
0

имеет, т.к. целевая функция неограниченна сверху.

В остальных случаях переход к следующему пункту.

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

min k k ,	k 0 ( max k	k ,	k 0).
0		0

Направляющая строка i0 выбирает из условия:

	b		bi
min	i		0	, ai k	0, i 1,m,
	aik		ai k	0 0
0		0 0

где ai0k0 – направляющий элемент.

8. Заполнение таблицы, соответствующей новому решению.

В базис вводится вектор Ak0 вместо вектора An0 , имеющего i0-ую коорди-

нату, равную 1. Для этого используются следующие соотношения: а) новые элементы направляющей строки находятся:

		17
	ai k
ai k :	0		, k 1,n m;
	ai k
0
	0 0

б) новые элементы направляющего столбца:

ik0 : 0 , i 1,m, причем i i0; i0k0 : 1

в) новые значения остальных элементов матрицы:

	ai j				i	i0
aij : aij		0	aik	,			;
	a				j	k
			0
	i k					0
		0 0

г) новые значения симплексных разностей:

			ai	j
	j :	j	0		aik .
			ai k
					0
			0 0

Правильность вычислений контролируется по формулам непосредственного счета:

k	AkCб ck , k		.
		1,n m
F	BCб

Получается (j+1)-ая крайняя точка. Переход к пункту 6.

Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.

5. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ "ОПТИМИЗАЦИЯ ПЛАНИРОВАНИЯ ПЕРЕВОЗОК"

Пример математической постановки задачи приведен по теме «Оптимизация планирования поставки грузов» из реального курсового проекта.

Дано: m пунктов отправления груза и объемы отправления по каждому пункту a1, a2, ..., am. В роли последних выступают объемы выпуска на каждом предприятии поставщике. Известна потребность в грузах b1, b2,...,bn по каждому из n пунктов назначения. Потребности определяются из пришедших менеджеру по поставкам заявок на поставку продукции от каждой из точек сбыта. Задана

также С – матрица	стоимостей доставки груза из пункта i в пункт j,
cij C,(i 1,2,,...,m, j	1,2,...,n).Допустим, что cij - это цена бензина, затрачен-

ного на транспортировку продукции от поставщика потребителю.

Требуется получить: оптимальный план перевозок, т. е. определить, сколько груза xij X должно быть отправлено из каждого пункта отправления

(от поставщика) в каждый пункт назначения (до потребителя) с минимальными суммарными транспортными издержками. Естественно, чем меньше суммарный путь, тем меньше транспортные издержки.

18

5.1. Анализ целевой функции

Итак, входными параметрами системы являются m,n,A,B,C, где m – количество поставщиков;

n – количество пунктов назначения;

A – множество, элементами которого являются объемы груза, отправляемые из каждого пункта поставки. A {ai},i [1,m];

B – множество, элементами которого являются объемы груза, потребные

в каждом пункте назначения. B	{bj}, j [1,n];
С – множество стоимостей перевозок от каждого поставщика каждому
потребителю. C {cij},i [1,m], j	[1,n] .

Выходным параметром является множество X, элементами которого являются объемы груза, поставляемого от каждого поставщика каждому потребителю при минимальных транспортных издержках Z. X {xij},i [1,m], j [1,n]

Транспортная задача называется закрытой [5], если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения

m ai	n bi .
i 1	j 1

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

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

n xij ai, i 1,2,...,m .

j 1

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

n	xij bj, j 1,2,...,n .
j	1

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

xij 0, i 1,2,...,m; j 1,2,...,n .

Перевозки необходимо осуществить с минимальными транспортными издержками (суммарной транспортной работой). Следовательно, целевая функция примет вид:

Z	m n cijxij min.
	i 1 j 1

19

Как видно из выражения, уравнение баланса является обязательным условием решения закрытой транспортной задачи, поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если:

потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

В удобном для просмотра виде исходные данные представлены в таблице

3.

					Таблица 3
Потребители					Запасы
Поставщики	В4	В2		Вn	(объемы
					отправления)
А1	C11	C12	…	C1n	a1
	X11	X12		X1n
А2	C21	C22	…	C2n	a2
	X21	X22		X2n
…	…	…	…	…	…
Аm	Cm1	Cm2	…	Cmn	am
	Xm1	Xm2		Xmn
Потребность	b1	b2	…	bn

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

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

Потенциалы – вспомогательные переменные в транспортной задаче, вводимые для проверки оптимальности плана перевозок.

В первую очередь необходимо выполнить разработку начального плана (опорного решения);

Решение задачи методом потенциалов включает следующие этапы [Фролькис, 2002]:

-расчет потенциалов;

-проверку плана на оптимальность (если план оптимальный, то вычислительный процесс прекращается, в противном случае выполняются следующие пункты);

-поиск максимального звена неоптимальности;

20

-составление контура перераспределения ресурсов;

-определение минимального элемента в контуре перераспределения;

-перераспределение ресурсов по контуру и возврат к первому этапу. Описанная процедура повторяется несколько раз (итераций), пока не бу-

дет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.

5.2. Построение начального плана

Опорный план – план перевозок, у которого число ненулевых перевозок N равно сумме числа производителей и потребителей без единицы(N=m+n-1).

Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения):

метод минимальной стоимости по строке; метод северо-западного угла; метод двойного предпочтения и т. д.

Начальный план можно составить одним из перечисленных выше мето-

дов.

Воспользуемся способом минимальной стоимости по строке, т.к. он дает начальный план наиболее приближенный к оптимальному. Суть метода заключается в том, что начиная с 1-й строки в каждой строке из всей строки выбирают клетку с наименьшей стоимостью и в нее помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Если у поставщика еще остались запасы, то из оставшейся части строки снова выбирают клетку с наименьшей стоимостью и в нее помещают меньшее из чисел ai и bj. Далее переходят на следующую строку. Процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм построения начального плана методом минимальной стоимости по строке (поставщику) имеет следующий вид:

1. Введем рабочее множество TA = {tai}, i [1,m] запасов поставщиков, которые в начальный момент совпадают с заданными в множестве А, а в ходе построения плана будут уменьшаться по мере выполнения перевозок: (tai ТА)(tai = ai), т.е. для каждого элемента tai из множества ТА истинно выражение (высказывание) tai = ai.

2. Введем рабочее множество TB = {tbj}, j [1,n] потребностей, которые так же в начальный момент совпадают с заказами из множества B: (tbj

ТB)(tbj = bj).