Тема: Математическое программирование
Лекция 15. П.15. Основы математического моделирования. Математическая модель.
Математические модели задач линейного программирования
Математические модели позволяют определять оптимальные значения неизвестных параметров экономических систем, что является важным в процессе принятия решений. Математическое программирование как раз и дает аппарат, позволяющий оптимизировать процесс отбора лучших вариантов планов в процессе управления в экономических системах. Используется в матстастике, оптимизационные методы, методы экономич. При изучении сложных процессов и явлений в экономике очень часто применяется моделирование — вполне определенное конкретное отображение рассматриваемых характеристик изучаемого объекта. Суть его состоит в том, что изучаемое явление воспроизводится в экспериментальных условиях с помощью модели в другом временном и пространственном масштабе. Модель — это специально создаваемый объект, с помощью которого воспроизводится вполне определенные характеристики исследуемой системы с целью ее изучения. Математическое моделирование является наиболее совершенным и вместе с тем эффективным методом получения информации об исследуемом объекте. Оно представляет собой мощное средство анализа в экономике. Результаты исследования с помощью моделей будут иметь практический интерес тогда, когда построенная модель будет достаточно адекватна рассматриваемому явлению, то есть достаточно хорошо отображать реальную ситуацию. Трудности применения классических методов оптимизации при решении экономических задач. Математическое программирование — это раздел прикладной математики, который разрабатывает теоретические основы и методы решения экстремальных задач. К математическому программированию относятся ряд разделов, основные из которых следующие:. К данному разделу относятся задачи, в которых неизвестные переменные входят в математические соотношения в первой степени. К данному разделу относятся задачи, в которых целевая функция и или ограничения могут быть нелинейными. К данному разделу относятся задачи, в которых процесс решения можно разбить на отдельные этапы. К данному разделу относятся задачи, в которых неизвестные переменные могут принимать только целочисленные значения. К данному разделу относятся задачи, в которых содержатся случайные величины в целевой функции или ограничениях. К данному разделу относятся задачи, в которых коэффициенты при неизвестных переменных в целевой функции или ограничениях зависят от некоторых параметров. Для решения задач математического программирования сложно использовать классические методы нахождения экстремума т. Полный перебор допустимых точек невозможен из-за значительного их количества. Понятие математической модели, виды мат. Математическая модель — это записанная в математических символах и выражениях абстракция реального явления или процесса. Математические модели экономических процессов и явлений называются экономико-математическими моделями. Общая постановка задач математического програмирования. Рассмотрим общую постановку задачи математического программирования. Общая задача математического программирования состоит в определении оптимального значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Математически определение оптимального решения выражается в нахождении экстремума max или min функции многих переменных. Задача об оптимизации плана выпуска продукции. Экономическая постановка и построение математической модели задач. Предприятие производит n видов продукции с использованием m видов сырья. Для производства единицы продукции используется строго определённое количество сырья того или иного вида. Сырьё каждого вида на предприятии ограничено. Предприятие получает определённую прибыль от реализации единицы продукции. Необходимо найти такой план производства продукции, при котором предприятие получит максимальную общую прибыль. Аi — заданное ограничение на имеющийся объём ресурсов i-го вида;. Рj — прибыль, получаемая от реализации единицы продукции j-го вида;. В терминах введённых обозначений данная задача запишется следующим. Экономическая постановка и построение математической модели задачи. В некотором фермерском хозяйстве производится откорм животных. Для откорма используется n видов кормов. Известно содержание питательных веществ кальций, фосфор и др. Для полноценного питания животных необходимо потребление питательных веществ не меньше заданных количеств. Известна стоимость единицы каждого корма. Необходимо определить рацион кормления животных, при котором общие затраты на откорм будут минимальными. Аi — необходимое суточное потребление питательного вещества i —го вида;. Имеется m поставщиков однородной продукции и n потребителей этой продукции. Известны удельные затраты на доставку единицы продукции от каждого поставщика каждому потребителю. Запасы продукции у поставщиков ограничены. Известны так же потребности в продукции каждого потребителя. Необходимо определить такой план перевозки продукции от поставщиков к потребителям, при котором общие затраты на перевозку будут минимальными. Cij — удельные затраты на перевозку единицы продукции от i-го поставщика j-му потребителю. В терминах введённых обозначений данная задача запишется следующим образом:. От каждого поставщика можно вывести продукцию не более имеющегося количества:. Потребность каждого потребителя в продукции должна быть удовле-. Задача о выборе назначениях или о назначениях. Имеются n видов работ и n исполнителей. Каждый из исполнителей может выполнить любую, но только одну работу. Задана себестоимость выполнения каждой работы, каждым исполнителем. Необходимо закрепить исполнителей за работой таким образом, чтобы общая стоимость выполнения работ была минимальной. В данной задаче неизвестные переменные могут принимать только два значения 0 или 1. Такие переменные называются нулевыми. Задача о раскрое материалов. На раскрой поступает исходный материал одинакового размера. Его требуется раскроить на заготовки заданного размера в заданном количестве, таким образом, чтобы общие отходы были минимальными. Сj —размер отходов при раскрое единицы исходного материала по варианту j;. Математическая модель раскроя строится в два этапа. На первом этапе производится построение вариантов раскроя, в результате которого определяются значения количества вариантов n, количества заготовок каждого вида, получаемых при различных вариантах раскроя аij , а так же значения отходов Сj. Построение вариантов раскроя единицы исходного материала осуществляется в виде следующей таблицы:. Заготовки располагаются в порядке невозрастания их размеров. Построение вариантов осуществляется методом полного перебора. Общая форма модели задач ЛП и ее особенности. В общей форме каждый символ R1 , R2 ,…, Rm означает один из знаков: Система ограничений представлена в виде уравнений жестких условий и неравенств нежестких условий. Стандартная форма модели задач ЛП и ее особенности. Особенности стандартной формы модели задачи ЛП следующие:. Каноническая форма модели задач ЛП и ее особенности. Особенности канонической формы следующие:. Система ограничений представлена в виде уравнений жестких условий. Условия неотрицательности накладываются на все переменные. В некоторых источниках целевая функция задачи ЛП, представленной в канонической форме, стремится к максимуму. Это делается для удобства решения задачи по алгоритму, разработанному на максимум целевой функции. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных ОДЗ. План задачи линейного программирования, при котором целевая функция принимает минимальное или максимальное значение на ОДЗ называется оптимальным. Виды записей задач ЛП: Модели задач ЛП могут быть записаны в различных видах. Модель задачи ЛП в матричном виде:. Модель задачи ЛП в векторном виде:. Х1 a11 a12 a1n a1. Хn am1 am2 am2 am. Переход от стандартной и общей формы задач ЛП к канонической. Для перехода от общей или стандартной формы к канонической используют следующие приёмы. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая — Х7 и т. Переход от канонической формы модели ЗЛП к стандартной. Другой способ состоит в приведении системы уравнений к специальному виду и дальнейшему исключению некоторых переменных. С помощью метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое выделение осуществляется с помощью эквивалентных элементарных гаусовских преобразований. Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:. Далее подставляем в целевую функцию z выражениех 1 и х 2 … х n. Понятие гиперплоскости полуплоскости, опорная гиперплоскость. Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий. Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству. Любую точку отрезка можно представить в виде выпуклой комбинации его угловых точек. Любую точку выпуклого замкнутого множества можно представить в виде выпуклой комбинации его угловых точек. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме. Проверяется количество неизвестных переменных. Если это количество больше трёх, то задача не может быть решена графическим методом существуют другие эффективные методы решения таких задач. Строится область допустимых значений переменных для ЗЛП. Строится направляющий вектор c. Через ОДЗ проводится исходная изоцель перпендикулярно направляющему вектору. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи. Для того, чтобы определить координаты оптимальной точки, необходимо решить систему соответствующих линейных уравнений. Для нахождения оптимального значения целевой функции необходимо оптимальные значения переменных подставить в целевую функцию и вычислить её значение. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ. Строится направляющий вектор С по коэффициентам при переменных целевой функции. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель. Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи. Для определения координат оптимальной точки необходимо решить систему соответствующих линейных уравнений тех условий, на пересечении которых находится оптимальная точка. Для нахождения оптимального значения целевой функции, необходимо координаты оптимальной точки подставить в целевую функцию и вычислиь ее значение. Область допустимых решений задачи ЛП выпуклое множество замкнутое и ограниченное в n-мерном пространстве. О целевой функции задачи линейного программирования. Целевая функция ЗЛП принимает своё оптимальное значение в одной из угловых точек области допустимых значений переменных. Если целевая функция принимает своё оптимальное значение в нескольких угловых точках, то такое же значение она принимает и в любой точке, являющейся выпуклой комбинацией данных угловых точек. Теорема об угловой точке. Достаточное и необходимое условие. Следствия из теоремы о свойствах решений задач ЛП и выводы. Опорный план имеет не более m положительных координат. Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае вырожденным. Каждая угловая точка ОДЗ является опорным планом. При решении задач ЛП симплексным методом необходимо выполнить следующую последовательность действий. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму. Выделяется начальный опорный план и значение целевой функции при этом опорном плане. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0. Данная строка называется разрешающей строкой. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С Б. Переходим к выполнению пункта 4 данного алгоритма. После построения каждой таблицы можно проверить правильность вычислений с использованием формул вычисления оценок, приведенных в предыдущем параграфе. Формулы расчета коэффициентов индексной строки. Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом. С — вектор, состоящий из коэффициентов при базисных переменных целевой функции Z. Таким образом теорема и следствие позволяют установить, является ли очередной опорный план оптимальным и, если не является, то необходимо перейти к другому опорному плану, при котором значение целевой функции будет меньше. В теореме и следствии предполагается, что задача находится в канонической форме с целевой функцией на минимум. Однако симплекс-методом моно решать и задачи с целевой функцией на максимум. В этом случае при анализе значений оценок используется их противоположный смысл, то есть план будет оптимальным, если все оценки оптимальности будут не отрицательными положительным или отрицательным. Выбор вектора, вводящегося в базис и выводящегося из базиса. Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Координаты вектора Х1 должны быть неотрицательными, то есть. Если , то эта координата будет неотрицательной. Соотношение 6 называется симплексным отношением. Правило полных жордановых исключений для перерасчета симплекс таблицы. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом. При решении задач симплекс-методом возможны следующие виды оптимальных решений:. Если оценки всех свободных векторов строго отрицательные, то полученный опорный план является оптимальным и единственным. Альтернативный оптимум множество оптимальных решений. Если среди неположительных оценок свободных векторов имеется хотя бы одна нулевая, то полученный опорный план будет оптимальным, но не единственным. В этом случае можно перейти к другим опорным планам вводятся в базис векторы, которым соответствуют нулевые оценки и, затем, общее оптимальное решение записать в виде выпуклой комбинации полученных оптимальных опорных планов. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу. Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану. ЗЛП не имеет оптимального решения, так как система ограничений противоречива. Поскольку при решении ЗЛП обычным симплекс-методом должен быть исходный опорный план, то система линейных уравнений заведомо не противоречива. Следовательно, такой случай не может встретиться при решении обычным симплекс методом. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода. В каких случая применяется метод искусственного базиса. Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. Такая переменная называется искусственной. Искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом так как целевая функция на нахождения минимума. Это число обозначается латинской буквой M. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом так как целевая функция на нахождения минимума. Если решается задача с целевой функцией на нахождение максимума, то искусственные переменные входят в целевую функцию с коэффициентом —М. Таким образом, в расширенной задаче мы имеем опорный план хотя некоторые из базисных переменных и являются искусственными. Строится исходная симплекс таблица, в которой индексная строка разбивается на две строки, поскольку оценки состоят из двух слагаемых. В верхней строке записывается слагаемое оценки без M, в нижней строке — коэффициенты при М. Знак оценки определяется знаком коэффициента при M, независимо от величины и знака слагаемого без M, так как M очень большое положительное число. Таким образом, для определения вектора, который вводится в базис необходимо провести анализ нижней индексной строки. Если выводится из базиса искусственный вектор, то соответствующий столбец в последующих симплексных таблицах можно не вычислять, если нет необходимости в получении решения двойственной задачи см. После того, как все искусственные векторы будут выведены из базиса, нижняя строка будет иметь все нулевые элементы, за исключением оценок, соответствующих искусственным векторам. Они будут равны —1. Такую строку можно удалить из рассмотрения и дальнейшее решение проводить обычным симплекс-методом, если нет необходимости в получении решения двойственной задачи см. Критерий оптимальности в методе искусственного базиса. Признак построение начального опорного плана исходной задачи. Считается, что такая задача должна иметь исходный единичный базис. Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0. Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки. Пересчитывают симплексную таблицу по правилу полных жордановых исключений. Признаком получения допустимого опорного плана является отсутствие в столбце А0 отрицательных элементов. Если в столбце А0 имеются отрицательные элементы то переходят ко второму пункту. Если же их нет, то переходят к решению полученной задачи обычным способом. Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой. Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку. Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей. Для решения транспортной задачи необходимо, чтобы она была закрытой. Открытую транспортную задачу можно преобразовать к закрытой следующим образом. Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат. Способы построения первоначального распределения в транспортной задаче: Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетворяет первого потребителя. Затем, если у поставщика товар еще остался,. Сущность метода заключается в том, что максимально возможная поставка всегда проставляется в клетку, которой соответствует наименьший тариф матрицы. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам. Заполнения организуем при прохождении таблицы слева направо и сверху вниз. Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами. Закрытая транспортная задача всегда имеет решение. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то и решение транспортной задачи также будет целочисленным. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Теорем оптимальности транспортной задачи. Если для некоторого распределения транспортной задачи вы-. Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов. Для нахождения потенциалов строк и столбцов пользуются следующими рассуждениями, исходя из условия а теоремы оптимальности. Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а теоремы вычисляются значения остальных неизвестных потенциалов. Исходя из соотношения б теоремы можно записать следующую формулу для вычисления оценок: Для того, чтобы оценки не перепутать с объёмами перевозок, они оценки заключаются в круги. Оценки оптимальности в свободных клетках ТЗ представляют собой критерий оптимальности, с помощью которого осуществляется проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным. Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок. Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Для любой свободной клетки существует цикл пересчета и притом единственный. Пусть рассматриваемый план перевозок не оптимальный, то есть имеются положительные относительные оценки. Тогда берется неблагоприятная клетка одна из неблагоприятных и для нее строится цикл пересчета, согласно которому потом делается перераспределение намеченных перевозок. Цикл строится в виде ломаной замкнутой линии, отрезки которой идут либо вдоль столбика, либо вдоль строки. В одном из углов ломаной претендующая на товар неблагоприятная клетка, а в остальных углах клетки заполненные, то есть при построении цикла мы исходим из претендующей клетки и возвращаемся в нее по ломаной, но повороты мы можем делать только в клетках заполненных соответствующих базисным переменным. Пусть неблагоприятная клетка претендует на товар Q. Чтобы не произошел разбаланс в таблице, надо в переходах по циклу по очереди. Так как углов чётное количество, в половине клеток Q прибавится, а в другой половине - отнимется. Обход цикла начинают по часовой стрелке или против с претендующей клетки, помещая туда товар Q, затем из соседней клетки вычитают Q, затем прибавляют и т. Сама величина Q выбирается так, чтобы одна из клеток опустошалась, но ни одна из поставок не стала бы отрицательной. Для этого Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. При этом опустошаются две клетки. Но надо, чтобы взаимно пустой стала лишь одна клетка. Эта клетка считается в новой таблице базисной заполненной. Определение объёма перемещаемой продукции. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений:. Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции выбрать следующим: Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу. Проверить, выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель. Вычисляются оценки свободных клеток. Если все они не отрицательные — план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т. Переходят к пункту 4. Учет затрат на производство и транспортировку продукции. Транспортная задача с запретами на поставки. При решении некоторых задач необходимо учитывать затраты не только на перевозку груза, но и на производство перевозимой продукции. Для этого в матрице трансп. В некоторых ситуациях нельзя перевозить продукцию по какому-либо маршруту. Для этого в матрице транспортной задачи перевозка через которую является запретной проставляется запрещающий тариф М. В некоторых транспортных задачах по некоторым маршрутам устанавливают меньшую пропускную способность чем необходимо для удовлетворения спроса пункта потребления. В некоторых случаях в задаче требуется, что например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs. Возможные выводы при экономич. При получении оптимального распределения необходимо вернуться к исходной задаче и сделать соответствующие экономич. Увеличиваются мощности тех пунктов производства, которые ближе всего расположены к пунктам потребления, привязанным к фиктивному пункту производства. Производится увеличение мощности производителя на величину привязки. Для этого рассматривают столбец пункта потребления, который привязан к фиктивному пункту производства, и находят в нем наименьший тариф. Мощность соответствующего этому тарифу пункта производства наиболее эффективно увеличить на величину привязки. Экономическая постановка двойственных задач на примере задачи об оптимизации плана выпуска продукции. Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи. Пусть имеется зада об оптимизации плана выпуска продукции. Она имеет следующий вид:. Пусть предприятие по какой-либо причине не может выпускать продукцию. Для того, чтобы уменьшить затраты простоя, предприятие может реализовать сырье, которое у него имеется. По каким ценам нужно реализовать сырье? Соответствие между структурными элементами прямой и двойственной задачи. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из. Отметим также, что соотношение двойственности взаимное, то есть задача, двойственная по отношению к двойственной, совпадает с исходной. Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре ограничения прямой и двойственной задач являются нестрогими неравенствами и, следовательно, переменные обеих задач могут принимать только неотрицательные значения. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели построение симметричных и несимметричных двойств. Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Основная и вторая теорема двойственности сформулировать теоремы и разъяснить. При этом экстремальные значен. Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: Это условия дополняющей нежесткости. Если же какая-то компонента опт. Такой рес-с наз-ся дефицитным. Построение оптимального опорного плана двойственной задачи по симплексной таблице исходной задачи. Информация из столбцов обратной матрицы линейных преобразований, приведших к оптимальному результату. Из столбцов матрицы D-1 можно почерпнуть весьма полезную информацию. Z - соответствующее приращение дохода. Из столбца A4 еще следует, что при увеличении ресурса S2 на 1 у. Сказанное по столбцу A4 будет ниже прокомментировано с помощьюграфических построений рис. Это означает, чтоувеличение ресурса S3 на 1 у. При этом, как следует из столбика A5 табл. Запас по сырью S1 см. Идея метода динамического програмирования и его геометрическая интерпретация. Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения. В результате после первого шага известно решение Un и соответствующее значение функции f1 Sn Уменьшить значение l на единицу и записать соответствующее функциональное уравнение. Если l не равно 0, перейти к выполнению п. Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу. Метод динам программ позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Решение осуществляется по шагам. Основной принцип, на котором базируется оптимизация многошагового процесса, а также особенности вычислительного метода—принцип оптимальности Беллмана. Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения. Требования, предъявляемые к задачам, решаемым методом ДП. Динамическое программирование—математический метод для нахождения оптимальных решений многошаговых задач. Многошаговым является процесс, развивающийся во времени и распадающийся на ряд шагов, или этапов. Одна из особенностей метода динамического программирования состоит в том, что принятые решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией. Цель оптимального планирования—выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной. Другой важной особенностью метода является независимость оптимального решения, принимаемого на очередном шаге, от предистории, то есть от того, каким образом оптимизируемый процесс достиг теперешнего состояния. Оптимальное решение выбирается лишь с учетом факторов, характеризующих процесс в данный момент. Метод динам программ характеризуется также тем, что выбор оптимального решения на каждом шаге должен производиться с учетом его последствий в будущем. Это означает, что, оптимизируя процесс на каждом отдельном шаге, ни в коем случае нельзя забыть обо всех последующих шагах. Экономическая постановка и построение математической модели задачи, решаемой методом ДП на примере задачи о распределении капиталовложений. Предварительно поясним, что метод динамического программирования применяется прежде всего к тем задачам, в которых оптимизируемый процесс или ситуация разворачивается в пространстве или во времени, или в том и другом. Пусть сам процесс ситуация настолько сложен, что нет возможности его оптимизировать известными методами. Тогда по методу динамического программирования СЛОЖНЫЙ процесс операция, ситуация разбивается членится на ряд этапов шагов. Эта разбивка во многих случаях является естественной, но в общем случае привносится искусственно. Например, при рассмотрении какой-либо партии игры в шахматы любой ход каждого из игроков как раз и служит. А в военной операции по преследованию одной ракеты другой весь непрерывный процесс приходится искусственно разбивать на этапы, например, через каждую секунду наблюдения. Метод динамического программирования позволяет оптимизацию всего сложного процесса заменить условной оптимизацией по каждому из этапов. При этом метод предусматривает, что условная оптимизация на отдельном шаге этапе делается в интересах, прежде всего, всей операции. Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, fn S0 , проводятся по формуле 1 , которая носит название основного функционального уравнения Беллмана или рекуррентное соотношение. Для решения задачи об оптимальном распределении капиталовложений мы будем пользоваться функциональным уравнением Беллмана. Сначала с помощью простейшей ситуации проиллюстрируем вывод функционального уравнения Беллмана, а потом на примере докажем, как использовать это уравнение для решения интересующей нас задачи. Начнем с оптимального распределения выделенных капиталовложений в сумме К между двумя предприятиями. Плановые отделы предприятий на основе своих расчетов сформировали функции дохода q x для предприятия П1 и h x - для предприятия П2. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием. Итак, пусть предприятию П1 выделены капиталовложения в сумме х, тогда предприятию П2 выделяется сумма К - х. В этом случае от первого предприятия будет получен доход q x , а от второго - h К - x. Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R K, x приняло свое максимальное значение, которое мы обозначим через F K:. УСЛОЖНИМ нашу задачу, распределив капиталовложения на два плановых периода два этапа. Пусть изначально решено первому предприятию П1 выделить сумму х, а второму К — х. Оптимизацию по методу динамического программирования, как правило, начинают с концевого этапа. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором. Затем к рассмотренному последнему в нашем случае второму этапу как бы пристраиваем предшествующий у нас первый этап и находим максимальный доход от двух этапов вместе:. Полученное функциональное уравнение Беллмана носит рекуррентный характер, то есть связывает значение Fn со значением Fn Понятие о решении задач нелинейного программирования. Пусть задача нелинейного программирования ставится в следующем общем виде: Например, область допустимых решений может уже быть невыпуклой, а экстремум целевой функции может наблюдаться в любой точке допустимой области. Существенно отличаются и методы решения нелинейных задач. Рассмотрим лишь некоторые подходы к решению этих задач. Прежде всего также справедлив графический подход при решении простейших задач нелинейного программирования. Так, если аргументами задачи являются переменные х1 и х2, то сначала на плоскости этих переменных строится область допустимых решений, а затем с помощью уровней целевой функции f х1,х2 определяется оптимальная точка в области. В нелинейном программировании для решения многих задач используется градиентный подход. Имеется целый ряд градиентных методов, сущность которых состоит в поиске оптимального результата с помощью градиента целевой функции - вектора, указывающего направление максимального возрастания цели для рассматриваемой точки. В общем случае процедура поиска совершается в итеративном режиме от первоначально выбранной точки к точкам с лучшим показателем. По мере приближения к оптимальной точке Q направления рабочих градиентов сближаются. Поэтому идеальным критерием остановки процесса будет коллинеарность градиента цели и градиента нарушенной границы. Понятие о параметрическом и целочисленном программировании. В задачах с неделимыми объектами на переменные накладываются условия целочисленности. Иногда эти условия распространяются на все переменные, иногда—на часть переменных. Рассматривают полностью целочисленную задачу. Теперь в отличие от общей задачи линейного программирования, оптимальный план не обязательно будет в вершине многогранника планов. Существуют следующие методы решения целочисленных задач:. Параметрическое программирование — раздел математического программирования, посвящённый исследованию задач оптимизации, в которых условия допустимости и целевая функция зависят от некоторых детерминированных параметров. Главная Опубликовать работу О сайте. Шпаргалка по Математическому программированию. Сохрани ссылку на реферат в одной из сетей: К математическому программированию относятся ряд разделов, основные из которых следующие: Математические модели экономических процессов и явлений называются экономико-математическими моделями Модели делятся на: Введём обозначения заданных параметров. В терминах введённых обозначений данная задача запишется следующим образом: Экономическая постановка В некотором фермерском хозяйстве производится откорм животных. Введём обозначения заданных параметров: От каждого поставщика можно вывести продукцию не более имеющегося количества: Потребность каждого потребителя в продукции должна быть удовле- т ворена: За каждой работой должен быть закреплён только один исполнитель: Каждый исполнитель может выполнить только одну работу: Введём обозначения неизвестных переменных. Построение вариантов раскроя единицы исходного материала осуществляется в виде следующей таблицы: Общая форма модели задач ЛП и ее особенности Общая форма ЗЛП имеет вид: Найти максимум или минимум целевой функции z: Общая форма модели задачи ЛП обладает следующими особенностями. Условия неотрицательности накладываются не на все переменные Целевая функция стремится либо к максимуму, либо к минимуму. Стандартная форма модели задач ЛП и ее особенности Стандартная форма имеет следующий вид. Каноническая форма модели задач ЛП и ее особенности Каноническая форма имеет вид: Найти минимум целевой функции z: Условия неотрицательности накладываются на все переменные Целевая функция стремится к В некоторых источниках целевая функция задачи ЛП, представленной в канонической форме, стремится к максимуму. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП Определение 1. Модель задачи ЛП в матричном виде: Модель задачи ЛП в векторном виде: Теорема связи Для перехода от общей или стандартной формы к канонической используют следующие приёмы. Переход от канонической формы модели ЗЛП к стандартной Для перехода от канонической формы к стандартной можно каждое из уравнений заменить системой неравенств: Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы: Записываем задачу в стандартной форме. Выпуклый многогранник Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий. Выпуклое множество Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству. Область допустимых решений задачи ЛП выпуклое множество замкнутое и ограниченное в n-мерном пространстве Теорема 2. Достаточное и необходимое условие Проводится построение исходной симплексной таблицы. При решении задач симплекс-методом возможны следующие виды оптимальных решений: В каких случая применяется метод искусственного базиса Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. Построение М-задачи в методе искусственного базиса Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. Строится исходная симплекс таблица. Алгоритм двойственного симплекс-метода Алгоритм двойственного симплекс-метода: Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0 Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки. Пересчитывают симплексную таблицу по правилу полных жордановых исключений проверяют полученный план на допустимость. Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей т. Затем, если у поставщика товар еще остался, Метод наименьшего элемента в матрице. Свойства транспортных задач Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами. Если для некоторого распределения транспортной задачи вы- полняются условия: Потенциалы и способы их расчета. Чтобы не произошел разбаланс в таблице, надо в переходах по циклу по очереди прибавлять и отнимать Q к имеющимся перевозкам. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений: Проверить, выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель 2. Условие задачи записывается в форме транспорт. Строится начальный опорный план 4. Определяются потенциалы пост-ков и потреб-лей 5. Дальше задача решается обычным способом. Задачи с запретами на поставки. Она имеет следующий вид: Соответствие между структурными элементами прямой и двойственной задачи Каждой задаче линейного программирования можно сопоставить двойственную задачу по следующим правилам: Во всех ограничениях исходной задачи свободные члены должны находиться справа, а члены с неизвестными - слева. Ограничения-неравенства исходной задачи должны иметь знаки, направленные в одну строну. Каждому ограничению исходной задачи соответствует переменная в двойственной задаче. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из коэффициентов при переменных исходной задачи. Свободные члены исходной задачи являются коэффициентами при переменных в функции цели двойственной задачи, а свободными членами в двойственной задаче — коэффициенты при переменных в функции исходной задачи. Возьмем ЗЛП на максимум в канонической форме: Основная и вторая теорема двойственности сформулировать теоремы и разъяснить Первая теорема двойственности. Вторая теорема двойственности и ее эконом. Построение оптимального опорного плана двойственной задачи по симплексной таблице исходной задачи Информация из столбцов обратной матрицы линейных преобразований, приведших к оптимальному результату. Математически он записывается выражением вида: Требования, предъявляемые к задачам, решаемым методом ДП Динамическое программирование—математический метод для нахождения оптимальных решений многошаговых задач. Например, при рассмотрении какой-либо партии игры в шахматы любой ход каждого из игроков как раз и служит разбивке всей партии на отдельные шаги этапы. Метод динамического программирования позволяет оптимизацию всего сложного процесса заменить условной оптимизацией по каждому из этапов шагов с последующим синтезом оптимального управления всем процессом. Задача о распределении капитальных вложений пример. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием будет получен доход q x , а вторым h x , причем величина x может принимать непрерывные или известные дискретные значения от 0 до К. Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R K, x приняло свое максимальное значение, которое мы обозначим через F K: Эта запись является как бы остовом для более полных записей функционального уравнения Беллмана. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором этапе. Получим Затем к рассмотренному последнему в нашем случае второму этапу как бы пристраиваем предшествующий у нас первый этап и находим максимальный доход от двух этапов вместе: Аналогичным образом для n этапов получаем где Fn-1 - целевая функция, дающая наилучший результат за последние n - 1 этапы. В более общем начертании уравнение Беллмана имеет вид где , Fn-1 - максимальный доход за n - 1 последних этапов, Fn - максимальный доход за все n этапов. Понятие о решении задач нелинейного программирования Пусть задача нелинейного программирования ставится в следующем общем виде: По своим общим свойствам задачи нелинейного программирования могут существенно отличаться от линейных. Постановка и математич модель ЗЦЛП. Существуют следующие методы решения целочисленных задач:
Текстиль красноярск каталог
Дрель ударная интерскол ду 1000эр
Структуру общества составляют
Первомайская 25 череповец на карте
Сколько куры пьют воды
Rics результаты цт
План работы с семьей в младшей группе
Сколько дней идет письмо первым классом
Эриспирус 80 мг инструкция по применению
Решение задачи 5 класса дорофеев
Лекарства от сердечной недостаточности
Трансмиссионное масло gl 3
Сколько варить филе индейкидо готовности
К8 18 насос характеристики
Методы и приемы управления проектами