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

скачать (4801.3 kb.)

  1   2   3   4   5   6   7   8   9   ...   13
Лекция 1, 2

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

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

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

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

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


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


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

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

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

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

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

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

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

Найти план х = (х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. Основные понятия теории оптимизации


Говорят, что функция F(x) имеет в т. х*(х12, … , хn) локальный максимум (минимум), если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F(x) ? F(x*) (F(x) ? F(x*)).

Необходимое условие экстремума: чтобы F(x) имела в т. х* экстремум необходимо, чтобы ?F(x*)/?xj = 0, .

Достаточное условие экстремума: если F(x) в т. х* имеет ?F(x*)/?xj = 0, , то чтобы в этой точке F(x) имела экстремум достаточно, чтобы квадратичная форма

была положительно (минимум) или отрицательно (максимум) определена.

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

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

Функция F(x), определенная на выпуклом множестве S, выпукла, если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:

Функция F(x), определенная на выпуклом множестве S, вогнута, если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:

Теорема 1: пересечение выпуклых множеств является выпуклым множеством.

Теорема 2: сумма выпуклых функций является выпуклой функцией, сумма вогнутых функций - вогнутой функцией.

Теорема 3 (основное свойство выпуклых задач):

Всякий локальный оптимум является глобальным.

Теорема Вейерштрасса:

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

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

При численных расчетах часто необходимо использовать еще два важных понятия.

Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции grad F(x) = (?F/?x1, … ,?F/?xn). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.

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


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


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

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

Рассмотрим постановку ЗЛП на примере задачи и наилучшем использовании ресурсов. Имеется m видов ресурсов в ограниченном количестве b = (b1, b2, … , bm). Ресурсы используются предприятием для выпуска n видов продукции. Известна экономическая выгода производства каждого вида продукции, исчисляемая, например, ценой реализации С = (С1, С2, … , Сn). Известны технологические коэффициенты аij, соответствующие количеству i-го вида ресурса, необходимого для производства единицы j -го вида продукции - А = ( аij ). Необходимо составить план производства х = (х12, … , хn), приносящий предприятию максимальную прибыль.

В общем виде математическую модель задачи (ЗЛП) можно записать следующим образом:
F(x) = C1x1 + C2x2 + … + Cnxn ? max

a11x1 + a12x2 + … + a1nxn ? b1, xj ? 0, j= 21x1 + a22x2 + … + a2nxn ? b2,

… … … … m1x1 + am2x2 + … + amnxn ? bm.
Рассмотрим задачу о диете. Необходимо составить диету (рацион), содержащую определенные питательные вещества. Имеем n видов продуктов, каждый из которых сожержит необходимые m видов питательных веществ. Единица j-го продукта содержит аij единиц i-го питательного вещества. Для нормальной жизнедеятельности необходимо не менее bi единиц i-го вещества. Известна стоимость единицы каждого вида продукта С = (С1, С2, … , Сn). Необходимо составить диету минимальной стоимости.

Математическая модель задачи примет вид:
F(x) = C1x1 + C2x2 + … + Cnxn ? min 11x1 + a12x2 + … + a1nxn ? b1, xj ? 0, j= 21x1 + a22x2 + … + a2nxn ? b2,

… … … … m1x1 + am2x2 + … + amnxn ? bm.
Здесь хj - количество j - го продукта в рационе.

В матричной форме общая ЗЛП выглядит так:

F(x) = CTx ? max (min) ? (=,?) B ; x ? 0.
Кроме того, для записи ЗЛП можно использовать знак суммы:

F(x) = ? max (min)

, .
Рассмотрим задачу о размещении заказа. Имеется m однородных групп оборудования, на котором нужно выполнить заказ на выпуск n видов продукции в объемах х*j, . Мощность оборудования ограничена, например, временем Тi. Производительность оборудования задана коэффициентами аij. Известны коэффициенты затрат Сij - затраты i - го оборудования на производство j - го продукта. Построить план хij размещения заказа (загрузки оборудования). Составим математическую модель задачи.
F(x) = ? min , xij ? 0, j= , ,
по мощности - , ,

по видам продукции, план по которой может быть перевыполнен
, j= ,
по видам продукции, план по которой должен соответствовать заказу

, j= ,
по видам продукции, заказ на которую принимается для более полной загрузки

оборудования
, j= .
  1   2   3   4   5   6   7   8   9   ...   13



Рефераты Практические задания Лекции
Учебный контент

© ref.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации