Какие задачи называются задачами математического программирования

1.5. Типы задач математического программирования

Существует множество подходов к оптимизации управленческих решений в зависимости от того, какова процедура управления – многошаговая или «статическая», каковы условия функционирования объекта – в условиях определенности или неопределенности, сколько критериев выбрано для оценки решений – один или несколько, каков показатель эффективности – количественный или качественный. Соответственно и класс оптимизационных задач крайне разнообразен как по типу моделей, так и по применяемому для их решения математическому аппарату [1, 2, 4, 5, 10, 11]. Мы ограничимся классом управленческих ситуаций, протекающих в условиях определенности, когда в качестве показателя эффективности используется один количественный критерий. Такие задачи принято классифицировать по виду критерия оптимальности и типу ограничений, накладываемых на переменные решения. Если в задаче оптимизации критерий оптимальности единственный и его можно записать в виде целевой функции Z = f (x 1 , x 2 . x n ) , оп- ределенной на заданном множестве допустимых решений, то такие задачи называют задачами математического программирования. Методы решения задач математического программирования во многом зависят и определяются видом целевой функции и системы ограничений. • Задачи, в которых целевая функция линейна, т.е. имеет вид Z = c 1 x 1 + c 2 x 2 + . + c n x n , а система ограничений состоит из неравенств или равенств, также линейных относительно переменных решения x 1 , x 2 , K x n a i1 x 1 + a i2 x 2 +K+ a in x n ( = , ≥ , ≤ )b i , i=1,2,…m, называют задачами линейного программирования . • Задачи линейного программирования, в которых на переменные x 1 , x 2 , K x n дополнительно накладывают требования целочислен- ности (когда все переменные должны быть целыми числами), на- зывают задачами целочисленного программирования . Подобные ограничения часто возникают, например, при выборе оптимального плана перевозок, когда количество транспортных средств не может не быть целым числом, при оптимизации производственной программы выпуска штучных изделий и.т.д.

• Если целевая функция не является линейной относительно переменных x 1 , x 2 , K x n , то независимо от типа ограничений такой класс задач называют задачами нелинейного программирования . Среди перечисленных задач особое место занимают задачи линейного программирования. Во-первых, они достаточно просты. Вовторых, с их помощью удается описать большое число реальных экономических ситуаций. В силу этих обстоятельств они получили большое распространение и сегодня относятся к числу наиболее востребованных при моделировании и оптимизации управленческих решений.

1. Определение задачи математического программирования

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

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

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

Классическая задача математического программирования – задача выбора таких значений некоторых переменных, подчиненных системе ограничений в форме равенств, при которых достигается max или min функции.

2. Допустимое решение задачи, одр, оптимальное решение задачи.

Допустимым решением задачи называется любой n-мерный вектор

x (x = (,,…,)), удовлетворяющий системе ограничений и условию неотрицательности.

Множество допустимых решений образует ОДР.

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

3. Экономико–математические модели задач лп: задача о банке

К экономико-математическим моделям задач ЛП относятся:Задача планирования производства, определения оптимального ассортимента продукции, о диете, о банке, составления жидких смесей, Транспортная задача

Построение экономико – математической модели.

Задача о банке

Собственные средства банка в сумме с депозитами составляют 100 млн. $. Не менее 35 млн. $ из этой суммы размещена в кредитах (не ликвид). Ликвидное ограничение ценных бумаг должны составлять не менее 30 %, размещенных в кредитах и ликвидных активах.

Пусть — средства, размещенные в кредитах,– средства, размещенные в ликвидных активах.

Банк. Огран. (1)

Кред. Огран.

Ликвид. Огран.

Условие неопределенности ,≥0 (4)

— доходность кредитов, — доходность ликвидных активов

F = при услов. (1) – (4).

4. Экономико – математические модели задач лп: задача определения оптимального ассортимента продукции.

— П1, — П2

F = 3

2

3

5. Задача лп, стандартная форма, каноническая форма.

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

Задачей линейного программирования является выбор из множества допустимых планов наиболее выгодного (оптимального).

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

В общем виде модель записывается следующим образом:

Целевая функция: F (x)= c1x1 + c2x2 + . + cnxn → max(min)

ограничения: a11x1 + a12x2 + . + a1nxn b1,

a21x1 + a22x2 + . + a2nxn b2,

am1x1 + am2x2 + . + amnxn bm;

требование неотрицательности: xj ≥ 0,

Задача имеет каноническую форму, если является задачей на максимум (минимум) линейной функции F и ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, . хn являются неотрицательными:

F (x) =

, i= 1,2…m

, j = 1,2…n

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной функции f и система ограничений ее состоит из одних линейных неравенств типа «

F (x) =

, i= 1,2…m

, j = 1,2…n

Свойства задачи ЛП.

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

Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации — ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.

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

Научная электронная библиотека

Термин «математическое программирование» предложен Робертом Дорфманом в 1950 году [45] и теперь он объединяет линейное программирование, целочисленное программирование, квадратичное программирование, выпуклое программирование и нелинейное программирование. Математическое программирование имеет дело с оптимизацией линейной или нелинейной целевой функции при линейных и (или) нелинейных ограничениях.

В.2.3.1. Линейное программирование

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

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

(В.9)

Саму задачу в общем случае можно записать в виде:

i = 1, …, k;

i = k + 1, …, m. (В.10)

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

Для задач линейного программирования с двух индексными переменными, получившими название «транспортные задачи», с учетом специфики структуры их ограничений разработаны более эффективные методы, такие как метод потенциалов, распределительный метод и другие [37].

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

В.2.3.2. Квадратичное программирование

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

где предполагается, что х и с – вектора размерности n; A – матрица размерности m×n; D – матрица размерности n×n.

Задачи квадратичного программирования хорошо изучены и существуют достаточное количество эффективных методов их решения [25, 26, 37]. Здесь можно отметить несколько направлений, основанные на обобщении симплекс-алгоритма (например, методы Била, Баранкина – Дорфмана), на условиях Куна и Таккера (например, метод Франка – Вульфа) или на функции Лагранжа.

В.2.3.3. Выпуклое программирование

Задача оптимизации относится к выпуклому программированию, если множество ее допустимых решений Х выпукло, а целевая функция вогнута на Х. Форма записи выражений для множества допустимых решений Х и самой задачи выпуклого программирования совпадают с выражениями (В.7) и (В.8) с учетом того, что функция f(x) должна быть выпуклой, а функции gi(x) линейными и (или) выпуклыми. Для задач выпуклого программирования также разработано значительное число достаточно эффективных методов их решения. Среди них можно отметить методы возможных направлений, впервые предложенные Зойтендейком [84], метод проекции градиента, методы штрафных функций и другие.

В.2.3.4. Нелинейное программирование

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

Какие задачи называются задачами математического программирования

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

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

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

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

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

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

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

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

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

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

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

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

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