![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка и геометрическая интерпретацияСтр 1 из 2Следующая ⇒
Элементы целочисленного программирования Постановка и геометрическая интерпретация Многие задачи линейного программирования, возникающие в экономике и производстве, требуют решений, у которых компоненты целочисленны, то есть xj Î Z, j =1, 2, …, n. Например, когда количество выпускаемой продукции измеряется в целых величинах, скажем, поштучно. Так, количество выпускаемых автомобилей, станков не может быть дробным. Раздел линейного программирования, изучающий методы решения таких задач, называется целочисленным линейным программированием, а задачи с таким условием - задачами целочисленного линейного программирования. В математической модели таких задач появляется дополнительное условие: xj Î Z, j =1, 2, …, n: c 1 x 1+ c 2 x 2+…+ cnxn ®max(min)
В случае, когда задача имеет только две переменные: c 1 x 1+ c 2 x 2 ® max(min)
она имеет простую геометрическую интерпретацию: решением задачи является точка в многоугольнике решений системы ограничений
с целочисленными координатами, в которой достигается экстремум целевой функции задачи. Такие задачи геометрически решаются по следующей схеме: 1. Построить многоугольник решений системы (7.1). 2. В многоугольнике решений, полученном в п.1, отметить точки с целочисленными координатами. Получается область допустимых решений (ОДР) задачи (7.2). 3. Построить линии уровня c 1 x 1+ c 2 x 2= a целевой функции задачи. 4. В ОДР задачи (7.2), полученной в п.2, выбрать точку, в которой достигается требуемый экстремум. 5. Вычислить значение функции в найденной точке экстремума. Пример 1. Решить задачу целочисленного программирования геометрическим способом: 2 x 1+4 x 2 ® max(min) Решение. Действуем по вышеприведённой схеме: 1. Строим многоугольник решений системы (подробности опускаем) (Рис.4) Рис.4
Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок. — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта. — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы). — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание. SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение 2. В многоугольнике решений, полученном в п.1, отмечаем точки с целочисленными координатами. Это точки (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3). Таким образом, ОДР задачи - это множество {(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3)} (Рис.5): Рис.6
3. Cтроим линии уровня 2 x 1+4 x 2= a целевой функции задачи, ориентируясь на вектор Рис.7 4. В ОДР задачи, полученной в п.2, выбираем точки, в которых достигаются требуемые экстремумы. Это точки (1, 3) - точка максимума, и (0, 0) - точка минимума. 5. Вычислим значение функции в найденных точках экстремума: F max цел.= F (1, 3)=2× 1+4× 3=14, F min цел.= F (0, 0)=2× 0+4× 0=0. Ответ: X max цел.=(1, 3), F max цел.=14; X min цел.=(0, 0), F min цел.=0.
|