Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2018-01-13 | 532 |
5.00
из
|
Заказать работу |
|
|
Оптимизационные задачи линейного программирования
Оптимизационной задачей называется задача нахождения экстремума (максимума или минимума) целевой функции при наличии некоторой системы линейных или нелинейных ограничений. Часто оптимизационные задачи задаются в виде текстовых задач, когда перед решением нужно сначала составить систему уравнений и неравенств. Такие задачи постоянно встречаются в ЕГЭ и на ДВИ.
Начнем рассмотрение темы со случаев, когда и целевая функция, и система ограничений заданы линейно.
В общем виде задача выглядит так:
Здесь числа а и с – произвольные числа. Задача может быть направлена как на максимум, так и на минимум. При этом ограничения могут быть как меньше или равны нулю, так и больше или равны нулю.
Пример 1. Оптимизационная задача с использованием понятия градиента
Найти наибольшее и наименьшее значение параметра а, при котором выполняется следующая система:
Важные термины:
Линии уровня - линии, которые может задавать уравнение целевой функции с учетом значений параметра.
Градиент (от лат.gradiens, род.падеж gradientis – шагающий, растущий) – вектор, своим направлением указывающий направление наибольшего возрастания некоторой величины, значение которой меняется от одной точки пространства к другой, а по величине (модулю) равный скорости роста этой величины в этом направлении.
Градиент является вектором нормали, перпендикулярным линиям уровня – линии уровня будут двигаться вдоль этого вектора. Как мы знаем из лекции 2, если уравнение прямой задано в общем виде , то нормальный вектор задается как .
Целочисленные оптимизационные задачи
|
Некоторая специфика появляется, когда дана текстовая задача с такими условиями, что неизвестные являются целочисленными.
Пример 2. Целочисленная оптимизационная задача
Баржа грузоподъемностью 134 тонны перевозит контейнеры типов А и В. Количество загруженных на баржу контейнеров типа В не менее чем на 25% превосходит количество загруженных контейнеров типа А. Вес и стоимость одного контейнера типа А составляет 2 тонны и 5 млн. руб., контейнера типа В – 5 тонн и 7 млн. руб.соответственно. Определите наибольшую возможную суммарную стоимость (в млн. руб.) всех контейнеров, перевозимых баржей при данных условиях.
Задачи, которые сводятся к нахождению максимума/минимума квадратичной функции
В таких задачах необходимо использовать уже знакомые принципы нахождения максимального (или минимального) значения квадратичной функции: оно может достигаться в вершине параболы или в граничных точках ограничения, если оно есть.
И снова необходимо помнить, что если речь идет о текстовой задаче, на переменные могут быть дополнительные условия, связанные со смыслом – например, их неотрицательность, целочисленность.
Пример 3. Задача на максимум/минимум квадратичной функции
В распоряжении начальника имеется бригада рабочих в составе 24 человек. Их нужно распределить на день на два объекта. Если на первом объекте работает t человек, то их суточная зарплата составляет 4 t 2 у. е. Если на втором объекте работает t человек, то их суточная зарплата составляет t 2 у. е. Как нужно распределить на эти объекты бригаду рабочих, чтобы выплаты на их суточную зарплату оказались наименьшими? Сколько у. е. в этом случае придется заплатить рабочим?
|
|
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!