Понятие математического программирования

Математическое программирование для студентов сельхозакадемии

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

1. Основные понятия и определения математического программирования

На производстве специалисты часто сталкиваются с проблемой вы­бора наилучшего варианта решения планово-экономических задач.

Решить эту проблему помогает наука, занимающаяся разработкой теории и методов обоснования выбора наилучших вариантов плана из множества возможных. Она получила название «математическое программирование». Слово «программирование» означает выбор лучшей программы производства, лучшего плана. «Лучший» в за­висимости от конкретной цели производства. Цель обязательно выражается количественным показателем (стоимость валовой продукции, сумма затрат и т.д.). Этот показатель называется критерием оптимальности плана и задается математически в виде не­которой целевой функции (функционала). Таким образом, решение пла­ново-экономических задач сводится к нахождению либо максимально­го, либо минимального значения, другими словами, экстремального значения критерия оптимальности.

В практике наиболее широкое распространение получили плано­во-экономические задачи, в которых условия производства и крите­рий оптимальности могут быть представлены в виде системы линей­ных уравнений и неравенств. Такого рода задачи изучаются в теории линейного программирования — наибо­лее обширного, хорошо изученного и практически важного раздела ма­тематического программирования. Линейное программирование включает общие (симплексный и его модификации) и специальные (распределительный и его модификации) методы.

Под методами линейного программирования понимаются про­граммы математических действий, позволяющие находить оптимальное решение различных экономических проблем, условия решения которых выражены в виде линейных уравнений и неравенств и све­дены в единую систему линейных соотношений, подчиненную кон­кретной целевой функции.

Методами линейного программирования можно решать экономи­ческие проблемы, которые удовлетворяют следующим условиям:

• Все экономические, технологические, социальные и другие требования, определяющие оптимальное решение проблемы, должны допускать их математическую формулировку в виде линейных урав­нений и неравенств.
• Система линейных соотношений, характеризующая все усло­вия данной проблемы, должна иметь множество допустимых реше­ний, то есть прежде всего сама экономическая проблема должна до­пускать альтернативные решения.
• Основная цель, которую нужно достичь в результате решения проблемы, должна быть четко выражена экономически и сформули­рована в виде линейного соотношения.

Задача линейного программирования может быть представлена в следующих формах:

а) общая – система ограничений представлена неравенствами типа , =; не на все переменные наложены условия неотрицательности; целевая функция может стремиться как к минимуму, так и к максимуму;

б) каноническая (основная) – система ограничений однородна и представлена уравнениями; на все переменные наложено условие неотрицательности (хj?0, j=1…n); целевая функция стремиться к максимуму;

в) стандартная – система ограничений однородна, представлена неравенствами типа 0 j = 1,…,n.

4 этап — сбор исходной информации и разработка технико-экономических коэффициентов.
Основные требования, предъявляемые к исходной информации, — высокое качество, достаточное количество, соответствующая размер­ность, достоверность и надежность, своевременность и доступность.

Источниками информации служат годовые отчеты, технологиче­ские карты, данные первичного учета, различные нормативные спра­вочники и т.д. Если исходные данные будут недостаточно полными и неточными, то результаты решения задачи могут быть искажены.

Характер исходной информации связан с поставленной планово-экономической проблемой. Если ее решение относится к перспекти­ве, то применяется нормативная, а при решении текущих проблем — нормативная и отчетная информация.

Для любой модели технико-экономические характеристики объ­екта или процесса формируются в виде технико-экономических ко­эффициентов аij, коэффициентов целевой функции Cj и констант или объемных показателей ресурсов или продуктов bi. Эти коэффициенты представляют собой основную часть входной информации и их мож­но подразделить на три группы:

• удельные нормативы затрат или выхода продукции (рассчиты­ваются на основе нормативных справочников, технологических карт, с использованием методов математической статистики и другими способами);
• коэффициенты пропорциональности (коэффициенты при пере­менных в тех ограничениях, которые предусматривают определенные соотношения между зависимыми переменными по структуре посевов, по поголовью половозрастных групп животных и т.д.);
• коэффициенты связи (когда специально обусловливают зависимость переменной Xj от объемного показателя в ограничении bi, на­пример площадь посева овса не более 100 га).

При подготовке входной информации для ЭММ могут быть ис­пользованы производственные функции — математически выражен­ные связи и зависимости результатов производства от затрат произ­водственных факторов (урожайность культур — от доз внесения удоб­рений; продуктивность коров — от количества потребляемого корма и т.д.). Помимо прогнозирования уровня результативного признака, произ­водственные функции могут быть использованы для определения экономических оптимумов, коэффициентов эффективности и взаимо­заменяемости факторов.

Производственные функции могут быть представлены следую­щими способами:

• Табличный способ — в виде таблицы, где содержатся ряд значе­ний аргумента и соответствующие значения функции. Этот способ удобен, когда изучают зависимости по опытам и наблюдениям.
• Графический способ — по графику непосредственно выявляются основные свойства представленной функции и весь ход ее изменения.

Недостаток — иногда трудно точно определить значения зависи­мой переменной у при данных значениях признака х.

3. Аналитический способ — наиболее распространенный — произ­водственная функция представляет собой математическую модель многофакторного экономического процесса, которая позволяет вы­числить ожидаемое значение результата производства в зависимости от действующих на него факторов.

В отличие от ЭММ оптимального программирования, состоящих из ряда уравнений и неравенств, модель производственной функции в общем виде в большинстве случаев описывается одним уравнением, где результат производства представляется как функция n независи­мых факторов:

5 этап — разработка развернутой (матричной) модели экономи­ко-математической задачи.

Модель можно записать развернуто в виде системы неравенств и уравнений, то есть в числовом виде. Однако при достаточно большом числе переменных и ограничений такая запись громоздка, уменьшает обозримость и затрудняет чтение.

Основой развернутой модели является матрица — прямоугольная таблица, в которой записывается развернутая модель задачи в удоб­ной и сокращенной форме.
В матрице по строкам записываются ограничения, а по столбцам -переменные. Все члены одного ограничения должны иметь одну еди­ницу измерения.

Переменные матрицы подразделяются на основные, дополни­тельные и вспомогательные переменные.

Основные переменные обозначают размер видов или способов Деятельности (площадь посева культур, поголовье скота и т.д.).

Дополнительные переменные вводятся при математической реа­лизации задачи для преобразования неравенств в равенства (прирост кормов, привлечение рабочей силы и т.д.).

Вспомогательные переменные вводятся для определения расчет­ных величин (для определения общей суммы материально-денежных затрат, показателей эффективности производства и т.д.).

Ограничения матрицы могут налагаться на отдельные перемен­ные, на часть их или на все. По своему характеру ограничения под­разделяются на основные, дополнительные и вспомогательные.

К основным ограничениям относятся такие ограничения, которые накладываются на все или большинство переменных и выражают главные, наиболее существенные условия задачи (по использованию производственных ресурсов).

Дополнительные ограничения накладываются на отдельные пере­менные или на небольшие группы их. Обычно они формулируются в виде неравенств, ограничивающих «снизу» или «сверху» объемы про­изводства отдельных видов продукции, потребление животными от­дельных видов или групп кормов и т.д. Особенно важно не перенасы­щать модель дополнительными переменными, не сокращать степень свободы системы, иначе решение задачи сведется к арифметическим вычислениям заранее предрешенного результата.
Вспомогательные ограничения не имеют самостоятельного эко­номического значения. Их используют главным образом для обеспе­чения правильной формулировки экономических требований (опре­деление вспомогательных переменных).

Ограничения матрицы модели могут иметь разные единицы из­мерения (площадь посева — га, трудовые ресурсы — чел.-дн.), причем размерность каждого ограничения определяется единицей измерения его правой части. Развернутую числовую ЭММ можно рассмотреть на примере.

Составить план сочетания посевных площадей трех культур при условии, что объем земельных ресурсов не должен превышать 900 га, а объем трудовых ресурсов — 5000 чел.-дн. При этом необходимо получить максимум произведенной продукции (ВП) в стоимостном выра­жении.

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования,
• задачи нелинейного программирования .

Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования .

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти при условиях

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме

Математическое программирование

Лекция 1,2.

Профессиональный отбор

Профессиональный отбор – комплекс мероприятий, направленных на выявление лиц, наиболее пригодных к обучению и последующей трудовой деятельности по своим моральным, психофизиологическим и психологическим качествам, уровню необходимых знаний и навыков, состоянию здоровья и физического развития. Профессиональный отбор предусматривает оценку у конкретного индивидуума состояния здоровья, физического развития, уровня общеобразовательной подготовки, социальных, профессиональных способностей.

Профессиональный отбор осуществляется путем проведения медицинского, психологического, образовательного и социального отборов.

Медицинский отбор направлен на выявление лиц, которые по состоянию здоровья и физического развития могут успешно овладеть профессией и в течение длительного времени эффективно выполнять профессиональные обязанности.

Психологический отбор специалистов основывается на изучении состояния, степени развития, совокупности тех психических и психофизиологических качеств личности кандидатов, которые определяются требованиями конкретных профессий и специальностей и способствуют успешному их овладению и последующей эффективной рабочей деятельности.

Образовательный отбор (изучение уровня подготовленности) предусматривает выявление у кандидатов необходимых знаний и навыков, профессионального опыта для обучения, освоения и совершенствования по избранной профессии.

Социальный отбор. Его цель – оценка моральных качеств, некоторых социально-демографических характеристик, организаторских способностей, общественной активности, мотивов выбора профессии, устойчивости к воздействию социальных факторов профессиональной деятельности.

Понятие об оптимизационных задачах. Задача линейного программирования (ЗЛП). Графический метод решения ЗЛП.

Вопросы:

1. Предмет – математическое программирование, краткая классификация методов.

2. Основные понятия теории оптимизации.

3. Постановка ЗЛП, различные формы записи. Примеры экономических задач.

4. Графический метод решения ЗЛП. Основные свойства ЗЛП.

1. Предмет – математическое программирование.

Среди многочисленных проблем, возникновение которых связано с бурно развивающейся научно-технической революцией, пожалуй, наиболее важной является проблема совершенствования управления во всех звеньях хозяйства.

Современные промышленные предприятия, предприятия бытового обслуживания, транспортные агентства, научно-технические организации представляют собой сложные системы «человек-машина». Эффективность работы таких систем зависит от качества организационного управления. Чтобы добиться качества современному руководителю не всегда бывает достаточно личного опыта, интуиции и организаторских способностей в их традиционном понимании. При формировании стратегических и тактических решений руководитель должен учитывать множество подчас противоречивых соображений, опираться на сложные критерии эффективности путей достижения конечных целей. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием – математическое программирование.

Математическое программирование – область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функций многих переменных с ограничениями на область изменения этих переменных.

Для того, чтобы успешно руководить крупным предприятием в условиях конкуренции руководителю, возможно, и не надо быть самому классным специалистом в области математического программирования, но чтобы понимать суть и смысл решаемой задачи, получаемых результатов и не «упустить руль», он должен понимать способ решения, быстро реагировать на возникающие изменения, чтобы эффективно использовать возможности математического программирования. Математическое программирование в настоящее время используется практически во всех областях жизни и производства:

— в экономике – для решения больших макроэкономических моделей (типа модели Леонтьева и др.), микроэкономических моделей или моделей предпринимательства, для оптимизации технико-экономических систем (планирование, эконометрика), транспортные задачи, в теории принятия решений, теории игр и т.п.;

— в технике – управление размерами и оптимизация структур, оптимальное планирование сложных технических систем, как информационные системы, сети компьютеров, транспортные и телекоммуникационные сети и др.;

— в автоматике – распознавание систем и объектов, оптимальное управление системами, фильтрация, роботы, автоматизированные линии и т.п.;

— в медицине, политике, социологии и т.п., и т.д.

Дадим ряд определений.

— Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности.

— Экономические возможности формализуются в виде системы ограничений.

Все это составляет математическую модель. Математическая модель – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д. Модель задачи математического программирования включает:

— совокупность неизвестных величин х = (х₁, х₂, …, х_n), действуя на которые систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, стратегией, поведением и т.п.);

— целевую функцию, которая позволяет выбрать наилучший вариант из множества возможных. Целевая функция обозначается F(x). Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности и т.д.;

— условия (система ограничений), налагаемые на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений.

Т.о., модель задачи математического программирования примет вид:

Найти план х = (х₁, х₂, …, х_n), доставляющий экстремальное значение целевой функции F(x)→ max(min), при ограничениях g_i(x) ≤ (=, ≥) b_i, i=.

Из экономических или физических соображений на план задачи или некоторые его компоненты, как правило, налагаются условия неотрицательности, х_j≥ 0, иногда – целочисленности.

План х, удовлетворяющий системе ограничений задачи, называют допустимым. Допустимый план, доставляющий целевой функции экстремальное значение, называют оптимальным.Оптимальный план обозначают х*, экстремальное значение функции F(x*) = F*.

В зависимости от особенностей целевой функции F(x) и функций ограничений g_i(x), задачи математического программирования делятся на ряд типов.

1. Задача линейного программирования (ЗЛП) – задача оптимизации линейной функции при линейных ограничениях.

2. Задача нелинейного программирования (ЗНП) – задача оптимизации нелинейной функции при ограничениях или без них (когда или F(x) и/или g_i(x) нелинейны).

3. Задача дискретного (в частности целочисленного) программирования – Задача оптимизации, в которой на переменные наложено дополнительное требование принимать лишь дискретные (в частности целочисленные) значения.

4. Задача динамического программирования – задача оптимизации динамических систем (т.е. развивающихся с течением времени).

5. Задача вероятностного или стохастического программирования – задача оптимизации, содержащая случайные величины.

Понятие математического программирования. Классификация задач математического программирования

Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

· задачи линейного программирования,

· задачи нелинейного программирования;

· задачи динамического программирования.

Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования.

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин «линейное программирование» возник в результате неточного перевода английского «linearprogramming». Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского «linearprogramming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

Графический метод решения задачи ЛП;

Решение задачи ЛП средствами табличного процессора Excel;

В большинстве инженерных задач построение математической модели не удается свести к задаче линейного программирования.

Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования – это задачи нелинейного программирования (НП).

Метод множителей Лагранжа позволяет отыскивать максимум (или минимум) функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа.

Динамическое программирование представляет собой математические аппарат, позволяющий быстро находить оптимальное решение в случаях, когда анализируемая ситуация не содержит факторов неопределенности, но имеется большое количество вариантов поведения, приносящих различные результаты, среди которых необходимо выбрать наилучший. Динамическое программирование подходит к решению некоторого класса задач путем разложения на части, небольшие и менее сложные задачи. В принципе, задачи такого рода могут быть решены путем перебора всех возможных вариантов и выбора среди них наилучшего, однако часто такой перебор весьма затруднен. В этих случаях процесс принятия оптимального решения может быть разбит на шаги (этапы) и исследован с помощью метода динамического программирования.

Решение задач методами динамического программирования проводится на основе сформулированного Р.Э.Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

Таким образом, планирование каждого шага должно проводится с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.

Вместе с тем динамическое программирование не является универсальным методом решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации.

Динамическое программирование применяется для решения таких задач, как: распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом и запасами; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети и т.д.

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результатWk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

Все решения задачи разбиваются на два этапа. На первом этапе, который называют условной оптимизацией, отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего.

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, производится второй этап решения задачи, который называется безусловной оптимизацией.

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

Особенности математической модели динамического программирования заключаются в следующем:

задача оптимизации формулируется как конечный многошаговый процесс управления;

целевая функция является аддитивной и равна сумме целевых функций каждого шага

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

где максимум ищется по всем возможным значениям Xn.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Математическое программирование

Математическое программирование

Математическое программирование — математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

Формально, задача математического программирования формулируется так:

Найти

В зависимости от природы множества X задачи математического программирования классифицируются как:

Кроме того, разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование. Математическое программирование используется при решении оптимизационных задач исследования операций.

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• Определение границ системы оптимизации
  • Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
• Выбор управляемых переменных
  • «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
• Определение ограничений на управляемые переменные
  • … (равенства иили неравенства)
• Выбор числового критерия оптимизации
  • Создаём целевую функцию

История

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин «линейное программирование» был предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование «Математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий.

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Л. В. Канторовичем совместно с М. К. Гавуриным в 1949 г разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных ученых. В 1941 г. Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна (англ.), А. Таккера (англ.), Гасса (Gass S. I.), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 г была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.

Начиная с 1955 г опубликовано много работ, посвященных квадратическому программированию (работы Била, Э. Баранкина (Barankin E.) и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Г. Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.