Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Виды математического программирования

Виды математического программирования

Дата добавления: 2013-12-23 ; просмотров: 3030 ; Нарушение авторских прав

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

В самом общем случае задача нахождения оптимального (максимального или минимального) значения целевой функции может быть записана как:

U=f(X)→ max;X,W,

где X = (x1,x2,…,xn);

W — область допустимых значений переменных x1,x2,…,xn;

f(X) — целевая функция.

Для того чтобы решить эту оптимизационную задачу, достаточно указать XОW такое, что f(X) ≥f(X) при любом XОW, f(X) ≤f(X)при любом XОW. Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функциейn переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

· задачи линейного программирования, если f(X) и W линейны;

· задачи целочисленного программирования, если ставится условие целочисленности переменных x1,x2,…,xn;

· задачи нелинейного программирования, если f(X) или W имеют нелинейный характер.

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

W=f(x1,x2. xn)→ max.

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

Идея метода штрафных функций в том, что вместо наложения системы ограничений, налагается некоторый достаточно большой «штраф» за нарушение ограничений, который добавляется к целевой функции W. Штраф имеет общий вид: a(x1,x2. xn), где a — коэффициент пропорциональности (если W максимизируется он отрицателен, если минимизируется — положителен). Далее можно, увеличивая абсолютное значение a, посмотреть, как изменяется при этом оптимальное решение (x1°,x2°. xn°)и, когда оно практически перестанет меняться, остановиться на нем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 1,2.

Читать еще:  Основные термины программирования

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

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

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

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

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

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

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

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

Вопросы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найти план х = (х1, х2, …, хn), доставляющий экстремальное значение целевой функции F(x)max(min), при ограничениях gi(x) ≤ (=, ≥) bi, i=.

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Современные системы программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Дана задача линейного программирования

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

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

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых переменных, определяющих данную задачу. Примерами таких переменных являются: численность исполнителей, станков, машин и др. Число переменных (обозначим их X1, X2. Хn, где n — число переменных) характеризует степень сложности задачи оптимизации.

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

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

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

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

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

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

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

1.2. Общая задача математического программирования.

Сформулируем общую задачу математического программирования.

Дадим количественную, математическую постановку этой задачи.

Найти значения «n» переменных X1, X2. Хn , которые неотрицательны

Xi 0, i=1,2,…,n

удовлетворяют «m» ограничениям:

и максимизируют функцию:

Z=F(X1,X2,…,Xn) MAX

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

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

В основе той или иной классификации лежит признак, по которому объекты разделяются или объединяются в классы.

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

Если функция цели и ограничения являются линейными:

Z=F(X1,X2,…,Xn)=C1X1+C2X2+…CnXn MAX;

где (Ci),(Bj),(Aij) — известные постоянные, то данная задача является задачей линейного программирования.

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

Частным случаем задач нелинейного программирования являются задачи целочисленного программирования. От задач линейного программирования они отличаются только наличием условия целочисленности переменных X1, X2. Хn.

Если целевая функция задачи математического программирования квадратичная, но все её ограничения линейны, то такую задачу называют задачей квадратичного программирования. Линейные ограниче­ния, для данной задачи записываются так же как для задачи линейного программирования, а целевая функция имеет вид:

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

Z=F(X1,X2)=X1*X2 MAX;

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

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

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

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

— задача управления запасами;

— задачи замены оборудования;

— задача выбора оптимальных режимов движения;

— задача выбора оптимальной структуры.

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

Примерами распределительных задач являются:

транспортная задача, в которой рассматривается вопрос об оптимальном прикреплении пунктов производства и пунктам потребления;

задача о назначении, в которой рассматривается вопрос об опти­мальном прикреплении производителя работ к объекту производст­ва;

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

задача o выборе рациона;

задача выбора применения ресурсов;

задача выбора типажа и другие задачи.

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

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

Задача замены оборудования — состоит в решении вопроса: продолжить производить или эксплуатировать старое оборудование или же заменить его новым, более совершенным, т.е. решается вопрос построения оптимального плана технического переоснащения производ­ства.

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

Задача поиска сводится к отысканию оптимального плана поиска объектов. Например: объектов противника, неисправностей, брака, полезных ископаемых и др.

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

Ссылка на основную публикацию
Adblock
detector