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

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

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

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

Кафедра АСОИ

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

Базис

РешениеОценка
1515-10-1-1-100000034
-210100000000066
10000001000006
010000001000077
17-1000000100071
2500-100000100102
52000-10000010105
710000-100000177

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

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

Итерация 1

Базис

РешениеОценка
12,857101,14290-1-1-100-2,142900019
-2,142900,1429100000-0,14290005
100000010000066
-0,142900,1429000001-0,14290006
0,14291-0,14290000000,142900017
1,285700,71430-10000-0,714310053,8889
4,714300,285700-1000-0,285701081,697
6,857100,1429000-100-0,142900160,875

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

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

Итерация 2

Базис

РешениеОценка
000,8750-1-10,87500-1,87500-1,8757,75
000,1875100-0,312500-0,1875000,31256,87536,6667
00-0,02080000,1458100,020800-0,14585,125
000,1458000-0,020801-0,1458000,02086,12542
01-0,14580000,0208000,145800-0,02080,875
000,68750-100,187500-0,687510-0,18753,8755,6364
000,187500-10,687500-0,187501-0,68753,87520,6666
100,0208000-0,145800-0,0208000,14580,87542

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

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

Итерация 3

Базис

РешениеОценка
00000,2727-10,636400-1-1,27270-1,63642,8182
00010,27270-0,3636000-0,272700,36365,8182
0000-0,030300,15151000,03030-0,15155,242234,6009
00000,21210-0,0606010-0,212100,06065,3033
0100-0,212100,06060000,21210-0,06061,696727,9978
0010-1,454500,272700-11,45450-0,27275,636420,6670
00000,2727-10,6364000-0,27271-0,63642,81824,4285
10000,03030-0,1515000-0,030300,15150,7578

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

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

Итерация 4

Базис

Решение
000000000-1-1-1-10
00010,4285-0,57130000-0,42850,571307,4283
0000-0,09520,238101000,0952-0,238104,5714
00000,238-0,09520010-0,2380,095205,5716
0100-0,2380,095200000,238-0,095201,4284
0010-1,57140,4285000-11,5714-0,428504,4288
00000,4285-1,57131000-0,42851,5713-14,4283
10000,0952-0,23810000-0,09520,238101,4286

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

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

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

Базис

РешениеОценка
0000-0,2381,09530003,6508
00010,4285-0,57130007,428317,3356
0000-0,09520,23810104,5714
00000,238-0,09520015,571623,4101
0100-0,2380,09520001,4284
0010-1,57140,42850004,4288
00000,4285-1,57131004,428310,3344
10000,0952-0,23810001,428615,0063

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

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

Базис

Решение
000000,22260,5554006,1110
000101-1003
00000-0,1110,2222105,5552
000000,7775-0,5554013,112
01000-0,75110,5386003,8889
00100-5,33383,66720020,6683
00001-3,6672,33370010,3344
100000,111-0,2222000,4445

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

, Х = { , }


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