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

6698
знаков
7
таблиц
0
изображений

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

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

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

Кафедра АСОИ

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

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

Выполнил:

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

Проверил:

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

 Саликов В.А.

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

2007г.


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

 

 

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

r = R1+R2+…Ri;

min = min(r);

Ri=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

Таким образом, оптимальное решение задачи имеет вид:

, Х = {  , }


Информация о работе «Исследование математических операций»
Раздел: Математика
Количество знаков с пробелами: 6698
Количество таблиц: 7
Количество изображений: 0

Похожие работы

Скачать
13893
1
0

... к составлению математических моделей. Если математическая модель - это диагноз заболевания, то алгоритм - это метод лечения. Можно выделить следующие основные этапы операционного исследования: наблюдение явления и сбор исходных данных; постановка задачи; построение математической модели; расчет модели; тестирование модели и анализ выходных данных. Если полученные результаты не удовлетворяют ...

Скачать
116560
0
4

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

Скачать
210505
4
8

... и младших школьников. Анкета для студентов включала в себя два вопроса, один из которых о том, в чем, по их мнению, заключается развитие математических способностей школьников, а второй ¾ для выяснения отношения студентов к проведению внеклассной работы по математике в начальных классах. Анкета для преподавателей имела своей целью выяснить, проводят ли (а если проводят, то как часто) учителя ...

Скачать
26658
29
0

... или тактические управленческие решения. Исторически сложились две группы способов и приемов: традиционные и математические. Рассмотрим подробнее применение математических методов в экономическом анализе. Математические методы в экономическом анализе Использование математических методов в сфере управления - важнейшее направление совершенствования систем управления. Математические методы ускоряют ...

0 комментариев


Наверх