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

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

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

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

Кафедра АСОИ



















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


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



, Х = {  , }