Министерство образования и науки Украины
Днепропетровский НациональныйУниверситет
Факультет электроники, телекоммуникацийи компьютерных систем
Кафедра АСОИ
Расчётнаязадача №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 -1 -1 -1 34
/> -2 1 1 6 6
/> 1 1 6 -
/> 1 1 7 7
/>/> 1 7 -1 1 7
1/>
/> 2 5 -1 1 10 2
/> 5 2 -1 1 10 5
/> 7 1 -1 1 7 7
/> — ведущий столбец
/> — ведущая строка
Итерация1
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
Оценка
/> 12,8571 1,1429 -1 -1 -1 -2,1429 19
/> -2,1429 0,1429 1 -0,1429 5 -
/> 1 1 6 6
/> -0,1429 0,1429 1 -0,1429 6 -
/> 0,1429 1 -0,1429 0,1429 1 7
/> 1,2857 0,7143 -1 -0,7143 1 5 3,8889
/> 4,7143 0,2857 -1 -0,2857 1 8 1,697
/>/> 6,8571 0,1429 -1 -0,1429 1 6
0,875/>
/> — ведущий столбец
/> — ведущая строка
Итерация2
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
Оценка
/> 0,875 -1 -1 0,875 -1,875 -1,875 7,75
/> 0,1875 1 -0,3125 -0,1875 0,3125 6,875 36,6667
/> -0,0208 0,1458 1 0,0208 -0,1458 5,125 -
/> 0,1458 -0,0208 1 -0,1458 0,0208 6,125 42
/> 1 -0,1458 0,0208 0,1458 -0,0208 0,875 -
/>/> 0,6875 -1 0,1875 -0,6875 1 -0,1875 3,875
5,6364/>
/> 0,1875 -1 0,6875 -0,1875 1 -0,6875 3,875 20,6666
/> 1 0,0208 -0,1458 -0,0208 0,1458 0,875 42
/> — ведущий столбец
/> — ведущая строка
Итерация3
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
Оценка
/> 0,2727 -1 0,6364 -1 -1,2727 -1,6364 2,8182
/> 1 0,2727 -0,3636 -0,2727 0,3636 5,8182 -
/> -0,0303 0,1515 1 0,0303 -0,1515 5,2422 34,6009
/> 0,2121 -0,0606 1 -0,2121 0,0606 5,3033 -
/> 1 -0,2121 0,0606 0,2121 -0,0606 1,6967 27,9978
/> 1 -1,4545 0,2727 -1 1,4545 -0,2727 5,6364 20,6670
/>/> 0,2727 -1 0,6364 -0,2727 1 -0,6364 2,8182
4,4285/>
/> 1 0,0303 -0,1515 -0,0303 0,1515 0,7578 -
/> — ведущий столбец
/> — ведущая строка
Итерация4
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
/> -1 -1 -1 -1
/> 1 0,4285 -0,5713 -0,4285 0,5713 7,4283
/> -0,0952 0,2381 1 0,0952 -0,2381 4,5714
/> 0,238 -0,0952 1 -0,238 0,0952 5,5716
/> 1 -0,238 0,0952 0,238 -0,0952 1,4284
/> 1 -1,5714 0,4285 -1 1,5714 -0,4285 4,4288
/> 0,4285 -1,5713 1 -0,4285 1,5713 -1 4,4283
/> 1 0,0952 -0,2381 -0,0952 0,2381 1,4286
Полученнаясимплекс-таблица удовлетворяет условиям оптимальности и допустимости.
Переходим на на 2 этапдвухэтапного метода
Полученное на этапе Iрешение используется в качестве начального базиса на этапе II. Далее задачарешается обычным симплекс-методом.
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
Оценка
/> -0,238 1,0953 3,6508
/> 1 0,4285 -0,5713 7,4283 17,3356
/> -0,0952 0,2381 1 4,5714 -
/> 0,238 -0,0952 1 5,5716 23,4101
/> 1 -0,238 0,0952 1,4284 -
/> 1 -1,5714 0,4285 4,4288 -
/>/> 0,4285 -1,5713 1 4,4283
10,3344/>
/> 1 0,0952 -0,2381 1,4286 15,0063
/> — ведущий столбец
/> — ведущая строка
Базис
/>
/>
/>
/>
/>
/>
/>
/>
/>
Решение
/> 0,2226 0,5554 6,1110
/> 1 1 -1 3
/> -0,111 0,2222 1 5,5552
/> 0,7775 -0,5554 1 3,112
/> 1 -0,7511 0,5386 3,8889
/> 1 -5,3338 3,6672 20,6683
/> 1 -3,667 2,3337 10,3344
/> 1 0,111 -0,2222 0,4445
Таким образом,оптимальное решение задачи имеет вид:
/>, Х = { /> ,/>}