Цель, задачи и разделы математического программирования

Цель, задачи и разделы математического программирования

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

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

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

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

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений. Задачи математического программирования: 1) задача об использовании ресурсов – необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет max, 2) задача составления рациона (задача о диете, задача о смесях) – необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела, 3) задача об использовании мощностей (задача о загрузке оборудования) – необходимо составить план работы станков (т.е. так распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными, 4) задача о раскрое материалов – необходимо найти план раскроя, обеспечивающий максимальное число комплектов, 5) транспортная задача – найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы мощности всех поставщиков были реализованы, спросы всех потребителей были удовлетворены, суммарные затраты на перевозку были бы min

ЭММ задачи оптимального использования ресурсов

Для изготовления двух видов продукции P1 и P2 используют 4 вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число ед ресурсов, затрачиваемых на изготовление ед продукции приведены в табл. Прибыль получаемая от ед продукции P1 и P2 соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет max

x1, x2-число ед. продукции соответственно P1 и P2, запланированных к производству. Для их изготовления потребуется (1*x1 +3*x2) ед ресурса S1, (2*x1 +1*x2) ед ресурса S2, (1*x2) ед ресурса S3 и 3*x1 ед ресурса S4. Так как потребление ресурсов S1, S2, S3 и S4 не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств: (система) x1+3x2≤18, 2x1+x2≤16, x2≤5, 3x1≤21 (1.1). По смыслу задачи переменные x1,x2≥0 (1.2). Суммарная прибыль F составит 2x1 руб. от реализации продукции P1 и 3x2 руб. – от реализации продукции P2, т.е. F=2x1+3x2 (1.3). ЭММ задачи: найти такой план выпуска продукции X=(x1,x2), удовлетворяющий системе 1.1 и условию 1.2, при котором функция 1.3 принимает max значение

ЭММ задачи составления рациона

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S1, S2 и S3. Содержание числа ед питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в табл. Стоимость 1 кг корма I и II = соответственно 4 и 6 руб. необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

x1, x2 – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать (3*x1 +1*x2) ед пит вещества S1, (1*x1 +2*x2) ед пит вещества S2, (1*x1 +6*x2) ед пит вещества S3. Так как содержание пит веществ S1, S2, S3 в рационе должно быть не менее соответственно 9,8,12 ед, то получим: (система) 3*x1+x2≥9, x1+2*x2≥8, x1+6*x2≥12 (1.1). переменные x1,x2≥0 (1.2). Общая стоимость рациона составит (в руб.) F=4x1+6x2 (1.3). ЭММ задачи: составить дневной рацион X=(x1,x2), удовлетворяющий системе 1.1 и условию 1.2, при котором функция 1.3 принимает min значение.

Общая формулировка ЗЛП. Виды ЗЛП. Формы записи ЗЛП

Дана система m линейных уравнений и неравенств с n переменными: (система) a₁₁*x₁ + a₁₂*x₂ + … + a_{1 n}*x_n {≤, =, ≥} b₁, a₂₁*x₁ + a₂₂*x₂ + … + a_{2 n}*x_n {≤, =, ≥} b₂, …. a_{m 1}*x₁ + a_m2*x₂ + … + a_{m n}*x _n {≤, =, ≥} b _m (1.1)

и линейная функция F = c1*x1 + c2*x2 + …+ cn*xn

Необходимо найти такое значение решение системы Х= (x1, x2,…х_j…x_n), где х_j ≥0 (j=1,2…,l; l≤n), при котором F→extr

Если в сист ограничений (1.1) присутствуют только неравенства то такая ЗЛПназ-сястандартной

Если же в сист огр (1.1) содержит только равенства то такая ЗЛПназ-сяканонической

2 вида записи канонической задачи

Матричная форма записи: F=CX→max(min) при ограничениях AX=B, X≥0, где

С=(с₁,с₂,…с_n); A=(матрица) (a₁₁ a₁₂ a_{1 n} , a₂₁ a₂₂ a_{2 n} , …. a_{m 1} a_m2 a_{m n}); X=(матрица столбик-сверху вниз) (x₁,x₂,…x­_n) B=( b₁,b₂,…b­_n) Здесь С-матрица-строка, А-матрица системы, Х-матрица столбец переменных, В-матрица-столбец свободных членов

Векторная форма записи: F=CX→max(min) при ограничениях P₁x₁+ P₂x₂+… P_nx_n=P, X≥0, где CX-скалярное произведение векторов С=(с₁,с₂,…с_n) и X=(x₁,x₂,…x­_n), векторы P₁=(матрицы-столбцы-сверху вниз) (a₁₁ a₂₁… a _m1 ), P₂=(a₁₂ a₂₂… a _m2 ), …, P_n= (a_1n a_2n… a _{m n} ), P= (b₁ b₂… b _m) состоят соответственно из коэффициентов при переменных и свободных членов. Векторное неравенство X≥0 означает что все компоненты вектора Х неотрицательны, т.е. x_j≥0, j=1,2,…,n

Свойства ЗЛП с 2 переменными

Z (x) = c1*x1 + c2*x2 → extr

Система: a₁₁*x₁ + a₁₂*x₂ ≤ b₁, a₂₁*x₁ + a₂₂*x₂ ≤, b₂ ,…. a_{m 1}*x₁ + a_m2*x₂ ≤ b_m

x1, x2≥0

1.a₁*x₁ + a₂*x₂ ≤ b (4) Множеством решения нерав-ва (4) яв-ся одна из двух полуплоскостей, на которые вся плоскость делится прямой a1*x1+a2*x2=b включая саму эту прямую, все точки другой полуплоскости удовлетворяют нерав-ву a1*x1 + a2*x2>b Для определения нужной полуплоскости выбираем контрол. точку

2. ОДР задач линейного программирования с двумя переменными яв-ся: а) выпуклый многоугольник б) выпуклая многоугольная область в) пустое множество г) одна единств. точка

3. Если оптимал. значение сущ-ет, то сущ-ет в одной из условных точек

Градиент и линии уровня ЦФ

Градиент - вектор, который определяет направление наискорейшего роста функции, его координаты находятся как частные производные функции. Z(x) = C1*x1 + C2*x2, C = grad Z = (ðZ/ðx1; ðZ/ðx2) = (c1,c2)

Линия уровня ЦФ наз-ся линией, имеющей уравнение: Z(x)= const; с1*x1 + c2*x2 = const

ЛУ _|_ C (линия уровня перпендикулярна градиенту).

Свойства ЗЛП с п переменными

1⁰ ОДР является выпуклым многогранником или выпуклой многогранной областью если система ограничений совместна (без док-ва) 2⁰ Если оптимальное значение сущ-ет то оно достигается по крайней мере в одной угловой точке 3⁰ Если оптимум достигается более чем в 2 точке, то он достигается только в 2ух соседних точках а также во всех точках, явл-ся выпуклой комбинацией точек 4⁰ Между угловыми точками и базисными точками ЗЛП сущ-ет однозначное соответствие (не будем рассм-ть угловые точки

12.Базисное решение ЗЛП. Вырожденное базисное решение. Допустимое базисное
решение

Базисное решение – такое решение, в котором свободные переменные =0. Базисных решений конечное число. Каждое базисное решение должно быть допустимым, т.е. удовлетворять тривиальным ограничениям. Базисное решение называется вырожденным, если вектор X_B=B^-1b имеет нулевые компоненты.

Алгоритм симплексного метода

1) Привести ЗЛП к каноническому виду

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

3) вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу

4) если выполняется признак единственности оптимального решения то решение задачи заканчивается

5) если выполняется условие существования множества оптимальных решений то путем простого перебора найти все оптимальные решения

6) если имеют место условия неограниченности ЦФ, то задача не имеет решения

7) если пункты 4-6 не выполняются, найти новое опорное решение и перейти к п.3

Цель, задачи и разделы математического программирования

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

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

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