Общая задача оптимизации

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

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

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

В общем виде математическая постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х1, х2, …, хn) при условиях gi (х1, х2, …, хn) bi; (i =1,2,…m), где f и gi; - заданные функции, а bi — некоторые действительные числа.

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

В общем виде задача линейного программирования (ЗЛП) ставится следующим образом:

Найти вектор, максимизирующий линейную форму.

(1).

и удовлетворяющий условиям.

(2).

(3).

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

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

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

.

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

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

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

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):

В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.

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

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

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

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

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

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

Общая задача и основные понятия линейного программирования Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

математические модели очень большого числа экономических задач линейны относительно искомых переменных;

эти типы задач в настоящее время наиболее изучены;

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

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

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

Отметим, что, оптимальное решение в задаче линейного программирования, вообще говоря, не обязательно существует, возможны следующие случаи:

Оптимального решения не существует;

Существует единственное оптимальное решение;

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