Системный анализ и принятие решений - Презентация

Типичные задачи: План снабжения предприятий Постройка магистрали Продажа сезонных товаров Снегозащита дорог Противолодочный рейд Выборочный контроль продукции Медицинское обследование Телефонное обслуживание Некоторые примеры формулировок задач, имеющих отношение к ИО: Задача о ранце Задача коммивояжера Транспортная задача Задача об упаковке в контейнеры Задачи составления расписания, диспетчеризации Это задача укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объем (или вес) всех предметов ограничен. Ветвящаяся схема Дейкина x 1 ?3 x 1 ? 4 ЛП 0 ЛП 1 ЛП 2 x 1 = 3 ?, x 2 = 1 1/4, F= 23 3/4 89Базис x1 x2 y1 y2 Решение F 0 0 5/2 1/4 95/4 = 23 3/4 x 2 0 1 5/2-1/4 5/4 = 1 1/4 x 1 1 0-3/2 1/ 4 15/4 = 3 3/4 Подзадача ЛП 1 (i= 1 ) x 1 ?3 - ограничение в точке оптимума не выполняется x 1 - 3 /2 *y 1 1/4*y 2 = 15/4 x 1 ?3 ? x 1 y 3 = 3 Подставим x 1 = 3 /2 *y 1 - 1/4*y 2 15/4 в x 1 y 3 = 3 . В итоге получим выражение для новой базисной переменной y 3 , записанное через небазисные переменные итоговой симплекс-таблицы задачи ЛП 0 : 3 /2 *y 1 - 1/4*y 2 y 3 = 3 - 15/4 = - 3/4 Базис x1 x2 y1 y2 y3 Решение F 0 0 5/2 1/4 0 23 ? x 2 0 1 5/2-1/4 0 1 ? x 1 1 0-3/2 1/ 4 0 3 ? y3 0 0 3/2-1/4 1 3/4 90Базис x1 x2 y1 y2 y3 Решение F 0 0 5/2 1/4 0 23 ? x 2 0 1 5/2-1/4 0 1 ? x 1 1 0-3/2 1/ 4 0 3 ? y3 0 0 3/2-1/4 1 3/4 Базис x1 x2 y1 y2 y3 Решение F 0 0 4 0 1 23 x 2 0 1 1 0-1 2 x 1 1 0 0 0 1 3 y2 0 0-6 1-4 3 Как видим в подзадаче ЛП 1 получено целочисленное решение. Присваиваем i = 2 и переходим к подзадаче ЛП 2 . Подзадача ЛП 1 (i= 1 ) 91Базис x1 x2 y1 y2 Решение F 0 0 5/2 1/4 95/4 = 23 3/4 x 2 0 1 5/2-1/4 5/4 = 1 1/4 x 1 1 0-3/2 1/ 4 15/4 = 3 3/4 Подзадача ЛП 2 (i= 2 ) x 1 ? 4 - ограничение в точке оптимума не выполняется x 1 - 3 /2 *y 1 1/4*y 2 = 15/4 x 1 ?4 ? - x 1 ?-4 ? - x 1 y 4 = - 4 Подставим x 1 = 3 /2 *y 1 - 1/4*y 2 15/4 в - x 1 y 4 =-4 . В итоге получим выражение для новой базисной переменной y 4 , записанное через небазисные переменные итоговой симплекс-таблицы задачи ЛП 0 :-3 /2 *y 1 1/4*y 2 y 4 = - 4 15/4 = - 1 /4 Базис x1 x2 y1 y2 y4 Решение F 0 0 5/2 1/4 0 23 ? x 2 0 1 5/2-1/4 0 1 ? x 1 1 0-3/2 1/ 4 0 3 ? y4 0 0-3/2 1/4 1 1/4 92Подзадача ЛП 2 (i= 2 ) Базис x1 x2 y1 y2 y4 Решение F 0 0 5/2 1/4 0 23 ? x 2 0 1 5/2-1/4 0 1 ? x 1 1 0-3/2 1/ 4 0 3 ? y4 0 0-3/2 1/4 1 1/4 Базис x1 x2 y1 y2 y4 Решение F 0 0 0 2/3 5/3 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 5/6 x 1 1 0 0 0-1 4 y1 0 0 1-1/6-2/3 1/6 Как видим в подзадаче ЛП 2 не получено целочисленное решение. В итоге получим выражение для новой базисной переменной y 5 , записанное через небазисные переменные итоговой симплекс-таблицы задачи ЛП 2 : - 1/6 *y 2 - 5 / 3 *y 4 y 5 = - 5/6 Базис x1 x2 y1 y2 y4 Решение F 0 0 0 2/3 5/3 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 5/6 x 1 1 0 0 0-1 4 y1 0 0 1-1/6-2/3 1/6 Итоговая симплекс-таблица задачи ЛП 2 : Базис x1 x2 y1 y2 y4 y5 Решение F 0 0 0 2/3 5/3 0 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 0 5/6 x 1 1 0 0 0-1 0 4 y1 0 0 1-1/6-2/3 0 1/6 y5 0 0 0-1/6-5/3 1-5/6 95Подзадача ЛП 3 (i= 3 ) Базис x1 x2 y1 y2 y4 y5 Решение F 0 0 0 2/3 5/3 0 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 0 5/6 x 1 1 0 0 0-1 0 4 y1 0 0 1-1/6-2/3 0 1/6 y5 0 0 0-1/6-5/3 1-5/6 (2/3)/ (-1/6) =-4 (5/3)/ (-5/3)=-1 - т.к. исходная задача максимизации Базис x1 x2 y1 y2 y4 y5 Решение F 0 0 0 1/2 0 1 135 / 6=22 1/2 x 2 0 1 0 0 0 1 0 x 1 1 0 0 1/10 0-3/5 4 1/2 y1 0 0 1-1/ 10 0-2/5 1/ 2 y 4 0 0 0 1/ 10 1-3/5 1 / 2 Как видим в подзадаче ЛП 3 не получено целочисленное решение. Поскольку x 2 принимает целочисленное значение, то переменной ветвления выбираем x 1 . В итоге получим две подзадачи: ЛП 5 при x 1 ? 4 и ЛП 6 при x 1 ? 5 . 9697 Подзадача ЛП 4 (i =4) x 2 ? 1 - ограничение в точке оптимума не выполняется x 2 1/6 *y 2 5 / 3 *y 4 = 5/ 6 x 2 ? 1 ? - x 2 ?-1 ?-x 2 y 6 =-1 Подставим x 2 = - 1/6 *y 2 - 5 / 3 *y 4 5/ 6 в-x 2 y 6 =-1 . В итоге получим выражение для новой базисной переменной y 6 , записанное через небазисные переменные итоговой симплекс-таблицы задачи ЛП 2 : 1/6 *y 2 5 / 3 *y 4 y 6 = - 1 /6 Базис x1 x2 y1 y2 y4 Решение F 0 0 0 2/3 5/3 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 5/6 x 1 1 0 0 0-1 4 y1 0 0 1-1/6-2/3 1/6 Итоговая симплекс-таблица задачи ЛП 2 : Базис x1 x2 y1 y2 y4 y6 Решение F 0 0 0 2/3 5/3 0 70/3 =23 1/3 x 2 0 1 0 1/6 5/3 0 5/6 x 1 1 0 0 0-1 0 4 y1 0 0 1-1/6-2/3 0 1/6 y6 0 0 0 1/6 5/3 1-1/6 Согласно, ДСМ исключаемая переменная y 6 , а по условию оптимальности вводимую переменную мы выбрать не может, отсюда следует, что подзадача ЛП 4 не имеет допустимого решения.