Исследование математических операций
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Министерство образования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №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-21010000000006610000001000006-01000000100007717-10000001000712500-10000010010252000-10000010105710000-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,1429000171,285700,71430-10000-0,714310053,88894,714300,285700-1000-0,285701081,6976,857100,1429000-100-0,142900160,875
- ведущий столбец
- ведущая строка
Итерация 2
Базис
РешениеОценка000,8750-1-10,87500-1,87500-1,8757,75000,1875100-0,312500-0,1875000,31256,87536,666700-0,02080000,1458100,020800-0,14585,125-000,1458000-0,020801-0,1458000,02086,1254201-0,14580000,0208000,145800-0,02080,875-000,68750-100,187500-0,687510-0,18753,8755,6364000,187500-10,687500-0,187501-0,68753,87520,6666100,0208000-0,145800-0,0208000,14580,87542
- ведущий столбец
- ведущая строка
Итерация 3
Базис
РешениеОценка00000,2727-10,636400-1-1,27270-1,63642,818200010,27270-0,3636000-0,272700,36365,8182-0000-0,030300,15151000,03030-0,15155,242234,600900000,21210-0,0606010-0,212100,06065,3033-0100-0,212100,06060000,21210-0,06061,696727,99780010-1,454500,272700-11,45450-0,27275,636420,667000000,2727-10,6364000-0,27271-0,63642,81824,428510000,03030-0,1515000-0,030300,15150,7578-
- ведущий столбец
- ведущая строка
Итерация 4
БазисРешение000000000-1-1-1-1000010,4285-0,57130000-0,42850,571307,42830000-0,09520,238101000,0952-0,238104,571400000,238-0,09520010-0,2380,095205,57160100-0,2380,095200000,238-0,095201,42840010-1,57140,4285000-11,5714-0,428504,428800000,4285-1,57131000-0,42851,5713-14,428310000,0952-0,23810000-0,09520,238101,4286Полученная симплекс-таблица удовлетворяет условиям оптимальности и допустимости.
Переходим на на 2 этап двухэтапного метода
Полученное на этапе I решение используется в качестве начальн