Исследование математических операций (работа 1)
Министерство образования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №3
«Исследование математических операций»
Выполнил:
Ст. группы РС-05
Проверил:
Доцент кафедры АСОИ
Саликов В.А.
г. Днепропетровск
2007г.
Условие задачи
Решение задачи
r = R>1>+R>2>+…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 |
Таким образом, оптимальное решение задачи имеет вид:
,
Х = {
,
}