Основы линейного программирования
2. Основы линейного программирования
Линейное программирование
Оглавление Назад Далее Глоссарий понятий. Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции линейной формы при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования. Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Итак, Линейное программирование — это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы. Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений , которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных аргументов функции F , которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F , максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F , называется оптимальным планом задачи. Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования ЗЛП является выбор из множества допустимых планов наиболее выгодного оптимального. В зависимости от вида функции f x и области G и различают разделы математического программирования: Линейное программирование характеризуется тем, что а функция f x является линейной функцией переменных х 1 , х 2 , … х n б область G определяется системой линейных равенств или неравенств. В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Поyтому в наиболее общей форме задачу линейного программирования формулируют следующим образом:. Итак, решения, удовлетворяющие системе ограничений 2. Выше описанная задача линейного программирования ЗЛП представлена в общей форме, но одна и та же ЗЛП может быть сформулирована в различных эквивалентных формах. Наиболее важными формами задачи линейного программирования являются каноническая и стандартная. В канонической форме задача является задачей на максимум минимум некоторой линейной функции F , ее система ограничений состоит только из равенств уравнений. При этом переменные задачи х 1 , х 2 , Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют в целевой функции и во всех ограничениях разностью неотрицательных переменных. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме. В стандартной форме задача линейного программирования является задачей на максимум минимум линейной целевой функции. Все переменные задачи неотрицательны. Всякую задачу линейного программирования можно сформулировать в стандартной форме. Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположных неравенств:. Существует и другие способы преобразования системы равенств в систему неравенств, то есть всякую задачу линейного программирования можно сформулировать в стандартной форме.
Большинство задач оптимизации относится к нелинейным, но решение нелинейных задач — это сложная вычислительная проблема. Поэтому практически во всех реальных приложениях для решения нелинейных задач используются приближенные методы решения. Линейное программирование выделяется среди других методов программирования как основа для многих процедур решения. Математически задача линейного программирования ставится следующим образом: Словесно задачу линейного программирования можно сформулировать так: Поэтому можно сказать, что при решении задачи линейного программирования определяются такие значения n переменных x j , которые бы обращали в максимум линейную форму. Рассмотрим несколько практических задач, которые сводятся к линейному программированию. В трех месторождениях добывается определенное количество угля. Имеются три пункта потребления угля. Необходимо так определить девять чисел x ij , означающих количество грузов, перевозимых из пункта добычи в пункт потребления, чтобы суммарная стоимость перевозок была минимальна:. Считается, что количество добытого угля равно сумме потребляемого, то есть. При правильном питании калорийность пищевых продуктов должна полностью возмещать расход энергии человека, причем потребление отдельных растительных и животных жиров, белков, углеводов и витаминов не должно превышать определенную норму. В единице массы j-го продукта содержится a 2j жиров, a 3j белков, a 4j углеводов. Обозначим через b 1 , b 2 , b 3 , b 4 потребность организма в энергии, жирах, белках и углеводах, соответственно. Тогда при правильном питании должны выполняться следующие соотношения:. Если ввести требование экономного расходования средств, то это эквивалентно критерию. После этого задача о рациональном питании приобретает стандартный вид задачи линейного программирования. Предприятие имеет определенное количество ресурсов: Для простоты будем считать, что число ресурсов равно трем, и каждого ресурса имеется b 1 , b 2 , b 3 , условных единиц. Предприятие выпускает два вида товаров. Для производства единицы каждого товара затрачивается а ij ресурсов. Известна стоимость с i единицы каждого товара. Требуется при данных ресурсах выпустить такую комбинацию товаров x 1 и x 2 , чтобы доход предприятия L был максимален. При линейной зависимости стоимости продукции от количества продукции задача записывается в виде. Если стоимость товаров не зависит линейно от их количества, то имеет место задача нелинейного программирования. Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами x j в разных количествах, причем c j — стоимость; w j — вес отдельного предмета j-го типа. Требуется определить оптимальную загрузку так, чтобы стоимость перевозимого груза была минимальной. Она существенно отличается от ранее рассмотренных тем, что в ней искомые значения величин x j целочисленные. Поэтому ее можно отнести к задачам целочисленного линейного программирования, которые решаются различными способами, в том числе и с помощью динамического программирования. FAQ Обратная связь Вопросы и предложения. Upload Опубликованный материал нарушает ваши авторские права? Основы линейного программирования 2. Задачи линейного программирования 2. Математическая формулировка задачи линейного программирования Большинство задач оптимизации относится к нелинейным, но решение нелинейных задач — это сложная вычислительная проблема. Так, ограничение a 2. Примеры прикладных задач линейного программирования Рассмотрим несколько практических задач, которые сводятся к линейному программированию. Транспортная задача В трех месторождениях добывается определенное количество угля. Необходимо так определить девять чисел x ij , означающих количество грузов, перевозимых из пункта добычи в пункт потребления, чтобы суммарная стоимость перевозок была минимальна: Считается, что количество добытого угля равно сумме потребляемого, то есть хотя это ограничение непринципиально. Задача о рациональном питании При правильном питании калорийность пищевых продуктов должна полностью возмещать расход энергии человека, причем потребление отдельных растительных и животных жиров, белков, углеводов и витаминов не должно превышать определенную норму. Тогда при правильном питании должны выполняться следующие соотношения: Задача об использовании ресурсов Предприятие имеет определенное количество ресурсов: Задача о загрузке транспорта Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами x j в разных количествах, причем c j — стоимость; w j — вес отдельного предмета j-го типа.
Какой кондиционер выбрать один на две комнаты
Сколько стоит грамм турецкого золота
Лечение горла народными средствами в домашних условиях
Сады джусти на карте вероны
Герпес на губах врач