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

Общая классификация задач оптимального программирования.

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

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

3.По учету факторов времени: а) статистические. Моделирование и принятие решений осуществляются в предположении о независимости от времени элементов модели в течении периода времени, на который принимается управленческое решение, б) динамические. Такое предположение принято не может быть.

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

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

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

По ЭММ Леонтьева (Е-А)X=Y можно определить объемы валовой продукции отрасли Х1, Х2, …, Хn по заданным объемам конечной продукции: Х = (Е-А)‾¹ Y; X=BY, B=(E—A)‾¹. Элементы Bij обратной матрицы B = (E—A)‾¹ называются коэффициентами полных (материальных) затрат, т.е. это затраты i-й отрасли на каждый рубль конечной продукции отрасли j. Соответственно матрицу В называют матрицей коэффициентов полных затрат, а матрицу А – матрицей коэффициентов прямых затрат. Неотрицательную матрицу А (А≥0) называют продуктивной, если существует хотя бы один такой положительный вектор Х>0, что каждый объект может произвести некоторое количество конечной продукции. Для продуктивности матрицы А необходимо и достаточно, что бы выполнялось одно из перспективных условий: 1) матрица (Е-А) неотрицательно обратима, т.е. существует обратная матрица (Е-А)‾¹ и все ее элементы неотрицательны, 2) положительны все главные миноры матрицы (Е – А), 3) матричный ряд

Источник

4. Принцип оптимальности в планировании и управлении.

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

Линейное программирование — это частный раздел оптимального

программирования. В свою очередь оптимальное

(математическое) программирование — раздел прикладной

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

экономике такие задачи возникают при практической реали-

-зации принципа оптимальности в планировании и управлении.

Необходимым условием использования оптимального

подхода к планированию и управлению (принципа оптимальности)

является гибкость, альтернативность производственно-

хозяйственных ситуаций, в условиях которых приходится

принимать планово-управленческие решения. Именно

такие ситуации, как правило, и составляют повседневную

практику хозяйствующего субъекта (выбор производственной

программы, прикрепление к поставщикам, маршрутизация,

раскрой материалов, приготовление смесей и т.д.).

Суть принципа оптимальности состоит в стремлении выбрать

такое планово-управленческое решение X = (Х1, Х2… Хп), где

Хj, (j = 1, п ) — его компоненты, которое наилучшим образом

учитывало бы внутренние возможности и внешние условия

производственной деятельности хозяйствующего субъекта.

Слова «наилучшим образом» здесь означают выбор некоторого

критерия оптимальности, т.е. некоторого экономического

показателя, позволяющего сравнивать эффективность

тех или иных планово-управленческих решений. Традиционные

критерии оптимальности: «максимум прибыли», «минимум

затрат», «максимум рентабельности» и др.

Слова «учитывало бы внутренние возможности и внешние

условия производственной деятельности» означают, что

на выбор планово-управленческого решения (поведения) накладывается

ряд условий, т.е. выбор X осуществляется из

некоторой области возможных (допустимых) решений D;

эту область называют также областью определения задачи.

Таким образом, реализовать на практике принцип оптимальности

в планировании и управлении — это значит решить

экстремальную задачу вида:

Условие (2.5) необязательно, но его всегда при необходимости

можно добиться. Обозначение [> говорит о том,

что в конкретном ограничении возможен один из знаков:

Задача (2.6)-(2.8) — общая задача оптимального (математического)

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

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

построения (разработки) которой лежат принципы оптимальности

Вектор X (набор управляющих переменных Xj, j = 1, п )

называется допустимым решением, или планом задачи оптимального

программирования, если он удовлетворяет системе

ограничений. А тот план X (допустимое решение), который

доставляет максимум или минимум целевой функции

f(Х1, Х2 . хп), называется оптимальным планом (оптимальным

поведением, или просто решением) задачи оптимального

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

в конкретной производственной ситуации связан с

проведением с позиций системности и оптимальности экономико-

математического моделирования и решением задачи

Задачи оптимального программирования в наиболее общем

виде классифицируют по следующим признакам.

1. По х а р а к т е р у в з а и м о с в я з и между

В случае а) все функциональные связи в системе ограничений

и функция цели — линейные функции; наличие нелинейности

хотя бы в одном из упомянутых элементов приводит

2. По х а р а к т е р у и з м е н е н и я п е р е м е н н

В случае а) значения каждой из управляющих переменных

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

чисел; в случае б) все или хотя бы одна переменная

могут принимать только целочисленные значения.

3. По у ч е т у ф а к т о р а в р е м е н и —

В задачах а) моделирование и принятие решений осуществляются

в предположении о независимости от времени

элементов модели в течение периода времени, на который

принимаетсяпланово-управленческое решение. В случае б)

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

не может быть и необходимо учитывать фактор времени.

4. По н а л и ч и ю и н ф о р м а ц и и о п е р е м е н н

а) задачи в условиях полной определенности (детерминированные),

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

В задачах б) отдельные элементы являются вероятностными

величинами, однако известны или дополнительными

статистическими исследованиями могут быть установлены

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

о возможных исходах случайных элементов, но

нет возможности сделать вывод о вероятностях исходов.

5. П о ч и с л у к р и т е р и е в о ц е н к и а л ь т е р на т и в —

а) простые, однокритериальные задачи,

б) сложные, многокритериальные задачи.

В задачах а) экономически приемлемо использование одного

критерия оптимальности или удается специальными

процедурами (например, «взвешиванием приоритетов») свести

многокритериальный поиск к однокритериальному; примеры

многокритериальных задач рассмотрены в гл. 3.

Сочетание признаков 1—5 позволяет группировать (классифицировать)

в самом общем виде задачи и методы оптимального

программирования, например: 1а)2а)3а)4а)5а) —

задачи и методы линейного программирования, 1б)2а)3а)

4а)5а) — задачи и методы нелинейного программирования,

1а)2б)3а)4а)5а) — задачи и методы целочисленного (дискретного)

линейного программирования и т.д.

Источник

4.Общая запись оптимизационной эмм (задача оптимального программирования). Основные элементы и понятия.

Реализовать на практике принцип оптимальности это значит разработать и получить решение по модели: max(min) максимизировать или минимизировать функцию f(x) при ограничениях, где f(x1,x2,…,xn) – математическая запись критерия оптимальности -ЦФ. Max(min) f(x)=f(x1,x2,…,xn),x є D.

Обычно, приведенную модель записывают в виде:

5.Общая классификация задач оптимального программирования.

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

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

3.По учету факторов времени: а) статистические. Моделирование и принятие решений осуществляются в предположении о независимости от времени элементов модели в течении периода времени, на который принимается управленческое решение, б) динамические. Такое предположение принято не может быть.

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

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

7.Общая задача линейного программирования, основные элементы и понятия.

Реализовать на практике принцип оптимальности это значит разработать и получить решение по модели: max(min) максимизировать или минимизировать функцию f(x) при ограничениях, где f(x1,x2,…,xn) – математическая запись критерия оптимальности -ЦФ. Max(min) f(x)=f(x1,x2,…,xn),x є D.

Обычно, приведенную модель записывают в виде:

9.Графический метод решения задачи линейного программирования.

Если в задаче линейного программирования ограничения заданы в виде неравенств с двумя переменными, то задача может быть решена графически. Графический метод решения ЗЛП состоит из этапов: 1.Стоится многоугольная область допустимых решений ЗЛП. 2.Строится вектор-градиент целевой функции. Начало в т.О(0,0), а вершина в т.(df/dx1; df/dx2)=(C1;C2). 3.Строим линию уровня c1x1+c2x2=a, a=const. Линия уровня это прямая перпендикулярная вектору-градиенту. Передвигаемся в направлении этого вектора. В случае максимизации ЦФ до тех пор, пока не покинет ОДР. Предельная точка ОДР при этом движении и является точкой max ЦФ. 4.Для нахождения координат указанной предельной точки, достаточно решить 2 уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку max. Значение ЦФ найденное в этой точке является max. При минимизации ЦФ линия уровня перемещается в направлении противоположном вектору-градиенту.

Источник