Основы линейного программирования

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

После изучения данной главы студенты должны:

знать

• • общие принципы оптимального планирования и управления в экономике:
• • основные понятия линейного программирования;
• • методы решения задач линейного программирования (ЗЛП);

уметь

• • формулировать общую постановку ЗЛП;
• • представить ЗЛП в различных формах записи;
• • дать экономическую интерпретацию полученных результатов на всех этапах графического и симплексного методов решения ЗЛИ;

владеть

• • математическим аппаратом линейного программирования;
• • практическими навыками формулирования и решения ЗЛП.

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

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

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

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

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

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

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

(2.1).

(2.2)

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

Задачу условной оптимизации (2.1), (2.2) обычно записывают в виде:

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

(2.3).

при ограничениях.

(2.4).

(2.5).

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

(2.6).

(2.7).

(2.8).

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

Вектор (набор управляющих переменных , j= 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а) — задачи и методы целочисленного (дискретного) линейного программирования и т. д.

Новые возможности для широкого практического применения методов оптимального программирования представляют современные офисные средства. Широкий круг специалистов в своей повседневной практике использует необходимый компонент финансово-экономических расчетов — Microsoft Excel (MS Excel), который содержит специальное средство — надстройку Поиск решения, позволяющую реализовывать модели линейной, нелинейной и дискретной оптимизации. Технология оптимизации с помощью надстройки Поиск решения с решением некоторых типовых задач оптимального программирования в среде MS Excel подробно рассмотрена, например, в литературе^[1]•^[2].

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

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

Математическая модель. Введем необходимые обозначения, пусть :

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

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

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

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

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

Именно эти задачи в дальнейшем рассматриваются в данной главе.

• [1] Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. Μ.: Вильямс, 2004.
• [2] Гармаш А. Н., Орлова И. В. Математические методы в управлении: учеб. пособие. М.: Вузовский учебник, 2012.