Министерствообразования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №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,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 |
Таким образом, оптимальное решение задачи имеет вид:
, Х = { , }