Тема 2

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

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

2. Экономическое содержание симплекс-метода линейного программирования. (см. практика)

3. Теория двойственности в анализе оптимальных решений экономических задач. (см. практика)

4. Метод потенциалов в решении распределительных задач. Транспортная задача. (см. практика)

- 1 -

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

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

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

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

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

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

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

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

В зависимости от числа критериев оценки альтернатив рассматривают простые, однокритериальные задачи и сложные, многокритериальные задачи.

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

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

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

Найти максимальное (минимальное) значение линейной целевой функции:

F(X)=ΣС_jX_j→max(min) jЄ(1,n)

при условиях-ограничениях:

ΣA_ijX_j ≤(≥) B_i iЄ(1,k)

ΣA_ijX_j = B_i iЄ(k+1,m) k≤m

X_j ≥ 0 jЄ(1,l) l≤n

С_j , A_ij , B_i -заданные постоянные величины.

В частности: С_j – коэффициенты целевой функции, характеризуют экономическую эффективность функционирования отрасли, вида деятельности; A_ij – коэффициенты в системе ограничений, означают нормативы затрат ресурсов, выхода продукции на 1 отрасли, вида деятельности; B_i - объем ограничений, означают наличие производственных ресурсов, планируемые объемы производства или реализации продукции; X_j – размеры отрасли, вида деятельности, которые нужно определить в результате решения задачи.

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

Ограничения обычно выражают определенные зависимости между переменными величинами, которые по своей сути могут быть теоретическими и статистическими. Теоретические зависимости справедливы при любых условиях и для их получения не требуется никаких дополнительных измерений. Если нет известной функциональной зависимости, необходимы статистические данные, чтобы получить определенную аналитическую зависимость, которая и будет ограничением в задаче оптимизации. Обозначение ≤(≥) говорит о том, что в конкретном ограничении возможен один из знаков: ≤ или ≥ . Условие неотрицательности переменных Х необязательно, его всегда при необходимости можно добиться.

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

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

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

Таблица. Классификация задач оптимизации процессов и принятия решений.

Область применения	Управление	Проектирование	Разработка технологических процессов
Производство Образование Культура Бизнес Экономика Финансы Искусство Бытовая сфера Принятие решений	Различные задачи распределения ресурсов (материальных, финансовых, информационных, трудовых)	Оптимизация параметров объекта проектирования Оптимизация структуры объекта проектирования Оптимизация функционирования объекта проектирования	Оптимизация маршрута изготовления изделия Оптимизация параметров технологических процессов Выбор режима работы, обеспечения качества и эффективности

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

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

- 2 -

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

Исходная ЗЛП:

max(min)F(X)=Σс_jх_j при ограничениях Σа_ijх_j (≤= ≥ ) в_i х_j ≥ 0

Матричная форма записи ЗЛП:

max(min)F(x)=CX при условиях АХ(≤ ≥) В, X ≥ 0.

C — вектор-строка; А — матрица размерности т х п, Х, В - вектор-столбцы.

Сначала ЗЛП приводится к каноническому виду. Система неравенств приводится к системе уравнений введением в левую часть соответствующего ограничения дополнительной переменной х_к >0 со знаком «-» в случае ограничения типа «≥»и знаком «+» в случае ограничения типа «≤». В преобразованной задаче все переменные неотрицательные.

Реализация симплекс-метода включает следующие элементы:

1. Определение первоначального допустимого базисного решения задачи;

2. Критерий проверки оптимальности найденного решения;

3. Правила перехода к лучшему решению.

Существует две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом. Для применения этого метода ЗЛП должна быть сформулирована в канонической форме, причем матрица системы уравнений должна содержать единичную подматрицу размерностью тхn. Например, первые т векторов матрицы системы составляют единичную матрицу. В этом случае очевиден начальный опорный план (неотрицательное базисное решение).

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

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

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

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

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

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

- 3 –

См. практическое занятие

- 4 –

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

Рассмотрим транспортную задачу по критерию стоимости, которую можно сформулировать следующим образом: В m пунктах А₁, А₂ ..А_m, которые называются поставщиками, сосредоточено определенное количество единиц однородного продукта. Данный продукт потребляется в n пунктах B₁, B₂, ..B_n, которые называются потребителями. Известны расходы на перевозку единицы продукта из пункта A в пункт B, которые равны C_ij и приведены в матрице транспортных расходов. Требуется составить план прикрепления потребителей к поставщикам, т.е. план поставок продукции от поставщиков потребителям, при котором общая величина транспортных издержек будет минимальной. Математический вид задачи:

Условия задачи означают полное удовлетворение спроса во всех пунктах потребления и определяют полный вывоз продукции от всех поставщиков.

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

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

Наиболее применяемым методом решения закрытой транспортной задачи является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал U_i, который можно интерпретировать как цену продукта в пункте поставщика, а каждому j-му столбцу (j-му потребителю) устанавливается потенциал V_j, который можно принять условно за цену продукта в пункте потребителя.

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

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

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