Численные методы оптимизации и их виды.

План:

1. Введение

2. Построение математических моделей. Задача использования сырья.

3. Задача составления рациона. 

{spoiler=Подробнее}

Введение

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

Численные методы в теоретическом аспекте делятся на следующие :

1) Линейное программирование;

2) Нелинейное программирование;

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

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

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

Задача использования сырья.  Для изготовления двух видов продукции Р₁,Р₂  используют три вида сырья: S₁,S₂ и S₃. Запасы сырья, количество единиц сырья, затрачиваемых  на изготовление единицы   продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в табл.1. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Обозначим через x₁ количество единиц продукции P₁, а через x₂ - количество единиц продукции P₂. Тогда, учитывая количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также запасы сырья, получим систему ограничений

2x₁+5x₂ £ 20,

8x₁+5x₂ £ 40,

5x₁+6x₂ £ 30,

которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысить имеющихся запасов. Если продукция  P₁ не выпускается, то x₁=0 ; в противном случае x₁>0. То же самое получаем и для продукции P_2. Таким образом,на неизвестные x₁ и x₂  должно быть наложено ограничение неотрицательности:  x₁ ³ 0 , x₂ ³ 0 .

Таблица 1.

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных  x₁ и  x₂. Реализация х₁  единиц продукции вида Р₁ и х₂ единиц продукции вида  дает соответственно 50 х₁ и 40 х₂ сум. прибыли, суммарная прибыль  Z =50 x₁+40 x₂ (сум).

Условиями не оговорена неделимость единицы продукции, поэтому x₁ и  x₂ (план выпуска продукции) могут быть и дробными числами, следовательно, задача имеет бесконечное множество вариантов планов (значений  x₁ и x₂, которые удовлетворяют системе ограничений). Необходимо найти такие неотрицательные значения x₁ и x₂ ,при которых функция Z достигает максимума, т.е. найти максимальное значение линейной функции Z=50х₁+40x₂ при ограничениях

2x₁+5x₂ £20,

8x₁+5x₂ £40, x₁ ³0,   x₂ ³ 0.

5x₁+6x₂ £30,

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

Задачу использования сырья можно легко обобщить, если при выпуске n видов продукции используются m видов сырья. Обозначим через S_i(i=1,2,…,m) виды сырья; b_i - запасы сырья, i -го вида; P_i (i=1,2,…,n) -виды продукции; a_ij -количество единиц i - го сырья, идущего на изготовление единицы j - й продукции; C_j - величину прибыли, получаемой при реализации единицы j - продукции. Условия задачи запишем в табл.2.

Таблица 2.

Пусть x_j - количество единиц j-й продукции, которое необходимо произвести. Тогда математическую модель задачи можно представить в следующем виде.

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

Z=C₁x₁+C₂x₂ +…+C_nx_n при ограничениях

a₁₁x₁+a₁₂x₂+…+a_1nx_n £b_1,

a₂₁x₁+a₂₂x₂+…+a_2nx_n £b_2,

. . . . . . . . . . . . . . . . . . .       b_i³0 (i=1,2,…,m),

a_m1x_1­+a_m2x₂+…+a_mnx_n £b_m,    x_j³ (j=1,2,…,n).

Задача составления рациона.  При откорме каждое животное ежедневно должно получить не менее 9 ед. питательного вещества S₁, не менее 8 ед. Вещества S₂ и не менее 12 ед. вещества  S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в табл.3.

Т а б л и ц а 3.

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

Для составления математической модели обозначим через x₁ и   x₂ cсоответственно количество килограммов корма I  и II в дневном рационе. Принимая во внимание значения, приведенные в табл.3. и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений

3x₁+x₂ ³9,

x₁+2x₂ ³8,  x₁³0,x₂³0.

Если корм I не используется в рационе, то x_1­=0 в противном случае x₁>0. Аналогично имеем x₂³0 т.е. должно выполнятся условие неотрицательности переменных: x_1­³0,x₂³0 .

Цель данной задачи - добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции  Z=4x₁+6x₂ (коп). Задача является многовариантной, x₁ и x₂ могут принимать бесконечное множество значений. Из этого множества следует выбрать такие x₁ и x₂ , при которых функция  Z принимает минимальное значение. Таким образом, необходимо найти минимальное значение линейной функции Z=4x₁+6x₂ при

ограничениях

3x₁+x₂ ³9,

x₁+2x₂ ³8,  x₁³0, x₂ ³0.

X₁+6x₂ ³12,

Задачу составления рациона можно обобщить, если предусмотреть в рационе  m видов питательных веществ количестве не менее b_i (i=1,2,…,m) (ед) и использовать n видов кормов. Для составления математической модели задачи обозначим через a_ij (i=1,2,…,m;j=1,2,…,n) кол-во единиц  i-го питательного вещества, содержащегося в единице j-го корма; C_j - стоимость единицы j-го корма; x_j - кол-во единиц j-го корма в дневном рационе.

Необходимо найти минимальное значение линейной функции Z=C₁x₁+C₂x₂+…+C_nx_n  при ограничениях

a₁₁x₁+a₁₂x₂+…+a_1nx_n ³b_1,

a₂₁x₁+a₂₂x₂+…+a_2nx_n ³b₂,

…………………………    x_j ³0 (j=1,2,…,n),

a_m1x₁+a_m2x₂+…+a_mnx_n ³b_m, b_i ³0 (i=1,2,…,m).

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

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

{/spoilers}