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

Посмотреть архив целиком

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

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

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

Кафедра АСОИ










Расчётная задача №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


Случайные файлы

Файл
143550.rtf
183910.rtf
referat.doc
economic Piter I.doc
143536.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.