Министерство образования и науки Украины

Днепропетровский Национальный Университет

Факультет электроники, телекоммуникаций и компьютерных систем

Кафедра АСОИ

Расчётная задача №3

«Исследование математических операций»

Выполнил:

Ст. группы РС-05

Проверил:

Доцент кафедры АСОИ

Саликов В.А.

г. Днепропетровск

2007г.

Условие задачи

Решение задачи

r = R₁+R₂+…R_i ;

min = min(r);

R_i=1,2,….

Полученное на 1 этапе оптимальное базисное решение используется в качестве начального решения исходной задачи.

Основные этапы реализации двухэтапного метода (как и других методов искусственного базиса) следующие:

1. Строится искусственный базис. Находится начальное недопустимое решение. Выполняется переход от начального недопустимого решения к неко­торому допустимому решению. Этот переход реализуется путем минимизации (сведения к нулю) искусственной целевой функции, представляющей собой сумму искусственных переменных.

2. Выполняется переход от начального допустимого решения к оптималь­ному решению.

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

Первый этап (поиск допустимого решения)

1. Во все ограничения, где нет базисных переменных, вводятся искусственные базисные переменные.

Примечание. Искусственная целевая функция всегда (в любой задаче) подлежит минимиза­ции.

2 Искусственная целевая функция выражается через небазисные пере­менные. Для этого сначала требуется выразить искусственные переменные че­рез небазисные:

3 Для приведения всей задачи к стандартной форме выполняется переход к искусственной целевой функции, подлежащей максимизации. Для этого она умножается на -1:

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

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

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

Двухэтапный метод

1 шаг

2 шаг

, где

В ходе преобразований имеем:

Строим симплекс таблицу:

Итерация 0

Базис

Решение

Оценка

15

15

-1

0

-1

-1

-1

0

0

0

0

0

0

34

-2

1

0

1

0

0

0

0

0

0

0

0

0

6

6

1

0

0

0

0

0

0

1

0

0

0

0

0

6

-

0

1

0

0

0

0

0

0

1

0

0

0

0

7

7

1

7

-1

0

0

0

0

0

0

1

0

0

0

7

1

2

5

0

0

-1

0

0

0

0

0

1

0

0

10

2

5

2

0

0

0

-1

0

0

0

0

0

1

0

10

5

7

1

0

0

0

0

-1

0

0

0

0

0

1

7

7

- ведущий столбец

- ведущая строка

Итерация 1

Базис														Решение	Оценка
	12,8571	0	1,1429	0	-1	-1	-1	0	0	-2,1429	0	0	0	19
	-2,1429	0	0,1429	1	0	0	0	0	0	-0,1429	0	0	0	5	-
	1	0	0	0	0	0	0	1	0	0	0	0	0	6	6
	-0,1429	0	0,1429	0	0	0	0	0	1	-0,1429	0	0	0	6	-
	0,1429	1	-0,1429	0	0	0	0	0	0	0,1429	0	0	0	1	7
	1,2857	0	0,7143	0	-1	0	0	0	0	-0,7143	1	0	0	5	3,8889
	4,7143	0	0,2857	0	0	-1	0	0	0	-0,2857	0	1	0	8	1,697
	6,8571	0	0,1429	0	0	0	-1	0	0	-0,1429	0	0	1	6	0,875

- ведущий столбец

- ведущая строка

Итерация 2

Базис														Решение	Оценка
	0	0	0,875	0	-1	-1	0,875	0	0	-1,875	0	0	-1,875	7,75
	0	0	0,1875	1	0	0	-0,3125	0	0	-0,1875	0	0	0,3125	6,875	36,6667
	0	0	-0,0208	0	0	0	0,1458	1	0	0,0208	0	0	-0,1458	5,125	-
	0	0	0,1458	0	0	0	-0,0208	0	1	-0,1458	0	0	0,0208	6,125	42
	0	1	-0,1458	0	0	0	0,0208	0	0	0,1458	0	0	-0,0208	0,875	-
	0	0	0,6875	0	-1	0	0,1875	0	0	-0,6875	1	0	-0,1875	3,875	5,6364
	0	0	0,1875	0	0	-1	0,6875	0	0	-0,1875	0	1	-0,6875	3,875	20,6666
	1	0	0,0208	0	0	0	-0,1458	0	0	-0,0208	0	0	0,1458	0,875	42

- ведущий столбец

- ведущая строка

Итерация 3

Базис														Решение	Оценка
	0	0	0	0	0,2727	-1	0,6364	0	0	-1	-1,2727	0	-1,6364	2,8182
	0	0	0	1	0,2727	0	-0,3636	0	0	0	-0,2727	0	0,3636	5,8182	-
	0	0	0	0	-0,0303	0	0,1515	1	0	0	0,0303	0	-0,1515	5,2422	34,6009
	0	0	0	0	0,2121	0	-0,0606	0	1	0	-0,2121	0	0,0606	5,3033	-
	0	1	0	0	-0,2121	0	0,0606	0	0	0	0,2121	0	-0,0606	1,6967	27,9978
	0	0	1	0	-1,4545	0	0,2727	0	0	-1	1,4545	0	-0,2727	5,6364	20,6670
	0	0	0	0	0,2727	-1	0,6364	0	0	0	-0,2727	1	-0,6364	2,8182	4,4285
	1	0	0	0	0,0303	0	-0,1515	0	0	0	-0,0303	0	0,1515	0,7578	-

- ведущий столбец

- ведущая строка

Итерация 4

Базис														Решение
	0	0	0	0	0	0	0	0	0	-1	-1	-1	-1	0
	0	0	0	1	0,4285	-0,5713	0	0	0	0	-0,4285	0,5713	0	7,4283
	0	0	0	0	-0,0952	0,2381	0	1	0	0	0,0952	-0,2381	0	4,5714
	0	0	0	0	0,238	-0,0952	0	0	1	0	-0,238	0,0952	0	5,5716
	0	1	0	0	-0,238	0,0952	0	0	0	0	0,238	-0,0952	0	1,4284
	0	0	1	0	-1,5714	0,4285	0	0	0	-1	1,5714	-0,4285	0	4,4288
	0	0	0	0	0,4285	-1,5713	1	0	0	0	-0,4285	1,5713	-1	4,4283
	1	0	0	0	0,0952	-0,2381	0	0	0	0	-0,0952	0,2381	0	1,4286

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

Переходим на на 2 этап двухэтапного метода

Полученное на этапе I решение используется в качестве начального базиса на этапе II. Далее задача решается обычным симплекс-методом.

Базис										Решение	Оценка
0 0 0 0 -0,238 1,0953 0 0 0 3,6508 0 0 0 1 0,4285 -0,5713 0 0 0 7,4283 17,3356 0 0 0 0 -0,0952 0,2381 0 1 0 4,5714 - 0 0 0 0 0,238 -0,0952 0 0 1 5,5716 23,4101 0 1 0 0 -0,238 0,0952 0 0 0 1,4284 - 0 0 1 0 -1,5714 0,4285 0 0 0 4,4288 - 0 0 0 0 0,4285 -1,5713 1 0 0 4,4283 10,3344 1 0 0 0 0,0952 -0,2381 0 0 0 1,4286 15,0063 - ведущий столбец - ведущая строка Базис Решение 0 0 0 0 0 0,2226 0,5554 0 0 6,1110 0 0 0 1 0 1 -1 0 0 3 0 0 0 0 0 -0,111 0,2222 1 0 5,5552 0 0 0 0 0 0,7775 -0,5554 0 1 3,112 0 1 0 0 0 -0,7511 0,5386 0 0 3,8889 0 0 1 0 0 -5,3338 3,6672 0 0 20,6683 0 0 0 0 1 -3,667 2,3337 0 0 10,3344 1 0 0 0 0 0,111 -0,2222 0 0 0,4445 Таким образом, оптимальное решение задачи имеет вид: , Х = { , } 1. Реферат Закони природи і астрономія 2. Реферат на тему Жидкофазное каталитическое окисление фенольных соединений 3. Реферат Константин Ипсиланти 4. Реферат Слово и человек в жизни 5. Реферат Проектирование муниципальных образовательных систем российской провинции 6. Статья Деловая сеть как альтернатива команде 7. Реферат Международный кредит функции и формы 8. Реферат на тему The Question Of Spanking Essay Research Paper 9. Реферат Получение пространственно упорядоченных пироуглеродных структур водородным восстановлением тетра 10. Реферат Состояние и перспективы развития туризма в Малайзии Bukvasha Правила Контакты