• Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования

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

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

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

такое планово-управленческое решение X = хп), где

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

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

Слова «учитывало бы внутренние возможности и внешние условия производственной деятельности» означают, что на выбор планово-управленческого решения (поведения) накладывается ряд условий, т.е. выбор X осуществляется из некоторой области возможных (допустимых) решений D; эту область называют также областью определения задачи.

Таким образом, реализовать на практике принцип оптимальности в планировании и управлении — это значит решить экстремальную задачу вида:

max(min)/(x), (2.1)

XeD, (2.2)

где f{x) — математическая запись критерия оптимальности — целевая функция.

Найти максимум или минимум функции

_ (2.3)

/(х) = f(xь х2, ..., хп)

при ограничениях } Ьъ

ФгОсь х2, ...,:<;„){<,=,>}Ь2. (2.4)

Фт(*Ъ*2. ...,хп) {<,=,>} Ът,

Xj>0,j=l,n. (2.5)

Условие (2.5) необязательно, но его всегда при необходимости можно добиться. Обозначение {<,=,>} говорит о том,

что в конкретном ограничении возможен один из знаков: <,= или >. Более компактная запись:

(2.6)

max(min)/Yхи х2,хп),

(2.7)

(2.8)

Фі(*ь х2, хп) {<,=,>}&*, і = 1, тп , Xj> 0, і = 1, п.

Задача (2.6)-(2.8) — общая задача оптимального (математического) программирования, иначе — математическая модель задачи оптимального программирования, в основе построения (разработки) которой лежат принципы оптимальности и системности.

Вектор X (набор управляющих переменных Xj, j = 1, п ) называется допустимым решением, или планом задачи оптимального программирования, если он удовлетворяет системе ограничений. А тот план X (допустимое решение), который доставляет максимум или минимум целевой функции f(x\, х2г ..., хп), называется оптимальным планом (оптимальным поведением, или просто решением) задачи оптимального программирования.

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

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

По характеру взаимосвязи между переменными —

а) линейные,

б) нелинейные.

В случае а) все функциональные связи в системе ограничений и функция цели — линейные функции; наличие нелинейности хотя бы в одном из упомянутых элементов приводит к случаю б). 2.

По характеру изменения переменных —

а) непрерывные,

б) дискретные.

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

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

а) статические,

б) динамические.

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

По наличию информации о переменных —

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

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

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

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

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

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

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

В задачах а) экономически приемлемо использование одного критерия оптимальности или удается специальными процедурами (например, «взвешиванием приоритетов») свести многокритериальный поиск к однокритериальному; примеры многокритериальных задач рассмотрены в гл. 3.

Сочетание признаков 1—5 позволяет группировать (классифицировать) в самом общем виде задачи и методы оптимального программирования, например: 1а)2а)3а)4а)5а) — задачи и методы линейного программирования, 1б)2а)3а) 4а)5а) — задачи и методы нелинейного программирования, 1а)2б)3а)4а)5а) — задачи и методы целочисленного (дискретного) линейного программирования и т.д.

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

Постановка задачи. Предлагается п инвестиционных проектов Pi, Р2, - ..,Pj, ... Рп> тщательная экономическая проработка которых позволяет получить для каждого из проектов Pj достаточно убедительные экономические оценки ожидаемого эффекта от его реализации Cj и необходимой величины капиталовложений gj. Общий объем возможных инвестиций ограничен величиной G. Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций.

Математическая запись задачи (модель).

х _ jl' если проект Pj следует инвестировать, 1 [о, если не следует.

С учетом этих обозначений задача по критерию «максимум экономического эффекта» математически запишется следующим образом:

п

max f(xux2, ...,хп) =Y^Cixi '

п

7=1

Xj є {0;l}; 7 = ій. J

Приведенная задача является задачей дискретного линейного программирования с булевыми переменными (переменные, которые могут принимать только два значения: 1 и О, т.е. «да» или «нет»), т.е. относится к классу задач 1а)2б)3а)4а)5а). Эта задача может быть решена, например, известным методом Балаша.

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

Развитие и совершенствование методов решения задач оптимального программирования идет от случаев типа а) к случаям типа б), в).

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