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

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

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

Кафедра АСОИ

Расчётная задача №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. Реферат на тему Solar System Essay Research Paper Origin Of 3. Курсовая на тему Формування і розподіл прибутку комерційного банку 4. Реферат на тему История Мальтийского Ордена от окончания Великой Осады до конца XVII века 5. Контрольная работа Погрешности вычислений на ЭВМ 6. Реферат Социальное значение физической культуры и спорта 7. Реферат на тему Ben Franklin 2 Essay Research Paper 8. Реферат на тему Biological Species Concept Essay Research Paper Over 9. Реферат на тему StupidA Essay Research Paper THE ADVANTAGES OF 10. Реферат на тему The Navy Of The Civil War Essay Bukvasha Правила Контакты