Экономические методы и модели

     Любая оптимизационная экономико-математическая модель задачи ЛП включает в себя 3 составные части:

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

      Математическая  модель общей задачи ЛП формулируется таким образом: необходимо найти максимум или минимум целевой функции

      Z=p₁x₁+p₂x₂+…+ p_nx_n (≥, ≤, =) max (min), (2.1)

при наличии  ограничений в виде системы неравенств или (и) уравнений

      a_i1x₁+a_i2x₂+…+ a_inx_n (≥, ≤, =) b_i (i=1…m), (2.2)

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

x_j≥0 (i=1…n). (2.3)

      Соотношение количества переменных n и ограничений m может быть произвольным.

     В приведенных формулах обозначено: p_i, a_ij, b_i (i=1…m, j=1…n) – известные постоянные коэффициенты; x_j – переменные, которые подлежат определению; значок (≥, ≤, =) показывает, что может использоваться тот или другой вид ограничения неравенств или равенств.

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

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

     Требование  неотрицательности переменных (2.3) отвечает их реальному экономическому смыслу и приводит к тому, что никакое допустимое решение, в том числе и оптимальное, не должно включать неотрицательных компонент.

     Задача  ЛП (2.1)…(2.3) может иметь и более  компактные формы записи.

     С использованием знака суммирования задачу ЛП можно записать так:

     

(2.4)

     

 (2.5)

     

 (2.6)

      Задачу  ЛП можно представить в матричной  форме, если ввести обозначения:

     P=( p₁, p₂, … p_n) – матрица-строка коэффициентов целевой функции;

- матрица коэффициентов  системы ограничений;

- матрица-столбец  правых частей ограничений;

- матрица-столбец  переменных.

      Тогда задача (2.1)…(2.3) может быть записана в таком матричном виде:

(2.7)

(2.8)

(2.9)

     Ограничения-неравенства (2.2), (2.5), (2.8) можно записать также  в виде уравнений, если ввести дополнительные переменные. Так, например, если ограничение-неравенство имеет знак (≤), то его можно превратить в уравнение (=) добавлением к левой части дополнительной неотрицательности переменной х_n+1, которая войдет в целевую функцию с нулевым коэффициентом; если ограничение-неравенство имеет знак (≥), то оно превращается в уравнение (=) вычитанием  из левой части дополнительной переменной х_n+1. В результате ограничения задачи сведутся к системе линейных алгебраических уравнений, которые включают, кроме основных переменных x_j≥0 (i=1…n), дополнительные переменные х_n+1, х_n+2, …, х_n+m. Такая форма записи задачи ЛП называется канонической, и она будет эквивалентной к общей задаче ЛП.

     Каноническая  форма задачи ЛП имеет такие недостатки: приводит к увеличению числа переменных за счет введения их дополнительных величин; для  практических задач большой размерности наличие значительного количества дополнительных переменных наряду с основными требует значительного объема оперативной памяти ПК; вычислительные операции с элементами системы ограничений большого размера могут привести к погрешностям в определении переменных и целевой функции из-за появления малых разностей близких величин.  

     2.2 Примеры задач ЛП и сформированных  на их основе оптимизационных  моделей 

     Задача  оптимального использования  ресурсов (оптимального планирования)

     Номенклатура  продукции, которая выпускается  предприятием, состоит из n наименований. Для их производства нужно m видов ресурсов, запасы которых ограниченны. Расходы i-го вида ресурсов на единицу вида продукции составляют a_ij(i=1…m, j=1…n). Запасы i-го вида ресурсов есть b₁. Прибыль от реализации единицы j-го изделия соответствует p_j.  Нужно составить такой оптимальный план выпуска продукции каждого вида x_j, при котором предприятие получает наибольшую прибыль.

     Экономико-математическая модель будет иметь такой вид: выполнить оптимальный план выпуска продукции Х=( x_j), по реализации которой предприятие получит наибольшую прибыль, которая характеризуется целевой функцией:

      , при ограничениях на наличие  ресурсов и условиях неотрицательности переменных  

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

     На  n предприятиях отрасли (в цехах одного завода) выпускается однородная продукция, для которой имеется m запасов ресурсов. Расходы i-го ресурса (i=1…m) на j-м предприятии или цехе (j=1…n) в единицу времени составляют a_ij. Нужно составить такое оптимальный план выпуска каждого вида продукции x_j, по которому каждое предприятие (цех) обеспечило бы максимальный объем выпуска продукции. Экономико-математическая модель имеет вид: целевая функция Z будет отвечать объему продукции, которой нужно максимизировать; каждое неравенство системы ограничений характеризует запасы ресурсов, которые при этом должны быть использованы.  

     Задача  оптимального использования мощностей

     Предприятию задан план по времени и номенклатуре выпуска изделий: необходимо за отведенный срок времени (час, день, и т.п.) выпустить  b_j  единиц продукции вида j=1…n; продукция изготавливается m станках, производительность которых заданно технологическими коэффициентами a_ij(i=1…m, j=1…n). Известны коэффициенты b_ij, которые отражают все расходы по изготовлению продукции вида j на i-м станке в единицу времени. Необходимо составить оптимальный план работы станков, чтобы расходы на производство продукции были минимальными.

     Экономико-математическая модель задачи будет такой: целевая  функция выражает минимальные расходы  на производство все продукции при  затратах времени х_ij каждого i-го станка на производство j-й продукции:

     

ограничения по времени 

ограничения по номенклатуре изделий 

условия неотрицательности  переменных: х_ij  ≥0 (i=1…m, j=1…n). 

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

     Предприятие получило полуфабрикаты в виде m, разных как по количеству единиц b_j (i=1…m), так и по размерам партий. В каждой партии полуфабрикат только одного размера. Этот полуфабрикат необходимо раскроить на необходимые заготовки, чтобы максимизировать общее количество полных комплектов заготовок.

     Известно, что в один комплект заготовок  s-го вида входит К_s штук полуфабрикатов (s=1…l). Каждую единицу полуфабриката можно раскроить на заготовки n разными способами, причем в раскрои единицы i-ой партии j-м способом (j=1…n) можно получить a_ijs  заготовок s-го вида.

     Обозначим через х_ij количество заготовок из i-ой партии полуфабрикатов, которые запланировано раскроить j-м способом, так что из i-ой партии при j-м способе раскроя будет изготовлено a_ijs х_ij заготовок s-го вида; y – количество полных комплектов заготовок.

     Тогда экономико-математическая модель оптимального раскроя материала запишется  в виде максимизации количества полных комплектов заготовок, что выражается целевой функцией Z=y→max при ограничениях: по количеству заготовок для составления числа комплектов:

     

по количеству заготовок в i-ой партии полуфабрикатов по условиям неотрицательности y≥0; x_ij≥0 (i=1…m, j=1…n). 

     Транспортная  задача

     Известно, что есть m поставщиков A₁, A₂, … A_m однородного груза в количестве соответственно a₁, a₂, … a_m единиц  и n потребителей груза B₁, B₂, …B_n которым нужно b₁, b₂, …b_n единиц этого груза. Стоимость перевозок единицы груза от i-го поставщика (i=1…m) к j-му потребителю (j=1…n) составляет c_ij.

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

     Обозначим через х_ij количество единиц груза, который перевозит от i-го поставщика к j-му потребителю.

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

     

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

при ограничениях на переменные: весь груз от поставщиков  должен быть вывезен

спрос потребителей в грузах должен быть удовлетворен

Требуется неотрицательность  переменных x_ij≥0 (i=1…m, j=1…n). 
 

2.8 Некоторые  нелинейные методы решения оптимизационных  задач 

     Общая характеристика нелинейных методов  оптимизации 

     К нелинейным методам получения оптимизационных  решений, которые находят применение в экономической практике, относятся:

     а) классические методы оптимизации типа метода множителей Лагранжа;

     б) выпуклое программирование;

     в) динамическое программирование и др.

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

     В общем случае нелинейная экономико-математическая модель может быть рассмотрена как  задача нелинейного программирования (НП) в виде:

     

 (2.7)

где , - нелинейные зависимости для целевой функции и ограничений.

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

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

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